問題タブ [ll]

Mini Java のサブグラマー用に 26 ルールのグラマーがあります。この文法は、非オブジェクト指向であると想定されています。とにかく、私はそれを左因数分解し、左再帰を削除しようとしています。ただし、JFLAP でテストしたところ、LL(1) ではないことがわかりました。私は Aho-Sethi 本のアルゴリズムのすべてのステップに従いました。

ヒントを教えてください。

それぞれ<IDENTIFIER>が有効な Java 識別子であり<INTEGER-LITERAL>、単純な整数です。各eプロダクションはイプシロン プロダクションを表し$、最初のルールの はファイルの終わりマーカーです。

一般に、最適化された PEG パーサーは、最適化された LALR(1) または LL(k) パーサーよりも高速ではないという主張を見てきました。(もちろん、解析のパフォーマンスは特定の文法に依存します。)

PEGパーサーに特定の制限があるかどうかを知りたい.

特に、パーサー ジェネレーターに興味がありますが、特定のケースでパフォーマンスを向上させるために出力を微調整できると想定しています。また、パーサーは最適化されており、パフォーマンスを向上させるために必要な場合は、特定の文法を少し調整できると想定しています。

PLY を使用して Javascript ファイルを解析する Python プログラムを作成したいのですが、ECMAScript、PLY を使用する Javascript ルールを実装するパーサーのソースが見つかりませんでした。

私が見つけた唯一のものは、javascript と ecmascript を解析するいくつかの ANTLR 文法ファイルでした: http://www.antlr.org/grammar/1153976512034/ecmascriptA3.g http://www.antlr.org/grammar/1206736738015/JavaScript.g

ANTLR 文法ファイルを PLY ルールとして使用するように適合させることはできますか? はいの場合、どのように半自動で行うことができますか? 文法ファイルを解析する必要がありますか? これに別の回避策はありますか (つまり、ANTLR 文法ファイルを使用する以外に) はありますか?

これまで lex/yacc を使用していましたが、ANTLR に切り替えようとしています。主な懸念事項は、LALR である yacc とは異なり、ANTLR が LL(*) パーサーであることです。私はボトムアップで考えることに慣れていて、LL 文法の利点が正確にはわかりません。最近は LL 文法の方が理解しやすく、人気が高いと言われています。しかし、LR パーサーの方が強力なようです。たとえば、LL パーサーは左再帰を処理できませんが、いくつかの回避策があるようです。

では、問題は、LALR に対する LL 文法の利点は何ですか? 誰かが私にいくつかの例を教えていただければ幸いです。役に立つ記事へのリンクも素晴らしいでしょう。

事前にご協力いただきありがとうございます。

(これは素晴らしいリソースだと思います: LL パーサーは LR パーサーに対してどのような利点がありますか? ですが、いくつかの例があればもっと良かったでしょう。)

次の BNF 文法が LL(1) であるかどうかを確認してください。

ここで、S は開始記号であり、非端子 A と B はイプシロンに導き出すことができます。解析テーブルの 1 つのセルに 2 つ以上のプロダクションがある場合、文法は LL(1) ではありません。しかし、セルに既にイプシロンが含まれている場合、解析テーブルを作成するときに、それを新しい生成物に安全に置き換えることができるでしょうか?

簡単な例では、左再帰を削除してこの文法を LL 文法に変換する方法について混乱しています。どんなヒントでも大歓迎です。

このアルゴリズムを適用すると、次のようになります。

これは、パーサー用の C 疑似コードを生成するために機能するようです。

そして、単語の解析ツリーを生成するには: aabab:

まあ、それが正しいかどうかはわかりません...

私はPEG（Parsing Expression Grammar）パーサーを調査中です。私が調査しているトピックの1つは、他の解析手法との同等性です。

From Regular Expressions to Parsing Expression Grammarsで、正規表現を同等のPEGに変換することについての良い論文を見つけました。

私はLL(*)パーサーのための同様の治療法を見つけたいと思っていますが、まだ手ぶらで出てきています。1で説明した手法の多くは、変換の問題にも適用できるように思われますLL(*)が、私自身の分析に自信を持てるように、形式主義に十分に没頭していません。

あなたの集合的な助けをいただければ幸いです！

私はANTLRに比較的慣れていません。私は非常に簡単な文法を持っています:

ルックアヘッドとバックトラッキング (構文述語で機能する) の概念の基本は既に理解できたと思います。したがって、この文法は k=4 または backtrack=true で機能します。しかし、正確な違いは何ですか。主な問題は、いつ何を使用するかです。インターネットで答えを見つけようとしましたが、成功しませんでした。

ここでhttp://slkpg.byethost7.com/llkparse.html FOLLOW_k-Sets が定義されています

「文法における記号の文字列の FOLLOWk セットは、文法で導出可能な何らかのセンテンシャル形式の記号の文字列に続く、文法における k 長の終端記号文字列のセットです」

最初に、リンクの下の例に関する引用があります。文法4.2があります

と言われている：

しかし、私はなぜそうしないのか自問しています

たとえば、単一の b から派生する可能性があるためです。

さらに文法に関しては

セットがわからない

空、{ epsilon } 、または { a, aa } は、これらの文字列が派生可能であるためか、S の後に何が来るかが重要であり、S は開始記号であるため、その後ろには何も来ないため、FOLLOW2(S) と書く必要があります。 = \empyset または FOLLOW2(S) = { イプシロン }?

LL（3）がLR（2）のサブセットではないことを証明しようとしています。

直感的には簡単ですが、そのような文法を見つけることに直感を向けることはできません。

手を貸していただけませんか。助けてくれてありがとう