Derivations

e.g.,

<Exp> _lm=> <Exp> + <Term> _lm=> <Term> + <Term> _lm=> <Term>*<Factor> + <Term> _lm=> <Factor>*<Factor> + <Term> _lm=> w*<Factor> + <Term> _lm=> w*x + <Term> _lm=> w*x + <Term>*<Factor> _lm=> w*x + <Factor>*<Factor> _lm=> w*x + y*<Factor> _lm=> w*x+y*z

 

recall that `lm' indicates left-most derivation.

Parse tree

	+
*				*
w		x		y		z

Left-recursion

The grammar for expressions that shows the correct binding and associativity of operators is left-recursive and is unsuitable for use in a practical top-down parser which could go into an infinite loop without reading any input.

<Exp> ::= <Exp> + <Term> |

<Exp> - <Term> |

<Term>

<Term> ::= <Term> * <Factor> |

<Term> / <Factor> |

<Factor>

<Factor> ::= x | y | ... |

( <Exp> ) |

- <Factor>

A grammar for the concrete syntax of simple arithmetic expressions

The left-recursion is being used to express (i) that + (and -, *, /) are left-associative, e.g., a-b-c=(a-b)-c, and (ii) that an <Exp> is a sequence of one or more <Term>s separated by + | -. Similarly for <Term>, <Factor>s and * | /.

Left-recursion removal

Repeated sequences can be expressed by right-recursion as well as they can by left-recursion.

<Exp> ::= <Term> <Exp'> |

<Term> <Exp''>

<Exp'> ::= + <Exp> | ε

<Exp''> ::= - <Exp> | ε

<Term> ::= <Factor> <Term'> |

<Factor> <Term''>

<Term'> ::= * <Term> | ε

<Term''> ::= / <Term> | ε

<Factor> ::= x | y | ... |

( <Exp> ) |

- <Factor>

A non-left-recursive grammar for the concrete syntax of simple arithmetic expressions

But beware: Building a parse tree naively with this grammar could suggest that a-b-c = a-(b-c) which is not the case.

Factoring

The previous grammar can be used in a top-down parser but only in one that must look arbitrarily far ahead, e.g., past the <Term>, to determine which alternative to use for <Exp>. This difficulty can be removed by factoring productions with a common prefix.

<Exp> ::= <Term> <Exp'>

<Exp'> ::= + <Exp> | - <Exp> | ε

<Term> ::= <Factor> <Term'>

<Term'> ::= * <Term> | / <Term> | ε

<Factor> ::= x | y | ... |

( <Exp> ) |

- <Factor>

An LL(1) grammar (factored, non-left-recursive) for the concrete syntax of simple arithmetic expressions

(Care is still needed when building a parse tree with this grammar.) The grammar can be used in a top-down parser that uses just one symbol lookahead, in an LL(1) parser.

Some recursion cannot be removed from the grammar. Note that an expression can contain a subexpression in parentheses, <Exp> =>⁺ ( <Exp> ). This is not left-recursive (nor right-recursive) because some input (of a '(') is necessary before the recursion so this does not cause any problems.