|
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.
(left-most) derivations | |
| Exp | <end> |
1 | Exp | + | Term |
2 | Term |
3 | Term | * | Factor |
4 | Factor |
5 | w |
6 | x |
7 | Term | * | Factor |
8 | Factor |
9 | y |
10 | z |
sentence: | w |
* |
x |
+ |
y |
* |
z |
<end> |
Parse tree
-
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.
-- 2002 LA, CSSE, Monash
|
key |
::= |
"can be replaced by" |
-> |
| | "or by" |
=> | derivation |
lm |
left most |
rm |
right most |
|
|