是否有可能使这个 YACC 语法明确？表达式：... | 表达式 表达式

Question

我正在用yacc / bison编写一个简单的计算器。

表达式的语法看起来有点像这样：

expr
: NUM
| expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
| expr '*' expr { $$ = $1 * $3; }
| expr '/' expr { $$ = $1 / $3; }
| '+' expr %prec '*' { $$ = $1; }
| '-' expr %prec '*' { $$ = $1; }
| '(' expr ')' { $$ = $2; }
| expr expr { $$ = $1 '*' $2; }
;

我已经这样声明了运算符的优先级。

%left '+' '-'
%left '*' '/'
%nonassoc '('

问题出在最后一条规则上：

expr expr { $$ = $1 $2; }

我想要这条规则，因为我希望能够像5(3+4)(3-24)计算器一样编写表达式。

是否有可能使这个语法变得明确？

Answer 1

歧义是由于您允许使用一元运算符 ( - expr)，因此2 - 2可以将其解析为简单的减法（生成 0）或隐式乘积（2 和 -2 的结果，生成 -4）。

很明显，减法是有意的（否则减法将无法表示），因此如果右侧expr: expr expr第二个是一元运算，则有必要禁止产生式。expr

这是无法通过优先级声明来完成的（或者至少不能以明显的方式完成），因此最好的解决方案是显式地写出语法，而不依赖优先级来消除歧义。

您还必须准确决定隐式乘法的优先级：要么与显式乘法/除法相同，要么更强。这会影响ab/cd解析方式。据我所知，还没有达成共识，所以这或多或少取决于你。

在下文中，我假设隐式乘法结合得更紧密。我还确保将-ab其解析为(-a)b，尽管-(ab)具有相同的最终结果（直到您开始处理非算术类型和自动转换等内容）。所以就拿它来举例吧。

term: NUM
    | '(' expr ')'
unop: term
    | '-' unop
    | '+' unop
conc: unop
    | conc term
prod: conc
    | prod '*' conc
    | prod '/' conc
expr: prod
    | expr '+' prod
    | expr '-' prod