在Bison中使用一元减的优先级不能解决移位/减少冲突 [英] Using precedence in Bison for unary minus doesn't solve shift/reduce conflict

问题描述

我正在设计一个非常简单的语法，其中我使用一元减操作数.但是，我遇到了转移/减少冲突.在Bison手册中，以及我所看到的其他地方，它都说我应该定义一个新令牌，并赋予它比二进制减号操作数更高的优先级，然后在规则中使用％prec TOKEN".

I'm devising a very simple grammar, where I use the unary minus operand. However, I get a shift/reduce conflict. In the Bison manual, and everywhere else I look, it says that I should define a new token and give it higher precedence than the binary minus operand, and then use "%prec TOKEN" in the rule.

我已经做到了，但是我仍然得到警告.为什么?

I've done that, but I still get the warning. Why?

我正在使用野牛(GNU Bison)2.4.1.语法如下所示:

I'm using bison (GNU Bison) 2.4.1. The grammar is shown below:

%{
#include <string>
extern "C" int yylex(void);
%}

%union {
    std::string token;
}

%token <token> T_IDENTIFIER T_NUMBER
%token T_EQUAL T_LPAREN T_RPAREN

%right T_EQUAL
%left T_PLUS T_MINUS
%left T_MUL T_DIV
%left UNARY

%start program

%%

program : statements expr
;

statements : '\n'
           | statements line
;

line : assignment
     | expr
;

assignment : T_IDENTIFIER T_EQUAL expr
;

expr : T_NUMBER
     | T_IDENTIFIER
     | expr T_PLUS expr
     | expr T_MINUS expr
     | expr T_MUL expr
     | expr T_DIV expr
     | T_MINUS expr   %prec UNARY
     | T_LPAREN expr T_RPAREN
;

推荐答案

%prec并没有您在这里希望做的那么多.它告诉Bison，在有- a * b的情况下，您想将此解析为(- a) * b而不是- (a * b).换句话说，相对于T_MUL规则，此处将首选UNARY规则.无论哪种情况，您都可以确定UNARY规则最终会被应用，而这只是输入被简化为一元参数的顺序的问题.

%prec doesn't do as much as you might hope here. It tells Bison that in a situation where you have - a * b you want to parse this as (- a) * b instead of - (a * b). In other words, here it will prefer the UNARY rule over the T_MUL rule. In either case, you can be certain that the UNARY rule will get applied eventually, and it is only a question of the order in which the input gets reduced to the unary argument.

在您的语法中，事情有很大不同. line非终端的任何序列都将构成sequence，没有什么可说line非终端必须在行尾结束.实际上，任何表达式都可以是line.因此，基本上，有两种解析a - b的方法:要么是带有二进制减号的单行，要么是两条线"，第二种是从一元负号开始的.没有什么决定这些规则将适用，因此基于规则的优先级在这里还行不通.

In your grammar, things are very much different. Any sequence of line non-terminals will make up a sequence, and there is nothing to say that a line non-terminal must end at an end-of-line. In fact, any expression can be a line. So here are basically two ways to parse a - b: either as a single line with a binary minus, or as two "lines", the second starting with a unary minus. There is nothing to decide which of these rules will apply, so the rule-based precedence won't work here yet.

您的解决方案是通过要求每个line实际以行结束符号结尾或跟随其后的行来纠正行拆分.

Your solution is correcting your line splitting, by requiring every line to actually end with or be followed by an end-of-line symbol.

如果您确实想要语法针对行尾的指示行为，则需要两个单独的非终结符来表示可以以T_MINUS开头的表达式，也可以不以T_MINUS开头的表达式.您必须将其传播到树上:第一个line可能以一元负号开头，但随后的不能.在括号内，从负号开始将恢复正常.

If you really want the behaviour your grammar indicates with respect to line endings, you'd need two separate non-terminals for expressions which can and which cannot start with a T_MINUS. You'd have to propagate this up the tree: the first line may start with a unary minus, but subsequent ones must not. Inside a parenthesis, starting with a minus would be all right again.

这篇关于在Bison中使用一元减的优先级不能解决移位/减少冲突的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！