CS 4980 CC, Note 4

Copyright © 2004, 2021
Robert W. Hasker

CS 4980 CC - Note 4

LR Parsing

LL(k) must predict; weak
LR(k): left-to-right parse, rightmost derivation, k symbol lookahead
- can postpone decisions until have seen entire right-hand-side of a production and k more input tokens beyond
- two basic operations:
  - shift: move first input token to top of stack
  - reduce: given a grammar rule X → A B C with C B A on top of stack, pop the C B A and push X
- will augment grammar with end-of-input marker: S' → S$
- initially: stack empty
- accept input when shift $
[see fig. 3.18, p. 56]
- This shows a series of shift/reduce actions
- Note first shift converts the program variable a into the terminal id
- Subscripts: capture state numbers from the underlying DFA; this DFA determines when to shift and when to reduce
The underlying DFA:
- DFA applied to stack top, not input
- edges of DFA labeled with symbols that can be on the stack
- example table: table 3.19, p. 57
- Grammar 3.1 (p. 40):
```
        S → S; S
        S → id := E
        S → print ( L )
        E → id
        E → num
        E → E + E
        E → (S, E)
        L → E
        L → L, E
```
- elements in table:
  - sn: shift and got to state n
  - gn: go to state n
  - rk: reduce by rule k
  - a: accept
  - (blank): error
- apply table to input in fig. 3.18:
  - a := 7; b := c + (d := 5 + 6, d) $
dfa allows us to avoid rescanning stack for each token
parsing algorithm: let x = top stack state, a be next input:
switch action(x, a):
- shift(n): advance input by one token, push n
- reduce(k): pop stack by number of symbols on right-hand side of rule k;
  let X be the left-hand-side of rule k, b be the state now on the top of the stack:
  - action(X, b) should be "goto(n)" for some n
  - push n on top of stack
- accept: stop parsing, report success
- error: stop parsing, report failure (or perhaps do error recovery)
LR(k) means k symbols of lookahead
- for LR(2), top of table would contain all possible pairs of symbols
- $k > 1$ is rare: huge tables, most prog. languages are LR(1)

LR(0) parser generation

First illustrate with LR(0)
- LR(0) not a very strong class, so not used often
- using grammar 3.20, p. 58:
  - 0. S' → S $
  - 1. S → (L)
  - 2. S → x
  - 3. L → S
  - 4. L → L , S
How does LR(0) parser work on grammar 3.20?
- goal: reduce S' → S $
- that is, expect input to be described by "S$"
- initial state: parsing by the rule S' → .S$ where the dot indicates the "current position" of the parser (with respect to the parse tree)
- furthermore, if input begins with an S, then that means it begins with any possible right-hand side of an S-production; this gives the state
```
        S' → .S$
        S  → .x
        S  → .(L)
```
  We call this state 1. Each state consists of a set of items where an item is one of the productions in the state.
