Search for notes by fellow students, in your own course and all over the country.
Browse our notes for titles which look like what you need, you can preview any of the notes via a sample of the contents. After you're happy these are the notes you're after simply pop them into your shopping cart.
Document Preview
Extracts from the notes are below, to see the PDF you'll receive please use the links above
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)
...
- 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
- This grammar is not LL(1) since number is in First(exp) and
in First(term)
...
- 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)
...
- 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)
...
- 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
Left Recursion and Right Recursion
Before we look at the technique of removing left recursion
from a grammar, we first discuss left recursion in general
...
Grammar rules in BNF provide for concatenation and choice
but no specific operation equivalent to the ∗ of regular
expressions are provided
...
Grammar rules in BNF provide for concatenation and choice
but no specific operation equivalent to the ∗ of regular
expressions are provided
...
Grammar rules in BNF provide for concatenation and choice
but no specific operation equivalent to the ∗ of regular
expressions are provided
...
Grammar rules in BNF provide for concatenation and choice
but no specific operation equivalent to the ∗ of regular
expressions are provided
...
Grammar rules in BNF provide for concatenation and choice
but no specific operation equivalent to the ∗ of regular
expressions are provided
...
Grammar rules in BNF provide for concatenation and choice
but no specific 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 first discuss left recursion in general
...
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 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 | ε 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
...
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 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
A→B a|Aa|c
B →B b|Ab|d
we have indirect 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
A → A α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
...
| A αn | β1 |
...
In general if we have productions of the form
A → A α1 |
...
| βm
we rewrite this as
A → β1 A |
...
| αn A | ε
in order to remove the left recursion
...
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
We obtain the syntax tree by removing all the unnecessary
information from the 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
...
Left Recursion Removal and Left Factoring
Left Factoring
Left factoring is required when two or more grammar rule
choices share a common prefix 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 prefix 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 prefix 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 prefix string, as in the rule
A→αβ |αγ
Obviously, an LL(1) parser cannot distinguish between the
production choices in such a situation
...
We
must first replace assign-stmt and call-stmt by the right-hand
sides of their defining 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 → identifier := exp
call-stmt → identifier ( exp-list )
This grammar is not in a form that can be left factored
...
We
must first replace assign-stmt and call-stmt by the right-hand
sides of their defining productions:
statement → identifier := exp | identifier ( exp-list ) | other
Then we left factor to obtain:
statement → identifier 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 → identifier := exp
call-stmt → identifier ( exp-list )
This grammar is not in a form that can be left factored
...
Left Recursion Removal and Left Factoring