LALR(1) Exercises

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>

1. Compute the set of LALR(1) states for the grammar. Build the corresponding LALR(1) parse table.
2. 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.
3. 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>

1. Compute the set of LALR(1) states for the grammar. Build the corresponding LALR(1) parse table.
2. 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.
3. 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>

1. Compute the set of LALR(1) states for the grammar. Build the corresponding LALR(1) parse table.
2. Compact the parse table, eliminating and propagating reductions.
3. 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.
4. 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>

1. Compute the set of LALR(1) states for the grammar. Build the corresponding LALR(1) parse table.
2. Compact the parse table, eliminating and propagating reductions.
3. 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>

1. Compute the set of LALR(1) states for the grammar. Build the corresponding LALR(1) parse table.
2. Compact the parse table, eliminating and propagating reductions.
3. 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>

1. Compute the set of LALR(1) states for the grammar. Build the corresponding LALR(1) parse table.
2. Compact the parse table, eliminating and propagating reductions.
3. 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

• Answers to exercises 1, 2, and 3
• Solutions to LALR(1) Tests