Notes for week 7

Day 1.

LR Parser

  1. LR parser overview
    1. Three parts
      1. input stream terminated by $
      2. Stack of grammar items and state numbers
      3. Parse table that consists of
        1. Rows labeled with state numbers
        2. Columns labeled with grammar items (terminal and nonterminal) plus $
    2. The Parse table has entries that tell the user to
      1. shift the current input item and a state number into the stack.
      2. reduce the current top of the stack by replacing a number of items with the left-hand side of a production that has these symbols as its right-hand side. (Just the reverse of the top-down model)
      3. GoTos that indicate the state of the stack when the left-hand side nonterminal is pushed.
      4. accept indicates the parse is successful.
      5. All other entries are errors.
    3. Different methods are used to build the table so that even ambiguous grammars can be parsed by this parser.
    4. Examples: 
      1 E -> E + T
2 E -> E - T
3 E -> T
4 T -> T * F
5 T -> T / F
6 T -> F
7 F -> (E)
8 F -> i

      1. (i+i)/i

        Line Stack Input Entry Action/Production
        1 0 (i+i)/i$ s4 Shift state 4
        2 0 (4 i + i)/i$ s5 Shift state 5
        3 0 (4 i5 + i)/i$ r8 F->i
        To get to line 4 pop right-hand side (i5) Look at Table[4,F] find 3, push F3
        4 0 (4 F3 + i)/i$ r6 T-> F
        5 0 (4 T2 + i)/i$ r3 E ->T
        6 0 (4 E10 + i)/i$ s6 shift state 6
        7 0 (4 E10 +6 i)/i$ s5 shift state 5
        8 0 (4 E10 +6 i5 )/i$ r8 F ->i
        9 0 (4 E10 +6 F3 )/i$ r6 T->F
        10 0 (4 E10 +6 T11 )/i$ r1 E-> E + T
        11 0 (4 E10 )/i$ s15 shift 15
        12 0 (4 E10 )15 /i$ r7 F ->(E)
        13 0 F3 /i$ r6 T->F
        14 0 T2 /i$ s9 Shift state 9
        15 0 T2 /9 i$ s5 Shift state 5
        16 0 T2 /9 i5 $ r8 F->i
        17 0 T2 /9 F14 $ r5 T -> T/F
        18 0 T2 $ r3 E ->T
        19 0 E1 $ acc parse successful

      2. i*(i-i.

Day 2

The SLR parser (SLR method of building the parse table)

  1. Introduction to SLR construction.
    1. When parsing (i), Would like to parse until we get F->(E)
      1. Start at the beginning of the right-hand side F->@(E) (item)
      2. When we push ( we have progressed to F->(@E)
      3. To make headway and have Stack Input $(i )$ How can we handle i? We know we should be at the beginning of an expression that is the right-hand side of a production that produces E. So we must be in one of the following places:
        1. E -> @E+T
        2. E -> @E - T
        3. E -> @T
          Because of 3 we could also be at a point where we are beginning a parse that produces T so we could be
        4. T->@T*F
        5. T->@T/F
        6. T-> @F
          Where else could we be?
        7. F-> @(E)
        8. F -> @ i
        Group all of these items together into a state of equivalent positions in the parse.
      4. We recognize that input i requires that we reduce by F->i. This moves use to the state containing F->i@ (and nothing else). What do we do now? First notice that ) can follow F so there is no error, but we have to know the history of the parse to decide what to do with 
        Stack				input
$(F				)$
      5. To find out where to go next, look at the state in which we had F ->@i we have now found F in this state, so what items in that state are transformed by passing F? T->@F goes to T->F@. This suggest that we should set the stack state to the state that we go to on input of F from the state with T->@F
    2. One last problem. When to stop. We need a nonterminal that does not occur on the right-hand side if any production as our start symbol. Augmented Grammar.
  2. Build the states. 
    0 Z -> E
1 E -> E + T
2 E -> E - T
3 E -> T
4 T -> T * F
5 T -> T / F
6 T -> F
7 F -> (E)
8 F -> i
    1. Create State 0 V[e].
      1. add first production in position 1 (Z ->@E)
      2. Find all productions that can start from this position (compute the Closure) 
        E->@E + T
E ->@E - T
E ->@T

T->@T * F
T->@T / F
T->@F

F->@(E)
F->@i
    2. Create State 1 V[E] on completion of E in state 0 
      Z->E@
E-> E@ + T
E-> E@ -T
    3. Create State 2 V[T] on completion of E in state 0
    4. Create State 3 V[F]
    5. State 4 V[(]
    6. State 5 V[i]
    7. State 6 V[E+] + in state 1
    8. State 7 V[E-] - in state 1
    9. As many states as possible

Work from March 8, 2001

Augmented Grammar

0 Z -> E
1 E -> E + T
2 E -> E - T
3 E -> T
4 T -> T * F
5 T -> T / F
6 T -> F
7 F -> (E)
8 F -> i

States Completed

State 0 
Core   
Z->@E
Closure  
E->@E + T
E->@E - T
E->@T		
T->@T * F	
T->@T / F	
T->@F	
F->@(E)
F->@i
State 1 [0 E] 
Core
Z->E@
E->E@ + T
E->E@ - T
Closure-Empty
State 2 [0 T] 
Core
E->T@
T->T@ * F
T->T@ / F
Closure-Empty
State 3 [0 F] 
Core 
T->F@
Closure - Empty
State 4 [0 (] 
Core
F->(@E)
Closure 
E->@E + T	
E->@E - T	
E->@T		
T->@T * F		
T->@T / F		
T->@F		
F->@(E)
F->@i
State 5 [0 i] 
Core 
F->i@
Closure - Empty
State 6 [1 +] 
Core 
E->E + @T
Closure 
T->@T * F		
T->@T / F		
T->@F		
F->@(E)
F->@i
State 7 [1 -] 
Core 
E->E - @T
Closure 
T->@T * F		
T->@T / F		
T->@F		
F->@(E)
F->@i
State 8 [2 *] 
Core 
T->T * @F
Closure 
F->@(E)
F->@i
 State 9 [2 /] 
Core
T->T / @F
Closure 
F->@(E)
F->@i
State 10 [4 E] 
Core 
F->(E@)
E->E@ + T
E->E@ - T
Closure - Empty   

[4 T]=[0 T]=2
[4 F]=[0 F]=3
[4 (]=[0 (]=4
[4 i]=[0 i]=5

Corresponding Table

  Terminals Non Terminals
State i + - * / ( ) $ E T F
0 s5         s4     1 2 3
1   s6 s7         Accept      
2   r3 r3 s8 s9   r3 r3      
3   r6 r6 r6 r6   r6 r6      
4 s5         s4     10 2 3

You can see the code for doing this process by clicking here .