Re: how to eliminate this left recursion

Chris F Clark <cfc@shell01.TheWorld.com>
26 Jul 2005 13:17:52 -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: Chris F Clark <cfc@shell01.TheWorld.com>
Newsgroups: comp.compilers
Date: 26 Jul 2005 13:17:52 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 05-07-083
Keywords: parse

Mike wrote:


> I understand how to eliminate left-recursion when a grammar rule
> looks like this: a->ab | c
...
> ERE_expression : one_character_ERE
> | '^'
> | '$'
> | '(' extended_reg_exp ')'
> | ERE_expression ERE_dupl_symbol
> ;


It is of the form a -> ab | c


a : ERE_expression
b : ERE_dupl_symbol
c : one_character_ERE
                                        | '^'
                                        | '$'
                                        | '(' extended_reg_exp ')'


Now, apply the transformation as you know it...


It it were truly of the form a -> ab with no other alternative(s), then
unless b -> null, there is no solution, and if b -> null there is only
one solution a -> null.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------


Post a followup to this message

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