1

JFlex と Cup を使用して JavaScript っぽい言語用のパーサーを作成しようとしていますが、これらの致命的なシフト/リデュースの問題とリデュース/リデュースの問題にいくつか問題があります。

私は徹底的に検索し、たくさんの例を見つけましたが、これらを私の文法に当てはめることができません. これまでの私の理解では、これらの問題は、パーサーが区別できないため、どちらの方法を取るべきかを判断できないためです。

私の文法は次のとおりです。

INPUT::= PROGRAM;

PROGRAM::= FUNCTION NEWLINE PROGRAM
| NEWLINE PROGRAM;

FUNCTION ::= function OPTIONAL id p_izq ARG p_der NEWLINE l_izq NEWLINE BODY l_der;

    OPTIONAL ::= 
    | TYPE;


    TYPE::= integer 
    | boolean

    ARG ::=  
    | TYPE id MORE_ARGS;

    MORE_ARGS ::=   
    | colon TYPE id MORE_ARGS;


    NEWLINE ::= salto NEWLINE 
    | ;

    BODY ::=  ;

いくつかの競合が発生していますが、これらの 2 つは単なる例です。

 Warning : *** Shift/Reduce conflict found in state #5
 between NEWLINE ::= (*) 
 and     NEWLINE ::= (*) salto NEWLINE 
 under symbol salto
 Resolved in favor of shifting.

 Warning : *** Shift/Reduce conflict found in state #0
 between NEWLINE ::= (*) 
 and     FUNCTION ::= (*) function OPTIONAL id p_izq ARG p_der NEWLINE l_izq NEWLINE BODY l_der 
 under symbol function
 Resolved in favor of shifting.

PS: 文法ははるかに複雑ですが、これらのシフト/リデュースの問題がどのように解決されるかを見れば、残りを修正できると思います。

回答ありがとうございます。

4

1 に答える 1

5

PROGRAM役に立たない（技術的な意味で）。つまり、文を生成することはできません。

PROGRAM::= FUNCTION NEWLINE PROGRAM
       |   NEWLINE PROGRAM;

両方のプロダクションPROGRAMは再帰的です。非端末が有用であるためには、最終的に端末の文字列を生成できる必要があり、それを行うには、少なくとも 1 つの非再帰的な生成が必要です。そうしないと、再帰は決して終了できません。CUPがこれについてあなたに言及しなかったことに驚いています. または、そうで、警告を無視することを選択した可能性があります。

それは問題です-役に立たない非端末は実際には何にも一致しないため、最終的には解析エラーになります-しかし、それはあなたが報告している解析の競合ではありません. 競合は、同じプロダクションの別の機能から発生します。これは、0 で割ることができないという事実に関連しています。

無についてのことは、無はいくらあっても無であるということです。つまり、何もないものがたくさんあり、誰かがやって来て、正確にいくつの何もないかを尋ねた場合、少し問題が発生します。「0 * たくさん」から「たくさん」を返すには、計算する必要があるからです。 「0 / 0」であり、明確な値ではありません。(あなたが 2 をたくさん持っていて、誰かがあなたに 2 をいくつ持っているか尋ねたとしても、それは問題にはなりません: たくさんの 2 が 40 になると仮定してください; 40 / 2 = 20 は簡単に計算できます。 20 * 2 = 40 であるため、完璧です。)

したがって、ここには算術はありません。記号の文字列があります。残念なことに、シンボルを含まない文字列は実際には見えません。たとえば、アラビアの数学者が何も記述できないことの価値に気付くまで、0 は何千年もの間存在していました。

これがすべて起こっているのは、あなたが持っているということです

PROGRAM::= ... something ...
       |   NEWLINE PROGRAM;

しかしNEWLINE、何も生産することは許されません。

NEWLINE ::= salto NEWLINE 
        |   ;

したがって、 の 2 番目の再帰的な生成はPROGRAM、何も追加しない可能性があります。また、生成は再帰的であるため、何度も何も追加されない可能性があります。しかし、パーサーは決定論的である必要があります: 存在する無の数を正確に知る必要があるため、それぞれのNEWLINE無を非終端に還元し、新しい非終端を還元できPROGRAMます。そして、追加する何もないものがいくつあるか本当にわかりません。

要するに、オプションの無と繰り返される無はあいまいです。言語に何も挿入しない場合は、パーサーが無を明確に分析できる唯一の方法であるため、有数の無が固定されていることを確認する必要があります。

さて、その特定の再帰の唯一のポイントは（私が見る限り）空の改行で終了するステートメントを許可することです（改行のために表示されますが、何もしません）。そして、何も回避しないように再帰を変更することでそれを行うことができます:

PROGRAM ::= ...
        |   salto PROGRAM;

現在の問題とは関係ありませんが、CUP は LALR パーサー ジェネレーターであり、再帰降下パーサーが左再帰を処理できないことについてインターネットで学んだことや読んだことはすべて当てはまりません。(構文解析手法の教え方に関する暴言を削除したので、私が残したヒントから復元する必要があります。) CUP や yacc/bison などのボトムアップ パーサー ジェネレーターは、左再帰が大好きです。もちろん、右再帰も処理できますが、左再帰以外の再帰ごとにスタック領域を浪費する必要があるため、しぶしぶです。. したがって、欠乏に対処するために文法を歪める必要はありません。文法を自然に書くだけで幸せになります。(したがって、何かの「残り」を表す非終端記号が必要になることはめったにありません。)

PD: 1934 年のオペラ「ポーギーとベス」の歌を文化的に具体的に参照したものはほとんどありません。

于 2017-06-04T05:29:31.083 に答える