Wed, 27 Jan 1993 17:42:25 GMT

Related articles |
---|

Top-Down Parser Construction Conjectures bart@cs.uoregon.edu (1993-01-18) |

Recursive descent parsing is better than LL(1) jan@klikspaan.si.hhs.nl (1993-01-22) |

Re: Recursive descent parsing is better than LL(1) tchannon@black.demon.co.uk (1993-01-23) |

Re: Recursive descent parsing is better than LL(1) pjj@cs.man.ac.uk (Pete Jinks) (1993-01-27) |

Re: Recursive descent is better than LL(1) jan@klikspaan.si.hhs.nl (1993-01-29) |

Automatic Transformation of CFG to LL/LR ramki@cs.du.edu (1993-01-29) |

Newsgroups: | comp.compilers |

From: | Pete Jinks <pjj@cs.man.ac.uk> |

Organization: | Compilers Central |

Date: | Wed, 27 Jan 1993 17:42:25 GMT |

Keywords: | LL(1), parse |

References: | 93-01-122 93-01-172 |

Barton Christopher Massey <bart@cs.uoregon.edu> writes:

*>I would like to prove or disprove the following conjectures:*

*> LL(1) Transformability: There exists an algorithm which, given any grammar G*

*> which is unambiguous and describes an LL(1) language L(G), produces an LL(1)*

*> grammar G' for the language L(G).*

*> LL(1) Decidability: There exists an algorithm which, given any grammar G*

*> which is unambiguous and describes a language L(G), decides whether L(G) is*

*> an LL(1) language.*

*>it seems most likely to me that LL1T is true, but I'm skeptical about LL1D.*

Bill Purvis <W.Purvis@daresbury.ac.uk> writes:

*>... SID... accepts a fairly arbitrary BNF description... produce an LL(1)*

*>grammar (assuming that the language is LL(1). - the first conjecture.*

*>...I suspect that in practical terms it probably covers the second conjecture.*

jan@klikspaan.si.hhs.nl writes:

*>I present a simple contra-example:*

*> S -> A | B*

*> A -> `x' A `y' | `a'*

*> B -> `x' B `z' | `b'*

*>...`SID may also report failure because*

*>its attempt to transform the grammar causes it to loop.'*

tchannon@black.demon.co.uk (Tim Channon) writes:

*>Is this a valid LL(1) solution? S = 'x' {'x'|'a'|'b'} ('y'|'z') | 'a' | 'b'.*

Jan's example causes SID problems, so SID may establish LL1T but can't

establish LL1D. I believe this is because his example is not LL(1), but

no-one has said so explicitly so far and I can't find the example in the

Dragon book - is it a well-known example?

To shorten the grammars/languages, I am using the following notation:

x^n means x repeated n times, [ab] or a|b means a or b

Thus Jan's original language is:

x^n a y^n | x^n b z^n for n>=0

Tim's version is:

x [xab]^n [yz] | a | b

which is not the same at all. Maybe he meant:

x^n [ab] [yz]^m | a | b for n,m>=1

i.e. x^n [ab] [yz]^m for n,m>=0

which is closer but still not right.

A slightly simpler example, with (I think) the same characteristics as the

original is:

x^n y^n | x^n z^n i.e. x^n ( y^n | z^n ) for n>=0

This and Jan's original are LR(1), but I believe that they are not LL(n) for

any finite n, as we have to negotiate an indefinitely long string of x-s

before we can chose whether to accept y-s or z-s, but we also have to have

been counting the x-s (i.e. selecting/stacking the "correct" non-terminal

symbol) to be able to accept the right number of y-s or z-s. By contrast:

x^n [yz]^n

and:

x^n (y^m | z^m).

are both LL(1).

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.