|How to check if grammar is LR(k) email@example.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) firstname.lastname@example.org (Sylvain Schmitz) (2004-12-05)|
|From:||Sylvain Schmitz <email@example.com>|
|Date:||5 Dec 2004 21:34:32 -0500|
|Posted-Date:||05 Dec 2004 21:34:32 EST|
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  was already describing a way to test
whether a grammar was LR(k) for a given k. A paper by Hunt, Szymanski
and Ullman  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 .
You might also want to check chapter 10 of the book  written by
Sippu and Soisalon-Soininen to get a general (and hopefully clearer)
view of the issue.
 On the Translation of Languages from Left to Right, Information and
Control 8: 607--639, 1965
 On the Complexity of LR(k) Testing, Communications of the ACM, vol
18, no 12, pp 707--716, dec 1975
 The Complexity of LALR(k) Testing, JACM, vol 30, no 2, pp 259--270,
 Parsing Theory, vol 2, Springer Verlag, 1990, isbn:0-387-51732-4
Hope that helps,
Return to the
Search the comp.compilers archives again.