2

我为解析文本文件而编写的野牛语法给了我 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
        {

        }
        ;

请帮我解决这个问题..

谢谢

4

1 回答 1

7

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

abody_statements可以是一个或多个// /TIME标记DATE的序列,因此当您输入 (eg)时,它可以是带有 as the 的第一条规则,也可能是带有as的第二条规则。DATAIDENTIFIERentry_prefix TIME DATAlog_entryTIME DATAbody_statementslog_entryDATAbody_statements

在这种情况下,默认解析将支持第二条规则(将其TIME视为 a 的一部分log_statements而不是将其减少为worda 的一部分body_statements),并将产生一个作为整个语言的“子集”——唯一的解析会错过都是暧昧的。这种情况类似于在某些语言中出现的“悬空的 else”,其中默认转换可能完全符合您的要求。

要消除这种冲突,最简单的方法就是摆脱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结束和另一个开始的地方。Asection_body由一个或多个 组成log_entries,每一个都是 anentry_prefix后跟 a body_statementsbody_statements如上所述,the可以是一个或多个word令牌,而 anentry_prefix可以是空的。因此,如果您的 asection_body只是一个word标记序列,则可以将其解析为单个log_entry(不带 no entry_prefix)或log_entry规则序列,每个规则都带 no entry_prefixstatement在 reduce 分辨率上的默认转换将有利于在减少 a 之前将尽可能多的标记放入单个中body_statement,因此将其解析为单个log_entry,这可能是可以的。

为了消除这种冲突,您需要重构语法。由于 a 中 any 的尾部statement可能log_entry是另一个log_entry没有entry_prefixstatement的尾部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

这个冲突是一个前瞻歧义问题——因为DATETIME标记可以出现在 a 中statement,当解析 a 时time_stamp它无法分辨statement结束和终端DATE/TIME开始的位置。默认分辨率将导致将任何DATE TIME对视为time_stamp. 现在因为time_stamp只出现在 a 的末尾,section_head就在 a 之前section_body,并且 asection_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)

这告诉您,bison 已确定从该状态可能的操作是转移到状态 48 或减少规则 9。转移操作仅在前瞻标记为 时才有可能TIME,而对许多前瞻标记包括减少操作是可能的时间。因此,为了最小化表大小,而不是为 reduce 操作枚举所有可能的下一个标记,它只是说$default——这意味着只要没有先前的操作与前瞻标记匹配,解析器就会执行 reduce 操作。该$default动作将始终是该状态中的最后一个动作。

因此,处于这种状态的解析器代码将沿着动作列表运行,直到找到与前瞻标记匹配的动作并执行该动作。包含 ... 动作只是为了TIME [reduce清楚地表明在这种状态下存在冲突,并且野牛通过reduce在前瞻为 时禁止该动作来解决它TIME。因此,为该状态构建的实际操作表将只有一个操作(在令牌上移位TIME),然后是一个默认操作(在任何令牌上减少)。

请注意,尽管并非所有令牌在 a 之后都是合法的word,但它仍然会执行此操作,但它仍然会减少任何令牌。这是因为即使下一个标记是非法的,因为归约不会从输入中读取它(它仍然是前瞻),稍后的状态(在可能的多个默认归约之后)将看到(并报告)错误。

于 2014-08-14T16:32:46.953 回答