不幸的是,bison 确实坚持生成(单个)解析,因此您必须指定某种方式来合并模棱两可的解析。如果你不这样做,并且有不止一种可能的解析,bison 的 GLR 解析器确实会抱怨解析不明确。
如果您并不真正关心接受多个解析中的哪一个,那么让野牛屈服于您的意愿并不难。最简单的方法是为%dprec
每个可能模棱两可的产生式分配一个不同的值。然后,Bison 将选择恰好具有最佳优先级的任何适用产品。
你甚至可以让 bison 用一个简单的%merge
函数告诉你多个解析;野牛手册中有一个例子。(此功能的文档不是很好,但可能足以满足您的需求。如果没有,请随时提出更具体的问题。)
我对 DParser 没有太多经验,但是手册表明它在面对多个可能的解析时的行为是相似的:默认是抱怨,但您可以提供自己的琐碎合并功能:(引用来自 Section 12,歧义)
歧义会根据优先级和关联性自动解决。此外,当其他解决技术失败时,用户定义的歧义解决是可能的。默认的歧义处理程序会在未解决的歧义上产生致命错误。此行为可以替换为用户定义的解析器,其签名在dparse.h
.
这是第二个示例的示例野牛 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