Parsing Derivations – Principles of Compiler Design

E Þ E+E

—E+E derives from E

—we can replace  E by E+E

—to able to do this, we have to have a production rule  E®E+E in our grammar.

—

E Þ E+E Þ id+E Þ id+id

—A sequence of replacements of non-terminal symbols is called a derivation of id+id from E.

  Þ   : derives in one step

  Þ  : derives in zero or more steps

  Þ  : derives in one or more steps

Means   E-> E+E -> id + E -> id + id

=  E -> E -> -E -> -(E) -> -(E+E) -> -(id + E ) -> -(id + id)

Parse tree is a graphical representation of derivation that filters out the order in which production are applied to replace nonterminals.

Each interior node of a parse tree represents the application a production.

Derivation Example

E Þ -E Þ -(E) Þ -(E+E) Þ -(id+E) Þ -(id+id)

  OR

E Þ -E Þ -(E) Þ -(E+E) Þ -(E+id) Þ -(id+id)

—At each derivation step, we can choose any of the non-terminal in the sentential form of G for the replacement.

—

—If we always choose the left-most non-terminal in each derivation step, this derivation is called as left-most derivation.

—

—If we always choose the right-most non-terminal in each derivation step, this derivation is called as right-most derivation.