問題タブ [shift-reduce-conflict]

Jisonにパーサーを実装しようとしています。パーサーは、JSON オブジェクト:{ a: 1 }とブロック:の両方をサポートしていますif (true) { statement(); }。

私の文法は次のようになります。

空のオブジェクトと空のブロックの両方をサポートする必要があるため、との{}両方にルールがあります。blockobjectExpression

動作しますが、次のような多くの警告を出力します。

これらの警告を修正または抑制するにはどうすればよいですか?

与えられた文脈自由文法について:

LR(1) になるように文法を書き直すにはどうすればよいですか?
現在の文法では、入力 "id : .id" を解析するときにシフト/リデュースの競合があります。パーサーの入力ポインターです。
この文法は、正規表現 (id:(id)*)+ を満たす言語を生成します。

パーサーが何かが単項演算子であるか二項演算子であるかを整理しようとすると、シフト/削減の競合が継続的に発生します。

私はたくさんのトークンを持っていることを知っており、最終的にはそれらを使用します。式の文法を機能させようとしているだけです。ここに私が得ているシフト/縮小エラーがあります

私はアイデアを使い果たしました。私が得ることができる助けをいただければ幸いです。

Haskell のように、通常の中置操作と中置セクションを含む文法の yacc のような実装 (特に ocamlyacc を使用) に問題があります。私はこれらすべてが文法的であることを望みます:

ただし、結合性/優先順位の宣言をいじっても、これを機能させることができませんでした。問題が発生している場所は grammar.output で確認できますが (削減したい場所に移動しています)、思い通りに進むように誘導することはできませんでした。これは、問題の単純化されたデモンストレーションです。

lex.mll には次のものがあります。

main.ml には次のものがあります。

そしてparse.mly（問題があるところ）には次のものがあります：

それを実行ocamlyaccすると、 があることがわかります1 shift/reduce conflict。特に、詳細ログの関連部分は次のとおりです。

コンパイルされたプログラムを実行すると、次のすべてが正しく解析されます。

しかし、次のように失敗します:

一方、HIGH優先度の高いダミー トークンを作成する場合:

次に%prec HIGH、ルール 9 を適用します。

その場合(1+2)は解析しますが、し(1+)ません。

shift/reduce 競合の一般的な背景を理解しています。この解析の課題を解決するために交渉する方法がわかりません。

文法をコンパイルしようとすると、2 つの shift/reduce エラーが発生します。

私は2シフト/削減を取得します

状態 38 の競合: 1 シフト/削減 状態 139 の競合: 1 シフト/削減

特定の状態は次のとおりです。

誰かがこのエラーを修正する方法を説明してもらえますか?私はそれが優先順位と関係があることを知っています.

状態 19 でシフト/リデュースの競合が 1 つあります。「識別子」のさまざまな出現に問題がある可能性があると思いますが、バイソン レポートを理解し、競合を解決するのに苦労しています。以下は、状態情報を含むバイソンレポートが続く私の文法です。

バイソン レポート:

Happy LALR パーサー ジェネレーターを使用してメソッド (Java のような) の文法を定義しようとしています

ここ、

• MD: メソッド宣言
• VD: 変数宣言
• S: ステートメント
• T：タイプ
• I: 識別子
• E: 式

他のすべてのトークンは端末です。

メソッド内では、変数宣言はステートメントの先頭とその後で行われます。

ご覧のとおり、型が識別子 (I) である型クラスの変数宣言が存在する可能性があるため、VD は I から開始できます。ステートメントは、変数への割り当てと変数名が I であるため、I から開始することもできます
。問題は、VD と S の両方が I から開始できることです。したがって、最初のプロダクションでは、シフト/リデュースの競合が発生します。

この問題を解決するために、文法やその他のパーサー ジェネレーターのトリックを書き直す方法はありますか?

演算子の結合性と優先順位を指定しました。問題を説明するための最小限の情報のみを説明しました。さらに情報が必要な場合はお知らせください。

アップデート：

以下は文法ファイルです

Shift-Reduce の競合と状態の詳細を含む Happy パーサーによって生成された .info ファイル

私がパーサーを書いている言語には、ここで関連する 3 つの構成要素があります。ordで表される演算子は、TOK_ORD文字式を整数式にキャストし、 と[ ]は.、C と同様にそれぞれインデックス アクセスとフィールド アクセスに使用されます。

以下は私の優先ルールからの抜粋です。

expr私の文法には、式を表す非終端記号があります。文法からの関連するスニペットを次に示します (は、ファイルTOK_IDENTで定義された識別子の正規表現です)。.l

bison 出力ファイルからの shift/reduce 競合に関する情報は次のとおりです。

参考までに州 92 および 93:

シフト/リデュースの競合が発生する理由がわかりません。私の文法では、インデックスとフィールドへのアクセスが よりも優先されるように明確に定義されていますがord、それだけでは十分ではないようです。

ご参考までに、はい、これは宿題ですが、課題は既に提出され、採点されています。何が起こっているのかをよりよく理解できるように、戻ってシフト/削減の競合を修正しようとしています。