Bison：有效表达式的 GLR 解析失败，没有错误消息
Bison: GLR-parsing of valid expression fails without error message
我正在 GNU bison 中开发 GLR 解析器，但遇到以下问题：
我尝试解析的语言允许布尔表达式，包括关系（<、>、<=、...）和布尔组合（and、or、not）。现在的问题是该语言还允许在关系的右侧有多个算术表达式……并且它们是使用用于布尔组合的相同 AND 标记组合的！这是一个非常愚蠢的语言设计，但我无法更改它。
所以你可以有 a > b and c 这应该等同于 (a > b) and (a > c) 你也可以有 a > b and c > d 这应该等同于 (a > b) and (c > d)
由此导致的 S/R 冲突在这个例子中已经很明显了：在使用先行 and 读取 a > b 之后，您可以将 a > b 简化为布尔表达式，并且等待另一个布尔表达式，或者您可以移动 and 并等待另一个算术表达式。
我的语法目前是这样的：
booleanexpression
: relation
| booleanexpression TOK_AND booleanexpression
...
;
relation
: arithmeticexpression TOK_GT maxtree
...
;
maxtree
: arithmeticexpression
| maxtree TOK_AND maxtree
...
;
对于任何 k，语言显然不是 LR(k)，因为 S/R 冲突不可能使用任何常量 k-lookahead 解析，因为中间的算术表达式可以有任意多个标记。因此，我打开了 GLR 解析。
但是当我尝试用这个解析 a > b and c 时，我可以在我的调试输出中看到解析器的行为如下：
- 它读取
a 并在前瞻 > 中将 a 减少为 arithmeticexpression
- 它读取
b 并在前瞻 and 中将 b 减少为 arithmeticexpression 然后已经减少为 maxtree
- 它将
a > b 减少为 relation
- 它读取
c 并将其缩减为 arithmeticexpression
然后什么都没有发生！ and c 显然被丢弃了——调试输出没有显示对这些标记的任何操作。甚至没有错误消息。相应的 if 语句在我的 AST 中不存在（我仍然得到一个 AST，因为我有错误恢复）。
我认为，看完b，应该有2个堆栈。但是 b 不应减少。或者至少它应该给我一些错误消息（"language is ambiguous" 没问题，我以前看过该消息 - 我不明白为什么它不适用于此处）。任何人都可以理解这一点吗？
稍微看一下语法，可以看出这里的主要问题是下一个算术表达式之后是否有
- 另一个关系标记（然后你应该减少）
- 另一个布尔组合（然后你应该移位）
- boolean/arithmetic 表达式语法之外的标记（如 THEN），它会终止表达式，你也应该 shift
你能想出一种不同的语法来以更好/更确定的方式捕捉情况吗？你会如何处理这个问题？我目前正在考虑使语法更加从右到左，比如
booleanexpression : relation AND booleanexpression
maxtree : arithmeticexpression AND maxtree
etc.
我认为这会让野牛更喜欢移动并且只会先在右边减少。也许通过使用不同的非终结符，它会允许在算术表达式后面有一个准"lookahead"...
旁注：GnuCOBOL 通过仅收集所有标记、将它们推送到中间堆栈并从那里手动构建表达式来处理此问题。这让我很沮丧，但我仍然希望他们这样做是因为 bison 在开始时不支持 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();
}
这个奇怪地在输入 a>b&c 上打印错误消息 "syntax error"。
能够通过使用优先级声明来简化语法确实很方便（有时）[注 1]，但它在使用 GLR 解析器时效果不佳，因为它会导致明确解析的早期拒绝。
优先级声明背后的想法是，它们使用简单的单标记先行和在可能的缩减和可能的移位之间配置的优先级来解决歧义（或者更准确地说，shift/reduce 冲突）。如果语法没有 shift/reduce 冲突，则不会使用优先级声明，但如果使用它们，它们将用于抑制移位或归约，具体取决于（静态）优先级关系。
Bison 生成的 GLR 解析器实际上并不能解决歧义，但它允许继续开发可能不正确的解析，直到歧义被语法解决为止。与优先权的使用不同，这是一个延迟的决议；有点慢但更强大。 （GLR 解析器可以生成包含所有可能解析的“解析森林”。但 Bison 没有实现此功能，因为它期望解析编程语言，并且与人类语言不同，编程语言不能有歧义。）
在您的语言中，不可能静态地解决 shift/reduce 冲突的不确定性，正如您在问题中指出的那样。您的语法根本不是 LR(1)，更不用说运算符优先级了，因此 GLR 解析是一种实用的解决方案。但是你必须让 GLR 完成它的工作。通过优先级比较过早地消除其中一个似是而非的解析将阻止 GLR 算法稍后考虑它。如果您设法消除唯一可能正确的解析，这将特别严重。
在您的语法中，无法定义 rel 产生式和 & 符号之间的优先关系，因为不存在优先关系。在某些句子中，rel减少需要取胜；换句话说，转变应该获胜。由于语法没有歧义，GLR最终会弄清楚哪个是哪个，只要shift和reduce都允许进行。
在您的完整语言中，布尔表达式和算术表达式都具有类似于运算符优先级的东西，但仅在它们各自的领域内。运算符优先级解析器（以及等效的 yacc/bison 的优先级声明）通过消除不同非终端之间的差异来工作；它无法处理像您这样的语法，其中某些运算符在不同域（或不同域之间）具有不同的优先级。
幸运的是，优先声明的这种特殊用法只是一种捷径；它没有给语法任何额外的权力，并且可以通过创建新的非终端来轻松和机械地实现，每个优先级别一个。替代语法不会有歧义。经典示例是 expr/term/factor 语法，您可以在任何包含解析算术表达式的教科书或教程中找到它。这里我也提供了优先语法来比较：
%left '+' '-'
%left '*' '/'
%% %%
expr : term
| expr '+' term expr: expr '+' expr
| expr '-' term | expr '-' expr
term : factor
| term '*' factor | expr '*' expr
| term '/' factor | expr '/' expr
factor: ID | ID
| '(' expr ')' | '(' expr ')'
在你的最小示例中，已经有足够多的非终端，不需要发明新的，所以我只是按照上面的模型重写了它。
我保留了我写的动作，以防风格对你有用。请注意，这种样式会像筛子一样泄漏内存，但这对于快速测试来说是可以的：
%code top {
#define _GNU_SOURCE 1
}
%{
#include <ctype.h>
#include <stdio.h>
#include <string.h>
int yylex(void);
void yyerror(const char* msg);
%}
%define api.value.type { char* }
%glr-parser
%token ID
%%
input : %empty
| input bool '\n' { puts(); }
arith : ID
maxtree : arith
| maxtree '&' arith { asprintf(&$$, "[maxtree& %s %s]", , ); }
rel : arith '>' maxtree { asprintf(&$$, "[COMP %s %s]", , ); }
bool : rel
| bool '&' rel { asprintf(&$$, "[AND %s %s]", , ); }
%%
void yyerror(const char* msg) { printf("%s\n", msg); }
int yylex(void) {
int c;
while ((c = getchar ()) == ' ' || c == '\t');
if (isalpha(c)) {
*(yylval = strdup(" ")) = c;
return ID;
}
else return c == EOF ? 0 : c;
}
int main (int argc, char** argv) {
#if YYDEBUG
if (argc > 1 && strncmp(argv[1], "-d", 2) == 0) yydebug = 1;
#endif
return yyparse();
}
这是一个示例 运行。请注意来自 bison 的关于 shift/reduce 冲突的警告。如果没有这样的警告，GLR 解析器可能就没有必要了，因为没有冲突的文法是确定性的。 （另一方面，由于 bison 的 GLR 实现针对确定性进行了优化，因此在确定性语言上使用 GLR 解析器的成本不会太高。）
$ bison -t -o glr_prec.c glr_prec.y
glr_prec.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
$ gcc -Wall -o glr_prec glr_prec.c
$ ./glr_prec
a>b
[COMP a b]
a>b & c
[COMP a [maxtree& b c]]
a>b & c>d
[AND [COMP a b] [COMP c d]]
a>b & c & c>d
[AND [COMP a [maxtree& b c]] [COMP c d]]
a>b & c>d & e
[AND [COMP a b] [COMP c [maxtree& d e]]]
$
备注
虽然当您了解实际发生的事情时优先级声明很方便，但人们有很大的倾向只是从他们在 Internet 上找到的其他一些语法中进行货物崇拜，而且并不罕见语法也是从其他地方学来的。当优先级声明没有按预期工作时，下一步就是随机修改它们，以期找到一个有效的配置。有时这会成功，通常会留下不必要的碎屑，这些碎屑会再次被货物崇拜。
因此，尽管在某些情况下优先声明确实简化了语法并且明确的实现会复杂得多（例如在具有许多不同复合语句类型的语言中的悬空 else 解析），但我已经我仍然发现自己不建议使用它们。
在 中，我写了我希望对优先算法的一个很好的解释（如果不是，请告诉我它的不足之处）。
欢迎来到 COBOL 的精彩世界。我可能是错的，但你可能有一些
这里有额外的问题。 COBOL 中的 A > B AND C 等表达式不明确
直到你知道 C 是如何声明的。考虑以下程序：
IDENTIFICATION DIVISION.
PROGRAM-ID EXAMPLE.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 A PIC 9 VALUE 2.
01 B PIC 9 VALUE 1.
01 W PIC 9 VALUE 3.
88 C VALUE 3.
PROCEDURE DIVISION.
IF A > B AND C
DISPLAY 'A > B AND 88 LEVEL C is TRUE because W = ' W
ELSE
DISPLAY 'A not > B or 88 LEVEL C is not TRUE'
END-IF
DISPLAY 'A: ' A ' B: ' B ' W:' W
GOBACK
.
这个程序的输出是：
A > B AND 88 LEVEL C is TRUE because W = 3
A: 2 B: 1 W: 3
本质上表达式：A > B AND C 等同于：A > B AND W = 3。有C
以类似于 A 和 B 的方式定义，语义将
已经：A > B AND A > C，在本例中为 FALSE。
上面提到的代码运行良好，但我从未在我的真实项目中使用它，即使我看不出我的真实项目和这段代码之间的区别。
这让我发疯，但我刚刚在我的代码中发现了另一个问题，它阻止了这个方法的工作：
我在序言中有一个（不可否认的货物崇拜）%skeleton "lalr1.cc"，它再次禁用了 GLR 解析！
我需要将其替换为
%skeleton "glr.cc"
我正在 GNU bison 中开发 GLR 解析器，但遇到以下问题：
我尝试解析的语言允许布尔表达式，包括关系（<、>、<=、...）和布尔组合（and、or、not）。现在的问题是该语言还允许在关系的右侧有多个算术表达式……并且它们是使用用于布尔组合的相同 AND 标记组合的！这是一个非常愚蠢的语言设计，但我无法更改它。
所以你可以有 a > b and c 这应该等同于 (a > b) and (a > c) 你也可以有 a > b and c > d 这应该等同于 (a > b) and (c > d)
由此导致的 S/R 冲突在这个例子中已经很明显了：在使用先行 and 读取 a > b 之后，您可以将 a > b 简化为布尔表达式，并且等待另一个布尔表达式，或者您可以移动 and 并等待另一个算术表达式。
我的语法目前是这样的：
booleanexpression
: relation
| booleanexpression TOK_AND booleanexpression
...
;
relation
: arithmeticexpression TOK_GT maxtree
...
;
maxtree
: arithmeticexpression
| maxtree TOK_AND maxtree
...
;
对于任何 k，语言显然不是 LR(k)，因为 S/R 冲突不可能使用任何常量 k-lookahead 解析，因为中间的算术表达式可以有任意多个标记。因此，我打开了 GLR 解析。
但是当我尝试用这个解析 a > b and c 时，我可以在我的调试输出中看到解析器的行为如下：
- 它读取
a并在前瞻>中将a减少为arithmeticexpression - 它读取
b并在前瞻and中将b减少为arithmeticexpression然后已经减少为maxtree - 它将
a > b减少为relation - 它读取
c并将其缩减为arithmeticexpression
然后什么都没有发生！ and c 显然被丢弃了——调试输出没有显示对这些标记的任何操作。甚至没有错误消息。相应的 if 语句在我的 AST 中不存在（我仍然得到一个 AST，因为我有错误恢复）。
我认为，看完b，应该有2个堆栈。但是 b 不应减少。或者至少它应该给我一些错误消息（"language is ambiguous" 没问题，我以前看过该消息 - 我不明白为什么它不适用于此处）。任何人都可以理解这一点吗？
稍微看一下语法，可以看出这里的主要问题是下一个算术表达式之后是否有
- 另一个关系标记（然后你应该减少）
- 另一个布尔组合（然后你应该移位）
- boolean/arithmetic 表达式语法之外的标记（如 THEN），它会终止表达式，你也应该 shift
你能想出一种不同的语法来以更好/更确定的方式捕捉情况吗？你会如何处理这个问题？我目前正在考虑使语法更加从右到左，比如
booleanexpression : relation AND booleanexpression
maxtree : arithmeticexpression AND maxtree
etc.
我认为这会让野牛更喜欢移动并且只会先在右边减少。也许通过使用不同的非终结符，它会允许在算术表达式后面有一个准"lookahead"...
旁注：GnuCOBOL 通过仅收集所有标记、将它们推送到中间堆栈并从那里手动构建表达式来处理此问题。这让我很沮丧，但我仍然希望他们这样做是因为 bison 在开始时不支持 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();
}
这个奇怪地在输入 a>b&c 上打印错误消息 "syntax error"。
能够通过使用优先级声明来简化语法确实很方便（有时）[注 1]，但它在使用 GLR 解析器时效果不佳，因为它会导致明确解析的早期拒绝。
优先级声明背后的想法是，它们使用简单的单标记先行和在可能的缩减和可能的移位之间配置的优先级来解决歧义（或者更准确地说，shift/reduce 冲突）。如果语法没有 shift/reduce 冲突，则不会使用优先级声明，但如果使用它们，它们将用于抑制移位或归约，具体取决于（静态）优先级关系。
Bison 生成的 GLR 解析器实际上并不能解决歧义，但它允许继续开发可能不正确的解析，直到歧义被语法解决为止。与优先权的使用不同，这是一个延迟的决议；有点慢但更强大。 （GLR 解析器可以生成包含所有可能解析的“解析森林”。但 Bison 没有实现此功能，因为它期望解析编程语言，并且与人类语言不同，编程语言不能有歧义。）
在您的语言中，不可能静态地解决 shift/reduce 冲突的不确定性，正如您在问题中指出的那样。您的语法根本不是 LR(1)，更不用说运算符优先级了，因此 GLR 解析是一种实用的解决方案。但是你必须让 GLR 完成它的工作。通过优先级比较过早地消除其中一个似是而非的解析将阻止 GLR 算法稍后考虑它。如果您设法消除唯一可能正确的解析，这将特别严重。
在您的语法中，无法定义 rel 产生式和 & 符号之间的优先关系，因为不存在优先关系。在某些句子中，rel减少需要取胜；换句话说，转变应该获胜。由于语法没有歧义，GLR最终会弄清楚哪个是哪个，只要shift和reduce都允许进行。
在您的完整语言中，布尔表达式和算术表达式都具有类似于运算符优先级的东西，但仅在它们各自的领域内。运算符优先级解析器（以及等效的 yacc/bison 的优先级声明）通过消除不同非终端之间的差异来工作；它无法处理像您这样的语法，其中某些运算符在不同域（或不同域之间）具有不同的优先级。
幸运的是，优先声明的这种特殊用法只是一种捷径；它没有给语法任何额外的权力，并且可以通过创建新的非终端来轻松和机械地实现，每个优先级别一个。替代语法不会有歧义。经典示例是 expr/term/factor 语法，您可以在任何包含解析算术表达式的教科书或教程中找到它。这里我也提供了优先语法来比较：
%left '+' '-'
%left '*' '/'
%% %%
expr : term
| expr '+' term expr: expr '+' expr
| expr '-' term | expr '-' expr
term : factor
| term '*' factor | expr '*' expr
| term '/' factor | expr '/' expr
factor: ID | ID
| '(' expr ')' | '(' expr ')'
在你的最小示例中，已经有足够多的非终端，不需要发明新的，所以我只是按照上面的模型重写了它。
我保留了我写的动作，以防风格对你有用。请注意，这种样式会像筛子一样泄漏内存，但这对于快速测试来说是可以的：
%code top {
#define _GNU_SOURCE 1
}
%{
#include <ctype.h>
#include <stdio.h>
#include <string.h>
int yylex(void);
void yyerror(const char* msg);
%}
%define api.value.type { char* }
%glr-parser
%token ID
%%
input : %empty
| input bool '\n' { puts(); }
arith : ID
maxtree : arith
| maxtree '&' arith { asprintf(&$$, "[maxtree& %s %s]", , ); }
rel : arith '>' maxtree { asprintf(&$$, "[COMP %s %s]", , ); }
bool : rel
| bool '&' rel { asprintf(&$$, "[AND %s %s]", , ); }
%%
void yyerror(const char* msg) { printf("%s\n", msg); }
int yylex(void) {
int c;
while ((c = getchar ()) == ' ' || c == '\t');
if (isalpha(c)) {
*(yylval = strdup(" ")) = c;
return ID;
}
else return c == EOF ? 0 : c;
}
int main (int argc, char** argv) {
#if YYDEBUG
if (argc > 1 && strncmp(argv[1], "-d", 2) == 0) yydebug = 1;
#endif
return yyparse();
}
这是一个示例 运行。请注意来自 bison 的关于 shift/reduce 冲突的警告。如果没有这样的警告，GLR 解析器可能就没有必要了，因为没有冲突的文法是确定性的。 （另一方面，由于 bison 的 GLR 实现针对确定性进行了优化，因此在确定性语言上使用 GLR 解析器的成本不会太高。）
$ bison -t -o glr_prec.c glr_prec.y
glr_prec.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
$ gcc -Wall -o glr_prec glr_prec.c
$ ./glr_prec
a>b
[COMP a b]
a>b & c
[COMP a [maxtree& b c]]
a>b & c>d
[AND [COMP a b] [COMP c d]]
a>b & c & c>d
[AND [COMP a [maxtree& b c]] [COMP c d]]
a>b & c>d & e
[AND [COMP a b] [COMP c [maxtree& d e]]]
$
备注
虽然当您了解实际发生的事情时优先级声明很方便，但人们有很大的倾向只是从他们在 Internet 上找到的其他一些语法中进行货物崇拜，而且并不罕见语法也是从其他地方学来的。当优先级声明没有按预期工作时，下一步就是随机修改它们，以期找到一个有效的配置。有时这会成功，通常会留下不必要的碎屑，这些碎屑会再次被货物崇拜。
因此，尽管在某些情况下优先声明确实简化了语法并且明确的实现会复杂得多（例如在具有许多不同复合语句类型的语言中的悬空 else 解析），但我已经我仍然发现自己不建议使用它们。
在
欢迎来到 COBOL 的精彩世界。我可能是错的，但你可能有一些
这里有额外的问题。 COBOL 中的 A > B AND C 等表达式不明确
直到你知道 C 是如何声明的。考虑以下程序：
IDENTIFICATION DIVISION.
PROGRAM-ID EXAMPLE.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 A PIC 9 VALUE 2.
01 B PIC 9 VALUE 1.
01 W PIC 9 VALUE 3.
88 C VALUE 3.
PROCEDURE DIVISION.
IF A > B AND C
DISPLAY 'A > B AND 88 LEVEL C is TRUE because W = ' W
ELSE
DISPLAY 'A not > B or 88 LEVEL C is not TRUE'
END-IF
DISPLAY 'A: ' A ' B: ' B ' W:' W
GOBACK
.
这个程序的输出是：
A > B AND 88 LEVEL C is TRUE because W = 3
A: 2 B: 1 W: 3
本质上表达式：A > B AND C 等同于：A > B AND W = 3。有C
以类似于 A 和 B 的方式定义，语义将
已经：A > B AND A > C，在本例中为 FALSE。
上面提到的代码运行良好，但我从未在我的真实项目中使用它，即使我看不出我的真实项目和这段代码之间的区别。
这让我发疯，但我刚刚在我的代码中发现了另一个问题，它阻止了这个方法的工作：
我在序言中有一个（不可否认的货物崇拜）%skeleton "lalr1.cc"，它再次禁用了 GLR 解析！
我需要将其替换为
%skeleton "glr.cc"