13.4 Example of nulled symbol

As already stated, Marpa prunes every null subtree back to its topmost null symbol. Here is an example grammar, with S as the start symbol.

        S ::= L R
        L ::= A B X
        L ::=
        R ::= A B Y
        R ::=
        A ::=
        B ::=
        X ::=
        X ::= "x"
        Y ::=
        Y ::= "y"

If we let the input be ‘x’, we can write the unpruned parse tree in preorder (depth-first), indenting children below their parents, like this:

        0: Visible Rule: S := L R
             1: Visible Rule L := A B X
                 1.1: Nulled Symbol A
                 1.2: Nulled Symbol B
                 1.3: Token, Value is "x"
             2: Nulled Rule, Rule R := A B Y
                 2.1: Nulled Symbol A
                 2.2: Nulled Symbol B
                 2.3: Nulled Symbol Y

In this example, five symbols and a rule are nulled. The nulled rule and three of the nulled symbols are in a nulled subtree: 2, 2.1, 2.2 and 2.3. Marpa prunes every null subtree back to its topmost symbol, which in this case is the LHS of the rule numbered 2. The pruned tree looks like this:

         0: Visible Rule: S := L R
              1: Visible Rule L := A B X
                  1.1: Nulled Symbol A
                  1.2: Nulled Symbol B
                  1.3: Token, Value is "x"
              2: LHS of Nulled Rule, Symbol R

Nulled nodes 1.1, 1.2 and 2 were all kept, because they are topmost in their nulled subtree. All the other nulled nodes were discarded.