Re: Predicates

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
P<-xPx/xx.


--
Regards,


      Sylvain

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