Можно ли сделать эту грамматику YACC однозначной? expr: ... | expr expr

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 '(' 

Проблема с последним правилом:

Я хочу, чтобы это правило, потому что я хочу, чтобы иметь возможность писать такие выражения, как 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