移进规约冲突

今天写了一个移进规约冲突的文法。文法规则如下：

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112%{#include #include #include "zend_compile.h"#include "zend_opcode.h"#include "zend_vm.h"#define YYDEBUG 1#define zendparse yyparseextern int yylex(void);extern int yyparse(void);extern FILE *yyin;extern int yylineno;int yywrap(){ return 1;}void yyerror(const char *s){ printf("[error] %s, in line %d\n", s, yylineno);}int main(int argc, char const *argv[]){ return 0;}%}%left '+' '-'%left '*' '/'%left '(' ')'%token T_ECHO "'echo'"%token T_LNUMBER "integer"%token T_VARIABLE "variable"%union { zend_ast *ast;}%type top_statement statement%type expr%type echo_expr%type scalar%type top_statement_list%type variable%%start: top_statement_list { CG(ast) = $1; };top_statement_list: top_statement_list top_statement { $$ = zend_ast_list_add($1, $2); } | %empty { $$ = zend_ast_create_list(0, ZEND_AST_STMT_LIST); };top_statement: statement { $$ = $1; };statement: T_ECHO echo_expr ';' { $$ = $2; }| expr ';' { $$ = $1; };echo_expr: expr { std::cout << "create echo zend_ast" << std::endl; $$ = zend_ast_create_1(ZEND_AST_ECHO, 0, $1); };expr: variable '=' expr { std::cout << "create assign zend_ast" << std::endl; $$ = zend_ast_create_2(ZEND_AST_ASSIGN, 0, $1, $3); }| expr '+' expr { std::cout << "create + zend_ast" << std::endl; $$ = zend_ast_create_binary_op(ZEND_ADD, $1, $3); }| expr '-' expr { std::cout << "create - zend_ast" << std::endl; $$ = zend_ast_create_binary_op(ZEND_SUB, $1, $3); }| expr '*' expr { std::cout << "create * zend_ast" << std::endl; $$ = zend_ast_create_binary_op(ZEND_MUL, $1, $3); }| expr '/' expr { std::cout << "create / zend_ast" << std::endl; $$ = zend_ast_create_binary_op(ZEND_DIV, $1, $3); }| '(' expr ')' { $$ = $2; }| scalar { $$ = $1; };scalar: T_LNUMBER { $$ = $1; };variable: T_VARIABLE { $$ = $1; }%%

执行生成代码的命令：

123456789101112131415bison -d -Wcounterexamples zend_language_parser.yzend_language_parser.y: warning: 4 shift/reduce conflicts [-Wconflicts-sr]zend_language_parser.y: warning: shift/reduce conflict on token '+' [-Wcounterexamples] Example: variable '=' expr • '+' expr Shift derivation expr ↳ variable '=' expr ↳ expr • '+' expr Reduce derivation expr ↳ expr '+' expr ↳ variable '=' expr •# 省略其他的警告

可以看到，警告说是有4个地方有移进规约的冲突。

那么，什么是移进规约冲突呢？意思就是说，当我们预读了词素的时候，既可以对分析栈里面已有的词素进行规约也可以对预读的词素进行移进，这就是已经规约冲突。

OK，我们来看看上面的报错。可以看到，当有字符串：

1$a = 1 + 1

输入时，会发生移进规约的冲突。

我们来看看如果是优先移进的话，状态是如何变化的：

12345678910111213141516171819202122232425262728293031323334353637383940414243+----------------------------------+ +-----+ +----------------------------------+| | |init | | $a = 1 + 1 |+----------------------------------+ +-----+ +----------------------------------+ +----------------------------------+ +-----+ +----------------------------------+| $a | |shift| | = 1 + 1 |+----------------------------------+ +-----+ +----------------------------------+ +----------------------------------+ +-----+ +----------------------------------+| $a = | |shift| | 1 + 1 |+----------------------------------+ +-----+ +----------------------------------+ +----------------------------------+ +-----+ +----------------------------------+| $a = 1 | |shift| | + 1 |+----------------------------------+ +-----+ +----------------------------------+ +----------------------------------+ +-----+ +----------------------------------+| $a = 1 + | |shift| | 1 |+----------------------------------+ +-----+ +----------------------------------+ +----------------------------------+ +-----+ +----------------------------------+| $a = 1 + 1 | |shift| | |+----------------------------------+ +-----+ +----------------------------------+ +----------------------------------+ +------+ +----------------------------------+| $a = expr | |reduce| | |+----------------------------------+ +------+ +----------------------------------+ +----------------------------------+ +------+ +----------------------------------+| expr | |reduce| | |+----------------------------------+ +------+ +----------------------------------+

对应的AST如下：

12345678910111213141516171819202122232425 +------------+ |ZEND_ASSIGN | | | +------------+ | | +--------------+--------------+ | | | | v v +------------+ +------------+ | $a | | ZEND_ADD | | | | | +------------+ +------------+ | | | +---------------+-------------+ | | | | v v +------------+ +------------+ | 1 | | 1 | | | | | +------------+ +------------+

计算这个AST，我们会得到$a的最终值为2。这是符合主流语言的预期的。

我们来看看如果是优先规约的话，状态是如何变化的：

12345678910111213141516171819202122232425262728293031323334353637383940414243+----------------------------------+ +-----+ +----------------------------------+| | |init | | $a = 1 + 1 |+----------------------------------+ +-----+ +----------------------------------+ +----------------------------------+ +-----+ +----------------------------------+| $a | |shift| | = 1 + 1 |+----------------------------------+ +-----+ +----------------------------------+ +----------------------------------+ +-----+ +----------------------------------+| $a = | |shift| | 1 + 1 |+----------------------------------+ +-----+ +----------------------------------+ +----------------------------------+ +-----+ +----------------------------------+| $a = 1 | |shift| | + 1 |+----------------------------------+ +-----+ +----------------------------------+ +----------------------------------+ +------+ +----------------------------------+| expr | |reduce| | + 1 |+----------------------------------+ +------+ +----------------------------------+ +----------------------------------+ +-----+ +----------------------------------+| expr + | |shift| | 1 |+----------------------------------+ +-----+ +----------------------------------+ +----------------------------------+ +------+ +----------------------------------+| expr + 1 | |shift | | |+----------------------------------+ +------+ +----------------------------------+ +----------------------------------+ +------+ +----------------------------------+| expr | |reduce| | |+----------------------------------+ +------+ +----------------------------------+

对应的AST如下：

12345678910111213141516171819202122232425262728 +-----------------+ | | | ZEND_ADD | | | +-----------------+ | | +---------------+----------------+ | | | | v v +-----------------+ +-----------------+ | | | | | ZEND_ASSIGN | | 1 | | | | | +-----------------+ +-----------------+ | | | +-----------------+----------------+ | | | | v v +-----------------+ +-----------------+ | | | | | $a | | 1 | | | | | +-----------------+ +-----------------+

计算这个AST，我们会得到$a的最终值为1。这和我们想的不太一样。

所以，移进规约的冲突，会导致一些执行的顺序不一致。如果我们学习过bison官方文档经典的if ... else的移进规约冲突问题的话，我们知道，解决它的办法是修改文法，进而避免冲突（因为这个例子有一点绕，所以我没有用那个例子）。那我们这种情况呢，就可以通过设置词素的优先级来解决掉，我们设置=的优先级低于+即可：

1234%left '='%left '+' '-'%left '*' '/'%left '(' ')'

这样的话，当我们的分析栈为如下情况的时候：

123+----------------------------------+ +-----+ +----------------------------------+| $a = 1 | |shift| | + 1 |+----------------------------------+ +-----+ +----------------------------------+

我们预读一个+，因为+号的优先级更高一点，所以，此时不会选择规约，而是把+移进。这样，我们可以保证在后续规约的时候，先规约1 + 1，进而也保证了运算符的优先级。