Re: Parsing Expression Grammar

I replied to George Neuner:
c>I think predicates are wonderful. I don't know that predicates
c>"require" mid-rule computations. Syntactic ones don't. Semantic
c>predicates "are" mid-rule computations, so yes they require them.


George Neuner <gneuner2@comcast.net> replied back:
g> That depends on your definitions ... syntactic predicates are extra
g> grammatic computation - meaning they are (generally) nicety rather
g> than necessity. Offhand I can't think of a case of a grammar that
g> could be written using a syntactic predicate but not without.


Syntactic predicates are far more than a nicety. There are two well
studied cases that one can parse with predicated grammars that one
can't (deterministically) parse with unpredicated ones: palindromes
{ w w**reverse } and multi-part matching { a**i b**i c**i }. Now,
perhaps those cases are mostly of theoretical importance.


However, syntactic predicates can also be used to resolve conflicts
(and ambiguities), which are a quite practical concern for compiler
writers. For example, If one has a context sensitive special case,
one can usually code the special case and the context up as a
predicate which is then used to parse only the special case part.
that way you tell the parser generator how much context and lookahead
to use to idetify the special case and make the parser generator's job
easier.


Moreover, predicates imply an ordering of the parsing space (just as
parsing expression grammars do), so that one can be certain that the
special case takes precedence over incidental matches with other
sequences. The advantage of predicates is that they apply this
ordering only in limited contexts, so that one knows eactly which
clauses to be careful with and not globally over the entire grammar.


My rule of thumb to Yacc++ users is first write your grammar without
any predicates or precedence rules. Then, look at the conflict
reports, and determine for each of the conflicts how you want the
problem resolved, and from that use either predicates or precedence
directives to guide the generator to parse those conflict situations
the way you want.


By the way, the C++ rule, of if it looks like a declaration it is, and
otherwise it is a statement can only be handled with a syntactic
predicate.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

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