yacc question / n! rules explosion

Ares Lagae <ares@cs.kuleuven.ac.be>
27 Apr 2003 02:32:32 -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)
| List of all articles for this month |

From: Ares Lagae <ares@cs.kuleuven.ac.be>
Newsgroups: comp.compilers
Date: 27 Apr 2003 02:32:32 -0400
Organization: KULeuvenNet
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 ?


--
Ares Lagae
[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]





Post a followup to this message

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