6.6. Some Example Grammars

List of one or more expressions, separated by commas

L E , L

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

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

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.

L ε

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.

L E  L
n L
n E L
n n L
n n

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

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

List of zero or more expressions, separated by commas

L ε
N E , N


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

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

I if ( E ) S
I if ( E ) S else S

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.

I if ( E ) S R
R ε
R else S