Parse Tree

• Inner nodes of a parse tree are non-terminal symbols.

•  The leaves of a parse tree are terminal symbols.

•  A parse tree can be seen as a graphical representation of a derivation

Ambiguity

•A grammar produces more than one parse tree for a sentence is called as an ambiguous grammar.

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

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

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

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

—Ambiguous grammars (because of ambiguous operators) can be disambiguated according to the precedence and associativity rules.

  E ® E+E  |  E*E  |  E^E  |  id  |  (E)

      disambiguate the grammar

  precedence:    ^   (right to left)

  *   (left to right)

  +   (left to right)

  E ® E+T  |  T

  T ® T*F  |  F

  F ® G^F  |  G

  G ® id  |  (E)

Left Recursion

—A grammar is  left recursive  if it has a non-terminal   “A” such that there is  a derivation.

 

   A Þ Aa  for some string a

 

—Top-down parsing techniques cannot handle left-recursive grammars.

—So, we have to convert our left-recursive grammar into an equivalent grammar which is not left-recursive.

—The left-recursion may appear in a single step of the derivation (immediate left-recursion), or may appear in more than one step of the derivation.

Immediate Left-Recursion

•A ® A a |  b       where b does not start with A

•  ß  eliminate immediate left recursion

•A ® b A’

•A’ ® a A’  |  e   an equivalent grammar

•

•A ® A a1 | ... | A am | b1 | ... | bn   where b1 ... bn do not start with A

•  ß  eliminate immediate left recursion

•A ® b1 A’  | ... | bn A’

•A’ ® a1 A’  | ... | am A’  | e   an equivalent grammar