是否可以使这个 YACC 语法明确无误？表达式：... |表达式表达式

Question

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

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

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

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

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

最后一条规则有问题：

expr expr { $$ =  ; }

我想要这个规则，因为我希望能够在我的计算器中写出像 5(3+4)(3-24) 这样的表达式。

是否可以让这个语法没有歧义？

Answer 1

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

很明显是减法的意思（否则减法无法表示）所以如果右边第二个expr是一元数，就需要禁止产生式expr: expr expr操作。

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

您还必须准确决定隐式乘法的优先级：与显式 multiplication/division 相同或更强。这会影响 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

是否可以使这个 YACC 语法明确无误？表达式：... |表达式表达式

Is it possible to make this YACC grammar unambiguous? expr: ... | expr expr

grammar

bison

yacc

ambiguity

ambiguous-grammar