有问题的简单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 ')'              {{ $$ =  }}
    | expr AND expr             {{ $$ = NewASTComplexNode(OPND_AND, , ) }}
    | expr AND NOT expr         {{ $$ = NewASTComplexNode(OPND_AND, , NewASTComplexNode(OPND_NOT, , nil)) }}
    | NOT expr AND expr         {{ $$ = NewASTComplexNode(OPND_AND, NewASTComplexNode(OPND_NOT, , nil), ) }}
    | expr OR expr              {{ $$ = NewASTComplexNode(OPND_OR, , ) }}
    | STRING                    {{ $$ = NewASTSimpleNode(OPRT_STRING, ) }}
    | BYTES                     {{ $$ = NewASTSimpleNode(OPRT_BYTES, ) }}
    ;

谁能给我解释一下为什么会出现这些错误？:

rule expr:  NOT expr AND expr  never reduced
1 rules never reduced

conflicts: 3 reduce/reduce

Answer 1

在评论中明确要求是：

The NOT operator should apply only to operands of AND and [the operands] shouldn't be both 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 的一部分，这要求序列包含正数。

备注

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

但是%nonassoc只在一个优先级内有效，并且只有在优先级中的所有运算符都需要相同的处理时它才有效。如果预期的语法不完全符合这些要求，则有必要 - 与此语法一样 - 放弃使用优先声明并写出明确的语法。

有问题的简单YACC语法

Simple YACC grammar with problems

parsing

yacc

备注