CSC448: Parsing Revisited: Derivations III [104/133]

A derivation is leftmost if the chosen non-terminal symbol is always the leftmost non-terminal.

Leftmost derivations are interesting, because they correspond to the parsing strategy used by a JavaCC parser.

As a JavaCC parser sees the terminals symbols "(" digit "+" digit ")" "*" digit, it makes "local" decisions about which production to use. The decisions must be based upon the next terminal symbol.

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 page 169 and section 4.4 of the Dragon book.