Predicates (was: Parsing Expression Grammar)

Chris F Clark said:


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


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"


Found here:


http://www.cs.queensu.ca/home/okhotin/boolean/


Except for the behavior of the conjunction operators | and /, conjunctive
grammars and PEGs are pretty much one and the same, formally.


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.


Now, it could be shown that there exists no algorithm for detecting such
cases as the P <- x P x / x situation noted in other posts, since x can be
replaced with any arbitrary production X, and the crux of finding such cases
would rest in proving that the LHS and RHS expressions of P accept the same
language, where that language might be a CSL. I haven't given this too much
formal thought, and so I freely admit I could be speaking out the top of my
head.


That is to say, one could easily say that P <- X P X / X is not acceptable
(or potentially misleading), but what of P <- X P Y / Z where X, Y, and Z
generate the same strings?


--
Quinn


http://members.shaw.ca/qtj/

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