Re: how to eliminate this left recursion

"Mike" <hammeron56@yahoo.com> wrote in message


> I understand how to eliminate left-recursion when a grammar rule
> looks like this: a->ab | c
>
> but how do you do it when it looks only like this: a->ab


If the expansion of "a" is "ab" with no other alternative, then you have an
infinite recursion that you can never get out of.


> Such a grammar rule exists in the following regular expressions grammar
> (see rule ERE_expression)
[snip]
> ERE_expression : one_character_ERE
> | '^'
> | '$'
> | '(' extended_reg_exp ')'
> | ERE_expression ERE_dupl_symbol
> ;
[snip]


Seems to me, this could be rewritten as:


ERE_expression : ( one_character_ERE
                                          | '^'
                                          | '$'
                                          | '(' extended_reg_exp ')'
                                          )
                                          ( ERE_dupl_symbol )*;


- Oliver

Return to the comp.compilers page.
Search the comp.compilers archives again.