2

テキスト ファイルを解析するために私が書いた bison 文法では、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 つあります。通常、1 つの状態での競合はすべて、1 つの関連する問題です。


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は 1 つ以上の // / トークンのシーケンスである可能性があるTIMEためDATE、(eg) を含む入力がある場合DATA、それは最初のルールがであるか、2 番目のルールがである可能性があります。IDENTIFIERentry_prefix TIME DATAlog_entryTIME DATAbody_statementslog_entryDATAbody_statements

この場合のデフォルトの解決策は、2 番目の規則 ( を の一部として削減するのではなく、 の一部として扱うようにシフトする) を優先し、言語全体TIMEである「サブセット」になります。あいまいです。これは、一部の言語で見られる「ぶら下がっているelse」に似たケースであり、デフォルトのシフトがまさにあなたが望むものを実行する可能性があります。log_statementswordbody_statements

log_entry: entry_prefix TIME body_statementsこの競合を解消する最も簡単な方法は、ルールを取り除くことです。これは、デフォルトの解像度とは逆の効果があります。現在、TIME は常に BODY の一部と見なされます。TIME問題は、ボディのイニシャルである場合を別の方法で処理したい場合に、削減する別のルールがなくなったことです。TIME何か特別なことをする必要がある場合は、で始まるボディのアクションでチェックを行うことができます。


state 40
6 statement: statement . word
22 body_statements: statement .

これはもう 1 つのあいまいさの問題です。今回は、どこで終わり、section_bodyどこで始まっているのかわかりません。は 1 つ以上log_entryので構成され、それぞれの後に が続きます。上記のは 1 つ以上のトークンである場合がありますが、 は空である場合があります。したがって、単なる一連のトークンである がある場合、それは単一( no を使用) または一連のルール (それぞれが no を使用) として解析できます。reduce resolution に対するデフォルトのシフトは、 a を減らす前にできるだけ多くのトークンを single に入れることを優先するため、それを single として解析しますが、これはおそらく問題ありません。section_bodylog_entriesentry_prefixbody_statementsbody_statementswordentry_prefixsection_bodywordlog_entryentry_prefixlog_entryentry_prefixstatementbody_statementlog_entry

この競合を解消するには、文法をリファクタリングする必要があります。aの any の末尾は、noおよびの別のものstatementであるlog_entry可能性があるため、そのケースをほぼ排除する必要があります (これは、デフォルトの競合解決が行うことです)。2 番目のルールを削除して以前の競合を修正したと仮定すると、最初に unfactorを実行して、問題のあるケースを独自のルールにします。log_entryentry_prefixstatementbody_statementslog_entrylog_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

この競合は、先読みのあいまいさの問題です。トークンが aDATETIME現れる可能性があるため、 astatementを解析するときに、終端と終端/がどこで始まるtime_stampかを判断できません。デフォルトの解像度では、. a は a の直前の a の最後にのみ表示され、aは a で始まる可能性があるため、これでも問題ない可能性があります。statementDATETIMEDATE TIMEtime_stamptime_stampsection_headsection_bodysection_bodystatement


したがって、文法内のすべての競合は無視できる場合があり、無視することが望ましい場合もあります。これは、文法を書き直してそれらを取り除くよりも簡単だからです。一方、競合が存在すると、文法を変更するのが難しくなります。なぜなら、変更するたびに、すべての競合を再調査して、問題がないことを確認する必要があるからです。


「競合のデフォルトの解決」と「状態のデフォルトのアクション」には紛らわしい問題があります。これら 2 つのデフォルトは互いに何の関係もありません。1 つ目はパーサーを構築するときに yacc/bison によって行われる決定であり、2 つ目は実行時のパーサーによる決定です。したがって、出力ファイルに次のような状態がある場合:

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 を削減することであると判断したことを示しています。シフト アクションは、先読みトークンが の場合にのみ可能ですがTIME、削減アクションは、時間。そのため、テーブル サイズを最小化するために、reduce アクションの可能な次のトークンをすべて列挙するのではなく、単に$default、前のアクションが先読みトークンと一致しない限り、パーサーが reduce アクションを実行することを意味します。$defaultアクションは常に状態の最後のアクションになります。

したがって、この状態のパーサーのコードは、先読みトークンに一致するアクションを見つけてそのアクションを実行するまで、アクションのリストを実行します。TIME [reduce... アクションは、この状態で競合があったことと、そのバイソンがreduce先読みがTIME. したがって、この状態用に構築された実際のアクション テーブルには、1 つのアクション (トークンのシフトTIME) とそれに続くデフォルト アクション (任意のトークンのリデュース) があります。

の後にすべてのトークンが正当であるとは限らないという事実にもかかわらず、これを行うことに注意してくださいword。これは、次のトークンが不正なものであっても、リダクションが入力からそれを読み取らない (まだ先読みである) ため、後の状態 (潜在的に複数のデフォルト リダクションの後) でエラーが表示される (および報告される) ためです。

于 2014-08-14T16:32:46.953 に答える