很不幸,bison 确实坚持生成(单个)解析,因此您必须指定一种方法来合并模糊的解析。如果您不这样做,并且有多个可能的解析,则 bison 的 GLR 解析器确实会抱怨解析是模糊的。
如果您真的不在乎接受哪个多个解析,那么弯曲 bison 以符合您的意愿并不是太困难。最简单的方法是只为每个可能存在歧义的产生式分配不同的 %dprec。然后,bison 将选择具有最佳优先级的适用产生式。
您甚至可以通过一个简单的 %merge 函数让 bison 告诉您有关多个解析的信息;在
bison manual 中有一个示例。(该功能的文档不是很好,但可能足以满足您的需求。如果不行,请随时提出更具体的问题。)
我对DParser的经验不多,但是手册表明,当面临多个可能的解析时,它的行为类似:默认情况下会发出警告,但是您可以提供自己的简单合并函数:(引用来自第12节,歧义)
歧义根据优先级和结合性自动解决。此外,当其他解决技术失败时,可以使用用户定义的歧义解决方法。默认歧义处理程序在未解决歧义时会产生致命错误。此行为可以用提供在dparse.h
中的签名的用户定义解析器替换。
这是第二个例子的bison GLR语法示例。我省略了词法分析器,因为它并不重要(而且有点令人尴尬,因为我很匆忙)。
%{
int yylex();
void yyerror(const char* msg);
%}
%error-verbose
%glr-parser
%token WORD_A "a"
%token WORD_BOY "boy"
%token WORD_GIRL "girl"
%token WORD_IN "in"
%token WORD_LIKED "liked"
%token WORD_PARK "park"
%token WORD_SAW "saw"
%token WORD_TELESCOPE "telescope"
%token WORD_THE "the"
%token WORD_WITH "with"
%%
S : NP VP {puts("S: NP VP");} %dprec 1
| NPA VP {puts("S: NPA VP");} %dprec 2
;
NPA: D N {puts("NPA: D N");} %dprec 3
| NP PP {puts("NPA: NP PP");} %dprec 4
;
NP : D N {puts("NP: D N");} %dprec 6
| NP PP {puts("NP: NP PP");} %dprec 7
| NPA {puts("NP: NPA");} %dprec 10
;
VP : V NP {puts("VP: V NP ");} %dprec 11
| VP PP {puts("VP: VP PP");} %dprec 12
;
PP : P NP {puts("PP: P NP");} %dprec 14
;
D : "the" {puts("D: the");} %dprec 15
| "a" {puts("D: a");} %dprec 16
;
P : "in" {puts("P: in");} %dprec 17
| "with" {puts("P: with");} %dprec 18
;
V : "liked" {puts("V: liked");} %dprec 19
| "saw" {puts("V: saw");} %dprec 20
;
N : "girl" {puts("N: girl");} %dprec 21
| "boy" {puts("N: boy");} %dprec 22
| "park" {puts("N: park");} %dprec 23
| "saw" {puts("N: saw");} %dprec 24
| "telescope"{puts("N: telescope");} %dprec 25
;
%%
int main(int argc, char** argv) {
printf("yyparse returned %d\n", yyparse());
return 0;
}
编译:
$ make ambig2
bison30 -v -d -o ambig2.c ambig2.y
ambig2.y: warning: 6 shift/reduce conflicts [-Wconflicts-sr]
ambig2.y: warning: 10 reduce/reduce conflicts [-Wconflicts-rr]
gcc-4.8 -ggdb -Wall -D_POSIX_C_SOURCE=200809L -std=c99 -c -o ambig2.o ambig2.c
gcc-4.8 ambig2.o -o ambig2
rm ambig2.o ambig2.c
样例解析:
$ ./ambig2 <<<"a boy saw a girl"
D: a
N: boy
NPA: D N
V: saw
D: a
N: girl
NPA: D N
NP: NPA
VP: V NP
S: NPA VP
yyparse returned 0
$ ./ambig2 <<<"a saw saw the saw in a saw"
D: a
N: saw
NPA: D N
V: saw
D: the
N: saw
NPA: D N
NP: NPA
VP: V NP
P: in
D: a
N: saw
NPA: D N
NP: NPA
PP: P NP
VP: VP PP
S: NPA VP
yyparse returned 0
%dprec
解决方案需要大量键入,但除此之外是微不足道的;只需将%dprec N
添加到每个产生式的末尾,其中N
是唯一的整数(例如,您可以顺序编号)。 - rici