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

John Sasso <jsassojr@nycap.rr.com>
3 Aug 2006 11:07:08 -0400

          From comp.compilers

Related articles
How to deal with unordered, non-repeated nonterminals of expression jsassojr@nycap.rr.com (John Sasso) (2006-08-03)
Re: How to deal with unordered, non-repeated nonterminals of expressio diablovision@yahoo.com (2006-08-09)
| List of all articles for this month |

From: John Sasso <jsassojr@nycap.rr.com>
Newsgroups: comp.compilers
Date: 3 Aug 2006 11:07:08 -0400
Organization: Road Runner
Keywords: parse, question, comment

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]


Post a followup to this message

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