6.6. Some Example Grammars

List of one or more expressions, separated by commas

---

Here is a parse tree for n, n, n.

         L
        /|\
       / | \
      E  ,  L
      |    /|\
      n   / | \
         E  ,  L
         |     |
         n     E
               |
               n

List of zero or more expressions, without separators

---

The right-hand side of a production can be an empty string, which we make visible as symbol ε. The following grammar takes advantage of that.

The first production, L → ε, is called an erasing production, or an epsilon-production.

Erasing productions present no difficulties to derivations. Here is a leftmost derivation of n n from L.

A parse tree needs a way to show that a nonterminal was erased. Do that by showing ε below a nonterminal.

       L
      / \
     /   \
    E     L
    |    / \
    n   E   L
        |   |
        n   ε

List of zero or more expressions, separated by commas

---

If-statement

---

Suppose that nonterminal S derives a statement and I derives an if-statement.

One of the productions would be S → I, so that a statement can be an if-statement. Productions for I might be as follows, where if and else are tokens.

If-statements, left-factored

---

There are a lot of choices that you can make. One is to factor out the shared parts of the two productions for if-statements, as follows. Nonterminal R derives the rest of an if-statement, after the common part.