Re: Predicates

Sylvain Schmitz <>
4 Oct 2005 01:45:40 -0400

          From comp.compilers

Related articles
Re: Parsing Expression Grammar (Chris F Clark) (2005-09-25)
Predicates (was: Parsing Expression Grammar) (Quinn Tyler Jackson) (2005-10-02)
Re: Predicates (Sylvain Schmitz) (2005-10-04)
Re: Predicates (Chris F Clark) (2005-10-05)
Re: Predicates (Sylvain Schmitz) (2005-10-06)
| List of all articles for this month |

From: Sylvain Schmitz <>
Newsgroups: comp.compilers
Date: 4 Oct 2005 01:45:40 -0400
Organization: Compilers Central
References: 05-09-124 05-10-019
Keywords: parse
Posted-Date: 04 Oct 2005 01:45:40 EDT

Quinn Tyler Jackson wrote:
> Indeed, predicated grammars can accept a great number of fairly intricate
> programming language constructions, as seen in this paper from Okhotin:
> "On the existence of a Boolean grammar for a simple procedural language"

I would not really consider predicates on the same level as the
operators in boolean grammars: syntactic predicates are additional
run-time checks written by the user to help disambiguate a conflict. As
such, they are highly convenient and utterly dangerous, allowing more or
less arbitrary code to be run during the parsing phase, possibly
unrelated to the language at hand and possibly introducing an
exponential overhead. Basically, you have to trust the grammar writer
for not doing anything harmful.

      Boolean grammars on the other hand integrate the additional
conjunction and negation operations with clear language semantics; I'm
not sure the difference in philosophy is sensible here, but it is rather
huge: the operations are really part of the grammar, and not ad hoc rules.

> I suppose one might be able to show a direct relation of the implied
> predication of the ordering in PEGs and the explicit predicates found in
> both formalisms, and this suspicion leads me to believe that one way to
> address language equivalency with PEGs is not to examine their relation to
> the CFLs, but to the conjunctive/Boolean languages, and work from there.

That seems the best hope one would have to express what exactly is the
language of A / B given the language of A and that of B. It still seems
very difficult. (The formula I expressed earlier in this thread was
completely false.) Its definition involves the remaining "unmatched"
input, and I don't really see how to get rid of it.
      In his "Boolean Grammars" paper, Okhotin presents a grammar for {
a^(2^n) | n >= 0 } (on page 23), which bears little resemblance with



Post a followup to this message

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