|predicate parsing email@example.com (Ariel Meir Tamches) (1993-04-21)|
|Re: predicate parsing firstname.lastname@example.org (1993-04-22)|
|predicate parsing email@example.com (Stephen J Bevan) (1993-04-22)|
|Re: predicate parsing firstname.lastname@example.org (1993-04-23)|
|Re: predicate parsing email@example.com (1993-04-23)|
|Re: predicate parsing firstname.lastname@example.org (1993-04-27)|
|Re: predicate parsing email@example.com (1993-04-28)|
|predicate parsing firstname.lastname@example.org (Trevor Jenkins) (1993-04-28)|
|Re: predicate parsing email@example.com (1993-04-29)|
|Re: predicate parsing firstname.lastname@example.org (1993-04-29)|
|Re: predicate parsing email@example.com (1993-04-30)|
|From:||firstname.lastname@example.org (Kiong Beng Kee)|
|Organization:||National University of Singapore|
|Date:||Wed, 28 Apr 1993 18:43:27 GMT|
email@example.com (Simon Huntington) writes:
: What exactly are predicates? I've had a look at the *excellent* PCCTS
: which uses predicates, but I don't see how they can help very much. I'm
: trying to write a C++ parser (something simple to start with :-)), but
: predicate parsing would have to look-ahead many tokens to decipher
: ambiguities wouldn't it?
I see predicates as being used to help the parser resolve ambiguites. In
top-down parsing, it points out the path to take for rules with common
prefixes. A multi-token lookahead could be one way; semantic attributes
In bottom-up parsing, these predicates point out which reduction to take
(when there is a reduce-reduce conflict) or whether to reduce at all (when
there is a shift-reduce conflict).
Intuitively, one needs fewer and simplier(?) predicates in bottom- up
parsing because these are invoked later in the case of bottom-up parsing
when the context is better known; rather than the top-down case when it
must guide the parser.
: I wrote a backtracking LALR parser which basically recursively 'trial'
: parses (similar method to Gary Merrill, but trial parsing is specified
: with the grammar). I've managed to get it to parse almost all C++,
: including templates and exceptions, but it's pretty big (>950states). I
: also needed error repair which is why I **had** to write my own parser.
I know that firstname.lastname@example.org has a C++ parser, and I heard it is
small. However, I do not know how many states. They also incorporate the
FMQ method of error repair into the parser generation process, but I think
the FMQ method for bottom-up parsing (as in Fischer's book) is somewhat
less clever than the one for top-down parsing. Top-down parsing always
have the benefit when it comes to error-repair since the parsing context
is already on the stack. The same cannot be said for bottom-up parsing --
so I do not see how LL parsers are disadvantaged in error repair.
Kiong Beng Kee
Dept of Information Systems and Computer Science
National University of Singapore
Lower Kent Ridge Road, SINGAPORE 0511
Return to the
Search the comp.compilers archives again.