Re: Is there an error correcting parser generator out there?

Ronald F. Guilmette <rfg@netcom.com> wrote:
[...LL 'easier' error recovery/handling than LR?...]
>This seems to be the current `conventional wisdom' (among a lot of folks I
>know anyway), but is it really true? Where's the irrefutable evidence to
>support this view?


Good question. *I* am basing my opinions on my personal experiences in
writing, debugging, maintaining lex/flex & yacc/bison code versus using the
predicated-LL(k) tools in PCCTS. Perhaps I'm just working with languages
that skew my observations (all algol/c like languages).




[...Automated techniques are a Good Thing...]
[...Recursive descent is better?...]
>...what if they're right?? Would that imply that all that time I spent in
>school learning about LALR table generators, and all those nights I've
>spent YACC'ing things was all wasted effort?)


Automation *is* good! Using/creating the right tools for the job seems to
me to be a critical determiner of project success. I've found it to be a
big help in having had to fight with yacc for so long. I think about
parsing differently. It's wonderfully interesting to me to find that so
many of those problems are totally absent in using pred-LL(k) tools. Note
that I certainly wouldn't write any non-trivial parsing using a hand
written RD parser. ANTLR generates wonderfully fast code.






Warren Stevens writes:
[...LL 'easier' error recovery/handling over LR?...]
>Well, my compiler prof went to great lengths to tell us this was hogwash.
>His argument: once a LL parser has choosen a path, it's doomed to go along
>that path, regardless of what it may find along the way. It would be
>possible to back up a few steps, but that's not easy.


Aha! This is 'Conventional Myth #1'(tm :-) about LL parsers. Go read
Terrance Parr et al's papers about predicated-LL(k) parsing. It's
implemented and used by a good number of people in the ANTLR parser
generator that's part of the PCCTS. The use of syntactic and semantic
predicates opens up the use of LL(k) parsing to a vastly larger world.
Basically, syntactic predicates 'solve' the infinite lookahead problem and
semantic predicates allows context dependent decisions to direct the parse.






Jon Mauney writes:
[...More work to do LR error recovery/handling than LL...]


Ah, so perhaps it's not that LL error recovery/handling is any more
powerful than LR's but that it's (much) easier to do. Well, gee, I'd say
that that certainly rests *my* case. :-)




>2) LL(1) is not equivalent to recursive descent. LL parsers can
> (and should) be table-driven. Recursive descent takes the very
> simple predictions of upcoming context, and encodes it into
> the procedure call stack, which again requires code and/or
> auxiliary data to extract.


What's your argument that LL parsers should be table-driven?




Take care,
John
--

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