Left Recursion Removal and Left Factoring

Left Recursion Removal and Left Factoring

Motivating example
In this lecture we discuss techniques (that sometimes work) to convert a grammar that is not LL(1) into an equivalent grammar that is LL(1).

Left Recursion Removal and Left Factoring

Motivating example
In this lecture we discuss techniques (that sometimes work) to convert a grammar that is not LL(1) into an equivalent grammar that is LL(1).
- Consider the following grammar:

Left Recursion Removal and Left Factoring

Motivating example
In this lecture we discuss techniques (that sometimes work) to convert a grammar that is not LL(1) into an equivalent grammar that is LL(1).
- Consider the following grammar: exp exp addop term | term addop + | term term mulop factor | factor mulop factor ( exp ) | number

Left Recursion Removal and Left Factoring

Motivating example
In this lecture we discuss techniques (that sometimes work) to convert a grammar that is not LL(1) into an equivalent grammar that is LL(1).
- Consider the following grammar: exp exp addop term | term addop + | term term mulop factor | factor mulop factor ( exp ) | number - This grammar is not LL(1) since number is in First(exp) and in First(term).

Left Recursion Removal and Left Factoring

Motivating example
In this lecture we discuss techniques (that sometimes work) to convert a grammar that is not LL(1) into an equivalent grammar that is LL(1).
- Consider the following grammar: exp exp addop term | term addop + | term term mulop factor | factor mulop factor ( exp ) | number - This grammar is not LL(1) since number is in First(exp) and in First(term). - Thus in the entry M[exp, number] in the LL(1) parsing table we will have the entries exp exp addop term and exp term

Left Recursion Removal and Left Factoring

Motivating example
In this lecture we discuss techniques (that sometimes work) to convert a grammar that is not LL(1) into an equivalent grammar that is LL(1).
- Consider the following grammar: exp exp addop term | term addop + | term term mulop factor | factor mulop factor ( exp ) | number - This grammar is not LL(1) since number is in First(exp) and in First(term). - Thus in the entry M[exp, number] in the LL(1) parsing table we will have the entries exp exp addop term and exp term - The problem is the presence of the left recursive rule exp exp addop term | term.

Left Recursion Removal and Left Factoring

Motivating example
In this lecture we discuss techniques (that sometimes work) to convert a grammar that is not LL(1) into an equivalent grammar that is LL(1).
- Consider the following grammar: exp exp addop term | term addop + | term term mulop factor | factor mulop factor ( exp ) | number - This grammar is not LL(1) since number is in First(exp) and in First(term). - Thus in the entry M[exp, number] in the LL(1) parsing table we will have the entries exp exp addop term and exp term - The problem is the presence of the left recursive rule exp exp addop term | term. - Thus in order to try to convert this grammar into an LL(1) grammar, we remove the left recursion from this grammar.
Left Recursion Removal and Left Factoring

Left Recursion and Right Recursion

Before we look at the technique of removing left recursion from a grammar, we rst discuss left recursion in general.

Left Recursion Removal and Left Factoring

Left Recursion and Right Recursion

Before we look at the technique of removing left recursion from a grammar, we rst discuss left recursion in general. Grammar rules in BNF provide for concatenation and choice but no specic operation equivalent to the of regular expressions are provided.

Left Recursion Removal and Left Factoring

Left Recursion and Right Recursion

Before we look at the technique of removing left recursion from a grammar, we rst discuss left recursion in general. Grammar rules in BNF provide for concatenation and choice but no specic operation equivalent to the of regular expressions are provided. We can obtain repetition by using for example rules of the form

Left Recursion Removal and Left Factoring

Left Recursion and Right Recursion

Before we look at the technique of removing left recursion from a grammar, we rst discuss left recursion in general. Grammar rules in BNF provide for concatenation and choice but no specic operation equivalent to the of regular expressions are provided. We can obtain repetition by using for example rules of the form A Aa | a

Left Recursion Removal and Left Factoring

Left Recursion and Right Recursion

