使用优先级解决shift/reduce冲突的经典例子（%prec UMINUS）

2023-04-17 13:57:45 浏览数 (1)

1 前言

在postgresql的gram.y中能看到一些提高优先级的语法，例如最容易理解的：

代码语言：javascript复制
a_expr:		c_expr									{ $$ = $1; }
			...
			...
			| ' ' a_expr					%prec UMINUS
				{ $$ = (Node *) makeSimpleA_Expr(AEXPR_OP, " ", NULL, $2, @1); }
			| '-' a_expr					%prec UMINUS
				{ $$ = doNegate($2, @1); }
			| a_expr ' ' a_expr
				{ $$ = (Node *) makeSimpleA_Expr(AEXPR_OP, " ", $1, $3, @2); }
			| a_expr '-' a_expr
				{ $$ = (Node *) makeSimpleA_Expr(AEXPR_OP, "-", $1, $3, @2); }

这里的%prec UMINUS将对应的规则提为更高的优先级，在例如select 1 -1;的场景中，可以将-1优先reduce为a_expr，在同级规则中，通过prec得到了优先匹配的结果。

这里UMINUS是在gram.y上面定义的无具体意义的运算符，因为定义的位置靠下，所以拥有较高的优先级（优先级是越在下面的越高）。

2 案例：%prec UMINUS解决shift/recude冲突

gram.y中处理select语句的语法规则，发生语法冲突。

代码语言：javascript复制
SelectStmt: select_no_parens            %prec UMINUS
			| select_with_parens		// 此处应该有一个%prec UMINUS，删掉发生冲突
		;

select_with_parens:
			'(' select_no_parens ')'				{ $$ = $2; }
			| '(' select_with_parens ')'			{ $$ = $2; }
		;

select_no_parens:  
			...
			...
			（这里组成select语句）

发生冲突

代码语言：javascript复制
$ bison -Wno-deprecated  -d -o gram.c gram.y -Wcounterexamples
gram.y: error: shift/reduce conflicts: 1 found, 0 expected
gram.y: warning: shift/reduce conflict on t0ken ')' [-Wcounterexamples]
  Example: '(' select_with_parens • ')'
  Shift derivation
    RuleActionList
    ↳ 1405: RuleActionStmt
            ↳ 1409: SelectStmt
                    ↳ 1664: select_with_parens
                            ↳ 1666: '(' select_with_parens • ')'
  Reduce derivation
    RuleActionList
    ↳ 1406: '(' RuleActionMulti                                      ')'
                ↳ 1408: RuleActionStmtOrEmpty
                        ↳ 1414: RuleActionStmt
                                ↳ 1409: SelectStmt
                                        ↳ 1664: select_with_parens •

ok现在我们来分析：

  1. 当前lookahead token为')'
  2. 当前rule为：select_with_parens

根据提示，右括号可以直接匹配当前的select_with_parens，也可以让select_with_parens一直reduce上去，直到RuleActionMulti位置，再把右括号匹配给RuleActionMulti。

当前没有定义select_with_parens的优先级，所以发生了shift/recude冲突。如果加上%prec UMINUS为什么就没有冲突了，bison选择了shift还是recude？

代码语言：javascript复制
SelectStmt: select_no_parens            %prec UMINUS
			| select_with_parens		%prec UMINUS   // <---新增
		;

select_with_parens:
			'(' select_no_parens ')'				{ $$ = $2; }
			| '(' select_with_parens ')'			{ $$ = $2; }
		;

select_no_parens:  
			...
			...
			（这里组成select语句）

冲突解决，增加prec后：

  1. 当前lookahead token为')'
  2. 当前rule为：select_with_parens
  3. 在gram.y中定义了')'的优先级高于UMINUS，所以select_with_parens有更低的优先级。

处理上述情况bison的规则：

  1. 如果rule的优先级更高，bison选择reduce。
  2. 如果lookahead token的优先级更高，bison选择shift。

Finally, the resolution of conflicts works by comparing the precedence of the rule being considered with that of the lookahead token. If the token’s precedence is higher, the choice is to shift. If the rule’s precedence is higher, the choice is to reduce. If they have equal precedence, the choice is made based on the associativity of that precedence level. The verbose output file made by -v (see Invoking Bison) says how each conflict was resolved.

所以，在上述两条路径中，select_with_parens比')'的优先级低，bison执行shift操作，将右括号和更内层、更近的左括号结合，避免了语法错误。

代码语言：javascript复制
  Shift derivation
    RuleActionList
    ↳ 1405: RuleActionStmt
            ↳ 1409: SelectStmt
                    ↳ 1664: select_with_parens
                            ↳ 1666: '(' select_with_parens • ')'

总结

增加语法时，如果发生了shift/recude错误，且错误发生的原因是lookahead token和同一条规则的冲突，可以尝试为规则配置优先级，达到帮助bison选择shift、reduce的效果。

reduce select shift 配置 语法

0 人点赞