CMPS 450 Week 07: Parsing Techniques, Chapter 4.6

resources:
chapter 4.6 lecture notes
ch 4 dragon book

SECTION 4.6 "Bottom-up LR Parsing: Simple LR"

01. Give all the viable prefixes for the grammar G 
       S -> 0S1 | 01
    A viable prefix for grammar G is a prefix of some right-sentential form that
    ends no farther right than the end of the handle of that right-sentential
    form. In shift-reduce parsing of an LR(0) grammar by an LR(0) automaton, 
    the stack always contains a viable prefix for G. (see Sec 4.6.5 pg 256).

 

02. Construct an SLR (Simple LR) parser for this Grammar G:
         S -> SS+ | SS* | a
    An SLR parser is an LR(1) parser. The SLR sets of items and GOTO functions 
    are the same as those constructed for the LR(0) automaton. An SLR parser 
    is the implementation of the LR(0) automaton for Grammar G. The language 
    for this Grammar G is
         L = { a, aa+,  aa*, aaa++, aaa*+, aaa**, aaa+*, aa+a, aa*a, ... }
    a) augment the grammar


  b) construct the SLR sets of items for the augmented grammar 


  c) compute the GOTO function for the SLR sets of items

  To compute GOTO, first compute the unique closure set for all sets of items.
  Compute GOTO for terminals +,*,a, $ and nonterminal S on each of those sets. 
  Ask yourself what would happen if you encounter +,*,a,$,or S from each 
  parser state; i.e., which state would you then goto?


d) construct the parsing table for the grammar using these conventions: 
   The initial state 0 is the set of items containing [S` -> .S].
   Production labels:
         1. S->SS+   
         2. S->SS*   
         3. S->a
   Stack States:  0 - 5 correspond to Item Collections I_0 - I_5
   Actions: 's2' means shift stack state 2; 'r3' means reduce by production 3 
STEP 1. Compute FOLLOW(A) for each nonterminal in G.           
        FOLLOW(S)={ +, *, a, $}    // S is the only nonterminal.
 
STEP 2. Apply these rules to make shift, reduce decisions and GOTO decisions.

 Rule 1. To make shift decisions, look for Items with a dot followed by a
         terminal; i.e., foreach GOTO[I_i,a]=I_j, denote ACTION[i,a] as sj.
         There are 2 such states: .a isin I_0, so ACTION[0,a] is s1. SS.+ 
         and SS.* are in I_2, so ACTION[2,+] = ACTION[2,*] = s1. 

 Rule 2. To make reduce decisions, look for Items ending in dot; i.e., if 
         [A->alpha.] isin I_i then set ACTION[i,a] to "reduce A->alpha" for
         all terminals a in FOLLOW(A). 
         S->a. isin I_1 and 'a' isin FOLLOW(S), so reduce by S->a (production 
            rule 3) upon encountering an a.
         2. S->SS+. isin I_1 and + isin FOLLOW(S) so reduce by S->SS+ (r1)
         3. S->SS*. isin I_4 and * isin FOLLOW(S) so reduce by S->SS* (r2)

 Rule 3. If [S` -> S.] isin I_i, then set ACTION[i,$] to accept.
 
 Rule 4. If GOTO(I_i, A) = I_j, then GOTO[i,A] = j, where A is a nonterminal. 
         This rule extends the GOTO function to map State x Nonterminals -> 
         State; e.g. GOTO[1,N]->2 means from state 1 and nonterminal N, move 
         to state 2. The GOTO action is used after a reduction to determine what
         state to push onto the stack; e.g., pop the current state and push 
         the state number defined by GOTO.

 Rule 5. Anything not filled in by this point is an error state



 e) show the actions of your parsing table on input 
         aa*a+


 e) This grammar is technically not SLR. Why?

 
03. Show that the grammar, where e is epsilon
        S -> AaAb | BbBa
        A -> e
        B -> e

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

  
04. Show that the grammar G
        S -> S A | A
        A -> a
    is SLR(1) but not LL(1).