Before we look at the technique of removing left recursion from a grammar, we rst discuss left recursion in general. Grammar rules in BNF provide for concatenation and choice but no specic operation equivalent to the of regular expressions are provided. We can obtain repetition by using for example rules of the form A Aa | a or

Left Recursion Removal and Left Factoring

Left Recursion and Right Recursion

Before we look at the technique of removing left recursion from a grammar, we rst discuss left recursion in general. Grammar rules in BNF provide for concatenation and choice but no specic operation equivalent to the of regular expressions are provided. We can obtain repetition by using for example rules of the form A Aa | a or A aA | a

Left Recursion Removal and Left Factoring

Left Recursion and Right Recursion

Before we look at the technique of removing left recursion from a grammar, we rst discuss left recursion in general. Grammar rules in BNF provide for concatenation and choice but no specic operation equivalent to the of regular expressions are provided. We can obtain repetition by using for example rules of the form A Aa | a or A aA | a Both these grammars generate {an |n 1}.

Left Recursion Removal and Left Factoring

Left Recursion and Right Recursion

Before we look at the technique of removing left recursion from a grammar, we rst discuss left recursion in general. Grammar rules in BNF provide for concatenation and choice but no specic operation equivalent to the of regular expressions are provided. We can obtain repetition by using for example rules of the form A Aa | a or A aA | a Both these grammars generate {an |n 1}. We call the rule A Aa | a left recursive and A aA | a right recursive.

Left Recursion Removal and Left Factoring

Left and right recursion continue

In general, rules of the form

Left Recursion Removal and Left Factoring

Left and right recursion continue

In general, rules of the form A A | are called left recursive

Left Recursion Removal and Left Factoring

Left and right recursion continue

In general, rules of the form A A | are called left recursive and rules of the form A A | right recursive. Grammars equivalent to the regular expression a are given by pause A Aa |

Left Recursion Removal and Left Factoring

Left and right recursion continue

In general, rules of the form A A | are called left recursive and rules of the form A A | right recursive. Grammars equivalent to the regular expression a are given by pause A Aa | or

Left Recursion Removal and Left Factoring

Left and right recursion continue

In general, rules of the form A A | are called left recursive and rules of the form A A | right recursive. Grammars equivalent to the regular expression a are given by pause A Aa | or A aA |

Left Recursion Removal and Left Factoring

Left and right recursion continue

Notice that left recursive rules ensure that expressions associate on the left.

Left Recursion Removal and Left Factoring

Left and right recursion continue

Notice that left recursive rules ensure that expressions associate on the left. The parse tree for the expression 34 3 42 in the grammar

Left Recursion Removal and Left Factoring

Left and right recursion continue

Notice that left recursive rules ensure that expressions associate on the left. The parse tree for the expression 34 3 42 in the grammar
exp exp addop term | term addop + | term term mulop factor | factor mulop factor ( exp ) | number

Left Recursion Removal and Left Factoring

Left and right recursion continue

Notice that left recursive rules ensure that expressions associate on the left. The parse tree for the expression 34 3 42 in the grammar
exp exp addop term | term addop + | term term mulop factor | factor mulop factor ( exp ) | number

is for example given by

Left Recursion Removal and Left Factoring

Left and right recursion continue

Notice that left recursive rules ensure that expressions associate on the left. The parse tree for the expression 34 3 42 in the grammar
exp exp addop term | term addop + | term term mulop factor | factor mulop factor ( exp ) | number

is for example given by

Left Recursion Removal and Left Factoring

Left Recursion Removal and Left Factoring

In the rule

Left Recursion Removal and Left Factoring

Left Recursion Removal and Left Factoring

In the rule
exp exp + term | exp term | term

we have immediate left recursion and in

Left Recursion Removal and Left Factoring

Left Recursion Removal and Left Factoring

In the rule
exp exp + term | exp term | term

we have immediate left recursion and in

AB a|Aa|c B B b|Ab|d

we have indirect left recursion. We only consider how to remove immediate left recursion.

