Re: best grammar for handling optional symbols?

On minor point is response to what Max Hailperin <max@gustavus.edu>
writes:


> 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 did a Google search looking for permutation grammars but didn't find
anything on the first page, although the link to Royal Holloway seemed
promising, as Adrian Johnstone and Elizabeth Scott could easily be
interested in such an extension.


Note, if someone find this paper, it would be nice to see the
reference posted here. I wouldn't mind reading that paper again.


Hope this helps,
-Chris


******************************************************************************
Chris Clark Internet: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. or: compres@world.std.com
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)

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