RE: best grammar for handling optional symbols?

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


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


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.


Cheers,


--
Quinn Tyler Jackson

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