# Re: How to check if grammar is LR(k)

## Chris F Clark <cfc@shell01.TheWorld.com>1 Dec 2004 23:14:57 -0500

From comp.compilers

Related articles
How to check if grammar is LR(k) hhsaffar@gmail.com (2004-11-28)
Re: How to check if grammar is LR(k) cfc@shell01.TheWorld.com (Chris F Clark) (2004-12-01)
Re: How to check if grammar is LR(k) schmitz@i3s.unice.fr (Sylvain Schmitz) (2004-12-05)
| List of all articles for this month |

 From: Chris F Clark Newsgroups: comp.compilers Date: 1 Dec 2004 23:14:57 -0500 Organization: The World Public Access UNIX, Brookline, MA References: 04-11-113 Keywords: parse, LR(1) Posted-Date: 01 Dec 2004 23:14:57 EST

> Is it possible to find out if a grammar is LR(k) or not without making
> the parsing table?

1) There are some sets of grammars which are known to be LR(k). For
example, if all the recursion in the grammar is either left or
right (but not a mixture of some left and some right)--the grammar
is linear and all linear grammars are LR(k). Similarly, if the
grammar is known to be LL(k), the grammar is known to be LR(k), but
not necessarily SLR(k) or LALR(k).

2) Likewise, there are some things know to make a grammar inherently
not LR(k), ambiguity is one of them. Thus, the inclusion of a rule
like "A: A A ; /* A being a non-terminal */" is ambiguous and means
any grammar with the rule used in it is not LR(k).

3) There is an algebra promoted by Mark William Hopkins (sp?) that
purports to solve the LR problem, but produces results that have
always struck me as supiciously contradictory of other facts I know
of grammar theory. However, perhaps I just don't understand.

4) Making a parser table is easy (well, perhaps not by hand for a
non-trivial grammar, but quite easy once mechanized).

-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