Re: Why LL(1) Parsers do not support left recursion?

Hans-Peter Diettrich <DrDiettrich1@aol.com>
29 Jul 2006 19:36:44 -0400

          From comp.compilers

Related articles
[24 earlier articles]
Re: Why LL(1) Parsers do not support left recursion? find@my.address.elsewhere (Matthias Blume) (2006-07-28)
Re: Why LL(1) Parsers do not support left recursion? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-07-28)
Re: Why LL(1) Parsers do not support left recursion? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-07-28)
Re: Why LL(1) Parsers do not support left recursion? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-07-28)
Re: Why LL(1) Parsers do not support left recursion? wyrmwif@tsoft.org (SM Ryan) (2006-07-29)
Re: Why LL(1) Parsers do not support left recursion? ajo@andrew.cmu.edu (Arthur J. O'Dwyer) (2006-07-29)
Re: Why LL(1) Parsers do not support left recursion? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-07-29)
Re: Why LL(1) Parsers do not support left recursion? parsersinc@earthlink.net (SLK Parsers) (2006-07-31)
Re: Why LL(1) Parsers do not support left recursion? wyrmwif@tsoft.org (SM Ryan) (2006-08-01)
Re: Why LL(1) Parsers do not support left recursion? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-08-03)
Re: Why LL(1) Parsers do not support left recursion? parsersinc@earthlink.net (SLK Parsers) (2006-08-03)
Re: Why LL(1) Parsers do not support left recursion? parsersinc@earthlink.net (SLK Parsers) (2006-08-04)
| List of all articles for this month |

From: Hans-Peter Diettrich <DrDiettrich1@aol.com>
Newsgroups: comp.compilers
Date: 29 Jul 2006 19:36:44 -0400
Organization: Compilers Central
References: 06-07-095 06-07-098
Keywords: parse, design

SM Ryan schrieb:


> If the grammar is ambiguous then you don't have a guarentee what a
> construct means. The compiler is allowed to translate your program
> into different object programs.


I agree that there should exist no ambiguities with regards to code
generation. But a programming language covers more than computational stuff.




> # How will you determine, in this special case or in general, which
> # grammars or parse trees are "correct"?
>
> This issue was solved a long time ago. Apparently the solution
> has been forgotten.


I didn't ask for a solution, but instead for the specification, that
allows to determine the "correct" procedure, parse tree, grammar, or
whatsoever.


BTW, do you have a corresponding general solution for "+++"?




> <statement> ::= <closed statement> | <open statement>
> <closed statement> ::= <assignment> | <block> | <closed if> | <closed while>
  > <open statement> ::= <open if> | <open while>


I assume that further statements typically will go into <closed
statement>. Can you give a rule, what classifies statements as open,
closed, or possibly as both? Without a general rule it will be difficult
to extend your solution, for use in a different language. I only can
guess that every statement, ending in another <statement>, has to be
split into an open and a closed form. But what about an eventual
embedded <statement>?


As already mentioned with regards to the Java grammar, I think that a
grammar with unrolled implied rules is a maintenance nightmare. How
should any new kind of statement be added correctly, if the reason and
the criteria for the splitting into open and closed statements is not
documented explicitly, but instead is only built into an existing grammar?


That's why I would prefer an explicit syntactical termination of an
if-statement, by e.g. an "endif" or "fi" terminal, over your solution.
This would IMO eliminate the dangling else problem, without the risk of
collissions with other rules, in the current or any future extended grammar.


DoDi
[Every useful programming language I know is defined with a
combination of formal and informal language. Both the C and C++
standards say that the languages are tokenized using the longest
prefix, so +++ means ++ + and any compiler that treats it otherwise
isn't a C or C++ compiler. You can have a separate argument about
whether it's a good idea to define languages that make +++ a synonym
for ++ +. -John]



Post a followup to this message

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