シフト/リダクションの競合の解決

Question

私はPLYを使用して、thisの文法を解析しています。リンクされた仕様で使用されているEBNFのメタグラフを実装しましたが、PLYは複数のシフト/リダクションの競合を報告します。

文法：

Rule 0  S' -> grammar 
Rule 1  grammar -> prod_list 
Rule 2  grammar -> empty 
Rule 3  prod_list -> prod 
Rule 4  prod_list -> prod prod_list 
Rule 5  prod -> id : : = rule_list 
Rule 6  rule_list -> rule 
Rule 7  rule_list -> rule rule_list 
Rule 8  rule -> rule_simple 
Rule 9  rule -> rule_group 
Rule 10 rule -> rule_opt 
Rule 11 rule -> rule_rep0 
Rule 12 rule -> rule_rep1 
Rule 13 rule -> rule_alt 
Rule 14 rule -> rule_except 
Rule 15 rule_simple -> terminal 
Rule 16 rule_simple -> id 
Rule 17 rule_simple -> char_range 
Rule 18 rule_group -> (rule_list) 
Rule 19 rule_opt -> rule_simple ? 
Rule 20 rule_opt -> rule_group ? 
Rule 21 rule_rep0 -> rule_simple * 
Rule 22 rule_rep0 -> rule_group * 
Rule 23 rule_rep1 -> rule_simple + 
Rule 24 rule_rep1 -> rule_group + 
Rule 25 rule_alt -> rule | rule 
Rule 26 rule_except -> rule - rule_simple 
Rule 27 rule_except -> rule - rule_group 
Rule 28 terminal -> SQ string_no_sq SQ 
Rule 29 terminal -> DQ string_no_dq DQ 
Rule 30 string_no_sq -> LETTER string_no_sq 
Rule 31 string_no_sq -> DIGIT string_no_sq 
Rule 32 string_no_sq -> SYMBOL string_no_sq 
Rule 33 string_no_sq -> DQ string_no_sq 
Rule 34 string_no_sq -> + string_no_sq 
Rule 35 string_no_sq -> * string_no_sq 
Rule 36 string_no_sq -> (string_no_sq 
Rule 37 string_no_sq ->) string_no_sq 
Rule 38 string_no_sq -> ? string_no_sq 
Rule 39 string_no_sq -> | string_no_sq 
Rule 40 string_no_sq -> [ string_no_sq 
Rule 41 string_no_sq -> ] string_no_sq 
Rule 42 string_no_sq -> - string_no_sq 
Rule 43 string_no_sq -> : string_no_sq 
Rule 44 string_no_sq -> = string_no_sq 
Rule 45 string_no_sq -> empty 
Rule 46 string_no_dq -> LETTER string_no_dq 
Rule 47 string_no_dq -> DIGIT string_no_dq 
Rule 48 string_no_dq -> SYMBOL string_no_dq 
Rule 49 string_no_dq -> SQ string_no_dq 
Rule 50 string_no_dq -> + string_no_dq 
Rule 51 string_no_dq -> * string_no_dq 
Rule 52 string_no_dq -> (string_no_dq 
Rule 53 string_no_dq ->) string_no_dq 
Rule 54 string_no_dq -> ? string_no_dq 
Rule 55 string_no_dq -> | string_no_dq 
Rule 56 string_no_dq -> [ string_no_dq 
Rule 57 string_no_dq -> ] string_no_dq 
Rule 58 string_no_dq -> - string_no_dq 
Rule 59 string_no_dq -> : string_no_dq 
Rule 60 string_no_dq -> = string_no_dq 
Rule 61 string_no_dq -> empty 
Rule 62 id -> LETTER LETTER id 
Rule 63 id -> LETTER DIGIT id 
Rule 64 id -> LETTER 
Rule 65 id -> DIGIT 
Rule 66 rest_of_id -> LETTER rest_of_id 
Rule 67 rest_of_id -> DIGIT rest_of_id 
Rule 68 rest_of_id -> empty 
Rule 69 char_range -> [ UNI_CH - UNI_CH ] 
Rule 70 empty -> <empty> 

