是否可以使此YACC语法明确? expr:... | expr expr [英] Is it possible to make this YACC grammar unambiguous? expr: ... | expr expr

问题描述

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

I am writing a simple calculator in yacc / bison.

表达式的语法看起来像这样:

The grammar for an expression looks somewhat like this:

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; }
;

我已经宣布了像这样的运算符的优先级.

I have declared the precedence of the operators like this.

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

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

The problem is with the last rule:

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

我想要此规则，因为我希望能够在计算器中编写类似5(3+4)(3-24)的表达式.

I want this rule because I want to be able to write expressions like 5(3+4)(3-24) in my calculator.

是否可以使该语法明确?

Is it possible to make this grammar unambiguous?

推荐答案

含糊不清的原因是您允许使用一元运算符(- expr)，因此2 - 2可以解析为简单的减法(屈服值为0)或作为隐式乘积(2和-2，产生-4).

The ambiguity results from the fact that you allow unary operators (- expr), so 2 - 2 can be parsed either as a simple subtraction (yielding 0) or as an implicit product (of 2 and -2, yielding -4).

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

It's clear that subtraction is intended (otherwise subtraction would be impossible to represent) so it is necessary to ban the production expr: expr expr if the second expr on the right-hand side is a unary operation.

那不能用优先声明来完成(或者至少不能以明显的方式来完成)，所以最好的解决方案是显式地写出语法，而不必依靠优先来消除歧义.

That can't be done with precedence declarations (or at least it cannot be done in an obvious way), so the best solution is to write out the grammar explicitly, without relying on precedence to disambiguate.

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

You will also have to decide exactly what is the precedence of implicit multiplication: either the same as explicit multiplication/division, or stronger. That affects how ab/cd is parsed. There is no consensus that I know of, so it is more or less up to you.

在下面，我假定隐式乘法的绑定更紧密.我还确保将-ab解析为(-a)b，尽管-(ab)具有相同的最终结果(直到您开始处理非算术类型和自动转换之类的事情).因此，以它为例.

In the following, I assume that implicit multiplication binds more tightly. I also ensure that -ab is parsed as (-a)b, although -(ab) has the same end result (until you start dealing with things like non-arithmetic types and automatic conversions). So just take it as an example.

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

这篇关于是否可以使此YACC语法明确? expr:... | expr expr的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！