RE: Some questions about recursive descent

I'll start with the most important response first.


It should definitely be possible to return the generated syntax tree
from a procedure implementing a parser rule (for a non-terminal) in a
recursive descent compiler. In fact, it surprises me that you say
that's not the normal case. It's *almost* the definition of recursive
descent. One calls the function implementing some non-terminal and
the non-terminal consumes its input, building internally a
representation of that input (as a single structure, i.e. an AST node)
and returns that structure to the caller, so that the caller can do
the same. Each call makes a new rooted tree (that identifies what
kind of tree it is, i.e. what non-terminal it represents) and it is
used by the caller as part of the larger tree containing it. Now, I
supposed it *could* make sense not to make that the return value for
the function implementing the non-terminal, but it certainly is a
natural value to return. More on that after I talk about tables.


It is possible to implement LL (as was as LR and precedence and other)
parsers as parser tables. Recursive descent doesn't generally do so.
It implements that parser as code, specifically nested function calls,
with some (generally, but not necessarily) small amount of logic to
determine which variant (alternative) of a non-terminal is being
processed. This logic is what uses the result of the first (and
follow) functions to determine based upon the initial tokens which
alternative matches the input. This is generally done without parsing
tables. Using parsing tables generally suggests you are implementing
a different parsing methodology than recursive descent, even if you
are doing so only as a subroutine within a recursive descent parser.
The parts not using the tables are the recursive descent part. The
part using the table is an embedded parsing technology within an
otherwise recursive descent framework.


Ok, back to the question of what a recursive descent parser's routine
implementing the parsing of a non-terminal should be. In an
Object-oriented world, it would be reasonable for it to return an
"object" representing the non-terminal, with methods/member functions
that get you the sub-parts, evaluate attributes, etc. Another
reasonable return value, comes from the Rust world, it could be a
"result type", where it is either the non-terminal as discussed
before, or an error. (Result<NonTerminal, Error>). However, in the
non-error case, you generally want each parsing rule to return the
root non-terminal of the AST is parsed.


--
******************************************************************************
Chris Clark email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. Web Site: http://world.std.com/~compres
23 Bailey Rd voice: (508) 435-5016
Berlin, MA 01503 USA twitter: @intel_chris
------------------------------------------------------------------------------

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