Spread Knowledge

CS606 - Compiler Construction - Lecture Handout 25

User Rating:  / 0

Related Content: CS606 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Compiler Construction

The set s changed so the repeat loop is executed again. This time, however, the item [E → •int, $/+] does not yield any more items because the dot is followed by the terminal int. The first set of items is

I0 = {
[S → •E, $],
[E → •E+(E), $/+],
[E → •int, $/+]

Let’s consider the rationale behind the Closure procedure. If [A → β•Cδ,a] ∈ s, then one potential completion for the left context is to find a string that reduces to C, followed by δa. This completion should cause a reduction to A, since it fills out the production’s right-hand side (Cδ), and follows it with a valid look-ahead symbol. For a production C → γ, closure must insert '•' before γ and add appropriate look-ahead symbols – all terminals that can appear as the initial symbol in δa. This includes every terminal in FIRST(δ). If ε ∈ FIRST(δ), it also includes a, thus FIRST(δa) in the algorithm.

The goto Procedure

The second critical step in the construction is to derive other parser states from I0. To accomplish this, we compute, for each state Ii and each grammar symbol y, the state that would arise if the parser recognized a y while in state Ii. A state s that contains [X → α • yβ, b] has a transition (goto) labeled y to the state that contains the items goto(s, y) where y can be terminal or a non-terminal.

goto(s, y)
m ← { }
for each item [X → α •yβ, b] ∈ s
m ← m ∪ {[X → α y•β, b]}
return closure(m)

Finite Automaton of Items

The LR(1) items are used as the states of a finite automaton (FA) that maintains information about the parsing stack and progress of a shift-reduce parser. The FA will start out as a nondeterministic finite automaton (NFA). A DFA can be constructed from this NFA using the subset construction, similar to one we used for lexical analysis.

Consider the NFA of LR(0) items, i.e., no look-ahead. What are the transitions of the NFA of LR(0) items? Consider the item A→ α•γ. Suppose γ begins with symbol X which may be a terminal (token) or non-terminal. The item can be written as A→ α•Xη.

Then there is a transition on symbol X for state represented by item A→ α•Xη to state represented by item A→ αX•η. If X is a terminal, then this transition corresponds to a shift of X from input to top of parse stack.

shift of X from input to top of parse stack

If X is a non-terminal, then the interpretation of this transition is more complex because non-terminals do not appear in input. In fact, such a transition will correspond to pushing of X onto the stack during the parse. But this can only occur during a reduction by the production X → β. Such a reduction must be preceded by recognition of a β. The state given by X → •β represents the beginning of this process (dot indicates we are about to recognize β). Then for every item A→ α•Xη we must add an ε-transition for every production X → β.

ε-transition for every