Left Recursion Removal and Left Factoring

Left Recursion Removal and Left Factoring continue

Consider again the rule

Left Recursion Removal and Left Factoring

Left Recursion Removal and Left Factoring continue

Consider again the rule
exp exp addop term | term

Left Recursion Removal and Left Factoring

Left Recursion Removal and Left Factoring continue

Consider again the rule
exp exp addop term | term

We rewrite this rule as

Left Recursion Removal and Left Factoring

Left Recursion Removal and Left Factoring continue

Consider again the rule
exp exp addop term | term

We rewrite this rule as

exp term exp exp addop term exp |

to remove the left recursion. In general if we have productions of the form

Left Recursion Removal and Left Factoring

Left Recursion Removal and Left Factoring continue

Consider again the rule
exp exp addop term | term

We rewrite this rule as

exp term exp exp addop term exp |

to remove the left recursion. In general if we have productions of the form

A A 1 | ... | A n | 1 | ... | m

Left Recursion Removal and Left Factoring

Left Recursion Removal and Left Factoring continue

Consider again the rule
exp exp addop term | term

We rewrite this rule as

exp term exp exp addop term exp |

to remove the left recursion. In general if we have productions of the form

A A 1 | ... | A n | 1 | ... | m

we rewrite this as

Left Recursion Removal and Left Factoring

Left Recursion Removal and Left Factoring continue

Consider again the rule
exp exp addop term | term

We rewrite this rule as

exp term exp exp addop term exp |

to remove the left recursion. In general if we have productions of the form

A A 1 | ... | A n | 1 | ... | m

we rewrite this as
A 1 A | ... | m A A 1 A | ... | n A |

in order to remove the left recursion.

Left Recursion Removal and Left Factoring

Left recursion removal continue

If we remove the left recursion from the rule

Left Recursion Removal and Left Factoring

Left recursion removal continue

If we remove the left recursion from the rule

exp exp + term | exp term | term

we obtain

Left Recursion Removal and Left Factoring

Left recursion removal continue

If we remove the left recursion from the rule

exp exp + term | exp term | term

we obtain
exp term exp exp + term exp | term exp |

Left Recursion Removal and Left Factoring

Left recursion removal continue

If we remove left recursion from the grammar

exp exp addop term | term addop + | term term mulop factor | factor mulop factor ( exp ) | number

Left Recursion Removal and Left Factoring

Left recursion removal continue

If we remove left recursion from the grammar

exp exp addop term | term addop + | term term mulop factor | factor mulop factor ( exp ) | number

we obtain the grammar

Left Recursion Removal and Left Factoring

Left recursion removal continue

If we remove left recursion from the grammar

exp exp addop term | term addop + | term term mulop factor | factor mulop factor ( exp ) | number

we obtain the grammar

exp term exp exp addop term exp | addop + | term factor term term mulop factor term | mulop factor ( exp ) | number

Left Recursion Removal and Left Factoring

Left recursion removal continue

Now consider the parse tree for 3 4 5

Left Recursion Removal and Left Factoring

Left recursion removal continue

Now consider the parse tree for 3 4 5

Left Recursion Removal and Left Factoring

Left recursion removal continue

Now consider the parse tree for 3 4 5

This tree no longer expresses the left associativity of subtraction.

Left Recursion Removal and Left Factoring

Left recursion removal continue

Now consider the parse tree for 3 4 5

This tree no longer expresses the left associativity of subtraction. Nevertheless, a parser should still construct the appropriate left associative syntax tree.
Left Recursion Removal and Left Factoring

Left recursion removal continue

We obtain the syntax tree by removing all the unnecessary information from the parse tree. A parser will usually construct a syntax tree and not a parse tree.

Left Recursion Removal and Left Factoring

Left recursion removal continue

We obtain the syntax tree by removing all the unnecessary information from the parse tree. A parser will usually construct a syntax tree and not a parse tree.

Left Recursion Removal and Left Factoring

Left Factoring

