有问题的简单YACC语法
Simple YACC grammar with problems
我想实现一个简单的 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
在评论中明确要求是:
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 解析器,但我的语法有问题:
%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
在评论中明确要求是:
The
NOT
operator should apply only to operands ofAND
and [the operands] shouldn't be bothNOT
.
该要求的第二部分有点奇怪,因为 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
只在一个优先级内有效,并且只有在优先级中的所有运算符都需要相同的处理时它才有效。如果预期的语法不完全符合这些要求,则有必要 - 与此语法一样 - 放弃使用优先声明并写出明确的语法。