問題タブ [shift-reduce]

shift-reduce 解析について学習しようとしています。ANSI C Yacc grammarに触発された、操作の順序を強制する再帰規則を使用する次の文法があるとします。

そして、shift-reduce 解析を使用して 1+2 を解析したいと考えています。まず、1 が NUMBER としてシフトされます。私の質問は、P、次に M、次に A、最後に S に還元されるのかということです。どこで停止するかをどのように知るのですか？

それが S までずっと還元され、それから '+' をシフトするとします。これで、以下を含むスタックができました。

「2」をシフトすると、リダクションは次のようになります。

ここで、最後の行のどちらかの側で、S は P、M、A、または NUMBER である可能性があり、任意の組み合わせがテキストの正しい表現であるという意味で有効です。パーサーはどのようにしてそれを「知る」のですか

式全体を A、次に S に還元できるようにするには? 言い換えれば、次のトークンをシフトする前に削減を停止することをどのように知るのでしょうか? これは LR パーサー生成における重要な問題ですか?

編集：質問への追加は次のとおりです。

を解析するとします1+2*3。一部のシフト/リデュース操作は次のとおりです。

これは正しいですか (確かに、まだ完全には解析されていません)? さらに、1 シンボルによる先読みは、 を読み取った後に避けられない構文エラーが発生するため、に還元A+Mしないことも教えてくれますか?A*3

私は bison を使用して C でパーサーを作成しています。これまでに試したすべての状況で正しく動作するように見えますが、2 項演算子 (単項 NOT 演算子の場合は 1 つ) で多数のシフト/リデュース警告が表示されます。良い）。

bison --verbose を使用して .y ファイルを実行すると、次のように表示されます。

二項演算子を実際に解析する問題は見られませんが、とにかくシフト/削減の問題を解決する必要があるようです。競合がどこにあるのかわかりません - set_existence プロダクションは完全に無関係のようです。私の最善の推測 (暗闇でのショット) は、EQ が二項演算子 (等価比較) および代入 (たとえば、"foo = bar = baz;" が設定される) として使用されるという事実と関係がある可能性があるということです。 bar と baz が等しいかどうかに基づいて、foo を true/false に変換します)。等価比較を == ("foo = bar==baz;") に変更すると、パーサーは期待どおりに動作しますが、同じシフト/削減の競合が発生します。

編集：結合性が指定されています：

私は、一見単純なシフト/削減の競合に無駄に取り組んでいます。当然、競合を無視すればパーサーは正常に機能しますが、ルールを再編成した方がはるかに安全だと感じます。ここでは、比較的複雑な文法を単一の競合に単純化しました。

yaccのverboseオプションを使用すると、前述の競合のある状態を説明する次の出力ファイルを取得します。

助けてくれてありがとう。

のような単純な文法が与えられます

最初の3つのトークンをシフトしてから、4番目のトークンを調べてどのルールを減らすかを確認することと、3つのトークンの先読みを実行してどのルールを減らすかを確認することの違いは何ですか？

ここに私のコードがあります:

私の入力文字列は次のとおりです。+selector1.selector2||-selector4->selector4

この入力の解析ツリーは次のようになると予想されます。

yacc によって生成された私のプログラムは、次のような出力を提供します。

プログラムが shift&& reduce once の実行を停止すると、yylex() からこれ以上シンボルを取得できないように見えますが、スタック内の残りのシンボルを削減してL||-P->C、コード内で解析ツリー全体を生成できるようになると期待しています。

私の期待される出力は次のとおりです。

提供されたスペイン語モデルで Stanford Shift Reduce Parser を使用しようとしています。ただし、レキシカライズされたパーサーとは異なり、lexparser.bat/sh で確認できるように、適切なフラグ -outputFormat typedDependencies を送信したにもかかわらず、TypedDependencies を取得できないことに気付きました。

念のため、これは私がフラグを渡し、パーサーを作成するために使用している Java コードです。

ありがとうございました

nlp を使用してセンチメントを分析しようとしています。私が使用している stanford-nlp のバージョンは 3.4.1 です。処理するジャンク データがあり、デフォルトの PCFG ファイルを使用して処理するのに約 45 秒かかるようです。

次に例を示します。

ここでの提案に基づいて、shift-reduce パーサーで再試行しました。

shift-reduce モデルをダウンロードしてクラスパスに配置する必要があります。モデル クラスが読み込まれていますが、null ポインター例外がスローされています。何か考えや提案はありますか？

私は、コンパイラー設計の主題に対してシフト削減アルゴリズムを実行しています。これがコードです。

行にコメントするとprintf("Stack = %s\nQueue = %s\n", stack, str);、うまくいきます。しかし、コメントを外すと、コードが返されます3221225477。

ところで。これはデキュー関数です:

そして addChar 関数:

そして最後に関数を置き換えます。

PS。prod配列:

正と負の小数を解析しようとしています。

最初の 2 つのルールを含めるとシフト/リデュースの競合が発生しますが、競合が発生しないように文法を記述する方法がわかりません。私はレモンパーサーを使用しています。

編集: .out ファイルからの競合

編集 2: 問題を引き起こす最小限の文法