Re: predicate parsing (Andrew Dunstan,,2285592,)
Thu, 29 Apr 1993 12:37:13 GMT

          From comp.compilers

Related articles
[3 earlier articles]
Re: predicate parsing (1993-04-23)
Re: predicate parsing (1993-04-23)
Re: predicate parsing (1993-04-27)
Re: predicate parsing (1993-04-28)
predicate parsing (Trevor Jenkins) (1993-04-28)
Re: predicate parsing (1993-04-29)
Re: predicate parsing (1993-04-29)
Re: predicate parsing (1993-04-30)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Andrew Dunstan,,2285592,)
Keywords: parse, performance
Organization: The University of Adelaide
References: 93-04-101
Date: Thu, 29 Apr 1993 12:37:13 GMT

> A) LL parsers can be as fast as anything else.

This is an understatement. Other things being equal, they are faster than
bottom-up parsers. (See Fischer & LeBlanc for an analysis.)

> 2) LL Parsers are to be *preferred* when repair is an issue.
> The simple structure of the data on the stacks makes life
> much easier.

Right, again, but for the wrong reason. Intuitively, LL parsers provide
better error recovery possibilities because they are predictive, i.e. you
know where you are going, whereas in L??R parsers, you don't always know
for sure where you are going till you've got there. The power of this
parsing method comes precisely from the ability to delay this decision.

[III is how to deal with ambiguities in C++]

Let's go back to the start of this thread. Using predicates in parsing,
either predictive or not, can add to the power of the parsing method.
Perhaps more importantly, they can reduce the extent to which the grammar
must be massaged in order to fit the parsing method. This is significant
in difficult grammars such as C++ and Ada.

At the GNAT project at NYU (which will produce GNU Ada), Robert Dewar is,
as I understand it, using a recursive descent parser with backtracking,
written in Ada83, with excellent recovery characteristics and blindingly
fast. So these methods are not just of "academic" interest.
# Andrew Dunstan
# net:
# or:

Post a followup to this message

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