Re: Parsing techniques

In response to Lex Augusteijn (lex@prl.philips.nl, no relation to
yacc@prl.philips.nl) who posted an illuminating discussion on recursive
assent parsing:


First, Lex introduces recursive ascent parsing issues into a discussion of
LL vs. LR in a somewhat peculiar fashion implying that it forms a bridge
between the two. In fact, this is somewhat of a misrepresentation based on
a mixing of two issues: recognition and implementation. In terms of
recognition, there are important differences between LL and LR that rise
above the question of whether each is implemented as a stack automation or
as set of recursive functions. In particular, the recursive functions
implementing the LL parser are equivalent in every informational way to a
set of recursive descent functions. Similarly for LR parsing.


(Mind you, I'm not criticizing the body of the post, merely its method of
introduction.)


However, every other point that Lex made is accurate. Recursive ascent
functions, like their recursive descent cousins, can be annotated with
additional parameters but then these are merely another form of
L-attributes. Recursive ascent will allow better support for error
handling but only if such support is not otherwise provided by the parser
generator.


    Although this technique was first regarded as
    an alternative implementation for a stack automaton, it was later on
    recognized that the stack automaton is merely a low level implementation
    of recursion, where one makes the recursion stack explicit and numbers
    all possible recursive calls to allow their encoding by means of a stack
    automaton.


The real difference between recursive a/descent parsing and stack
automation parsing lies in this difference, however it is stated.
Generally, though stack automation implementations result is smaller code
but recursive a/descent parsers usually run faster. This is why Penello
chose to implement his in assembly, to out squeeze every possible
millisecond of speed that he could.


I am, though, totally unconvinced that recursive ascent parsers exhibit
the naturalness and simplicity that recursive descent parsers do. Anybody
can write a recursive descent parser by hand. I challenge anybody to do
this for recursive ascent.


>When people are interested, I can summarize the theory behind recursive
>ascent parsers to the net.


This would, I think, be worthwhile.


>Our Elegant compiler generator generates recursive descent parsers for
>LL(1) grammars and recursive ascent parsers for LALR(1) grammars, both
>using essentially the same satisfying error recovery mechanism based on
>adding follower set arguments to the parse functions.


How does this compare to the automatic error handling methods for LR such
as that described by Fischer and LeBlanc? Our experience is that such
automatic error handling is very satisfying, indeed.


Our compiler toolikt, LADE is implemented the "old-fashioned" way. Its
automatic error-recovery is remarkably successful and it is hard to see
what advantage could be gained by converting to recursive ascent parsing.


--

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