PLY yacc parsing IF-ELSE IF-ELSE nested statements

Question

can somebody help me with writing correct grammar rules for nested if statements? In my language, I am able to write constructions like this:

(IF CONDITION)
    some statements
    (IF CONDITION)
        some statements 
    (ELSE IF CONDITION) 
        some statements
    (ELSE IF CONDITION) 
        some statements
    (ELSE IF CONDITION) 
        some statements 
    (ELSE) 
        some statements
    (END) 
    some statements 
(ELSE IF CONDITION) 
    some statements 
(ELSE) 
    some statements 
(END)

I wrote lexer so left and right parenthesis are RULE_OPEN and RULE_CLOSE tokens, "IF" is IF token, "END" is END token, "ELSE" is ELSE token, "CONDITION" is CONDITION token.

Assume that "some statements" may be anything that is allowed in my language (like in common programming language). It is important that it is possible to nest IF statements possibly infinitely.

Hope this is clear, please let me know if I explained it badly.

No matter how I am trying. I am always getting shift/reduce conflicts and parser is not accepting correct input.

Even though, I have successfully wrote rules without else-if. When I add rules for else-if, code starts to be very complicated for me.

Below is my sucessfull approach without else-if part (I listed only relevant rules):

statements: statement

statements: statements statement

statement: code
| data_out
| rule

rule: inline_if_statement
| block_if_statement

block_if_statement: RULE_OPEN IF CONDITION RULE_CLOSE statements RULE_OPEN END RULE_CLOSE

block_if_statement: RULE_OPEN IF CONDITION  RULE_CLOSE statements block_else_statement

block_else_statement: RULE_OPEN ELSE RULE_CLOSE statements RULE_OPEN END RULE_CLOSE 

block_else_statement: empty

empty : 

I think that this is very common problem in parsing and I hope that somebody here have already solved it :-) Thanks for helping!

Answer 1

Generally, a single shift-reduce conflict for a language that has an optional ELSE clause can be tolerated. Pete Jinks offers a couple of alternative formulations that can resolve the conflict.

A strategy for specifying ELSE-IF constructions: treat this like any other recursively-defined repeating block:

running_else_if_statement : RULE_OPEN IF CONDITION RULE_CLOSE statements else_if_blocks
    RULE_OPEN ELSE RULE_CLOSE statements RULE_OPEN END RULE_CLOSE
                          ;

else_if_blocks : else_if_block
               | else_if_blocks else_if_block
               ;

else_if_block : RULE_OPEN ELSE_IF CONDITION RULE_CLOSE statements 
              ;

As a side note on style: most practitioners consistently combine all alternatives for a production with pipes, the way you have done with

statement : code
          | data_out
          | rule
          ;

It's confusing to read:

statements : statement
           ;

statements : statements statement
           ;

Most prefer:

statements : statement
           | statements statement
           ;