K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 37
Текст из файла (страница 37)
If temp is new, it adds temp to CC.Whether or not temp is new, it records the transition from cci to temp forlater use in building the parser’s Goto table.To ensure that the algorithm processes each set cci just once, it uses a simplemarking scheme. It creates each set in an unmarked condition and marks theset as it is processed. This drastically reduces the number of times that itinvokes goto and closure.This construction is a fixed-point computation.
The canonical collection, CC,is a subset of the powerset of the lr(1) items. The while loop is monotonic;it adds new sets to CC and never removes them. If the set of lr(1) items hasn elements, then CC can grow no larger than 2n items, so the computationmust halt.This upper bound on the size of CC is quite loose. For example, the parentheses grammar has 33 lr(1) items and produces just 12 sets in CC. Theupper bound would be 233 , a much larger number. For more complex grammars, |CC| is a concern, primarily because the Action and Goto tables growwith |CC|. As described in Section 3.6, both the compiler writer and theparser-generator writer can take steps to reduce the size of those tables.The Canonical Collection for the Parentheses GrammarAs a first complete example, consider the problem of building CCfor the parentheses grammar. The initial set, cc0 , is computed asclosure([Goal → • List,eof]).3.4 Bottom-Up Parsing 131IterationItemGoalListPair()eof0cc0∅cc1cc2cc3∅∅1cc1cc2cc3∅∅∅∅∅∅cc4cc3∅∅∅∅cc5cc6cc7∅∅∅cc4cc5cc6cc7∅∅∅∅∅∅∅∅∅∅∅∅cc9cc6cc8cc10∅∅∅cc8cc9cc10∅∅∅∅∅∅∅∅∅∅∅∅cc11∅∅∅∅cc11∅∅∅∅∅∅234∅∅∅∅∅∅n FIGURE 3.23 Trace of the LR(1) Construction on the Parentheses Grammar.[Goal → • List, eof]cc0 = [List → • Pair, eof][Pair → • ( Pair ),(][List → • List Pair, eof][List → • Pair, (][Pair → • ( ), eof][List → • List Pair, (] [Pair → • ( Pair ), eof][Pair → • ( ),(]Since each item has the • at the start of its right-hand side, cc0 contains onlypossibilities.
This is appropriate, since it is the parser’s initial state. The firstiteration of the while loop produces three sets, cc1 , cc2 , and cc3 . All of theother combinations in the first iteration produce empty sets, as indicated inFigure 3.23, which traces the construction of CC.goto(cc0 , List) is cc1 . [Goal → List •, eof]cc1 = [Pair → • ( Pair ), eof][List → List • Pair, eof][Pair → • ( Pair ), (][Pair → • ( ), (][List → List • Pair, (][Pair → • ( ), eof]cc1 represents the parser configurations that result from recognizing a List.All of the items are possibilities that lead to another pair of parentheses,except for the item [Goal → List •, eof]. It represents the parser’s acceptstate—a reduction by Goal → List, with a lookahead of eof.goto(cc0 , Pair) is cc2 .nocc2 = [List → Pair •, eof] [List → Pair •, (]cc2 represents the parser configurations after it has recognized an initial Pair.Both items are handles for a reduction by List → Pair.132 CHAPTER 3 Parsersgoto(cc0 ,() is cc3 .(cc3 =[Pair → • ( Pair ), )][Pair → • ( ), )][Pair → ( • Pair ), eof][Pair → ( • ), eof])[Pair → ( • Pair ), (][Pair → ( • ), (]cc3 represents the parser’s configuration after it recognizes an initial (.When the parser enters state 3, it must recognize a matching ) at some pointin the future.The second iteration of the while loop tries to derive new sets from cc1 ,cc2 , and cc3 .
Five of the combinations produce nonempty sets, four of whichare new.goto(cc1 , Pair) is cc4 .ncc4 = [List → List Pair •, eof] [List → List Pair •, (]oThe left context for this set is cc1 , which represents a state where the parserhas recognized one or more occurrences of List. When it then recognizes aPair, it enters this state. Both items represent a reduction by List → List Pair.goto(cc1 ,() is cc3 , which represents the future need to find a matching ).goto(cc3 , Pair) is cc5 .nocc5 = [Pair → ( Pair • ), eof] [Pair → ( Pair • ), (]cc5 consists of two partially complete items.
The parser has recognized a (followed by a Pair; it now must find a matching ). If the parser finds a ), itwill reduce by rule 4, Pair → ( Pair ).goto(cc3 ,() is cc6 .([Pair → • ( Pair ), )]cc6 =[Pair → • ( ), )][Pair → ( • Pair ), )][Pair → ( • ), )])The parser arrives in cc6 when it encounters a ( and it already has at leastone ( on the stack. The items show that either a ( or a ) lead to valid states.goto(cc3 ,)) is cc7 .ncc7 = [Pair → ( ) •, eof] [Pair → ( ) •, (]oIf, in state 3, the parser finds a ), it takes the transition to cc7 . Both itemsspecify a reduction by Pair → ( ).The third iteration of the while loop tries to derive new sets from cc4 ,cc5 , cc6 , and cc7 .
Three of the combinations produce new sets, while oneproduces a transition to an existing state.3.4 Bottom-Up Parsing 133goto(cc5 ,)) is cc8 .nocc8 = [Pair → ( Pair ) •, eof] [Pair → ( Pair ) •, (]When it arrives in state 8, the parser has recognized an instance of rule 4,Pair → ( Pair ). Both items specify the corresponding reduction.goto(cc6 , Pair) is cc9 .ncc9 = [Pair → ( Pair • ), )]oIn cc9 , the parser needs to find a ) to complete rule 4.goto(cc6 ,() is cc6 . In cc6 , another ( will cause the parser to stack anotherstate 6 to represent the need for a matching ).goto(cc6 ,)) is cc10 .ncc10 = [Pair → ( ) •, )]oThis set contains one item, which specifies a reduction to Pair.The fourth iteration of the while loop tries to derive new sets from cc8 , cc9 ,and cc10 . Only one combination creates a nonempty set.goto(cc9 ,)) is cc11 .ncc11 = [Pair → ( Pair ) •, )]oState 11 calls for a reduction by Pair → ( Pair ).The final iteration of the while loop tries to derive new sets from cc11 .It finds only empty sets, so the construction halts with 12 sets, cc0through cc11 .Filling in the TablesGiven the canonical collection of sets of lr(1) items for a grammar, theparser generator can fill in the Action and Goto tables by iterating throughCC and examining the items in each ccj ∈ CC.
Each ccj becomes a parserstate. Its items generate the nonempty elements of one row of Action; thecorresponding transitions recorded during construction of CC specify thenonempty elements of Goto. Three cases generate entries in the Actiontable:134 CHAPTER 3 Parsers1. An item of the form [A→β•cγ ,a] indicates that encountering theterminal symbol c would be a valid next step toward discovering thenonterminal A. Thus, it generates a shift item on c in the current state.The next state for the recognizer is the state generated by computinggoto on the current state with the terminal c. Either β or γ can be .2.
An item of the form [A→β•, a] indicates that the parser has recognizeda β, and if the lookahead is a, then the item is a handle. Thus, itgenerates a reduce item for the production A→β on a in the currentstate.3. An item of the form [S 0 → S•, eof] where S 0 is the goal symbol indicatesthe accepting state for the parser; the parser has recognized an inputstream that reduces to the goal symbol and the lookahead symbol is eof.This item generates an accept action on eof in the current state.Figure 3.24 makes this concrete.
For an lr(1) grammar, it should uniquelydefine the nonerror entries in the Action and Goto tables.The table-filling actions can be integrated intothe construction of CC.Notice that the table-filling algorithm essentially ignores items where the •precedes a nonterminal symbol. Shift actions are generated when • precedesa terminal. Reduce and accept actions are generated when • is at the right endof the production.
What if cci contains an item [A→β • γ δ, a], where γ ∈N T ? While this item does not generate any table entries itself, its presencein the set forces the closure procedure to include items that generate tableentries. When closure finds a • that immediately precedes a nonterminalsymbol γ , it adds productions that have γ as their left-hand side, with a •preceding their right-hand sides. This process instantiates first(γ ) in cci .The closure procedure will find each x ∈ first(γ ) and add the items intocci to generate shift items for each x.for each cci ∈ CCfor each item I ∈ cciif I is [A→β • cγ ,a] and goto(cci ,c) = ccj thenAction[i ,c] ← ‘‘shift j’’else if I is [A→β•, a] thenAction[i ,a] ← ‘‘reduce A→β’’else if I is [S 0 → S•, eof] thenAction[i , eof ] ← ‘‘accept’’for each n ∈ N Tif goto(cci ,n) = ccj thenGoto[i ,n] ← jn FIGURE 3.24 LR(1) Table-Filling Algorithm.3.4 Bottom-Up Parsing 135For the parentheses grammar, the construction produces the Action andGoto tables shown in Figure 3.16b on page 120.
As we saw, combining thetables with the skeleton parser in Figure 3.15 creates a functional parser forthe language.In practice, an lr(1) parser generator must produce other tables needed bythe skeleton parser. For example, when the skeleton parser in Figure 3.15 onpage 119 reduces by A → β, it pops “2 × | β |” symbols from the stack andpushes A onto the stack. The table generator must produce data structuresthat map a production from the reduce entry in the Action table, say A → β,into both | β | and A. Other tables, such as a map from the integer representinga grammar symbol into its textual name, are needed for debugging and fordiagnostic messages.Handle Finding, Revisitedlr(1) parsers derive their efficiency from a fast handle-finding mechanismembedded in the Action and Goto tables.
The canonical collection, CC, represents a handle-finding dfa for the grammar. Figure 3.25 shows the dfa forour example, the parentheses grammar.How can the lr(1) parser use a dfa to find the handles, when we knowthat the language of parentheses is not a regular language? The lr(1) parserrelies on a simple observation: the set of handles is finite.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
