Re: Application of Conjunctive Grammars?

Mony Hall asked:
> I'm reading about conjunctive grammars and was curious where they are
> used. What feature of a programming language would require the use of
> a conjunctive grammar?


Thank you for an excellent question. I hadn't read about conjunctive
grammars before and as a result of your question read Okhotin's
introductory paper on them.


Having read that, I can tell you that conjunctive grammars (and their
extension to boolean grammars) are equivalent to syntactic predicates.
There are some slight differences in interpretation, but fundamentally
the principles are the same. The key difference between syntactic
predicates and conjunctive grammars is that predicates also establish
an ordering between alternatives and use that ordering to pick a
unique parse tree in cases where the gramar would be ambiguous without
the predicates. It is possible to reformulate a predicated grammar as
an unambiguous boolean grammar (you need the not operator to resolve
ambiguities for some cases)--if you don't care about ambiguity, you
can change a predicated grammar into a potentially ambiguous
conjunctive grammars.


The predicated grammar:


nterm : predicate >> parse-as
            | parse-otherwise
            ;


                This grammar is read as "if at the point of parsing an nterm,
                one can match predicate, then nterm is defined as parse-as.
                otherwise, nterm is defined as parse-otherwise."


The equivalent (but possibly ambiguous) conjunctive grammar:
                (assuming that predicate is shorter than parse-as)


nterm: predicate sigma* & parse-as
          | parse-otherwise
          ;


The equivalent unambiguous boolean grammar:


nterm: predicate sigma* & parse-as
          | ~(predicate sigma*) & parse-otherwise
          ;


There are two places where predicates help parse programming
languages. One could use conjunctive or boolean grammars to do the
same, given the above transformation.


The first place predicates can help is in the parsing of C++ (style
ambiguities). In the C++ grammar given in the standard, declarations
and expressions are ambiguous. The standard resolves this ambiguity
by saying if the input can be parsed as a declaration, it is a
declaration (even if it could also be parsed as an expression). This
ambiguity can be resolved by the following rule.


statement: decl ";"
                  | ~(decl (~";")* ";") & expr ";"
                  ;


The second place predicates are used to ease parsing problems is to
disambiguate rules where the parsing method isn't strong enough by
itself. For example, if one has a grammar with some LR(2) rules, but
a predicated LR(1) parser generator, one can work around the LR(2)
parts of the grammar with predicates. One could call this "lookahead
disambiguation".


func-name: ident "(" >> ident; // idents followed by parens are function names


Note, this is a little harder to do with conjunctive grammars, because
the predicate is longer than the alternative it is guarding, and
conjunctive grammars don't allow that (the two parts must be of
identical length). That restriction, probably renders conjunctive
grammars useless for lookahead diambiguation. However, the other
aspect of conjunctive grammars is that there are associated
implementation techniques. It is likely that those implementation
techniques could be helpful in implementing predicated grammars also,
since there is such a close correspondence, and since predicated
grammars can be used for lookahead disambiguation, the implementation
techniques would still be useable to practitioners.


Hopefully, now that I have said, all that I'm aware of on this topic,
Quinn Tyler Jackson will chime in, since I think his meta-S work is
closely related to these grammars and he has been studying which
problems predicates (and other grammar extensions) resolve.


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.