Re: Quick way to recognize grammar type

Chris F Clark <cfc@shell01.TheWorld.com>
4 Feb 2004 21:46:48 -0500

          From comp.compilers

Related articles
Quick way to recognize grammar type srivatsar@yahoo.com (2004-02-01)
Re: Quick way to recognize grammar type haberg@matematik.su.se (2004-02-04)
Re: Quick way to recognize grammar type joachim.durchholz@web.de (Joachim Durchholz) (2004-02-04)
Re: Quick way to recognize grammar type cfc@shell01.TheWorld.com (Chris F Clark) (2004-02-04)
Re: Quick way to recognize grammar type scavadini@ucse.edu.ar (2004-02-08)
Re: Quick way to recognize grammar type tbauer@cadrc.calpoly.edu (Tim Bauer) (2004-02-08)
| List of all articles for this month |

From: Chris F Clark <cfc@shell01.TheWorld.com>
Newsgroups: comp.compilers
Date: 4 Feb 2004 21:46:48 -0500
Organization: The World Public Access UNIX, Brookline, MA
References: 04-02-014
Keywords: parse
Posted-Date: 04 Feb 2004 21:46:48 EST

> Is there any way of determining quickly if a given grammar is one of
> LL(0)/LR(0)/LALR/LR(1)?


I'm not sure why you want this information, so this answer may not
lead you in the right direction. There are some quick checks one can
perform.


For example, if the grmamar has any left recursion, it is not LL. On
the other hand, if every rule in the grammar has a unique token at the
beginning of the rule, it is definitely LL.


Almost every LL grammar is also LR(0) and thus LALR. The exceptions
being grammars with empty rules, some of them may be LL without being
LR(0).


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
19 Bronte Way #33M voice : (508) 435-5016
Marlboro, MA 01752 USA fax : (508) 251-2347 (24 hours)


Post a followup to this message

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