Re: LL vs LR, no jihad initiation, but...

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 dww@inf.fu-berlin.de
Institut fuer Informatik +49 30 89691 124
Nestorstr. 8-9
D-W-1000 Berlin 31
--

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