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

Sylvain Schmitz <schmitz@i3s.unice.fr>
5 Dec 2004 21:34:32 -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: Sylvain Schmitz <schmitz@i3s.unice.fr>
Newsgroups: comp.compilers
Date: 5 Dec 2004 21:34:32 -0500
Organization: Compilers Central
References: 04-11-113
Keywords: LR(1), parse
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 [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

Post a followup to this message

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