K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 36
Текст из файла (страница 36)
One valid next step would be to recognize a γ . We call such anitem partially complete.3. [A→βγ •,a] indicates that the parser has found βγ in a context wherean A followed by an a would be valid. If the lookahead symbol is a,then the item is a handle and the parser can reduce βγ to A. Such anitem is complete.In an lr(1) item, the • encodes some local left context—the portions ofthe production already recognized. (Recall, from the earlier examples, thatthe states pushed onto the stack encode a summary of the context to theleft of the current lr(1) item—in essence, the history of the parse so far.)The lookahead symbol encodes one symbol of legal right context. When theparser finds itself in a state that includes [A→βγ •,a] with a lookahead of a,it has a handle and should reduce βγ to A.Figure 3.19 shows the complete set of lr(1) items generated by theparentheses grammar.
Two items deserve particular notice. The first,[Goal → • List,eof], represents the initial state of the parser—looking fora string that reduces to Goal, followed by eof. Every parse begins in thisstate. The second, [Goal → List •,eof], represents the desired final state ofthe parser—finding a string that reduces to Goal, followed by eof. Thisitem represents every successful parse.
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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
