Re: LL(1) Questions (Re: LL vs LR, strengths and weaknesses)

bart@cs.uoregon.edu (Barton Christopher Massey) writes:
| Conjecture 1: an algorithm exists which, given any unambiguous
| (but otherwise unrestricted) grammar for an LL(1) language,
| produces in finite time an LL(1) grammar for the same language.


|I suspect that full left-factorization and left-recursion removal will
|satisfy the requirements of (1), [ ... ]


Ok, I'll give it a try:


Consider a Post Correspondence Problem {v , v , ... v } {w , w , ... w }
                                                                                  1 2 n 1 2 n
over an alphabet A.


Let the terminal alphabet T be A+{x ,x , ... x }
1 2 n


Let the non-terminal alphabet N be { 1, 2, ... n, S, U }


Consider the following production rules of a context sensitive grammar:
                      _ _
S -> i v S w for i in [1 .. n] and w represents the word w reversed
                i i


S -> U


a U a -> U for t in A


a i -> i a for a in A and i in [1 .. n]


i -> x for i in [1 .. n]
            i


This grammar generates a language L = { x x ... x } iff the embedded PCP
                                                                                  i1 i2 im
has a solution. On the other hand, if the PCP doesn't have a solution,
this grammar generates the empty language. The sentences generated by
this grammar represent the indexes needed to solve the PCP. This language
is a regular language.


Proof: consider a string of indexes x x ... x such that they form
i1 i2 im
a solution to the PCP and there is no proper prefix of this string that
is a solution to this PCP too. Call such a string a `simple' solution.
There are a finite number of `simple' solutions to a PCP. No simple
solution has another simple solution as a proper prefix (by definition.)


Name these solutions s , s , ... s
                                            1 2 m


There exists a type three grammar with the following production rules:


S -> s S | s for i in [1 .. n]
            i i


that generates all the solutions of the PCP. The language generated by
this regular grammar is the same langauge as the one generated by our
first grammar. This is clearly an LL(1) language. Because of the simple
fact that no simple solution contains another simple solution as a proper
prefix, the language and the grammar are both non-ambiguous.


Now, suppose that by sheer madness, I can find a solution to any PCP, (I'm
not a Turing Machine, so don't tell me I can't do it.) Your algorithm,
proposed in the first conjecture, on the other hand, _is_ equivalent to a
Turing Machine. Suppose, I give you the first grammar described above, and
I solemnly swear that the embedded PCP has a solution, then still, your
algorithm won't find the equivalent LL(1) grammar for every input grammar
I feed it ...


Concluding: I think the first conjecture is false too.


kind regards,


Jos aka jos@and.nl


ps. I realize that my reasoning in the last paragraph is close to the edge.
        I'm still not completely sure myself ... correct me if I'm wrong.
--

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