CMSC 22610
Implementation of Computer Languages - I
Winter 2009

1. Give unambiguous grammars (and do not use Extended BNF) for the following languages:
   1. Non-empty palindromes over the terminals {0, 1}.
   2. The language denoted by the regular expression (a  b^*  a) | (b  a^*  b) (over the alphabet {a, b}).
   3. Strings where all as preceed all bs and there are strictly more as than bs over the terminals {a, b, c}.

   Hint: One way of verifying that a grammar is unambiguous is to run it through ML-Yacc or ML-Antlr and get no conflicts.

2. Consider the following grammar:

   Function-style prefix with {∧,∨}-lists

   S → P $

   P → var P → ¬ ( P ) P → ∧ ( L ) P → ∨ ( L )

   L →   L → P K

   K →   K → , P K

   1. Draw the derivation tree for the string ∧ ( a , ∨ ( b , ¬ ( c ) ) ) $.
   2. Compute Nullable, First, and Follow for each non-terminal in the grammar. Use Figure 1.
   3. Compute the LL(1) parse table for the grammar. Use Figure 2.
   4. Show the execution of the LL(1) parsing algorithm when parsing the string ∧ ( a , ¬ ( b ) ) $. Use Figure 3.
   5. The canonical LR(0) states for the grammar are given in Figure 4. Compute the LR(0) Goto function for the grammar. Use Figure 5.
   6. Compute the LR(0) action and goto tables for the grammar. Use Figures 6 and 7. Is the grammar LR(0)?
   7. Compute the SLR action table for the grammar. Use Figure 8. (Recall: the SLR goto table is the same as the LR(0) goto table in Problem 2(f).) Is the grammar SLR?
   8. Show the execution of the SLR parsing algorithm when parsing the string ∧ ( a , ¬ ( b ) ) $. Use Figure 9.

Document history

February 10, 2009

 
Figure 4: I₉ = { [ P → ¬ ( . P ) ] } ⇒ I₉ = { [ P → ∧ ( L ) . ] }

February 5, 2009

Original version

---

Nullable First Follow  S       P       L       K

Figure 1: Nullable, First, Follow (for Problem 2(b))

---

---

var ¬ ∧ ∨ ( ) , $  S                 P                 L                 K

Figure 2: LL(1) parse table (for Problem 2(c))

---

---

Stack Input Action  S  ( a , ¬ ( b ) ) $ parse S → P $  $ P  ( a , ¬ ( b ) ) $

Figure 3: Execution of LL(1) parsing the string ∧ ( a , ¬ ( b ) ) $ (for Problem 2(d))

---

---

I0 = {  [ S → . P $ ] , [ P → . var ], [ P → . ¬ ( P ) ], [ P → . ∧ ( L ) ], [ P → . ∨ ( L ) ] }  I1 = {  [ P → var . ]  }  I2 = {  [ P → ¬ . ( P ) ]  }  I3 = {  [ P → ∧ . ( L ) ]  }  I4 = {  [ P → ∨ . ( L ) ]  }  I5 = {  [ S → P . $ ]  }  I6 = {  [ P → ¬ ( . P ) ] , [ P → . var ], [ P → . ¬ ( P ) ], [ P → . ∧ ( L ) ], [ P → . ∨ ( L ) ] }  I7 = {  [ P → ∧ ( . L ) ] , [ L → . ], [ L → . P K ], [ P → . var ], [ P → . ¬ ( P ) ], [ P → . ∧ ( L ) ], [ P → . ∨ ( L ) ] }  I8 = {  [ P → ∨ ( . L ) ] , [ L → . ], [ L → . P K ], [ P → . var ], [ P → . ¬ ( P ) ], [ P → . ∧ ( L ) ], [ P → . ∨ ( L ) ] }  I9 = {  [ P → ∧ ( L ) . ]  }  I10 = {  [ L → P . K ] , [ K → . ], [ K → . , P K ] }  I11 = {  [ P → ∧ ( L . ) ]  }  I12 = {  [ P → ∨ ( L . ) ]  }  I13 = {  [ P → ¬ ( P . ) ]  }  I14 = {  [ K → , . P K ] , [ P → . var ], [ P → . ¬ ( P ) ], [ P → . ∧ ( L ) ], [ P → . ∨ ( L ) ] }  I15 = {  [ L → P K . ]  }  I16 = {  [ P → ∨ ( L ) . ]  }  I17 = {  [ P → ¬ ( P ) . ]  }  I18 = {  [ K → , P . K ] , [ K → . ], [ K → . , P K ] }  I19 = {  [ K → , P K . ]  }

Figure 4: Canonical LR(0) states (for Problems 2(e), 2(f), 2(g))

---

---

Goto    var ¬ ∧ ∨ ( , ) S P L K  I0 I1 I2 I3 I4 ∅ ∅ ∅ ∅ I5 ∅ ∅  I1 ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅  I2 ∅ ∅ ∅ ∅ I6 ∅ ∅ ∅ ∅ ∅ ∅  I3                       I4                       I5                       I6                       I7                       I8                       I9                       I10                       I11                       I12                       I13                       I14                       I15                       I16                       I17                       I18 ∅ ∅ ∅ ∅ ∅ I14 ∅ ∅ ∅ ∅ I19  I19 ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅

Figure 5: LR(0) Goto function (for Problem 2(e))

---

---

Action    var ¬ ∧ ∨ ( , ) $  I0 s I1 s I2 s I3 s I4         I1 r P → var r P → var r P → var r P → var r P → var r P → var r P → var r P → var  I2         s I6       I3                 I4                 I5                 I6                 I7                 I8                 I9                 I10                 I11                 I12                 I13                 I14                 I15                 I16                 I17                 I18                 I19

Figure 6: LR(0) action table (for Problem 2(f))

---

---

Goto    S P L K  I0   g I5     I1         I2         I3         I4         I5         I6         I7         I8         I9         I10         I11         I12         I13         I14         I15         I16         I17         I18         I19

Figure 7: LR(0) goto table (for Problem 2(f))

---

---

Action    var ¬ ∧ ∨ ( , ) $  I0 s I1 s I2 s I3 s I4         I1                 I2                 I3                 I4                 I5                 I6                 I7                 I8                 I9                 I10                 I11                 I12                 I13                 I14                 I15                 I16                 I17                 I18                 I19

Figure 8: SLR action table (for Problem 2(g))

---

---

Stack Input Action  I0  ( a , ¬ ( b ) ) $  I3  I0 I3  a , ¬ ( b ) ) $

Figure 9: Execution of SLR parsing the string ∧ ( a , ¬ ( b ) ) $ (for Problem 2(h))

---