CSC448: Parsing Revisited: Derivations I [102/133]

Derivations are an alternative to parse trees. They carry more information about how parse trees are built.

The first line consists of the start symbol.

In each successive line, one non-terminal symbol can be replaced with one of its productions.

exp 
=> exp "*" exp
=> "(" exp ")" "*" exp
=> "(" exp "+" exp ")" "*" exp
=> "(" num "+" exp ")" "*" exp
=> "(" digit "+" exp ")" "*" exp
=> "(" digit "+" num ")" "*" exp
=> "(" digit "+" digit ")" "*" exp
=> "(" digit "+" digit ")" "*" num
=> "(" digit "+" digit ")" "*" digit

See section 4.2 of the Dragon book.