Some questions about recursive descent?

Dear comp.compilers,


I am currently reading two compiler books, [Holub] and [Appel], and
then [Salomon] for a bit of context below,


      [Holub] Compiler Design in C, 1990, by Allen Holub


      [Appel] Modern Compiler Implementation in ML, 2004, by Andrew Appel


      [Salomon] Assemblers and Loaders, 1993, David Salomon


and I have some questions about the construction of recursive descent
parsers. If some of my questions are adequately answered in some other
publication, reference, preferably with chapter and verse, is welcome.


The reason for my questions is that I know production compilers /use/
recursive descent. GCC is probably the most famous example, but Watcom
does it too. More below as well.


My first question is: how are production recursive descent parsers con-
structed? From these two books, and other things I have read in the
past, recursive descent is so simple it's mostly just brushed off with
an example or two, but there seems to be a whole lot more to it. For
instance, [Appel] mentions a parse table but mostly does not explain how
to construct one. The rest of the book seems to be focused on ML-lex
and ML-yacc, which I haven't read yet.
          I have read more of [Holub] and he explains the theory much better,
in fact this seems to be the best theory introduction I remember coming
across ever. Yet, that book also does not spend too much effort on rec-
ursive descent, and goes on about implementing and using lex and yacc
like tools.
          [Holub] explains the construction/algorithms for FIRST and FOLLOW
sets better than [Appel], in my opinion, but I do not recall any more
details about said parse table, which seems instrumental in the con-
struction of the final recursive descent. [Holub] does mention Q
grammars, and how they are very easy to turn into recursive descent.


Second question: why are recursive descent parsers I've come across
always using globals and construct code and/or the parse tree as side
effects, rather than, say, return the parse tree to the caller?
          Is this something to do with /synthesized attributes/ that [Holub]
talks about? Where the recursive descent parser routines return values
to the caller, or is this maybe just a tradition that no one bothers to
change?


Now, to give these questions a bit of context, as a practice, I wanted
to create a recursive descent parser for the first programming exercise
in [Salomon] but found out the hard way that it's not so trivial to
figure out /how/.
          My first methods were somewhat ad-hoc to create and modify the
grammar to be non-left-recursive, which I think was mostly easy due to
the assembler being very bare bones, and hence the grammar can be very
simple. Then I ran into trouble when I tried to make the parser return
the parse tree, rather than construct it with side effects.
          Granted, some of my problems are from using a programming language,
ML, that I'm not familiar with, which I decided to use for another
wrinkle in the exercise. If the project is too easy, it just isn't
/fun/.
          The first wrinkle I stumbled upon, when I started to read up on the
subject, is that constructing the parse table, as a preliminary step,
isn't really explained in [Appel] -- at least not to my satisfaction --
and I found not much better coverage of the subject in [Holub] though
certain topics are covered better.
          In the past, when I've stumbled like this, reading up on the subject
has helped a lot, but so far, almost everything I've read seems inade-
quate in different ways.


Side thought: do any of the mentioned authors read this list?


Thanks,
--
Johann | email: invalid -> com | www.myrkraverk.com/blog/
I'm not from the Internet, I just work there. | twitter: @myrkraverk

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