martin@cs.umn.edu (Johnny Martin) (03/16/90)
In article <431@fornax.UUCP> mahajan@fornax.UUCP (Sanjeev Mahajan) writes: >In article <1990Mar14.001730.20147@cs.umn.edu>, martin@cs.umn.edu (Johnny Martin) writes: >> >> I am working on a similar problem, minimizing grammars for a given >> language. The problem is: you can't use Greibach's theorem for >> classes of grammars, it only works for classes of languages. So I >> don't think approach is going to work. What we really need is a >> undecidability theorem for grammars. >> > >No, Greibach's theorem does work as stated (that is, if LL and LR languages >are closed under quotient with one symbol). Infact on the same page >as the theorem is proved in Hopcroft and Ullmann, it is proved >(using the theorem) that if G is an arbitrary CFG, then it is undecidable >if L(G) is regular. > > >Sanjeev Yes, you're right. Thanks for pointing out my error. Grammar .vs. language: it doesn't matter. Anyway, back to the original question: >> 3. Given a BNF grammar for a language can one (automatically) determine >> whether it is (a) LL, (b) LR. 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)? However, there is an algorithm for determining if G is LL(k) for fixed k. On pp.556-7 of Harrison's introduction to formal langauge theory, a. L is a DCFL iff L is LR(k) for some k>=0 b. it is udecidable whether a CFG G is a DCFL or whether G is LR(k) for some k. -- Johnny Martin, Dept. of Computer Science, University of Minnesota, Minneapolis martin@umn-cs.cs.umn.edu --
mahajan@fornax.UUCP (Sanjeev Mahajan) (03/17/90)
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