問題タブ [ll]

私は最近、パーサー（言語/文脈自由文法用）がどのように機能するかを自分自身に教えようとしていますが、1つを除いて、そのほとんどは理にかなっているようです。特にLL（k）文法に注目しています。このアルゴリズムでは、2つの主要なアルゴリズムがLLパーサー（スタック/解析テーブルを使用）と再帰下降パーサー（単に再帰を使用）のようです。

私が見る限り、再帰下降アルゴリズムはすべてのLL（k）文法で機能し、場合によってはそれ以上で機能しますが、LLパーサーはすべてのLL（k）文法で機能します。ただし、再帰下降パーサーは、LLパーサーよりも実装がはるかに簡単です（LLパーサーがLRパーサーよりも単純であるのと同じです）。

だから私の質問は、どちらかのアルゴリズムを使用するときに遭遇する可能性のある利点/問題は何ですか？同じ文法セットで機能し、実装が難しいのに、なぜ再帰下降よりもLLを選ぶのでしょうか。

これは、しばらくの間私を悩ませてきたものです。ANTLR を使用して、次のテキストを以下の HTML に解析するにはどうすればよいですか? 私はこれについて頭を包むことができないようです。

何か案は？

マークダウン:

出力 HTML:

Antlr文法に左再帰の問題があります。なぜ問題があるのか​​は理解できたと思いますが、解決策は思いつきません。問題は、データ型ルールの最後の行にあります。私はあなたが見ることができるように文法全体を含めました：

私はこの問題を解決する機能を提供するAntlrの作品を使用して開発しています-しかし残念ながらそれはうまくいかないようです：s

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

ありがとう。

編集：

これが私が実装/解析しようとしている言語の例です

したがって、たとえば：

この表現を考えると：

3 + 2 + 2 * 2 = ?

14だろう？

FIRST セットと FOLLOW セットとは何ですか? それらは解析で何に使用されますか? トップダウンまたはボトムアップのパーサーに使用されますか?

次の一連の文法規則について、FIRST および FOLLOW SETS について説明してもらえますか。

こんにちはスタック オーバー フロー メンバーです。

私はコンパイラクラスのために勉強しています。トップダウン パーサーは左再帰を避け、右再帰に変換する必要があることを理解しました。

質問は、

a) トップダウン パーサーが LL に等しく、ボトムアップ パーサーが LR に等しいことを理解していますか?

b) 左再帰は自分自身を呼び出すルールであることがわかりました ex) Expr :== Expr '+' Term | Expr を見つける無限ループを引き起こす項。とにかく、C または Java での入力を考慮するサンプル コードはありますか? ( パーサーやスキャナーのコードはいらない ) 必要なのは、左再帰による無限ループが発生するセンテンシャル形式のコード例です。

c) トップダウン パーサーで右再帰を使用する方法で実際に何が違いますか?

ANS c) バックトラックの必要性をなくす。しかし、他の何か？

ANS b)x - 2 * yだけでなく、他の何か? これはバックトラックの解析方法で動作するためです。

非左再帰と左再帰の両方を発見した事例。

左再帰文法

非左再帰文法

どちらも無限ループに陥っています。

専門家の皆様、ありがとうございました。

今日のパーサー生成ツールで LL パーサーが相対的に人気を博しているのは、LR パーサーよりも LL パーサーが優れている点は何ですか?

Wikipediaによると、LR 解析は LL よりも優れているようです。

LR 構文解析は LL 構文解析よりも広い範囲の言語を処理でき、エラー報告にも優れています。つまり、入力が文法に準拠していない場合に構文エラーをできるだけ早く検出します。これは、バックトラッキングのために文法の別のブランチにエラー検出を延期する可能性のある LL(k) (またはさらに悪い場合は LL(*) パーサー) とは対照的であり、多くの場合、長い共通の接頭辞を使用した選言全体でエラーをローカライズするのが難しくなります。 .

注: これは宿題ではありません。Antlr が LL パーサー ジェネレーターであることを知ったときは驚きました (名前に「LR」が含まれているにもかかわらず!)。

パーサーを手動で作成する必要があります。LL(*) と LR のどちらかを選択できません (Earley を試してみてはいかがでしょうか?)。LL の文法はかなり難しいので、ボトムアップ解析を使用する必要がありますか?

私はSABLECC用のこの（動作する）LALR文法を持っています：

ANTLR（LLパーサジェネレーター）を使用するXTextに変換しようとしました。この2つの左再帰ルールの変換に問題があります。

どうすればいいですか？演算子の優先順位で作業する必要があると思いますが、厳密には、LLの方法で考えることはできません。

現在、プログラミング言語用の（非常に）小さなインタープリター/コンパイラーを作成しようとしています。言語の構文を設定したので、言語の文法を書き留める必要があります。少し調査した結果、LL(1) パーサーが最も使いやすいと思われるため、LL(1) パーサーを使用するつもりです。

私はこの分野には不慣れですが、収集した内容から、BNF または EBNF を使用して構文を形式化することを強くお勧めします。ただし、すべての文法が LL(1) パーサーを使用した実装に適しているわけではないようです。したがって、LL(1) 形式で文法を記述するための正しい (または推奨される) アプローチは何かと考えていました。

助けてくれてありがとう、チャーリー。

PS: Haskell の Parsec ライブラリを使用してパーサーを作成するつもりです。

編集: また、SK ロジックによると、Parsec は無限先読み (LL(k) ?) を処理できますが、質問は依然としてそのタイプの文法を表していると思います。