我正在研究 GNU bison 中的 GLR 解析器，但遇到以下问题：
我试图解析的语言允许布尔表达式，包括关系（<、>、<=、...）和布尔组合（和、或、非）。现在的问题是该语言还允许在关系的右侧有多个算术表达式......并且它们使用用于布尔组合的相同 AND 标记组合！这是一个非常愚蠢的语言设计，但我无法改变它。
所以你可以拥有a > b and c应该等同于的(a > b) and (a > c)，你也可以拥有a > b and c > d应该等同于的(a > b) and (c > d)
这导致的 S/R 冲突在此示例中已经很明显：在a > b使用前瞻读取之后，and您可以将 减少a > b为布尔表达式并等待另一个布尔表达式，或者您可以转移and并等待另一个算术表达式。
我的语法目前看起来像这样：
booleanexpression
: relation
| booleanexpression TOK_AND booleanexpression
...
;
relation
: arithmeticexpression TOK_GT maxtree
...
;
maxtree
: arithmeticexpression
| maxtree TOK_AND maxtree
...
;
对于任何k ，该语言显然不是LR(k) ，因为使用任何常量k -lookahead都无法解决 S/R 冲突，因为两者之间的算术表达式可以有任意多个标记。因此，我打开了 GLR 解析。
但是，当我尝试a > b and c对此进行解析时，我可以在调试输出中看到解析器的行为如下：
- 它读取并在
a前瞻>中将aarithmeticexpression - 它读取
b并向前看and它减少b到一个arithmeticexpression然后已经减少到一个maxtree - 它减少
a > b到一个relation - 它读取并将其简化
c为arithmeticexpression
然后什么也没有发生！and c显然被丢弃了 - 调试输出不显示这些令牌的任何操作。甚至没有错误消息。我的 AST 中不存在相应的 if 语句（我仍然得到一个 AST，因为我有错误恢复）。
我认为，在阅读完之后b，应该有 2 个堆栈。但是b不应该减少。或者至少它应该给我一些错误信息（“语言是模棱两可的”会好的，我以前看过这条信息 - 我不明白为什么它不适用于这里）。任何人都可以理解这一点吗？
看了一会儿语法，你可以看出这里的主要问题是在下一个算术表达式之后是否出现
- 另一个关系标记（那么你应该减少）
- 另一个布尔组合（那么你应该转移）
- 布尔/算术表达式语法（如 THEN）之外的标记，它将终止表达式，您还应该转换
你能想出一种不同的语法以更好/更确定的方式捕捉情况吗？你会如何处理这个问题？我目前正在考虑使语法更从右到左，比如
booleanexpression : relation AND booleanexpression
maxtree : arithmeticexpression AND maxtree
etc.
我认为这会使野牛更喜欢变速，并且只会首先减少右侧。也许通过使用不同的非终结符，它可以允许算术表达式后面的准“前瞻”......
旁注：GnuCOBOL 通过收集所有标记、将它们推送到中间堆栈并从那里手动构建表达式来处理这个问题。这让我灰心丧气，但我坚持希望他们这样做是因为野牛在开始时不支持 GLR 解析......
编辑：一个可重复的小例子
%{
#include <stdio.h>
int yylex ();
void yyerror(const char* msg);
%}
%glr-parser
%left '&'
%left '>'
%%
input: %empty | input bool '\n' {printf("\n");};
arith : 'a' | 'b' | 'c';
maxtree : arith { printf("[maxtree : arith] "); }
| maxtree '&' maxtree { printf("[maxtree : maxtree & maxtree] "); } ;
rel : arith '>' maxtree { printf("[rel : arith > maxtree] "); } ;
bool : rel { printf("[bool : rel] "); }
| bool '&' bool { printf("[bool : bool & bool] "); } ;
%%
void yyerror(const char* msg) { printf("%s\n", msg); }
int yylex () {
int c;
while ((c = getchar ()) == ' ' || c == '\t');
return c == EOF ? 0 : c;
}
int main (int argc, char** argv) {
return yyparse();
}
这个奇怪地确实在 input 上打印了错误消息“语法错误” a>b&c。