Compilers - How to check if grammar is LR(k)

Author

How to check if grammar is LR(k)

Hossein Saffar

2004-11-29, 4:10 pm

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

Thanks

Hossien
[I don't think so. -John]

Chris F Clark

2004-12-02, 3:57 am

Hossein Saffar asked:
> 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).

Why do you ask?
-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)

Sylvain Schmitz

2004-12-07, 4:21 am

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

Knuth's original paper [1] was already describing a way to test
whether a grammar was LR(k) for a given k. A paper by Hunt, Szymanski
and Ullman [2] further investigated this problem.

In case you are also interested in LALR(k) testing, there is yet
another paper by Sippu, Soisalon-Soininen and Ukkonen about it [3].

You might also want to check chapter 10 of the book [4] written by
Sippu and Soisalon-Soininen to get a general (and hopefully clearer)
view of the issue.

[1] On the Translation of Languages from Left to Right, Information and
Control 8: 607--639, 1965
[2] On the Complexity of LR(k) Testing, Communications of the ACM, vol
18, no 12, pp 707--716, dec 1975
[3] The Complexity of LALR(k) Testing, JACM, vol 30, no 2, pp 259--270,
apr 1983
[4] Parsing Theory, vol 2, Springer Verlag, 1990, isbn:0-387-51732-4

--
Hope that helps,

Sylvain

Sponsored Links