Path: utzoo!utgpu!news-server.csri.toronto.edu!clyde.concordia.ca!uunet!philmtl!atha!aunro!alberta!ubc-cs!fornax!mahajan
From: mahajan@fornax.UUCP (Sanjeev Mahajan)
Newsgroups: comp.theory
Subject: Re: Questions on BNF.
Message-ID: <436@fornax.UUCP>
Date: 16 Mar 90 22:33:56 GMT
References: <9003081854.AA28577@Neon.Stanford.EDU> <426@fornax.UUCP> <1990Mar15.171634.15800@cs.umn.edu>
Organization: School of Computing Science, SFU, Burnaby, B.C. Canada
Lines: 21

In article <1990Mar15.171634.15800@cs.umn.edu>, martin@cs.umn.edu (Johnny Martin) writes:
> 
> On p. 356 of Aho & Ullman's the theory of parsing, translation, and
> compiling: vol 1, the following two questions are stated to be
> undecidable, but no proof is given:
> 
>     a. given a grammar G, is G an LL grammar?
>        i.e., does there exist some value of k for which G is LL(k)?

>     b. if G is not LL(1) is ther an LL(1) grammar G',
>        where L(G') = L(G)?

I think Greibach's theroem should apply here. 

>    However, there is an algorithm for determining if G is LL(k) for fixed k.
This should be simple as one could construct the parsing table for the
grammar (the parsing table will depend on the lookahead k) and see if there
are any conflicts in it.


Sanjeev