Exercise 1
Consider the following grammar, where S is the initial symbol and { a, b } is the set of terminal symbols:
<text>
S -> G b b | a a b | b G a
G -> a
</text>
- Compute the set of LALR(1) states for the grammar. Build the corresponding LALR(1) parse table.
- Show the parsing process for input baaabb (including the actions/gotos and the input and stack states). In case of conflict, assume YACC's behavior.
- Is this an SLR(1) grammar? Why?
Exercise 2
Consider the following grammar, where E is the initial symbol and { [, ], ;, id } is the set of terminal symbols:
<text>
E -> [ E ; L ] | id
L -> E | E ; L
</text>
- Compute the set of LALR(1) states for the grammar. Build the corresponding LALR(1) parse table.
- Show the parsing process for input [id;id;id] (including the actions/gotos and the input and stack states). In case of conflict, assume YACC's behavior.
- Is this an LL(1) grammar? Why?
Exercise 3
Consider the following grammar, where S is the initial symbol and { e, i, x } is the set of terminal symbols:
<text>
S -> i S | i S e S | x
</text>
- Compute the set of LALR(1) states for the grammar. Build the corresponding LALR(1) parse table.
- Compact the parse table, eliminating and propagating reductions.
- Show the parsing process for input ixixex (including the actions/gotos and the input and stack states). In case of conflict, assume YACC's behavior.
- Is this an SLR(1) grammar? Why?
Exercise 4 (test)
Consider the following grammar, where A is the initial symbol and { x, y, z } is the set of terminal symbols:
<text>
A -> B y y | z z x | x B x
B -> z | ε
</text>
- Compute the set of LALR(1) states for the grammar. Build the corresponding LALR(1) parse table.
- Compact the parse table, eliminating and propagating reductions.
- Show the parsing process for input xx (including the actions/gotos and the input and stack states). In case of conflict, assume YACC's behavior.
Exercise 5 (test)
Consider the following grammar, where A is the initial symbol and { x, y, z } is the set of terminal symbols:
<text>
A -> B x y | x y x | x B y
B -> z | ε
</text>
- Compute the set of LALR(1) states for the grammar. Build the corresponding LALR(1) parse table.
- Compact the parse table, eliminating and propagating reductions.
- Show the parsing process for input xzy (including the actions/gotos and the input and stack states). In case of conflict, assume YACC's behavior.
Exercise 6 (test)
Consider the following grammar, where A is the initial symbol and { x, y, z } is the set of terminal symbols:
<text>
A -> A B A x | A y | z
B -> x | z B
</text>
- Compute the set of LALR(1) states for the grammar. Build the corresponding LALR(1) parse table.
- Compact the parse table, eliminating and propagating reductions.
- Show the parsing process for input zzxzyx (including the actions/gotos and the input and stack states). In case of conflict, assume YACC's behavior.
Answers