有问题的简单YACC语法

Question

我想实现一个简单的YACC解析器，但我的语法有问题：

%union {
s       string
b       []byte
t       *ASTNode
}
%token AND OR NOT
%token<s> STRING
%token<b> BYTES
%type<t> expr
%left AND
%left OR
%right NOT
%%
expr: '(' expr ')'              {{ $$ = $2 }}
| expr AND expr             {{ $$ = NewASTComplexNode(OPND_AND, $1, $3) }}
| expr AND NOT expr         {{ $$ = NewASTComplexNode(OPND_AND, $1, NewASTComplexNode(OPND_NOT, $4, nil)) }}
| NOT expr AND expr         {{ $$ = NewASTComplexNode(OPND_AND, NewASTComplexNode(OPND_NOT, $2, nil), $4) }}
| expr OR expr              {{ $$ = NewASTComplexNode(OPND_OR, $1, $3) }}
| STRING                    {{ $$ = NewASTSimpleNode(OPRT_STRING, $1) }}
| BYTES                     {{ $$ = NewASTSimpleNode(OPRT_BYTES, $1) }}
;

是否有人向我解释为什么会出现这些错误？：

rule expr:  NOT expr AND expr  never reduced
1 rules never reduced
conflicts: 3 reduce/reduce

Answer 1

在一条评论中，明确了要求是：

NOT运算符应仅应用于AND的操作数，并且[操作数]不应同时为NOT。

该要求的第二部分有点奇怪，因为AND运算符被定义为左关联。这意味着

a AND NOT b AND NOT c

将是合法的，因为它被分组为(a AND NOT b) AND NOT c，其中两个AND运算符都有一个正项。但是旋转参数(这可能根本不会改变语义(会产生：

NOT b AND NOT c AND a

这将是非法的，因为第一分组(NOT b AND NOT c(包含两个NOT表达式。

其意图可能是任何连词(AND运算符的序列(都包含至少一个正项。

这两种约束都是可能的，但不能使用运算符优先级声明来实现。

运算符优先级可以用于解决歧义语法中的歧义(expr: expr OR expr当然是歧义的，因为它允许OR在任意方向上关联(。但它不能用于导入操作数的附加要求，尤其是不能用于将两个操作数都考虑在内的要求[注1]。为了做到这一点，你需要写出一个明确的语法。幸运的是，这并不太难。

明确语法的基础是有时被称为级联优先级样式；这有效地将优先级编码到规则中，因此优先级声明是不必要的。基本布尔语法如下所示：

expr: conjunction           /* Cascade to the next level */
| expr OR conjunction
conjunction
: term                  /* Continue the cascade */
| conjunction AND term
term: atom                  /* NOT is a prefix operator */
| NOT term              /* which is not what you want */
atom: '(' expr ')'
| STRING

每个优先级具有相应的非终端；级联"；从某种意义上说，除了上一个，每一个都包括下一个级别作为一个单元生产。

为了适应NOT最多只能被限制为AND运算符的一个操作数的要求，我们可以或多或少地像在原始语法中那样写出可能性，但要遵循级联样式：

expr: conjunction
| expr OR conjunction
conjunction
: atom                     /* NOT is integrated, so no need for 'term' */
| conjunction AND atom
| conjunction AND NOT atom /* Can extend with a negative */
| NOT atom AND atom        /* Special case for negative at beginning */

atom: '(' expr ')'            
| STRING

conjunction的第三条规则(conjunction: conjunction AND NOT atom(允许在操作数列表的末尾添加任意数量的NOT应用程序，但不允许在列表的开头添加连续的NOT操作数。第四条规则允许在开始时使用单个NOT。

如果你喜欢连词必须至少有一个正项的规则，你可以使用以下非常简单的适应：

expr: conjunction
| expr OR conjunction
conjunction
: atom                     /* NOT is integrated, so no need for 'term' */
| conjunction AND atom
| conjunction AND NOT atom
| negative AND atom        /* Possible initial list of negatives */
negative                       /* This is not part of the cascade */
: NOT atom
| negative AND NOT atom
atom: '(' expr ')'            
| STRING

在这个变体中，negative将匹配，例如，NOT a AND NOT b AND NOT c。但因为它不在级联中，所以该序列不会自动成为有效的表达式。为了将其用作表达式，它需要是conjunction: negative AND atom的一部分，这要求序列包含阳性。

注释

1. %nonassoc优先级声明可用于拒绝来自相同优先级的运算符的链式使用。这有点像黑客攻击，有时会产生意想不到的后果。预期的用例是像C这样的语言中的<这样的运算符，它们对链式比较没有特殊的处理；使用%nonassoc，您可以声明在比较运算符的优先级中链接是非法的。

   但%nonassoc仅在单个优先级内工作，并且只有当优先级中的所有运算符都需要相同的处理时，它才工作。如果预期的语法不完全符合这些要求，那么就有必要——就像这个语法一样——放弃使用优先级声明，写出一个明确的语法。