Re: how to eliminate this left recursion

"Oliver Wong" <owong@castortech.com>
26 Jul 2005 13:21:57 -0400

          From comp.compilers

Related articles
how to eliminate this left recursion hammeron56@yahoo.com (Mike) (2005-07-22)
Re: how to eliminate this left recursion codeworker@free.fr (=?iso-8859-1?q?C=E9dric_LEMAIRE?=) (2005-07-26)
Re: how to eliminate this left recursion cfc@shell01.TheWorld.com (Chris F Clark) (2005-07-26)
Re: how to eliminate this left recursion owong@castortech.com (Oliver Wong) (2005-07-26)
| List of all articles for this month |

From: "Oliver Wong" <owong@castortech.com>
Newsgroups: comp.compilers
Date: 26 Jul 2005 13:21:57 -0400
Organization: GlobeTrotter
References: 05-07-083
Keywords: parse

"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


Post a followup to this message

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