問題タブ [context-free-grammar]

再帰下降パーサーは、説明が最も簡単であるだけでなく、設計と保守も最も簡単なようです。それらはLALR（1）文法に限定されず、コード自体は単なる人間によって理解することができます。対照的に、ボトムアップパーサーには認識できる文法に制限があり、特別なツールで生成する必要があります（それらを駆動するテーブルは手作業で生成することがほぼ不可能であるため）。

それでは、なぜボトムアップ（つまりシフトリデュース）解析がトップダウン（つまり再帰下降）解析よりも一般的であるのでしょうか？

コンテキストフリー言語をプッシュダウンオートマトンに変換するためのアプレットまたはプログラムをオンラインで見つけることができません...どんな助けでも大歓迎です。

私は最終試験に向けて勉強していて、ウィキペディアの文脈自由文法の記事を読んでいて、次の例に出くわしました。

左右の派生がよくわかります。この問題を解決しようとしたとき、開始記号から始めます

でも答えを見たらこんな感じでした

私の答えの何が問題なのかわかりませんか？最初の生産規則を 2 回使用する必要がありますか? 誰でもこれで私を助けてくれませんか。

すべての単語の言語Lの文脈自由文法（CFG）を見つけて、単語の各終端が、おそらく大きなアルファベットで偶数回出現するようにしますΣ

私の長いアプローチは（唯一の非終端記号はSです）：

これは正しいです？プロダクションは正しい単語を生成しますが、すべての単語を生成しますか？

編集：大きなアルファベットのCFGは、各端末が偶数回表示される言語を記述できますか？

EDIT_2：解が存在する場合、チョムスキー標準形が|Σ|で多項式になる可能性はありますか？？

次のルールで左再帰を削除するにはどうすればよいですか。

S -> aSAbb | aA

S -> SA | で実行する方法を理解しています。あ

これは S -> A になります | なので'; S' -> A | AS'、しかし端末はこの質問で私を怒らせます。

編集：

申し訳ありませんが、左再帰とは何かについて混乱していたようです。右側から左側のシンボルを削除する方法を尋ねる必要がありました。

AC プログラムのソース コードは、C 文法 (CFG で説明) に従って解析でき、最終的に多くの AST に変換できます。そのようなツールが存在するかどうかを検討しています。最初に、具体的な文字列値を持たないトークンを含む多くの AST をランダムに生成し、CFG に従ってトークンの型だけを生成することで、逆のことを行うことができます。正規表現のトークンの定義に従ってトークン。

最初のステップは、反復的な非端末置換のように見えると想像できます。これはランダムであり、特定の反復回数によって制限される可能性があります。2 番目のステップは、正規表現に従ってランダムな文字列を生成するだけです。

これを行うことができるツールはありますか？

重複の可能性：
cのどのバージョンで、括弧内のブロックが有効な値を返すために使用されていますか？

以下は、典型的なMAXマクロのタイプセーフバージョンです（これはgcc 4.4.5で動作します）。

ここで、この式max（a、b）が式の結果を返すことがわかります。

この式はブロック内にありますが。そこで、調査したところ、これが有効なCであることがわかりました。

誰かがこれが有効な文法である理由と（{statements}）の本当の振る舞いが何であるかを説明できますか？また、{123;}は有効な式ではなく、（{123;}）のみが有効であることに気付くでしょう。

この言語を生成するために文脈自由文法を設計しています:

最初の 2 つの文字列を次のように定義します。

そして、それらを組み合わせます：

しかし、その逆を文脈自由文法としてどのように表現すればよいのでしょうか?

Javaで実装されたCFGパーサーを探しています。問題は、私が自然言語を解析しようとしているということです。そして、そのうちの1つだけでなく、すべての可能な解析ツリー（あいまいさ）が必要です。私はすでにスタンフォードパーサーのような多くのNLPパーサーを研究しました。しかし、それらは主に統計データ（私が持っていないツリーバンク）を必要とし、それらを新しい言語に適応させることはかなり困難であり、十分に文書化されていません。ANTRLやJFlexなどのパーサジェネレータを見つけましたが、あいまいさを処理できるかどうかはわかりません。では、どのパーサジェネレータまたはJavaライブラリが私に最適ですか？前もって感謝します

Flex と Lemon を使用して、制約を解析する小さなパーサーを作成しています。Lemon は、私が取り除くことができなかったいくつかの構文解析の競合を報告しています。文脈自由文法で構文解析の競合を取り除くための特定のトリックはありますか?

文法は次のとおりです。

エラーは次のとおりです。

パーサー ジェネレーターのレポート全体はここにあります。http://pastebin.com/TRsV3WvK

ここで私が間違っていることを知っている人はいますか？これらの競合を無視できますか?