Re: predicate parsing

simonh@swidev.demon.co.uk (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
is another.


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 xorian@solomon.technet.sg 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 comp.compilers page.
Search the comp.compilers archives again.