Re: predicate parsing

isckbk@nuscc.nus.sg (Kiong Beng Kee)
Wed, 28 Apr 1993 18:43:27 GMT

          From comp.compilers

Related articles
predicate parsing tamches@wam.umd.edu (Ariel Meir Tamches) (1993-04-21)
Re: predicate parsing dave@cs.arizona.edu (1993-04-22)
predicate parsing bevan@computer-science.manchester.ac.uk (Stephen J Bevan) (1993-04-22)
Re: predicate parsing isckbk@nuscc.nus.sg (1993-04-23)
Re: predicate parsing simonh@swidev.demon.co.uk (1993-04-23)
Re: predicate parsing mauney@csljon.csl.ncsu.edu (1993-04-27)
Re: predicate parsing isckbk@nuscc.nus.sg (1993-04-28)
predicate parsing tfj@apusapus.demon.co.uk (Trevor Jenkins) (1993-04-28)
Re: predicate parsing mauney@csljon.csl.ncsu.edu (1993-04-29)
Re: predicate parsing andrewd@winnie.cs.adelaide.edu.au (1993-04-29)
Re: predicate parsing jourdan@minos.inria.fr (1993-04-30)
| List of all articles for this month |

Newsgroups: comp.compilers
From: isckbk@nuscc.nus.sg (Kiong Beng Kee)
Keywords: parse
Organization: National University of Singapore
References: 93-04-099
Date: Wed, 28 Apr 1993 18:43:27 GMT

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
--


Post a followup to this message

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