問題タブ [ambiguous-grammar]

あいまいな Marpa 文法とあいまいな入力文字列があるとします。

Marpa を使用して文字列を解析し、解析フォレストを作成できます。フォレスト内の各解析ツリーを反復処理することもできます。

しかし、パース フォレストに沿って反復処理するにはどうすればよいでしょうか。

私が何を意味するかを説明するには：

解析フォレストは一種のグラフであり、代替が分割されるノードと、代替が結合して「メイン ストリーム」になるノードを持つことができます。

これらが 1 つのパース フォレストの代替パース ツリーであるとします。

• A B1 C
• A B2 C
• A B3 B4 C

本流はあるがA……CあいまいなB部分がある。

もちろん、実際の解析では、分岐時に多くのレベルの分岐が存在する可能性があり、単一のメイン ストリームに再結合しないストリームが存在する場合があります。しかし、一般的には、2 つまたは多くの解釈に共通する多くの部分があります。

明確で曖昧なノードのチェーンに沿って反復するには、どのようなアプローチを使用できますか?

実際、グラフ全体を出力できますか?

基本の方言のantlr文法ファイルを書いています。そのほとんどは機能しているか、次に何をする必要があるかについて良い考えを持っています. ただし、等価テストと割り当ての両方に使用される「=」文字をどうすればよいか、まったくわかりません。

たとえば、これは有効なステートメントです

これは、x が 5 と等しいかどうかを評価し、y が 3 と等しい場合は、これらの結果に対して論理 AND を実行し、結果を t に割り当てます。

私の文法はこれを解析します。間違っていますが、あいまいさが解消されれば解決すると思います。

「=」文字の 2 つの使用方法を区別するにはどうすればよいですか?
1) 式から割り当てルールを削除し、コード生成中にビジターやリスナーの実装でこれらのケース (割り当てと等価テスト) を処理する必要がありますか?

2) すでに整理されているように文法を定義するより良い方法はありますか?

この言語の「機能」をどのように最適に実装するかについて、誰かが私を正しい方向に向けることができますか?

また、ANTLR4 の決定版ガイドと言語実装パターンを読んで、これに対する解決策を探しています。そこにあるかもしれませんが、私はまだ見つけていません。

以下は完全なパーサー文法です。ASSIGN トークンは現在「=」に設定されています。EQUAL は「==」に設定されています。

これがレクサー文法です。

質問

文脈自由文法 "S->SbS|ScS|a" が曖昧であることを、文字列 abaca に 2 つの構文木を与えることによって示します。

文字列がどのように曖昧なのかわかりませんか? 私はコンパイラと自己学習に関する本を読んでいたので、本でこの質問をしていましたが、困惑しています。

考えられる解決策

私の解決策が正しいかどうかを誰でも確認できますか。そうでない場合は、誰かが私を案内してください。

私は COOL (教室のオブジェクト指向言語) のパーサー/レクサーを書いています。次のリンクで文法を確認できます: (マニュアルの最後のページ)

http://theory.stanford.edu/~aiken/software/cool/cool-manual.pdf

ANTLR を使用してこのプログラムを作成しています。次の入力を使用して、次の出力が必要です。

入力:

出力:

しかし、私が得ている出力は次のとおりです。

ここに私のパーサー/レクサーコードがあります:

これは、ANTLR の COOL 文法のコード バージョンです。メインコードでコメントされている部分は曖昧さが解消され (意味はあいまいさが取り除かれます!)、2 番目の部分で左再帰が解放されます (数学規則)。

誰かがこれがどこで間違っているのか、そしてなぜ私は望ましい出力を得られないのか指摘できますか?

前もって感謝します！

述語を使用して文法を作成する必要があります。以下の文法は、特定のケースでは失敗します。

指定された入力に対して失敗します

結果部分の「name」キーの値として「create」を指定する必要があります。

どんな助けでも素晴らしいでしょう。

CFG が与えられた場合: S--> aS | Sa | b 2 つの異なる pars ツリーから作成できる文字列が見つかりません。

中間状態は再帰を残しましたが、それを排除せずに CFG のあいまいさを示す文字列はありますか? 誰でも助けてくれますか。

これを尋ねるのが適切なサイトかどうかはわかりません。しかし、私たちは文法の曖昧さについて研究しています。左端の派生と右端の派生を含む。私の練習問題はこれです：

曖昧にする方法はありますか？文法を曖昧にするためのヒントはありますか?