Re: predicate parsing (Kiong Beng Kee)
Wed, 28 Apr 1993 18:43:27 GMT

          From comp.compilers

Related articles
predicate parsing (Ariel Meir Tamches) (1993-04-21)
Re: predicate parsing (1993-04-22)
predicate parsing (Stephen J Bevan) (1993-04-22)
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: (Kiong Beng Kee)
Keywords: parse
Organization: National University of Singapore
References: 93-04-099
Date: Wed, 28 Apr 1993 18:43:27 GMT (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 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

Post a followup to this message

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