Copyright © 2006 Gradiance Corporation.

 

 

     

LR(1) Parsers

 

 

 

LR(1), SLR, and LALR parsing; YACC.

 

1.  

Construct the LR(1) sets of items for the grammar: 

 
S' → S
S → SS+ | a
 

Then, identify, in the list below, the one set that is NOT a set of LR(1) items for this grammar.

 

 

 

 a) 

[S→a., +a]

 

 b) 

[S'→S., $], [S→S.S+, $a], [S→.SS+, +a], [S→.a, +a]

 

 c) 

[S→SS.+, $a], [S→S.S+, +a], [S→.SS+, +a], [S→.a, +a]

 

 d) 

[S→SS.+, $+a], [S→S.S+, +a], [S→.SS+, +a], [S→.a, +a]

 

 

 

 

 

2.  

Construct the LALR(1) sets of items for the grammar: 

 
S' → S
S → +SS | a
 

Then, identify, in the list below, one of the LALR(1) sets of items for this grammar.

 

 

 

 a) 

[S→a., +a]

 

 b) 

[S→+SS., $+a]

 

 c) 

[S→+.SS, $+a], [S→.+SS, $+a], [S→.a, $+a]

 

 d) 

[S→+.SS, $], [S→.+SS, +a], [S→.a, +a]

 

 

 

 

 

3.  

Here are the LR(1) sets of items for the grammar: 

1) S → AaAb
2) S → BbBa
3) A → ε
4) B → ε

Construct the Action and Goto portions of the LR(1) parsing table for this grammar. In this table:

  1. The rows are numbered 0, 1,..., 9, corresponding to items I0, I1,..., I9, respectively.
  2. Action sj means shift and go to state (row) j.
  3. Action rj means reduce by production j (according to the numbering of the productions above).

Identify, from the list of choices below, the incorrect table entry.

 

 

 

 a) 

Action(6,b) = s8

 

 b) 

Action(0,b) = r4

 

 c) 

Goto(8,$) = 1

 

 d) 

Action(4,b) = r3

 

 

 

 

 

4.  

Here are the LR(1) sets of items for the grammar: 

1) S → AaAb
2) S → BbBa
3) A → ε
4) B → ε

It has a set of LR(0) items that are the same, but with the lookaheads removed. For example, I4 is just {[S→Aa.Ab], [A→.]}.

While the LR(1) parsing table has no conflicts, when we construct the SLR parsing table we get conflicts. Construct both tables, using the following conventions:

  1. The rows are numbered 0, 1,..., 9, corresponding to items I0, I1,..., I9, respectively.
  2. Action sj means shift and go to state (row) j.
  3. Action rj means reduce by production j (according to the numbering of the productions above).

Which of the following entries appears in the SLR table (possibly as one of several choices for that entry) but does not appear in the LR(1) table?

 

 

 

 a) 

r1 in Action(9,$)

 

 b) 

r4 in Action(0,a)

 

 c) 

r1 in Action(8,b)

 

 d) 

acc in Action(1,b)

 

 

 

 

 

5.  

Construct the LALR(1) sets of items for the grammar: 

 
S' → S
S → SS+ | a
 

Then, identify, in the list below, one of the LALR(1) sets of items for this grammar.

 

 

 

 a) 

[S→SS+., $+a]

 

 b) 

[S'→.S, $], [S→.SS+, $+a], [S→.a, $+a]

 

 c) 

[S→SS.+, +a], [S→S.S+, +a], [S→.SS+, +a], [S→.a, +a]

 

 d) 

[S'→S., $], [S→S.S+, $+a], [S→.SS+, +a], [S→.a, +a]

 

 

 

 

 

6.  

Here is the outline of a Yacc progam for parsing expressions over the noncommutative operators - and /. However, these operators may have nonstandard precedence and/or associativity. NUMBER is a token standing for any integer. Its lexical value is the value of that integer. 

 
. . .
%token NUMBER
%right '-'

%right '/'
. . .
expr : expr '-' expr {$$ = $1 - $3}
     | expr '/' expr {$$ = $1 / $3}
     | NUMBER
. . .
 

Suppose the input to the lexical analyzer and parser is:

6 - 5 - 4 / 3 / 2

What is the value returned when this string is parsed as an expr?

 

 

 

 a) 

-2

 

 b) 

11/3

 

 c) 

5/6

 

 d) 

-1/2