Re: yacc question / n! rules explosion

Ares Lagae wrote:
> for a small x, you can write those rules, but when x gets larger, x!
> gets very large
> so, my question is; is there a better way to do this in yacc than to
> explicitly enumerate all permutations ?
> 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.


Using counters with actions is the correct solution generally. In
fact, one of the parsing advances I mentioned elsewhere, "register
vectors", was a sophisticated way of encoding those counters and
checks (and give them a nice well-defined semantics). Unfortunately,
I am not aware of any tools that have adopted the model proposed in
the article I read [Comm ACM early-90's I think].


It's on my very full to-do list, but not near the top, so don't hold
your breath. I may retire before getting to it.


I wish I could help,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)

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