Re: LL vs LR, no jihad initiation, but...
Tue, 12 May 1992 12:39:55 GMT

          From comp.compilers

Related articles
LL vs LR, no jihad initiation, but... (1992-05-11)
Re: LL vs LR, no jihad initiation, but... (1992-05-12)
Re: LL vs LR, strengths and weaknesses (1992-05-13)
| List of all articles for this month |

Newsgroups: comp.compilers
Keywords: LL(1), LR(1), parse
Organization: Free University of Berlin
References: 92-05-059
Date: Tue, 12 May 1992 12:39:55 GMT

Perhaps I've missed something, but it would seem to me that LL parsers
need a lot of memory for all the pending production procedure calls, i.e
you can't reduce <prog> ::= <decl> <stmts> until the very last token has
been read in. You would normally have as many pending calls as the depth
of the parse tree at the moment. This could be a problem for some systems.

An then there would be the if-then-else problem. If you have a grammar like
      stmt --> ifstmt | otherstmts
      ifstmt --> 'if' expr 'then' stmt elsepart
      elsepart --> \epsilon | 'else' statement

you have the ambiguity in parsing a statement like

      if e1 then if b2 then s1 else s2

not knowing if the else should go with the inner if or the outer one.

You can transform the grammar, keeping it context-free of course, but the
transformed grammar that pairs an else with the innermost if is not LL(k)
for any k (says John Gough in "Syntax Analysis and Software Tools").
However, using explicit delimiters (hooray!) like end or fi nicely avoids
this problem.
Debora Weber-Wulff
Institut fuer Informatik +49 30 89691 124
Nestorstr. 8-9
D-W-1000 Berlin 31

Post a followup to this message

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