RE: yacc question / n! rules explosion

Quinn Tyler Jackson <>
5 May 2003 23:33:49 -0400

          From comp.compilers

Related articles
Re: yacc question / n! rules explosion (Chris F Clark) (2003-04-27)
RE: yacc question / n! rules explosion (Quinn Tyler Jackson) (2003-05-05)
| List of all articles for this month |

From: Quinn Tyler Jackson <>
Newsgroups: comp.compilers
Date: 5 May 2003 23:33:49 -0400
Organization: Compilers Central
References: 03-04-117
Keywords: parse, yacc
Posted-Date: 05 May 2003 23:33:49 EDT

> > The only alternative i see is write something like
> > file = element | file element; element = A | B | C; and
> do some checks
> > in the actions (eg some counters)
> As our moderator replied, there is nothing in BNF (or even
> most EBNF's
> that I am aware of) which handles permutation grammars. Moreover,
> even when the tool supports a permutation syntax, the
> resulting parser
> (or lexer) ends up with the combinatorial explosion in states.

A-BNF has the permutation phrase [Cameron] syntax, and allows
"relaxed" permutation phrases in the form:

S ::= <<A B C>>
A ::= "a";
B ::= "b";
C ::= "c";

The "relaxed" form does not allow any of A, B, or C to derive lamda,
and thus, cannot handle this:

S ::= <<A B C>>
A ::= "a";
B ::= ["b"];
C ::= "c";

At implementation, it does not generate state explosion.

[Cameron] Robert D. Cameron, "Extending Context-Free Grammars with
Permutation Phrases," LOPLAS 2(1-4): 85-94, 1993.

Quinn Tyler Jackson

Post a followup to this message

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