Bison打印规则输出顺序颠倒问题求助

我正在为课程作业开发一款简单编程语言的解析器，以下是我的Bison规则：

program:
    start var_decl_list main statement_list end

start:
    START EOS {printf("Start")};

var_decl_list: 
    var_decl_list variable_declaration | variable_declaration;

variable_declaration:
    S VAR_NAME EOS { add_variable($1, $2); };

main: 
    MAIN EOS {printf("Main")};

statement_list:
    statement_list statement | statement;

statement:
  move_statement
  | add_statement
  | input_statement
  | print_statement
  ;

move_statement:
    MOVE NUMBER TO VAR_NAME EOS { int_to_var($2, $4) }
    | MOVE VAR_NAME TO VAR_NAME EOS { move_var_to_var($2, $4) };

add_statement:
    ADD NUMBER TO VAR_NAME EOS { add_int_to_var($2, $4) }
    | ADD VAR_NAME TO VAR_NAME EOS { add_var_to_var($2, $4) };

input_statement:
    INPUT input_list;

input_list:
    VAR_NAME EOS { find_variable($1)};
    | VAR_NAME SEMICOLON input_list {printf("INPUT statement")};

print_statement:
    PRINT print_list;

print_list:
    VAR_NAME EOS {print_variable($1)}
    | TEXT EOS {print_text($1)}
    | VAR_NAME SEMICOLON print_list {print_variable($1)}
    | TEXT SEMICOLON print_list {print_text($1)};
end:
    END EOS {printf("End")};

当我输入以下内容时：

PRINT "I have ";XY;" apples".

得到的输出是：

" apples"35"I have "

请问我的print语句规则哪里出错了？

问题出在print_list的右递归规则执行顺序上。Bison是LR(1)解析器，采用自底向上的归约方式，对于你定义的右递归规则：

print_list:
    VAR_NAME SEMICOLON print_list {print_variable($1)}
    | TEXT SEMICOLON print_list {print_text($1)};

解析时会先归约最右侧的print_list分支，执行其动作，再归约当前的VAR_NAME/TEXT部分。拿你的输入"I have ";XY;" apples".来说，解析顺序是：

1. 先归约" apples" + EOS，执行print_text(" apples")，输出这部分内容
2. 再归约XY; + 上面的print_list，执行print_variable(XY)，输出35
3. 最后归约"I have "; + 上面的print_list，执行print_text("I have ")，输出这部分

最终就出现了输出顺序完全颠倒的情况。

修正方案 #

把print_list改成左递归结构，让先出现的内容先执行输出动作：

print_statement:
    PRINT print_list EOS;  // 把EOS移到这里，统一处理结束符

print_list:
    print_item
    | print_list SEMICOLON print_item;  // 左递归，先处理前面的print_list，再处理新的print_item

print_item:
    VAR_NAME {print_variable($1)}
    | TEXT {print_text($1)};

这样解析时，会先归约第一个print_item（"I have "）并执行输出，再归约print_list SEMICOLON print_item（即前面的结果 + ;XY），执行print_variable(XY)，最后归约加上;" apples"，执行print_text(" apples")，输出顺序就和输入一致了。

另外，你的input_list也存在同样的右递归问题，如果后续处理多变量输入时，也会出现顺序颠倒的情况，可以用同样的左递归方式修正。

内容的提问来源于stack exchange，提问作者Collander