Re: yacc question / n! rules explosion

Chris F Clark <cfc@world.std.com>
27 Apr 2003 17:15:01 -0400

          From comp.compilers

Related articles
yacc question / n! rules explosion ares@cs.kuleuven.ac.be (Ares Lagae) (2003-04-27)
Re: yacc question / n! rules explosion cfc@world.std.com (Chris F Clark) (2003-04-27)
RE: yacc question / n! rules explosion qjackson@shaw.ca (Quinn Tyler Jackson) (2003-05-05)
| List of all articles for this month |

From: Chris F Clark <cfc@world.std.com>
Newsgroups: comp.compilers
Date: 27 Apr 2003 17:15:01 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 03-04-102
Keywords: parse, yacc
Posted-Date: 27 Apr 2003 17:15:01 EDT

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)


Post a followup to this message

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