Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!world!iecc!compilers-sender
From: shite@sinkhole.unf.edu (Stephen Hite)
Newsgroups: comp.compilers
Subject: Top-down recursive descent parsers
Keywords: parse, LL(1)
Message-ID: <9012121639.AA27769@unf7>
Date: 12 Dec 90 16:39:43 GMT
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: shite@sinkhole.unf.edu (Stephen Hite)
Organization: Compilers Central
Lines: 42
Approved: compilers@iecc.cambridge.ma.us

Which top-down recursive descent parsing method is faster?

    1. Creating FIRST and FOLLOW sets of the grammar and then building
       a predictive parsing table (sec 4.4 of the "Red Dragon book").  Well,
       this is nonrecursive predictive parsing but "we" are handling the
       recursion via a stack in our program instead of the "machine"
       keeping track of the recursive function calls.  My assumption is
       that a separate program has built the table or it was done by
       hand so all of this work has been done before the parser is
       executed.

    2. Recursive function calls (i.e. sec 2.5 of the "Red Dragon book").

Assumption in both cases is that the grammar does not have any
left-recursive productions and it has been left-factored.

For a compiler project, it would seem to me that (1) would be easier
to program for error recovery and producing accurate error messages.
However, I suspect the table lookups would slow it down over (2).
  
I have not seen a discussion in a compiler book that addresses this.
Although (2) may be faster than (1) is it that big of a difference?  
Would (2) be a bad choice for a commercial compiler if speed were
a high priority?

All of the top-down parsers I've seen of the PD C compilers available
use method (2).  I have no idea if their respective authors even 
thought of using method (1).

-----------------------------
Steve Hite
shite@sinkhole.unf.edu
...gatech!uflorida!unf7!shite

[The relative performance has a lot to do with the speed of a procedure call.
They're usually pretty slow, so a non-recursive approach wins.  The reason
people write recursive procedures is that they don't have a table builder and
building the table by hand is tedious and hard to get right.  Those of us
with table builders are likely to use an LALR parser. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.