競合：

id : LETTER LETTER id 
      | LETTER DIGIT id 
      | LETTER 
      | DIGIT 

。

state 4 

    (62) id -> LETTER . LETTER id 
    (63) id -> LETTER . DIGIT id 
    (64) id -> LETTER . 

    ! shift/reduce conflict for LETTER resolved as shift 
    ! shift/reduce conflict for DIGIT resolved as shift 
    LETTER   shift and go to state 10 
    DIGIT   shift and go to state 9 
    |    reduce using rule 64 (id -> LETTER .) 
    -    reduce using rule 64 (id -> LETTER .) 
    (    reduce using rule 64 (id -> LETTER .) 
    SQ    reduce using rule 64 (id -> LETTER .) 
    DQ    reduce using rule 64 (id -> LETTER .) 
    [    reduce using rule 64 (id -> LETTER .) 
    $end   reduce using rule 64 (id -> LETTER .) 
    )    reduce using rule 64 (id -> LETTER .) 
    :    reduce using rule 64 (id -> LETTER .) 
    ?    reduce using rule 64 (id -> LETTER .) 
    *    reduce using rule 64 (id -> LETTER .) 
    +    reduce using rule 64 (id -> LETTER .) 

    ! LETTER   [ reduce using rule 64 (id -> LETTER .) ] 
    ! DIGIT   [ reduce using rule 64 (id -> LETTER .) ] 

idルールはプロダクションIDは文字で始まることを保証することになっています。

次の競合：

rule_alt  : rule '|' rule 

。

smiliar一つに接続

state 113 

    (25) rule_alt -> rule | rule . 
    (25) rule_alt -> rule . | rule 
    (26) rule_except -> rule . - rule_simple 
    (27) rule_except -> rule . - rule_group 

    ! shift/reduce conflict for | resolved as shift 
    ! shift/reduce conflict for - resolved as shift 
    (    reduce using rule 25 (rule_alt -> rule | rule .) 
    SQ    reduce using rule 25 (rule_alt -> rule | rule .) 
    DQ    reduce using rule 25 (rule_alt -> rule | rule .) 
    LETTER   reduce using rule 25 (rule_alt -> rule | rule .) 
    DIGIT   reduce using rule 25 (rule_alt -> rule | rule .) 
    [    reduce using rule 25 (rule_alt -> rule | rule .) 
    )    reduce using rule 25 (rule_alt -> rule | rule .) 
    $end   reduce using rule 25 (rule_alt -> rule | rule .) 
    |    shift and go to state 76 
    -    shift and go to state 74 

    ! |    [ reduce using rule 25 (rule_alt -> rule | rule .) ] 
    ! -    [ reduce using rule 25 (rule_alt -> rule | rule .) ] 

：

rule_except  : rule '-' rule_simple 
       | rule '-' rule_group 

私はこれらをどのように修正すればよいですか？

Answer 1

通常のスキャナー/パーサーアーキテクチャを真剣に考えなければなりません。それ以外の場合は、空白を処理する方法を見つける必要があります。

このように、空白を完全に無視しているようです。つまり、パーサーはthree consecutive identifiersの空白を認識できません。彼らはasoupofundifferentiatedlettersとして一緒に実行されて表示され、元の意図が何だったかを知る方法がありません。これは、あなたの文法が深く曖昧になります。なぜなら、文法において、2つの識別子は、何かが互いに区別されることを前提にお互いに続くことができるからです。あいまいな文法は常にLRの矛盾を引き起こします。

レクサーによって認識される識別子（および他の複数文字のトークン）がであることが多く、より簡単です。それ以外の場合は、文法を書き換えて空白がある場所（句読点の前後など）を指定するか、必要なものを指定する必要があります（two identifiersなど）。

正規表現を使用してスキャナ内の識別子を識別することも、あなたの文法や識別子を持つ他の問題が削除されます：

id -> LETTER LETTER id 
id -> LETTER DIGIT id 
id -> LETTER 

をこれらのルールは、数字だけでも中に表示される文字の数が奇数であるとidが必要ですポジション。従ってa1bはidであるが、ab1またはabまたはa1ではない。私はそれがあなたが意味するものではないと確信しています。

左回帰を避けようとしているようです。代わりに、左回帰を受け入れる必要があります。ボトムアップパーサーは、PLYのように、左回帰を愛します。 （。彼らは過度のパーサスタック使用量のコストで、右再帰を扱う）だから、あなたが本当に欲しいものです：

id: LETTER | id LETTER | id DIGIT 

は、同様の変更が必要な文法の他の場所があります。

もう1つの競合は、オペレータの優先順位の非正統的な処理によって引き起こされます。これは、左再帰を回避しようとした結果でもあります。 EBNF演算子は、代数演算子と同様に単純な優先順位スキームで解析できます。ただし、優先順位宣言（%leftおよびフレンド）の使用は、「見えない」連結演算子のために複雑になります。一般的に、標準のexpr/factor/term代数文法のように明示的な優先順位を使用する方が簡単です。 -演算子の優先順位に関する情報の不足に上記の対応で

item: id 
    | terminal 
    | '(' rule ')' 
term: item 
    | item '*' 
    | item '+' 
    | item '?' 
seq : term 
    | seq term 
alt : seq 
    | alt '|' seq 
except: term '-' term 
rule: alt 
    | except 

exceptの取り扱い：あなたのケースでは、同等のようなものになるだろう。これは、明示的なカッコのない-と|演算子の組み合わせを効果的に禁止することによって表現されます。

また、あなたがシフト/ここに競合を削減していることがわかります。

# The following will create a problem 
prod: id "::=" rule 
prod_list 
    : prod 
    | prod_list prod 

（注：私は左再帰の問題を作成しないことを書いているという事実。）

あいまいではありませんが、単一の先読みトークンで左から右に解析できるわけではありません。 idが現在解析中のシーケンスの一部であるか、idの後にトークンが表示されるまで、新しいプロダクションの開始点であるかを知ることができないため、2つのトークンが必要です。::=の場合、idは新しい生産の開始点であり、現在のルールに移行すべきではありません。この問題の通常の解決策は、レクサーのハッキングです。レクサーは、先読みトークンを1つ追加する機能によってラップされます。id ::=をタイプdefinitionという単一のトークンとして発行することができます。他のSOの質問には、さまざまなLRパーサーのこのハックの例がいくつかあります。あなたがXMLを解析するために、EBNFのためのパーサを構築したい理由

---

は、そのすべてを言って、私は本当に理解していません。 EBNFから作業パーサを構築することは基本的にPLYが行いますが、 "E"パートは実装されないため、?、*、+、および-演算子を使用するルールを書き直さなければなりません。 -演算子は一般的ではありませんが、これは自動的に処理できますが、単純ではありません。少しだけE BNFのルールをBNFに書き換えてからPLYを使うほうが簡単でしょう。しかし、あなたが挑戦を探しているなら、それに行きましょう。

Answer 2

まず、文法をスラブに翻訳したことがあります。入力ストリームをトークン化する必要があります。

通常、IDのようなものは、文法の一部として解析するのではなく、字句解析によって識別する端末となり

id : LETTER LETTER id 
     | LETTER DIGIT id 
     | LETTER 
     | DIGIT 

それは、ターミナルの下であなたが持っているすべてのもののように見えるべきではありません文法の一部である。

次に、文法で正しい再帰を使用します。 LALRは左と右の両方の再帰で動作しますが、左の再帰で小さなテーブルが得られます。

はあなたが識別子の構文解析を主張した場合、あなたがほしいと入力文字列のAAに

があると、より

id : id LETTER 
    | id DIGIT 
    | LETTER 

のようなものは最後に、Shiftキーを押しながら削減競合は必ずしも基づくものではありません。彼らは頻繁に演算子の先例によって解決される数値式で発生します。

Reduce-Reduceの競合は常に悪いです。