Tue, 19 Aug 2008 22:17:14 -0700

Related articles |
---|

Re: best grammar for handling optional symbols? cfc@shell01.TheWorld.com (Chris F Clark) (2008-08-19) |

RE: best grammar for handling optional symbols? quinn_jackson2004@yahoo.ca (Quinn Tyler Jackson) (2008-08-19) |

From: | "Quinn Tyler Jackson" <quinn_jackson2004@yahoo.ca> |

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

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.