Re: How to deal with unordered, non-repeated nonterminals of expression

John Sasso wrote:
> I am trying to figure out the best, most efficient way of parsing
> expressions having a [possibly large] set of non-terminals that can
> appear in any order in the expression BUT cannot be repeated in the
> expression.
>
> For example (nonterms are lc, terms are uc):
>
> expr -> CMD id FILE option1 option2 option3 option4
> option1 -> OP1 var | epsilon
> option2 -> OP2 var | epsilon
> option3 -> OP3 val | epsilon
> option4 -> flag | epsilon
> var -> ALPHANUMERIC_STRING
> val -> NUMBER
> id -> NUMBER
> flag -> X | Y | Z
>
> Here, option1, option2, option3, and option4 can appear in any
> order in the expression but only once:
>
> CMD 123 FILE OP1 acme X OP3 100 // OK
> CMD 456 FILE OP3 1111 OP2 abc OP1 def // OK
> CMD 9 FILE OP1 acme X OP3 100 OP1 foobar // ERROR!
> CMD 10 FILE X OP3 14 Y // ERROR!
>
> I doing development with Flex and Bison, which I am gradually
> getting the hang of. Any suggestions, sample code, and/or
> references to web links would be greatly appreciated!
>
> --john
> [You can mechanically create a huge parser with all of the
> combinatorial possibilities, but I would suggest that you simply
> parse a list of optionN and detect duplicates in semantic code.
> Free bonus: then you can say "redundant OP1 clause" rather than
> a generic "syntax error". -John]


I agree with John (Fine). Often in parsing the modifiers for type,
field, class, and method declarations many keywords are possible that
should only appear once. My experience is that by far the simplest and
most scalable approach is to just parse a list of modifiers (possibly
containing duplications) and then simply check for duplicates in a
second pass. It also gives the advantage that you can have a little
better error message for your users such as "duplicate option X" as
opposed to the parser giving a complex message that it was expecting
some large set of possible tokens at that point.

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