EBNF to Bison - Reduce/Reduce error

Question

i have to translate this EBNF to bison:

<compound-statement> ::= begin [ <statement> ( ; <statement> )*] end

<statement> ::= 
| <assignment>
| <if-statement>
| <while-statement>
| <proc-func-call>
| <compound-statement>

when i translate assignement, if,while statements and proc_func_ there is no error in bison. However when i type this in bison, translating the compound statement:

compound_statement : BEGINKEY state ENDKEY ;
state : | statement stm ;
stm : | BQUESTIONMARK statement stm ;

there is a reduce/reduce error.

Can someone explain to me, why there is a reduce/reduce error, because it doesnt make sense to me. I would really appreciate it.

Thanks in advance.

Answer 1

So you have a Pascal-ish language where the semicolon is a statement separator, not a terminator.

I assume that BQUESTIONMARK is your token for the semicolon (";").

I think that you will do best with one production that requires the first statement, then another left-recursive production that provides for the optional additional statements.

I may be misreading something, but your grammar allows state to be epsilon (null) as well as stm, and I think that is the source of your reduce/reduce error.

I would tackle the problem like this:

compound_statement : BEGINKEY first_statement statements ENDKEY
                   | BEGINKEY first_statement ENDKEY
                   ;

first_statement : statement ;

statement : assignment
          | if_statement
          | while_statement
          | proc_func_call
          | compound_statement
          ;

statements : statements statement_with_semi
           | statement_with_semi
           ;

statement_with_semi : BQUESTIONMARK statement ;