A.W. Appel, J. Palsberg - Modern Compiler Implementation in Java (Second Edition) (798439), страница 13
Текст из файла (страница 13)
How should error be handled?It is safe just to raise an exception and quit parsing, but this is not very friendly to the user. Itis better to print an error message and recover from the error, so that other syntax errors canbe found in the same compilation.A syntax error occurs when the string of input tokens is not a sentence in the language. Errorrecovery is a way of finding some sentence similar to that string of tokens. This can proceedby deleting, replacing, or inserting tokens.For example, error recovery for T could proceed by inserting a num token.
It's not necessary toadjust the actual input; it suffices to pretend that the num was there, print a message, andreturn normally.void T() {switch (tok) {case ID:case NUM:case LPAREN: F(); Tprime(); break;default: print("expected id, num, or left-paren");}}It's a bit dangerous to do error recovery by insertion, because if the error cascades to produceanother error, the process might loop infinitely. Error recovery by deletion is safer, becausethe loop must eventually terminate when end-of-file is reached.Simple recovery by deletion works by skipping tokens until a token in the FOLLOW set isreached. For example, error recovery for T′ could work like this:int Tprime_follow [] = {PLUS, RPAREN, EOF};void Tprime() { switch (tok) {case PLUS: break;54case TIMES: eat(TIMES); F(); Tprime(); break;case RPAREN: break;case EOF: break;default: print("expected +, *, right-paren,or end-of-file");skipto(Tprime_follow);}}A recursive-descent parser's error-recovery mechanisms must be adjusted (sometimes by trialand error) to avoid a long cascade of error-repair messages resulting from a single token outof place.3.3 LR PARSINGThe weakness of LL(k) parsing techniques is that they must predict which production to use,having seen only the first k tokens of the right-hand side.
A more powerful technique, LR(k)parsing, is able to postpone the decision until it has seen input tokens corresponding to theentire right-hand side of the production in question (and k more input tokens beyond).LR(k) stands for left-to-right parse, rightmost-derivation, k-token lookahead. The use of arightmost derivation seems odd; how is that compatible with a left-to-right parse? Figure 3.18illustrates an LR parse of the programa:=7;b:=c+(d:=5+6,d)55Figure 3.18: Shift-reduce parse of a sentence. Numeric subscripts in the Stack are DFA statenumbers; see Table 3.19.using Grammar 3.1, augmented with a new start production S′ → S$.The parser has a stack and an input. The first k tokens of the input are the lookahead.
Basedon the contents of the stack and the lookahead, the parser performs two kinds of actions:Shift: Move the first input token to the top of the stack.Reduce: Choose a grammar rule X → A B C; pop C, B, A from the top of the stack; push Xonto the stack.Initially, the stack is empty and the parser is at the beginning of the input. The action ofshifting the end-of-file marker $ is called accepting and causes the parser to stop successfully.In Figure 3.18, the stack and input are shown after every step, along with an indication ofwhich action has just been performed.
The concatenation of stack and input is always one lineof a rightmost derivation; in fact, Figure 3.18 shows the rightmost derivation of the inputstring, upside-down.56LR PARSING ENGINEHow does the LR parser know when to shift and when to reduce? By using a deterministicfinite automaton! The DFA is not applied to the input - finite automata are too weak to parsecontext-free grammars - but to the stack. The edges of the DFA are labeled by the symbols(terminals and nonterminals) that can appear on the stack.
Table 3.19 is the transition table forGrammar 3.1.Table 3.19: LR parsing table for Grammar 3.1.The elements in the transition table are labeled with four kinds of actions:sn Shift into state n;gn Goto state n;rk Reduce by rule k;a Accept;Error (denoted by a blank entry in the table).To use this table in parsing, treat the shift and goto actions as edges of a DFA, and scan thestack. For example, if the stack is id := E, then the DFA goes from state 1 to 4 to 6 to 11.
Ifthe next input token is a semicolon, then the ";" column in state 11 says to reduce by rule 2.The second rule of the grammar is S → id:=E, so the top three tokens are popped from thestack and S is pushed.57The action for "+" in state 11 is to shift; so if the next token had been + instead, it would havebeen eaten from the input and pushed on the stack.Rather than rescan the stack for each token, the parser can remember instead the state reachedfor each stack element. Then the parsing algorithm isLook up top stack state, and input symbol, to get action; If action isShift(n): Advance input one token; push n on stack.Reduce(k): Pop stack as many times as the number of symbols on the right-hand side of rulek;Let X be the left-hand-side symbol of rule k;In the state now on top of stack, look up X to get "goto n";Push n on top of stack.Accept:Stop parsing, report success.Error:Stop parsing, report failure.LR(0) PARSER GENERATIONAn LR(k) parser uses the contents of its stack and the next k tokens of the input to decidewhich action to take.
Table 3.19 shows the use of one symbol of lookahead. For k = 2, thetable has columns for every two-token sequence and so on; in practice, k > 1 is not used forcompilation. This is partly because the tables would be huge, but more because mostreasonable programming languages can be described by LR(1) grammars.LR(0) grammars are those that can be parsed looking only at the stack, making shift/reducedecisions without any lookahead.
Though this class of grammars is too weak to be veryuseful, the algorithm for constructing LR(0) parsing tables is a good introduction to the LR(1)parser construction algorithm.We will use Grammar 3.20 to illustrate LR(0) parser generation. Consider what the parser forthis grammar will be doing. Initially, it will have an empty stack, and the input will be acomplete S-sentence followed by $; that is, the right-hand side of the S′ rule will be on theinput. We indicate this as S′ → .S$ where the dot indicates the current position of the parser.GRAMMAR 3.200. S′ → S$3. L → S1.
S → (L)4. L → L, S2. S → xIn this state, where the input begins with S, that means that it begins with any possible righthand side of an S-production; we indicate that by58Call this state 1. A grammar rule, combined with the dot that indicates a position in its righthand side, is called an item (specifically, an LR(0) item). A state is just a set of items.Shift actions In state 1, consider what happens if we shift an x. Wethen know that the end ofthe stack has an x; we indicate that by shifting the dot past the x in the S → x production. Therules S′ → .S$ and S → .(L) are irrelevant to this action, so we ignore them; we end up in state2:Or in state 1 consider shifting a left parenthesis. Moving the dot past the parenthesis in thethird item yields S → (.L), where we know that there must be a left parenthesis on top of thestack, and the input begins with some string derived by L, followed by a right parenthesis.What tokens can begin the input now? We find out by including all L-productions in the set ofitems.
But now, in one of those L-items, the dot is just before an S, so we need to include allthe S-productions:Goto actions In state 1, consider the effect of parsing past some string of tokens derived bythe S nonterminal. This will happen when an x or left parenthesis is shifted, followed(eventually) by a reduction of an S-production.
All the right-hand-side symbols of thatproduction will be popped, and the parser will execute the goto action for S in state 1. Theeffect of this can be simulated by moving the dot past the S in the first item of state 1, yieldingstate 4:Reduce actions In state 2 we find the dot at the end of an item. This means that on top of thestack there must be a complete right-hand side of the corresponding production (S → x), readyto reduce. In such a state the parser could perform a reduce action.The basic operations we have been performing on states are closure(I) and goto(I, X), where Iis a set of items and X is a grammar symbol (terminal or nonterminal).
Closure adds moreitems to a set of items when there is a dot to the left of a nonterminal; goto moves the dot pastthe symbol X in all items.Closure(I) =repeatfor any item A → α.Xβ in IGoto(I, X) =set J to the empty setfor any item A → α:Xβ in I59for any production X → γI ← I ∩ {X → .γ}until I does not change.return Iadd A → αX.β to Jreturn Closure(J)Now here is the algorithm for LR(0) parser construction. First, augment the grammar with anauxiliary start production S′ → S$. Let T be the set of states seen so far, and E the set of (shiftor goto) edges found so far.Initialize T to {Closure({S′ → :S$})}Initialize E to empty.repeatfor each state I in Tfor each item A → α.Xβ in Ilet J be Goto(I, X)T ← T ∪ {J}E ← E ∪ {I *** J}until E and T did not change in this iterationHowever, for the symbol $ we do not compute Goto(I; $); instead we will make an acceptaction.For Grammar 3.20 this is illustrated in Figure 3.21.Figure 3.21: LR(0) states for Grammar 3.20.Now we can compute set R of LR(0) reduce actions:R ← {}for each state I in Tfor each item A → α.
in IR ← R ∪ {(I, A → α)}We can now construct a parsing table for this grammar (Table 3.22). For each edgewhere X is a terminal, we put the action shift J at position (I, X) of the table; if X is anonterminal, we put goto J at position (I, X). For each state I containing an item S′ → S.$ weput an accept action at (I, $). Finally, for a state containing an item A → γ.
(production n withthe dot at the end), we put a reduce n action at (I, Y) for every token Y.60Table 3.22: LR(0) parsing table for Grammar 3.20.In principle, since LR(0) needs no lookahead, we just need a single action for each state: Astate will shift or reduce, but not both. In practice, since we need to know what state to shiftinto, we have rows headed by state numbers and columns headed by grammar symbols.SLR PARSER GENERATIONLet us attempt to build an LR(0) parsing table for Grammar 3.23.
The LR(0) states andparsing table are shown in Figure 3.24.GRAMMAR 3.231. S → E $2. E → T + E3. E → T4. T → xFigure 3.24: LR(0) states and parsing table for Grammar 3.23.In state 3, on symbol +, there is a duplicate entry: The parser must shift into state 4 and alsoreduce by production 2. This is a conflict and indicates that the grammar is not LR(0) - itcannot be parsed by an LR(0) parser. We will need a more powerful parsing algorithm.A simple way of constructing better-than-LR(0) parsers is called SLR, which stands forsimple LR.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
