Difference between revisions of "Bottom-Up Parsing/LALR(1) Example 1"

Latest revision as of 11:35, 2 May 2024

Consider the following grammar (A is the start symbol):

A → C x A | ε
B → x C y | x C
C → x B x | z

Build the LALR(1) parser table. If conflicts exist, assume YACC's behavior.
Show the differences to LR(0) and SLR(1) parsers.
Compact the parse table, eliminating and propagating reductions.
Show the stack and input states, as well as the parser actions, for the sequence xxzxx.

Solution
There is a "bug" in this solution: in the compacted table, L3 in state 10 should be in the column corresponding to y (corresponding to the shift to state 11 in the uncompacted table).

@@ Line 1: / Line 1: @@
 Consider the following grammar ('''A''' is the start symbol):
-  A -> C x A | ε
+  A → C x A | ε
-  B -> x C y | x C
+  B → x C y | x C
-  C -> x B x | z
+  C → x B x | z
 # Build the LALR(1) parser table. If conflicts exist, assume YACC's behavior.
@@ Line 9: / Line 9: @@
 # Show the stack and input states, as well as the parser actions, for the sequence '''xxzxx'''.
-* [http://www.l2f.inesc-id.pt/~david/ist/docencia/compiladores/2007-2008/lalr-ex-1.pdf Solution]<br/>There is a "bug" in this solution: in the compacted table, L3 in state 10 should be in the column corresponding to '''y''' (corresponding to the shift to state 11 in the uncompacted table).
+* [https://www.hlt.inesc-id.pt/~david/ist/docencia/compiladores/2007-2008/lalr-ex-1.pdf Solution]<br/>There is a "bug" in this solution: in the compacted table, L3 in state 10 should be in the column corresponding to '''y''' (corresponding to the shift to state 11 in the uncompacted table).
 [[category:Compiladores]]
 [[category:Ensino]]