Re: Application of Conjunctive Grammars?

Chris F Clark <>
14 Sep 2004 16:58:04 -0400

          From comp.compilers

Related articles
Application of Conjunctive Grammars? (Monty Hall) (2004-09-13)
Re: Application of Conjunctive Grammars? (Chris F Clark) (2004-09-14)
Re: Application of Conjunctive Grammars? (Sylvain Schmitz) (2004-09-14)
| List of all articles for this month |

From: Chris F Clark <>
Newsgroups: comp.compilers
Date: 14 Sep 2004 16:58:04 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 04-09-085
Keywords: parse
Posted-Date: 14 Sep 2004 16:58:04 EDT

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

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 Clark Internet :
Compiler Resources, Inc. Web Site :
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

Post a followup to this message

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