Search code examples
c#parsinggrammarirony

Irony BnfExpression that produces different non terminals that can be in any order

I'm trying to create a grammar that allows productions to come in any order. For example:

    <NewObject>
     Name
     Type
     Value
    </NewObject>

and 

    <NewObject>
     Value
     Name
     Type
    </NewObject>

Should both be acepted.

Up until now I've been able to get away with just using the permutations of each production like this:

The following code is written using the irony's BnfExpresion, where + means concatenation

A.Rule = B + C + D |
         B + D + C |
         C + B + D |
         C + D + B |
         D + B + C |
         D + C + B;

However, this approach became a problem when I tried permuting a production with 6 different non terminals. 6 factorial is 720, way too much for c# to handle as it prompts a compiler error (An expression is too long or complex to compile).

Is there way I can achieve "any order" without having to permute all the different possibilities.

Solution

  • Basically, no. Your best bet is to accept arbitrary repetitions of the non-terminals and then check to for repetition in the associated semantic action.

    (There are several answers of this form already in SO but they don't ever seem to get upvoted or accepted, which means that SO won't accept them as duplicates.)