Home | | Compiler Design | | Compilers Principles, Techniques, & Tools | | Compiler Design | Introduction to LR Parsing: Simple LR

Introduction to LR Parsing: Simple LR - | Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail |

Chapter: Compilers - Principles, Techniques, & Tools : Syntax Analysis

Introduction to LR Parsing: Simple LR

1 Why LR Parsers? 2 Items and the LR(0) Automaton 3 The LR-Parsing Algorithm 4 Constructing SLR-Parsing Tables 5 Viable Prefixes 6 Exercises for Section 4.6

Introduction to LR Parsing: Simple LR

 

1 Why LR Parsers?

2 Items and the LR(0) Automaton

3 The LR-Parsing Algorithm

4 Constructing SLR-Parsing Tables

5 Viable Prefixes

6 Exercises for Section 4.6

 

The most prevalent type of bottom-up parser today is based on a concept called LR(fc) parsing; the "L" is for left-to-right scanning of the input, the "R" for constructing a rightmost derivation in reverse, and the k for the number of input symbols of lookahead that are used in making parsing decisions. The cases k = 0 or k = 1 are of practical interest, and we shall only consider LR parsers with k < 1 here. When (k) is omitted, k is assumed to be 1.

 

This section introduces the basic concepts of LR parsing and the easiest method for constructing shift-reduce parsers, called "simple LR" (or SLR, for short). Some familiarity with the basic concepts is helpful even if the LR parser itself is constructed using an automatic parser generator. We begin with "items" and "parser states;" the diagnostic output from an LR parser generator typically includes parser states, which can be used to isolate the sources of parsing conflicts.

 

Section 4.7 introduces two, more complex methods — canonical-LR and LALR — that are used in the majority of LR parsers.

 

1. Why LR Parsers?

 

LR parsers are table-driven, much like the nonrecursive LL parsers of Sec-tion 4.4.4. A grammar for which we can construct a parsing table using one of the methods in this section and the next is said to be an LR grammar. Intu-itively, for a grammar to be LR it is sufficient that a left-to-right shift-reduce parser be able to recognize handles of right-sentential forms when they appear on top of the stack.

 

LR parsing is attractive for a variety of reasons:

 

            LR parsers can be constructed to recognize virtually all programming-language constructs for which context-free grammars can be written. Non-LR context-free grammars exist, but these can generally be avoided for typical programming-language constructs.

 

            The LR-parsing method is the most general nonbacktracking shift-reduce parsing method known, yet it can be implemented as efficiently as other,

 

more primitive shift-reduce methods (see the bibliographic notes).

 

            An LR parser can detect a syntactic error as soon as it is possible to do so on a left-to-right scan of the input.

 

            The class of grammars that can be parsed using LR methods is a proper superset of the class of grammars that can be parsed with predictive or LL methods. For a grammar to be LR(fc), we must be able to recognize the occurrence of the right side of a production in a right-sentential form, with k input symbols of lookahead. This requirement is far less stringent than that for LL(ife) grammars where we must be able to recognize the use of a production seeing only the first k symbols of what its right side derives. Thus, it should not be surprising that LR grammars can describe more languages than LL grammars.

 

 

The principal drawback of the LR method is that it is too much work to construct an LR parser by hand for a typical programming-language grammar. A specialized tool, an LR parser generator, is needed. Fortunately, many such generators are available, and we shall discuss one of the most commonly used ones, Yacc, in Section 4.9. Such a generator takes a context-free grammar and automatically produces a parser for that grammar. If the grammar contains ambiguities or other constructs that are difficult to parse in a left-to-right scan of the input, then the parser generator locates these constructs and provides detailed diagnostic messages.

 

 

2. Items and the LR(O) Automaton

 

How does a shift-reduce parser know when to shift and when to reduce? For example, with stack contents $ T and next input symbol * in Fig. 4.28, how does the parser know that T on the top of the stack is not a handle, so the appropriate action is to shift and not to reduce TtoEP.

 

An LR parser makes shift-reduce decisions by maintaining states to keep track of where we are in a parse. States represent sets of "items." An LR(0) item (item for short) of a grammar G is a production of G with a dot at some position of the body. Thus, production A XYZ yields the four items

 

A -XYZ