Left factoring is required when two or more grammar rule choices share a common prex string, as in the rule

Left Recursion Removal and Left Factoring

Left Factoring

Left factoring is required when two or more grammar rule choices share a common prex string, as in the rule
A |

Left Recursion Removal and Left Factoring

Left Factoring

Left factoring is required when two or more grammar rule choices share a common prex string, as in the rule
A |

Obviously, an LL(1) parser cannot distinguish between the production choices in such a situation.

Left Recursion Removal and Left Factoring

Left Factoring

Left factoring is required when two or more grammar rule choices share a common prex string, as in the rule
A |

Obviously, an LL(1) parser cannot distinguish between the production choices in such a situation. In the following example we have exactly this problem:

Left Recursion Removal and Left Factoring

Left Factoring

Left factoring is required when two or more grammar rule choices share a common prex string, as in the rule
A |

Obviously, an LL(1) parser cannot distinguish between the production choices in such a situation. In the following example we have exactly this problem:
if -stmt if ( exp ) statement | if ( exp ) statement else statement

Left Recursion Removal and Left Factoring

Left factoring continue

Consider the following grammar of if-statements:

Left Recursion Removal and Left Factoring

Left factoring continue

Consider the following grammar of if-statements:

if -stmt if ( exp ) statement | if ( exp ) statement else statement

Left Recursion Removal and Left Factoring

Left factoring continue

Consider the following grammar of if-statements:

if -stmt if ( exp ) statement | if ( exp ) statement else statement

The left factored form of this grammar is

Left Recursion Removal and Left Factoring

Left factoring continue

Consider the following grammar of if-statements:

if -stmt if ( exp ) statement | if ( exp ) statement else statement

The left factored form of this grammar is

if -stmt if ( exp ) statement else-part else-part else statement |

Left Recursion Removal and Left Factoring

Left factoring continue

Here is a typical example where a programming language fails to be LL(1):

Left Recursion Removal and Left Factoring

Left factoring continue

Here is a typical example where a programming language fails to be LL(1):
statement assign-stmt | call-stmt | other assign-stmt identier := exp call-stmt identier ( exp-list )

Left Recursion Removal and Left Factoring

Left factoring continue

Here is a typical example where a programming language fails to be LL(1):
statement assign-stmt | call-stmt | other assign-stmt identier := exp call-stmt identier ( exp-list )

This grammar is not in a form that can be left factored. We must rst replace assign-stmt and call-stmt by the right-hand sides of their dening productions:

Left Recursion Removal and Left Factoring

Left factoring continue

Here is a typical example where a programming language fails to be LL(1):
statement assign-stmt | call-stmt | other assign-stmt identier := exp call-stmt identier ( exp-list )

This grammar is not in a form that can be left factored. We must rst replace assign-stmt and call-stmt by the right-hand sides of their dening productions:
statement identier := exp | identier ( exp-list ) | other

Then we left factor to obtain:

Left Recursion Removal and Left Factoring

Left factoring continue

Here is a typical example where a programming language fails to be LL(1):
statement assign-stmt | call-stmt | other assign-stmt identier := exp call-stmt identier ( exp-list )

This grammar is not in a form that can be left factored. We must rst replace assign-stmt and call-stmt by the right-hand sides of their dening productions:
statement identier := exp | identier ( exp-list ) | other

Then we left factor to obtain:

statement identier statement | other statement := exp | ( exp-list )

Left Recursion Removal and Left Factoring

Left factoring continue

Here is a typical example where a programming language fails to be LL(1):
statement assign-stmt | call-stmt | other assign-stmt identier := exp call-stmt identier ( exp-list )

This grammar is not in a form that can be left factored. We must rst replace assign-stmt and call-stmt by the right-hand sides of their dening productions:
statement identier := exp | identier ( exp-list ) | other

Then we left factor to obtain:

statement identier statement | other statement := exp | ( exp-list )

Note how this obscures the semantics of call and assignment by separating the identier from the actual call or assign action.
Left Recursion Removal and Left Factoring