Sun, 17 May 1992 14:27:21 GMT

Related articles |
---|

LL vs LR, no jihad initiation, but... parrt@ecn.purdue.edu (1992-05-11) |

LL(1) Questions (Re: LL vs LR, strengths and weaknesses) bart@cs.uoregon.edu (1992-05-15) |

Re: LL(1) Questions (Re: LL vs LR, strengths and weaknesses) jos@and.nl (1992-05-17) |

Newsgroups: | comp.compilers |

From: | jos@and.nl (Jos Horsmeier) |

Keywords: | LL(1) |

Organization: | AND Software BV Rotterdam |

References: | 92-05-059 92-05-094 |

Date: | Sun, 17 May 1992 14:27:21 GMT |

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.

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.