avoiding left recursion in a grammar with the production S->€
- From: xareon@xxxxxxxxx
- Date: 17 Apr 2007 12:07:01 -0700
hi all men, i'm back here to ask you a question. let G be a left-
recursive context-free grammar where i eliminated the unit and epsilon
productions, maintaining S->€ because € belongs to the language
generated by G. if i eliminate the left recursive production, i can't
avoid the unit productions getting back.
let's made a simple example, to avoid left recursion i have to
consider all the productions for a given nonterminal S for which there
is at least a left recursive production. let S -> Sa1 | Sa2 | ... |
San the left recursive productions for S, and let S -> b1 | b2 | ... |
bm be the non left-recursive prodcutions for A. Then, i should add a
new nonterminal B, and replace the productions for A with these
productions:
S-> b1 | ... | bn
S-> b1B | ... | bnB
B -> a1 | ... | an
B -> a1B | ... | anB
that is ok if i don't have the production S->€, because if i have it,
then i'll get the unit production S->B back. how can i avoid this? re-
eliminating unit productions could be useless, because i could get
again left recursive productions if the grammar is *also* indirectly
left recursive, like:
S -> Ab | SAb | €
A -> Sa | ASa | a
how can i solve this problem?
thank you
regards, Stefano
.
- Prev by Date: Re: Multidimensional binary search trees
- Next by Date: Re: more again: the complexity of Hamiltonian problem on 2-regular digraph
- Previous by thread: Multidimensional binary search trees
- Next by thread: Languages are regualar
- Index(es):