RE: yacc question / n! rules explosion

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

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