Можно ли сделать эту грамматику 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 '('

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

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