Cooper_Engineering_a_Compiler(Second Edition) (Rice), страница 36

All of the possible parses result fromstringing together parser states in a grammar-directed way, beginning with[Goal → • List,eof] and ending with [Goal → List •,eof].3.4 Bottom-Up Parsing 127Constructing the Canonical CollectionTo build the canonical collection of sets of lr(1) items, CC, a parser generator must start from the parser’s initial state, [Goal → • List,eof], andconstruct a model of all the potential transitions that can occur. The algorithm represents each possible configuration, or state, of the parser as a setof lr(1) items.

The algorithm relies on two fundamental operations on thesesets of lr(1) items: taking a closure and computing a transition.nnThe closure operation completes a state; given some core set of lr(1)items, it adds to that set any related lr(1) items that they imply. Forexample, anywhere that Goal → List is legal, the productions thatderive a List are legal, too. Thus, the item [Goal → • List,eof] impliesboth [List → • List Pair,eof] and [List → • Pair,eof].

The closureprocedure implements this function.To model the transition that the parser would make from a given stateon some grammar symbol, x, the algorithm computes the set of itemsthat would result from recognizing an x. To do so, the algorithm selectsthe subset of the current set of lr(1) items where • precedes x andadvances the • past the x in each of them. The goto procedureimplements this function.To simplify the task of finding the goal symbol, we require that the grammarhave a unique goal symbol that does not appear on the right-hand side of anyproduction. In the parentheses grammar, that symbol is Goal.The item [Goal → • List,eof] represents the parser’s initial state for theparentheses grammar; every valid parse recognizes Goal followed by eof.This item forms the core of the first state in CC, labelled cc0 .

If the grammarhas multiple productions for the goal symbol, each of them generates an itemin the initial core of cc0 .The closure ProcedureTo compute the complete initial state of the parser, cc0 , from its core, thealgorithm must add to the core all of the items implied by the items in thecore.

Figure 3.20 shows an algorithm for this computation. Closure iteratesover all the items in set s. If the placeholder • in an item immediately precedes some nonterminal C, then closure must add one or more items foreach production that can derive C. Closure places the • at the initial positionof each item that it builds this way.The rationale for closure is clear.

If [A→β • Cδ,a] ∈ s, then a string thatreduces to C, followed by δ a will complete the left context. Recognizinga C followed by δ a should cause a reduction to A, since it completes the128 CHAPTER 3 Parsersclosure(s)while (s is still changing)for each item [A→β • Cδ,a] ∈ sfor each production C →γ ∈ Pfor each b ∈ FIRST(δa)s ← s ∪ {[C →•γ ,b]}return sn FIGURE 3.20 The closure Procedure.production’s right-hand side (Cδ) and follows it with a valid lookaheadsymbol.In our experience, this use of FIRST(δ a) is thepoint in the process where a human is most tolikely make a mistake.To build the items for a production C →γ , closure inserts the placeholderbefore γ and adds the appropriate lookahead symbols—each terminal thatcan appear as the initial symbol in δ a. This includes every terminal infirst(δ).

If ∈ first(δ), it also includes a. The notation first(δ a) in thealgorithm represents this extension of the first set to a string in this way. Ifδ is , this devolves into first(a) = { a }.For the parentheses grammar, the initial item is [Goal → • List,eof]. Applying closure to that set adds the following items:[List → • List Pair,eof], [List → • List Pair,( ], [List → • Pair,eof ],[List → • Pair,( ], [Pair → • ( Pair ),eof ], [Pair → • ( Pair ),(],[Pair → • ( ),eof] [Pair → • ( ),(]These eight items, along with [Goal → • List,eof], constitute set cc0 in thecanonical collection. The order in which closure adds the items will dependon how the set implementation manages the interaction between the “foreach item” iterator and the set union in the innermost loop.Closure is another fixed-point computation.

The triply-nested loop eitheradds items to s or leaves s intact. It never removes an item from s. Since theset of lr(1) items is finite, this loop must halt. The triply nested loop looksexpensive. However, close examination reveals that each item in s needs tobe processed only once. A worklist version of the algorithm could capitalizeon that fact.The goto ProcedureThe second fundamental operation that the construction uses is the gotofunction. Goto takes as input a model of a parser state, represented as a setcci in the canonical collection, and a grammar symbol x. It computes, fromcci and x, a model of the parser state that would result from recognizing anx in state i.3.4 Bottom-Up Parsing 129goto(s, x)moved ← ∅for each item i ∈ sif the form of i is [α →β • xδ, a] thenmoved ← moved ∪ {[α →βx • δ, a]}return closure(moved)n FIGURE 3.21 The goto Function.The goto function, shown in Figure 3.21, takes a set of lr(1) items s anda grammar symbol x and returns a new set of lr(1) items.

It iterates overthe items in s. When it finds an item in which the • immediately precedesx, it creates a new item by moving the • rightward past x. This new itemrepresents the parser’s configuration after recognizing x. Goto places thesenew items in a new set, takes its closure to complete the parser state, andreturns that new state.Given the initial set for 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 → • ( ),(]we can derive the state of the parser after it recognizes an initial ( by computing goto(cc0 ,( ). The inner loop finds four items that have • before (.Goto creates a new item for each, with the • advanced beyond (.

Closureadds two more items, generated from the items with • before Pair. Theseitems introduce the lookahead symbol ). Thus, goto(cc0 ,( ) returns([Pair → ( • Pair ),eof][Pair → ( • ),(][Pair → ( • Pair ),(][Pair → • ( Pair ),)])[Pair → ( • ),eof].[Pair → • ( ),)]To find the set of states that derive directly from some state such as cc0 , thealgorithm can compute goto(cc0 ,x) for each x that occurs after a • in anitem in cc0 .

This produces all the sets that are one symbol away from cc0 .To compute the complete canonical collection, we simply iterate this processto a fixed point.The AlgorithmTo construct the canonical collection of sets of lr(1) items, the algorithmcomputes the initial set, cc0 , and then systematically finds all of the sets oflr(1) items that are reachable from cc0 .

It repeatedly applies goto to the newsets in CC; goto, in turn, uses closure. Figure 3.22 shows the algorithm.For a grammar with the goal production S0 →S, the algorithm begins byinitializing CC to contain cc0 , as described earlier. Next, it systematically130 CHAPTER 3 Parserscc0 ← closure({[S0 →• S, eof]})CC ← { cc0 }while (new sets are still being added to CC)for each unmarked set cci ∈ CCmark cci as processedfor each x following a • in an item in ccitemp ← goto(cci,x)if temp ∈/ CCthen CC ← CC ∪ {temp}record transition from cci to temp on xn FIGURE 3.22 The Algorithm to Build CC.extends CC by looking for any transition from a state in CC to a state notyet in CC. It does this constructively, by building each possible state, temp,and testing temp for membership in CC.

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 .