CSC448: Winter 2002 Notes: Derivations II

CSC448: Parsing Revisited: Derivations II [103/133]

It is possible to find alternate derivations of the same string of terminal symbols:

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

These derivations determine the same parse tree.