RE: best grammar for handling optional symbols?

"Quinn Tyler Jackson" <>
Tue, 19 Aug 2008 22:17:14 -0700

          From comp.compilers

Related articles
Re: best grammar for handling optional symbols? (Chris F Clark) (2008-08-19)
RE: best grammar for handling optional symbols? (Quinn Tyler Jackson) (2008-08-19)
| List of all articles for this month |

From: "Quinn Tyler Jackson" <>
Newsgroups: comp.compilers
Date: Tue, 19 Aug 2008 22:17:14 -0700
Organization: Compilers Central
References: 08-08-035
Keywords: parse
Posted-Date: 20 Aug 2008 13:59:55 EDT

> > But nothing like that is possible if the order is variable. In that
> > case, even if you are writing for humans, your best bet is to escape
> > from the BNF or EBNF into some more general means of communication --
> > which for a human, might well be a natural-language explanation.
> That's not completely true. I distinctly recall reading a paper where
> the author introduced an EBNF notation for generating permuations,
> which is exactly what this problem calls for. Now, permutations don't
> have trivial tranformations into BNF, in the sense that to describe
> permutations in BNF one must list each of the alternatives and that
> grows quite rapidly as the number of symbols to be permuted increases.
> However, it is quite feasible to generate code that recognizes
> permutations, and thus adding an operator that does such to one's EBNF
> is reasonable to my mind. Others may object that EBNF should be
> restricted to allowing only things expressible as regular expressions
> on the right-hand-side. However, as I remember the notation, it was
> restricted to combining fixed lists of symbols, so it technically was
> a regular expression, just not a traditional one.

I believe the reference Chris is referring to is:

[Cameron 1993] Robert D. Cameron, "Extending Context-Free Grammars with
Permutation Phrases," LOPLAS, Vol. 2 No. 1-4, pp. 85-94, 1993.

Meta-S grammars have both strict and relaxed permutation phrases.

S ::= <<A B C>>;
A ::= "amor";
B ::= "vincit";
C ::= "omnia";

Ignoring whitespace rules, the above would match any permutation of "amor
vincit omnia". A, B, and C must all generate strings, once and only once,
and must not generate the empty string, but the order of A, B, and C is

S ::= <<{A B C}>>; // the { } syntax means that one of the terms can
generate lambda
A ::= "amor";
B ::= "vincit";
C ::= ["omnia"];

In the above, C is optional. So, the grammar can generate "vincit amor" (for

Several other grammar formalisms have allowed for permutation phrases, as
well. I am not certain if they allow for both the lambda-generating and
non-lambda stricter form.


Quinn Tyler Jackson

Post a followup to this message

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