Jac*_*kzz 2 parsing bison shift-reduce-conflict
我为解析文本文件而编写的野牛语法给了我10个移位/减少冲突.parser.output文件对我没有帮助.该文件提供了以下信息:
State 38 conflicts: 5 shift/reduce
State 40 conflicts: 4 shift/reduce
State 46 conflicts: 1 shift/reduce
Grammar
0 $accept: session $end
1 session: boot_data section_start
2 boot_data: head_desc statement head_desc head_desc
3 head_desc: OPEN_TOK BOOT_TOK statement CLOSE_TOK
4 | OPEN_TOK statement CLOSE_TOK
5 statement: word
6 | statement word
7 word: IDENTIFIER
8 | TIME
9 | DATE
10 | DATA
11 section_start: section_details
12 | section_start section_details
13 | section_start head_desc section_details
14 $@1: /* empty */
15 section_details: $@1 section_head section_body section_end
16 section_head: START_TOK head_desc START_TOK time_stamp
17 time_stamp: statement DATE TIME
18 section_body: log_entry
19 | section_body log_entry
20 log_entry: entry_prefix body_statements
21 | entry_prefix TIME body_statements
22 body_statements: statement
23 | head_desc
24 entry_prefix: ERROR_TOK
25 | WARN_TOK
26 | /* empty */
27 $@2: /* empty */
28 section_end: END_TOK statement $@2 END_TOK head_desc
state 38
8 word: TIME .
21 log_entry: entry_prefix TIME . body_statements
OPEN_TOK shift, and go to state 1
TIME shift, and go to state 6
DATE shift, and go to state 7
DATA shift, and go to state 8
IDENTIFIER shift, and go to state 9
OPEN_TOK [reduce using rule 8 (word)]
TIME [reduce using rule 8 (word)]
DATE [reduce using rule 8 (word)]
DATA [reduce using rule 8 (word)]
IDENTIFIER [reduce using rule 8 (word)]
$default reduce using rule 8 (word)
head_desc go to state 39
statement go to state 40
word go to state 11
body_statements go to state 45
state 39
23 body_statements: head_desc .
$default reduce using rule 23 (body_statements)
state 40
6 statement: statement . word
22 body_statements: statement .
TIME shift, and go to state 6
DATE shift, and go to state 7
DATA shift, and go to state 8
IDENTIFIER shift, and go to state 9
TIME [reduce using rule 22 (body_statements)]
DATE [reduce using rule 22 (body_statements)]
DATA [reduce using rule 22 (body_statements)]
IDENTIFIER [reduce using rule 22 (body_statements)]
$default reduce using rule 22 (body_statements)
word go to state 19
state 46
9 word: DATE .
17 time_stamp: statement DATE . TIME
TIME shift, and go to state 48
TIME [reduce using rule 9 (word)]
$default reduce using rule 9 (word)
我的语法的等价部分是:
statement : word
{
printf("WORD\n");
$$=$1;
}
|statement word
{
printf("STATEMENTS\n");
$$=$1;
printf("STATEMENT VALUE== %s\n\n",$$);
}
;
word : IDENTIFIER
{
printf("IDENTIFIER\n");
$$=$1;
}
|TIME
{
printf("TIME\n");
$$=$1;
}
|DATE
{
printf("DATE\n");
$$=$1;
}
|DATA
{
}
;
section_start : section_details
{
printf("SINGLE SECTIONS\n");
}
|section_start section_details
{
printf("MULTIPLE SECTIONS\n");
}
|section_start head_desc section_details
;
section_details :
{
fprintf(fp,"\n%d:\n",set_count);
}
section_head section_body section_end
{
printf("SECTION DETAILS\n");
set_count++;
}
;
section_head : START_TOK head_desc START_TOK statement time_stamp
{
printf("SECTION HEAD...\n\n%s===\n\n%s\n",$2,$4);
fprintf(fp,"%s\n",$4);
}
;
time_stamp : DATET TIME
{
}
;
section_body :log_entry
{
}
|section_body log_entry
{
}
;
log_entry : entry_prefix body_statements
{
}
|entry_prefix TIME body_statements
{
}
;
body_statements : statement
{
}
|head_desc
{
}
;
请帮我解决这个问题..
谢谢
yacc/bison解析器中的冲突意味着语法不是LALR(1) - 这通常意味着某些内容不明确或需要多于1个前瞻标记.默认分辨率是选择始终转换为缩小,或选择始终缩小第一个规则(用于减少/减少冲突),这将导致解析器识别语法描述的语言的子集.这可能是也可能不是 - 在模糊语法的情况下,通常情况是"子集"实际上是整个语言,并且默认分辨率会消除不明确的情况.但是,对于需要更多前瞻的情况以及一些不明确的情况,默认解析将导致无法解析语言中的某些内容.
要弄清楚在任何给定冲突中出现了什么问题,该.output文件通常会为您提供所需的一切.在您的情况下,您有3个冲突状态 - 通常单个州的冲突都是一个相关的问题.
state 38
8 word: TIME .
21 log_entry: entry_prefix TIME . body_statements
这种冲突是规则之间的模糊性log_entry和body_statements:
log_entry: entry_prefix body_statements
| entry_prefix TIME body_statements
一个body_statements可以是一个或更多的序列TIME/ DATE/ DATA/ IDENTIFIER令牌,所以当你有(例如)的输入entry_prefix TIME DATA,它可以是第一log_entry与规则TIME DATA作为body_statements或第二log_entry只规则DATA作为body_statements.
在这种情况下,默认解决方案将有利于第二个规则(转而将其TIME视为一部分,log_statements而不是将其简化为worda的一部分body_statements),并将导致整个语言的"子集" - 唯一的解析将被遗漏的是暧昧的.这种情况类似于某些语言中显示的"悬挂其他",默认转移可能完全符合您的要求.
要消除这种冲突,最简单的方法就是摆脱log_entry: entry_prefix TIME body_statements规则.这与默认分辨率具有相反的效果 - 现在TIME将始终被视为BODY的一部分.问题是,如果你想以不同的方式处理作为TIME身体初始的情况,你现在没有单独的规则来减少.TIME如果你需要做一些特别的事情,你可以检查一下身体的动作.
state 40
6 statement: statement . word
22 body_statements: statement .
这是另一个模棱两可的问题,这次section_body它无法分辨出哪一个log_entry结束而另一个结束.A section_body由一个或多个组成log_entries,每个组合entry_prefix后跟一个body_statements.在body_statements以上所指出可以是一个或多个word令牌,而一个entry_prefix可能是空的.因此,如果你section_body只有一个word令牌序列,它可以被解析为单个log_entry(没有entry_prefix)或一系列log_entry规则,每个都没有entry_prefix.默认转换为降低分辨率将有利于statement在减少a之前将尽可能多的令牌放入单个中body_statement,因此将其解析为单个log_entry,这可能是正常的.
要消除这种冲突,您需要重构语法.由于statementa 中任何一个的尾部log_entry可能是另一个log_entry没有entry_prefix和statementfor body_statements,你几乎需要消除这种情况(这是默认的冲突解决方案所做的).假设您通过删除第二个log_entry规则修复了先前的冲突,首先log_entry要解决问题,使其成为自己的规则:
log_entry: ERROR_TOK body_statements
| WARN_TOK body_statements
| head_desc
initial_log_entry: log_entry
| statements
现在更改section_body规则,使其仅使用第一个分割规则:
section_body: initial_log_entry
| section_body log_entry
冲突就消失了.
state 46
9 word: DATE .
17 time_stamp: statement DATE . TIME
这种冲突是一种前瞻性的歧义问题 - 因为DATE和TIME解密可以出现在一个statement,当解析time_stamp它时无法分辨出statement终点和终端DATE/ TIME开始的位置.默认分辨率将导致处理DATE TIME被视为结束的任何一对time_stamp.现在既然time_stamp只出现在a section_head之前section_body,而a section_body可能以a开头,那么statement这也可能没问题.
所以很可能你的语法中的所有冲突都是可忽略的,甚至可能这样做,因为这比重写语法以摆脱它们更简单.另一方面,冲突的存在使得修改语法变得更加困难,因为任何时候你都需要重新检查所有冲突以确保它们仍然是良性的.
"冲突的默认解决方案"和"状态中的默认操作"存在一个令人困惑的问题.这两个默认值彼此无关 - 第一个是yacc/bison在构建解析器时做出的决定,第二个是解析器在运行时做出的决定.所以当你在输出文件中有一个状态时:
state 46
9 word: DATE .
17 time_stamp: statement DATE . TIME
TIME shift, and go to state 48
TIME [reduce using rule 9 (word)]
$default reduce using rule 9 (word)
这是告诉你,野牛已经确定,从这种状态可能的行动要么转移到状态48或减少规则9.换档动作只可能是超前记号IS TIME,而降低作用是可能的许多先行令牌包括时间.因此,在为减少行动最大限度地减少表的大小,而不是枚举所有可能的下一个令牌的利益,它只是说$default-这意味着解析器会做,只要没有先前的动作超前记号匹配的降低作用.该$default操作将始终是该州的最后一个操作.
因此,处于此状态的解析器代码将在操作列表中向下运行,直到找到与前瞻标记匹配并执行该操作的操作.该TIME [reduce只包括...的行动,使之清楚,有在这种状态下发生冲突和野牛通过禁止行动解决它reduce的时候超前的TIME.因此,为此状态构造的实际操作表将只有一个操作(转移令牌TIME),然后是默认操作(减少任何令牌).
请注意,尽管事实并非所有令牌在a之后都是合法的word,但它仍会对任何令牌进行减少.这是因为即使下一个令牌是非法的,因为减少不会从输入中读取它(它仍然是前瞻),稍后的状态(在可能多次默认减少之后)将看到(并报告)错误.