Generating the DFA for the parser
- need shift, goto, reduce, and accept actions
Shift
- in state 1, can shift an x and a (.
- If shift x, get state 2:
```
        S → x.
```
  This will lead to a reduction; more later
- If shift (, get the item
```
        S → (.L)
```
  Thus the remaining string must be something derived from L, meaning we need to include all of the L productions and then all S productions; this gives state 3:
```
        S → (.L)
        L → .L, S
        L → .S
        S → .(L)
        S → .x
```
Reduce
- In state 2, dot is at end of an item
- Can then reduce by that production
- More specifically, can pop the right hand side off the stack, push the left hand side
- Will then have a goto action to move to the next state
Goto
- Capture what to do after a reduce
- example, if in state 1 and parse all of S, will end up with "S' → S.$"
  - that is, if we reduce by some S production, will be popping all right-hand side symbols from that S production
  - the effect: moving the dot past the S
  - state 4:
```
        S → S.$
```
    If a nonterminal followed the dot, would have to compute the closure of it as well.
Accept: reducing by S' → S$
Elements of algorithm to compute shift/reduce/goto/accept table:
- Closure(I): adds items to a set for each case in which a dot is to the left of a nonterminal
- Goto(I, X): move dot past symbol X in all items
Algorithm for LR(0) parser construction
1. augment by adding S' → S$
2. construct state machine
  - T: set of states (where each state is a set of items)
  - E: set of shift/goto edges
  - [see p. 60; do example to construct figure 3.21]
  - This is based on grammar 3.20 (p. 58):
  - using grammar 3.20, p. 58:
    - 0. S' → S $
    - 1. S → (L)
    - 2. S → x
    - 3. L → S
    - 4. L → L , S
  - States for this grammar:
3. compute set of reduce actions
  - [see bottom p. 60 for algorithm]
4. construct full parsing table:
  - for each I -^a→ J where a is a terminal and I, J are states, put action shift J at position (I, a) in table
  - for each I -^X→ J where X is a nonterminal and I, J are states, put action goto J at position (I, X)
  - for each state containing an item S' → S.$ put an accept action at (I, $)
  - for each state containing A → γ. where A → γ is production n, put reduce n action at position (I, b) for each terminal b
[apply to grammar to create table 3.22]:

parsing the input "((a), b)" where a, b are variables represented by the x:

Step	State	Action executed	Resulting stack (subscript: result state)
1	1	Shift (	₁(₃
2	3	Shift (	₁(₃(₃
3	3	Shift a (as x)	₁(₃(₃x₂
4	2	Reduce by 2. S → x	₁(₃(₃S
5	3	Goto 7 (state 3 on S)	₁(₃(₃S₇
6	7	Reduce by 3. L → S	₁(₃(₃L
7	3	Goto 5 (state 3 on L)	₁(₃(₃L₅
8	5	Shift )	₁(₃(₃L₅)₆
9	6	Reduce by 1. S → (L)	₁(₃S
10	3	Goto 7 (state 3, on S)	₁(₃S₇
11	7	Reduce by 3. L → S	₁(₃L
12	3	Goto 5 (state 3, on L)	₁(₃L₅
13	5	Shift )	₁(₃L₅)₆
14	6	Reduce by 1. S → (L)	₁S
15	1	Goto 4 (state 1, on S)	₁S₄
16	4	Accept

What we have covered:
- constructing a dfa to parse strings
- this construct results in a single action for each state: shift or reduce

SLR Parser Generation

Limitation of LR(0) algorithm: shift/reduce decision cannot depend on next bit of input
Example: [construct table for grammar 3.23, p. 62]
- must shift or reduce on symbol + in state 3
SLR: "simple LR"
- extend algorithm: for each state containing A → γ. where A → γ is production n, put reduce n action at position (I, b) for each terminal b in FOLLOW(A)
[construct parsing table for grammar 3.23]
- note: need to determine FIRST, Nullable, FOLLOW for grammar 3.23
- should get table in fig. 3.25
Many useful programming languages are SLR.

LR(1) and LALR(1) Parser Generation

Extend capability of SLR parser generation by adding lookahead.
Each item: (A → α.β, x)
- α on top of stack
- input starts with something derivable from β x
- lookahead allows more "intelligent" decision making
Revise Closure and Goto to incorporate lookahead
- see bottom p. 63
- start state: (S' → .S $, ?)
  - the ? is a don't care since never shift the $
- Reduce items:
  - given (A → α., z) in state I,
  - add reduce by A → α to state I with next symbol z

example

construct LR(1) states for Grammer 3.26:

        0) S' → S $                 3) E → V
        1) S → V = E                4) V → x
        2) S → E                    5) V → * E

note: can combine lookaheads
check against figure 3.27
construct table; check against table 3.28 (a)

LALR(1) parsing table
- making a smaller compiler: combine states whose items are identical except for lookahead sets
- hence the name: Lookahead LR(1)
- see table 3.28 (b): combined states (6, 13), (7, 12), (8, 11), and (10, 14)
- LALR(1) can result in more reduce-reduce conflicts
- in practice, few differences
- LALR tables are much smaller
Hierarchy of grammar classes
- see fig. 3.29 (p. 66)

Ambiguity

no ambiguous grammars are LL(k) or LR(k)
ambiguity can be useful; consider
```
        S → if E then S else S
        S → if E then S
        S → other
```
- two parses for if a then if b then s₁ else s₂
- can fix by factoring, but resulting grammar may be more difficult to use in compilers
- LR(1) parsing table: will have a shift-reduce conflict:
```
        S → if E then S., else
        S → if E then S. else S, ?
```
- Preference: shift
  - this gives the interpretation we want (match else to closest unmatched then)
  - most parser generators will prefer shift over reduce, but have to be careful

Parser Generators

covering SableCC, not JavaCC
SableCC productions:
```
        nonterminal = sequence ;
```
Example:
```
        assignment = identifier assign expression semicolon ;
```
- identifier, expression: nonterminals
- assign, semicolon: terminals (defined in Tokens section)
  - Helpers cannot be used in productions - must use tokens
Example: Grammar 3.32 (p. 71)

This is a version of the grammar (3.30 in the textbook); see also 3.30.grammar

        P → L                      S → if id then S
        S → id := id               S → if id then S else S
        S → while id do S          L → S
        S → begin L end            L → L ; S

alternatives separated by |
- CANNOT have | within a production
must name each alternative (a design decision)
if grammar symbol duplicated in some sequence, must name at least one ([left:], [right:])

conflicts

shift-reduce, reduce-reduce conflicts reported (fig. 3.33):

        shift/reduce conflict in state [stack: TIf TId TThen PStm *] on TElse in {
                [ PStm = TIf TId TThen PStm * TElse PStm ] (shift),
                [ PStm = TIf TId TThen PStm * ] followed by TElse (reduce)
        }

note that tokens are prefixed with T and productions with P
SableCC: apparently resolve shift-reduce conflicts by favoring shifts

Predecence directives
- Classical expression syntax:
```
        E → E + E
        E → E - E
        E → E * E
        E → E / E
        E → E && E
        E → E || E
```
  - will result in shift-reduce conflicts:
```
        E → E * E., +
        E → E. * E., ?
```
    - would generally want a reduce, not a shift because * has higher precedence
    - if lookahead is * and operator is +, want to reduce not shift
- Same issue for associativity:
```
        E → E + E., +
        E → E. + E., ?
```
  - shift means + is right associative, reduce makes it left-associative
- may even have cases where operator shouldn't be associative: might decide an exponentiation operation ** shouldn't be associative so can just disallow
```
        x ** y ** z
```
- solution: precedence directives
  - Yacc:
```
        %prec nonassoc equals, notequals;
        %prec left plus, minus;
        %prec left times, div;
        %prec right assign;
```
- parser generator can use this information to resolve some shift-reduce conflicts
  - SableCC 3.x does not support such directives
  - Version 4 does, but in a restrictive way to avoid accidents
General principles
- use default shift over reduce in only controlled, known examples
- use precedence rules when straightforward
- rewrite grammar in all other cases
- don't try to do everything in the parser
  - For example, many C++ compilers will issue a warning for
```
        if ( x = 1 )
           f();
        else
           g();
```
    One could build this into the parser, but it's easier to just add code to check for such cases.

Review

LL(k)
LR(k)
dealing with ambiguous grammars
what you should get out of this:
- algorithm experience
- experience with manipulating grammars
- tools

Copyright © 2004, 2021 Robert W. Hasker