A -+ XYZ

A -> XYZ

A XYZ-

 

The production A ->• e generates only one item, A .

 

Intuitively, an item indicates how much of a production we have seen at a given point in the parsing process. For example, the item A -» XYZ indicates that we hope to see a string derivable from XYZ next on the input. Item

 

Representing Item Sets

 

A parser generator that produces a bottom-up parser may need to rep-resent items and sets of items conveniently. Note that an item can be represented by a pair of integers, the first of which is the number of one of the productions of the underlying grammar, and the second of which is the position of the dot. Sets of items can be represented by a list of these pairs. However, as we shall see, the necessary sets of items often include "closure" items, where the dot is at the beginning of the body. These can always be reconstructed from the other items in the set, and we do not have to include them in the list.

 

 

 

 

A -» XYZ indicates that we have just seen on the input a string derivable from X and that we hope next to see a string derivable from YZ. Item A —> XYZ-indicates that we have seen the body XYZ and that it may be time to reduce

 

XYZ     to     A.

 

One collection of sets of LR(0) items, called the canonical LR(0) collection, provides the basis for constructing a deterministic finite automaton that is used to make parsing decisions. Such an automaton is called an LR(0) automaton.3 In particular, each state of the LR(0) automaton represents a set of items in the canonical LR(0) collection. The automaton for the expression grammar (4.1), shown in Fig. 4.31, will serve as the running example for discussing the canonical LR(0) collection for a grammar.

 

To construct the canonical LR(0) collection for a grammar, we define an augmented grammar and two functions, CLOSURE and GOTO . If G is a grammar with start symbol S, then G', the augmented grammar for G, is G with a new start symbol 5" and production S' —> S. The purpose of this new starting production is to indicate to the parser when it should stop parsing and announce acceptance of the input. That is, acceptance occurs when and only when the parser is about to reduce by S' -» S.

 

 

Closure  of Item  Sets

 

If I is a set of items for a grammar G, then CLOSURE(I) is the set of items constructed from / by the two rules:

 

            Initially, add every item in / to CLOSURE(Z).

 

            If Aa-B/3 is in CLOSURE(J) and B ->• 7 is a production, then add the item B -7 to CLOSURE(7), if it is not already there. Apply this rule until no more new items can be added to CLOSURE(J).



 


 

Example 4.40 : Consider the augmented expression grammar:


