Search code examples
parsingcompiler-constructionbison

Different methods of implementing a specific parsing rule for a compiler


Let's say we have a rule in parsing tokens that specifies:

x -> [y[,y]*]

Where the brackets '[ ]' mean that anything in them is optional in order for the rule to take place and the * means 0 or more. e.g it could be:

x : (empty) 
  OR
x : y 
  OR
x : y,y

as well etc. (the above are examples of input that 'x' rule would be activated, not how the code should be)

I have tried the following that works already

x : y commaY
  |
  ;

commaY : COMMA y commaY
       |
       ;

I would like to know alternative options in the above that would make it work, if there are any, for educational purposes.

Thank you in advance.


Solution

  • EDIT my earlier answer was incorrect (as pointed out in the comments), but I cannot remove an accepted answer, so I decided to edit it.

    You will need (at least) 2 rules for x -> [y[,y]*]. Here is another possibility:

    x
     : list
     | /* eps */
     ;
    
    list
     : list ',' y
     | y
     ;