|yacc question / n! rules explosion email@example.com (Ares Lagae) (2003-04-27)|
|Re: yacc question / n! rules explosion firstname.lastname@example.org (Chris F Clark) (2003-04-27)|
|From:||Ares Lagae <email@example.com>|
|Date:||27 Apr 2003 02:32:32 -0400|
|Keywords:||yacc, parse, question|
|Posted-Date:||27 Apr 2003 02:32:32 EDT|
Suppose I Have A File Which Consists Of A Sequence Of Exactly X Tokens
(In Fact Larger Entities Matched By Rules), Where Each Token Appears
Exacly Once, In Arbitrary Order.
For Example, If x=3, With The Tokens A, B and C , Valid Files Are ABC,
ACB, BAC, BCA, CAB and CBA.
If I Translate This To Yacc, I Would Have 3!=6 Rules
File = A B C | A C B | B A C | B C A | C A B | C B A
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)
a concrete example:
suppose you have a html IMG tag (i am not trying to make a html parser,
just an example). the tag can have an ALT, HEIGHT, WIDTH and SRC
attribute. They can be at most once in the IMG tag, but in arbitrary
order. Is there another way than to put the 4!=24 rules in the parser ?
Have I Missed Something Fundamentally In Yacc ?
[No, you haven't missed anything, BNF doesn't express rules like "exactly
once in any order" very well. I'd write a looser grammer and knock out
the bad stuff semantically. That lets you provide better error messages
too, "duplicate HEIGHT tag" rather than generic "syntax error". -John]
Return to the
Search the comp.compilers archives again.