If I is the set of one item {[E' -»• -E]}, then CLOSURE(J) contains the set of items I0 in Fig. 4.31.

To see how the  closure is computed,  E' -»• E is put  in C L O S U R E ( J )  by rule  (1). Since there is an E immediately to the right of a dot,  we add the E-productions with dots at the left ends:  E  -E + T and E ->•  T.  Now there is a T immediately to the right of a dot in the latter item, so we add T -> T*F and T -> F. Next, the F to the right of a dot forces us to add F ->• -(E) and F -» -id, but no other items need to be added. •   

 

The closure can be computed as in Fig. 4.32. A convenient way to imple-ment the function closure is to keep a boolean array added, indexed by the nonterminals of G, such that added[B] is set to true if and when we add the item item b -- >  .'g for each B-production b -- > 'g


 


Moreover, each set of items of interest is formed by taking the closure of a set of kernel items; the items added in the closure can never be kernel items, of course. Thus, we can represent the sets of items we are really interested in with very little storage if we throw away all nonkernel items, knowing that they could be regenerated by the closure process. In Fig. 4.31, nonkernel items are in the shaded part of the box for a state.

 

The  Function  GOTO   

The second useful function is GOTO (I, X) where I is a set of items and X is a grammar symbol.  GOTO (I, X) is defined to be the closure of the set of all items [A -> aX-b] such that  [A -> a • Xb] is in I. Intuitively, the GOTO function is used to define the transitions in the LR(0) automaton for a grammar. The states of the automaton correspond to sets of items, and GOTO(I,X) specifies the transition from the state for I under input X.

 

We are now ready for the algorithm to construct C, the canonical collection of sets of LR(0) items for an augmented grammar G' — the algorithm is shown in Fig. 4.33.

 

void items(G') {

C = CLOSURE({[S' -> S]}); repeat

for ( each set of items I in C )

for ( each grammar symbol X )

if ( GOTO (I, X)  is not empty and not in C )

add  GOTO(I, X) to  C;

until no new sets of items are added to C on a round;

}

 

Figure 4.33:  Computation of the canonical collection of sets of LR(0) items

 

Example 4.42 :  The canonical collection of sets of LR(0) items for grammar (4.1) and the GOTO function are shown in Fig. 4.31. GOTO is encoded by the transitions in the figure. •

 

Use of the  LR(O)  Automaton

The central idea behind "Simple LR," or SLR, parsing is the construction from the grammar of the LR(0) automaton. The states of this automaton are the sets of items from the canonical LR(0) collection, and the transitions are given by the G O T O function. The LR(0) automaton for the expression grammar (4.1) appeared earlier in Fig. 4.31.

 

The start state of the LR(0) automaton is C L O S U R E ( { [ S' ->• S]}), where S' is the start symbol of the augmented grammar. All states are accepting states. We say "state j" to refer to the state corresponding to the set of items Ij.

 

How can LR(0) automata help with shift-reduce decisions? Shift-reduce decisions can be made as follows. Suppose that the string 7 of grammar symbols takes the LR(0) automaton from the start state 0 to some state j. Then, shift on next input symbol a if state j has a transition on a. Otherwise, we choose to reduce; the items in state j will tell us which production to use.

 

The LR-parsing algorithm to be introduced in Section 4.6.3 uses its stack to keep track of states as well as grammar symbols; in fact, the grammar symbol can be recovered from the state, so the stack holds states. The next example gives a preview of how an LR(0) automaton and a stack of states can be used to make shift-reduce parsing decisions.

Example 4.43 : Figure 4.34 illustrates the actions of a shift-reduce parser on input id * id, using the LR(0) automaton in Fig. 4.31. We use a stack to hold states; for clarity, the grammar symbols corresponding to the states on the stack appear in column S Y M B O L S . At line (1), the stack holds the start state 0 of the automaton; the corresponding symbol is the bottom-of-stack marker $.


The next input symbol is id and state 0 has a transition on id to state 5. We therefore shift. At line (2), state 5 (symbol id) has been pushed onto the stack. There is no transition from state 5 on input *, so we reduce. From item [F -» id] in state 5, the reduction is by production F ->• id.

With symbols, a reduction is implemented by popping the body of the pro-duction from the stack (on line (2), the body is id) and pushing the head of the production (in this case, F). With states, we pop state 5 for symbol id, which brings state 0 to the top and look for a transition on F, the head of the production. In Fig. 4.31, state 0 has a transition on F to state 3, so we push state 3, with corresponding symbol F; see line (3).

 

As another example, consider line (5), with state 7 (symbol *) on top of the stack. This state has a transition to state 5 on input id, so we push state 5 (symbol id). State 5 has no transitions, so we reduce by F —> id. When we pop state 5 for the body id, state 7 comes to the top of the stack. Since state 7 has a transition on F to state 10, we push state 10 (symbol F).

 

 

3. The LR-Parsing Algorithm

 

A schematic of an LR parser is shown in Fig. 4.35. It consists of an input, an output, a stack, a driver program, and a parsing table that has two parts (ACTION and GOTO). The driver program is the same for all LR parsers; only the parsing table changes from one parser to another. The parsing program reads characters from an input buffer one at a time. Where a shift-reduce parser would shift a symbol, an LR parser shifts a state. Each state summarizes the information contained in the stack below it.

 


 

The stack holds a sequence of states, sosi • • • sm, where sm is on top. In the SLR method, the stack holds states from the LR(0) automaton; the canonical-LR and LALR methods are similar. By construction, each state has a corre-sponding grammar symbol. Recall that states correspond to sets of items, and that there is a transition from state i to state j if GOTO(Ii,X) = Ij. All tran-sitions to state j must be for the same grammar symbol X. Thus, each state, except the start state 0, has a unique grammar symbol associated with it . 4

 

Structure  of the  LR Parsing  Table

 

The parsing table consists of two parts: a parsing-action function ACTION and a goto function GOTO.

 

1. The ACTION function takes as arguments a state i and a terminal a (or $, the input endmarker). The value of ACTION[i,a] can have one of four forms:

 

 

            Shift j, where j is a state. The action taken by the parser effectively shifts input a to the stack, but uses state j to represent a.

 

            Reduce A-> b. The action of the parser effectively reduces b on the top of the stack to head A.

 

            Accept.  The parser accepts the input and finishes parsing.

 

            Error. The parser discovers an error in its input and takes some corrective action. We shall have more to say about how such error-recovery routines work in Sections 4.8.3 and 4.9.4.

 

            We extend the GOTO function, defined on sets of items, to states: if GOTO[/i, A] = Ij, then GOTO also maps a state i and a nonterminal A to state j .

 

 

LR - Parser          Configurations

 

To describe the behavior of an LR parser, it helps to have a notation repre-senting the complete state of the parser: its stack and the remaining input. A configuration of ah LR parser is a pair:



 

where the first component is the stack contents (top on the right), and the second component is the remaining input. This configuration represents the right-sentential form

 


 

in essentially the same way as a shift-reduce parser would; the only difference is that instead of grammar symbols, the stack holds states from which grammar symbols can be recovered. That is, X{ is the grammar symbol represented by state Si. Note that s0, the start state of the parser, does not represent a grammar symbol, and serves as a bottom-of-stack marker, as well as playing an important role in the parse.

 

Behavir  of the  LR Parser

 

The next move of the parser from the configuration above is determined by reading a*, the current input symbol, and s m , the state on top of the stack, and then consulting the entry A C T I O N [ s m , a*] in the parsing action table. The configurations resulting after each of the four types of move are as follows

 

1. If ACTION[s m ,ai] = shift s, the parser executes a shift move; it shifts the next state s onto the stack, entering the configuration


The symbol ai need not be held on the stack, since it can be recovered from s, if needed (which in practice it never is). The current input symbol is       now   a j + i .

 

2. If ACTION [sm, ai]  =         reduce  A    ->     b,      then   the parser   executes  a  reduce move, entering the         configuration                                                       

     

where  r  is  the  length  of 0,   and    s        =  GOTO[sm-r, A].        Here  the     parser first popped  r  state  symbols  off the     stack,  exposing   state  s T O _ r .   The parser then pushed s, the entry for   G O T O [ s m _ r , A], onto the stack.  The current input symbol is not changed in a reduce move.  For the LR parsers we  shall  construct,   Xm-r+i-'Xm,   the   sequence  of  grammar   symbols corresponding to the states popped off the stack,  will  always        match (3, the        right  side of the reducing production.       

The output of an LR parser is generated after a reduce move by executing the semantic action associated with the reducing production. For the time being, we shall assume the output consists of just printing the reducing production.

 

3. If ACTlON [ s m , ai1 = accept, parsing is completed.

 

4. If ACTlON [ s m , ai1 = error, the parser has discovered an error and calls an error recovery routine.

The  LR-parsing algorithm  is  summarized below.       All  LR parsers behave in this fashion; the only difference between one LR parser and another is the information in the ACTION and GOTO fields of the parsing table.

 

Algorithm 4.44 :  LR-parsing algorithm.

INPUT : An input string w and an LR-parsing table with functions ACTION and grammar G. GOTO for a

OUTPUT : If w is in L(G), the reduction steps of a bottom-up parse for w; otherwise, an error indication.

METHOD : Initially, the parser has s0 on its stack, where s0 is the initial state, and w$ in the input buffer. The parser then executes the program in Fig. 4.36.

 

let a be the  first symbol of w$;

w h i l e(1) {         /* repeat forever */

 

let s be the state on top of the stack;

 

if ( ACTION[s, a] = shift t ) {

 

push t onto the stack;

 

let a be the next input symbol;

 

} else if ( ACTION [s, a] = reduce A (3 ) { pop 1{31 symbols off the stack;

 

let state t now be on top of the stack; push GOTOft, A] onto the stack; output the production A -» /?;

 

} else if ( ACTION[s,a] = accept ) break; /* parsing is done */ else call error-recovery routine;

 

}

 

Figure 4.36:  LR-parsing program

 

 

Example 4 . 4 5 : Figure 4.37 shows the ACTION and GOTO functions of an LR-parsing table for the expression grammar (4.1), repeated here with the productions numbered:

 

 

The codes for the actions are:

 

1. si means shift and stack state z,

 

2. rj means reduce by the production numbered j,

 

            acc means accept,

 

            blank means error.

 

Note that the value of GOTO[s, a] for terminal a is found in the ACTION field connected with the shift action on input a for state s. The GOTO field gives GOTOJs, A] for nonterminals A. Although we have not yet explained how the entries for Fig. 4.37 were selected, we shall deal with this issue shortly.

 


On input id * id + id, the sequence of stack and input contents is shown in Fig. 4.38. Also shown for clarity, are the sequences of grammar symbols corresponding to the states held on the stack. For example, at line (1) the LR parser is in state 0, the initial state with no grammar symbol, and with id the first input symbol. The action in row 0 and column id of the action field of Fig. 4.37 is s5, meaning shift by pushing state 5. That is what has happened at line (2): the state symbol 5 has been pushed onto the stack, and id has been removed from the input.

 

Then, * becomes the current input symbol, and the action of state 5 on input * is to reduce by F id.  One state symbol is popped off the stack.  State 0 is then exposed. Since the goto of state 0 on F is 3, state 3 is pushed onto the stack. We now have the configuration in line (3). Each of the remaining moves is determined similarly.

 

4. Constructing SLR-Parsing Tables

 

The SLR method for constructing parsing tables is a good starting point for studying LR parsing. We shall refer to the parsing table constructed by this method as an SLR table, and to an LR parser using an SLR-parsing table as an SLR parser. The other two methods augment the SLR method with lookahead information.

 

The SLR method begins with LR(0) items and LR(0) automata, introduced in Section 4.5. That is, given a grammar, G, we augment G to produce G', with a new start symbol S'. From G', we construct C, the canonical collection of sets of items for G' together with the G O T O function.


The ACTION and GOTO entries in the parsing table are then constructed using the following algorithm. It requires us to know FOLLOW(A) for each nonterminal A of a grammar (see Section 4.4).

 

Algorith m 4 . 4 6 : Constructing an SLR-parsing table.

 

INPUT :  An augmented grammar G'.

OUTPUT : The SLR-parsing table functions ACTION  and GOTO for G'.

METHOD :

 

 

If any conflicting actions result from the above rules, we say the grammar is not SLR(l) . The algorithm fails to produce a parser in this case.

 

  

The parsing table consisting of the ACTION and GOTO functions determined by Algorithm 4.46 is called the SLR(l) table for G. An LR parser using the SLR(l) table for G is called the SLR(l) parser for G, and a grammar having an SLR(l) parsing table is said to be SLR(l). We usually omit the "(1)" after the "SLR," since we shall not deal here with parsers having more than one symbol of lookahead.

 

E x a m p l e 4 . 4 7 : Let us construct the SLR table for the augmented expression grammar. The canonical collection of sets of LR(0) items for the grammar was shown in Fig. 4.31. First consider the set of items Io:

 


Example 4.48 : Every SLR(l) grammar is unambiguous, but there are many unambiguous grammars that are not SLR(l) . Consider the grammar with pro-ductions

 

 

Think of L and R as standing for /-value and r-value, respectively, and * as an operator indicating "contents of."5 The canonical collection of sets of LR(0) items for grammar (4.49) is shown in Fig. 4.39.


Consider the set of items I2.  The first item in this set makes A C T I O N [ 2 , = ] be "shift 6." Since F O L L O W ( J R )  contains = (to see why, consider the derivation S L = R *R - R), the second item sets ACTlON[2, =] to "reduce R -> L." Since there is both a shift and a reduce entry in A C T I O N [ 2 , = ] , state 2 has a shift/reduce conflict on input symbol =.

 

Grammar (4.49) is not ambiguous. This shift/reduce conflict arises from the fact that the SLR parser construction method is not powerful enough to remember enough left context to decide what action the parser should take on input =, having seen a string reducible to L. The canonical and LALR methods, to be discussed next, will succeed on a larger collection of grammars, including 5 A s in Section 2.8.3, an /-value designates a location and an r-value is a value that can be stored in a location. 

grammar (4.49). Note, however, that there are unambiguous grammars for which every LR parser construction method will produce a parsing action table with parsing action conflicts. Fortunately, such grammars can generally be avoided in programming language applications. •

 

5. Viable Prefixes

 

Why can LR(0) automata be used to make shift-reduce decisions? The LR(0) automaton for a grammar characterizes the strings of grammar symbols that can appear on the stack of a shift-reduce parser for the grammar. The stack contents must be a prefix of a right-sentential form. If the stack holds a and the rest of the input is x, then a sequence of reductions will take ax to S. In

 

Not all prefixes of right-sentential forms can appear on the stack, however, since the parser must not shift past the handle. For example, suppose


Then, at various times during the parse, the stack will hold (, (E, and (E), but it must not hold (E)*, since (E) is a handle, which the parser must reduce to F before shifting *.  

 

The prefixes of right sentential forms that can appear on the stack of a shift-reduce parser are called viable prefixes. They are defined as follows: a viable prefix is a prefix of a right-sentential form that does not continue past the right end of the rightmost handle of that sentential form. By this definition, it is always possible to add terminal symbols to the end of a viable prefix to obtain a right-sentential form.

 

We can easily compute the set of valid items for each viable prefix that can appear on the stack of an LR parser.  In fact, it is a central theorem of LR-parsing theory that  the set of valid items for a viable prefix g is exactly the set of items reached from the initial state along the path labeled g in the LR(0) automaton for the grammar. In essence, the set of valid items embodies all the useful information that can be gleaned from the stack. While we shall not prove this theorem here, we shall give an example.

 

 

 


 

6. Exercises for Section 4.6

 

Exercise 4 . 6 . 1 :  Describe all the viable prefixes for the following grammars:

a)       The grammar S    0 5 1 | 0 1 o f Exercise 4.2.2(a).

b)      The grammar S - > S S + 1 S S * 1 a of Exercise 4.2.1.

c)  The grammar S         S ( S ) | e of Exercise 4.2.2(c).

 

Exercise 4 . 6 . 2 : Construct the SLR sets of items for the (augmented) grammar of Exercise 4;2.1. Compute the GOTO function for these sets of items. Show the parsing table for this grammar. Is the grammar SLR?

Exercise 4 . 6 . 3 : Show the actions of your parsing table from Exercise 4.6.2 on the input aa * a+.

Exercise 4 . 6 . 4 :  For each of the (augmented) grammars of Exercise 4.2.2(a)-

(g):

          Construct the SLR sets of items and their GOTO function.

 

          Indicate any action conflicts in your sets of items.

 

          Construct the SLR-parsing table, if one exists.

 

Exercise 4 . 6 . 5 :  Show that the following grammar:

S       -»      Aa Ab |  B b B a

A       -»•     e

B       ->      e

 

is LL(1) but not SLR(l) .

 

Exercise 4 . 6 . 6 :  Show that the following grammar:

S       S A | A

A       -)•      a

is SLR(l) but not LL(1).

 

Exercise 4 . 6 . 7:  Consider the family of grammars Gn    defined by:

                             5        -»      Ai      bi       for 1 < i < n

                             Ai      ->      aj       Ai  | aj         for 1 < i,j < n and i ^ j

Show that:                                        

a)       Gn     has    2 n 2    -      n productions.     

b)      Gn     has    2n   + n2     + n sets of LR(0)  items.

c)  Gn    is  SLR(l) .

What does this analysis say about how large LR parsers can get?

Exercise 4 . 6 . 8 : We suggested that individual items could be regarded as states of a nondeterministic finite automaton, while sets of valid items are the states of a deterministic finite automaton (see the box on "Items as States of an NFA" in Section 4.6.5). For the grammar S S S + 1 S S * 1 a of Exercise 4.2.1:

a) Draw the transition diagram (NFA) for the valid items of this grammar according to the rule given in the box cited above.

b) Apply the subset construction (Algorithm 3.20) to your NFA from part

(a). How does the resulting DFA compare to the set of LR(0) items for the grammar?

c) Show that in all cases, the subset construction applied to the NFA that comes from the valid items for a grammar produces the LR(0) sets of items.

 

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail


Copyright © 2018-2021 BrainKart.com; All Rights Reserved. (BS) Developed by Therithal info, Chennai.