問題タブ [lalr]

次の (簡略化された) Bison 文法は、reduce reduce conflict を生成します。

問題はわかります。先読みのトークンが 1 つしかないため、 が であるか(an_idである'(' expr ')'かを判別することは不可能fnです。しかし、どうすれば解決できますか？

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

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

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

LALR（1）パーサージェネレーターであるLemonでコンパイルされます。

エラーメッセージは次のとおりです。

デバッグ出力は次のとおりです。

いくつかのパーサーとレクサー生成ツール (Lex と Bison に似ていますが、C# 用) を使用して、後で評価できる抽象構文ツリーに文字列を解析するプログラムを生成しています。

私はエラー回復を行いたいと思っていました (つまり、生成された抽象文ツリーで、欠落しているトークンなどがあることを報告します)。生成された文法を構造化するために 2 つのアプローチを念頭に置いていましたが、どちらのアプローチが優れているか、より柔軟であるか、または競合が発生しないか疑問に思っていました (.y および .lex ファイルは、電卓の記述に基づいて生成されます)。

電卓の説明により、ユーザーは端末/正規表現と演算子の配置、および結合性を指定できます。次のようなものです：

(優先順位は、TerminalとNonTerminalが追加された順序で指定されます。"Add"は、リフレクションを介して発見されたメソッドの名前です。基本的には、抽象構文ツリーで演算子を呼び出すものを NonTerminal に伝えます。)

アプローチ 1 : (任意の式に対して空のルールを許可する)

a端末です。 @空です。

アプローチ 2 : (開始ルールに空のルールのみを許可する)

これは、各アプローチを使用した悪い入力の左端の導出を示す例です。

入力： (a +

アプローチ 1 :

アプローチ 2 :

A -> A - Bアプローチ 2 のコーディングははるかに困難です (減算/単項負の演算子を検討してください。単純に減算を見て、最初にそれを取り出してAエラーを報告することはできません。A -> - Bこれは単項演算子に有効であるためです)。私は今朝、アプローチ 2 をコーディングしました。文法の問題があり、アプローチ 1 のように空のルールを使用すると、コードの観点から物事がはるかに単純になることがわかりましたが、私の主な関心事は、プログラマーが電卓の説明を次のように作成するときに、どのアプローチが文法の問題を最小限に抑えるかです。上で説明した。

式を表す文法があります。簡単にするために、次のようにしましょう。

、a、+、*が私(の)アルファベットの文字です。

上記のルールは、適切な演算順序と結合規則を使用して、括弧、乗算、および加算を含む有効な算術式を生成できます。

私の目標は、私のアルファベットの文字を 0 個以上含むすべての文字列を受け入れることです。ここに私の制約があります：

• 文法は、アルファベットの 0 文字以上を含むすべての文字列を「受け入れる」必要があります。
• 新しい端末は、アルゴリズムによって入力に導入および挿入できます。(端末を明示的に指定するEOFと、何らかの理由で、有効な式を超える余分なトークンを検出するのに役立つことがわかりました。)
• 新しい生産ルールが導入される場合があります。新しいルールはエラー フラグになります (つまり、文字列がエラー フラグを使用して解析された場合、文字列は受け入れられますが、意味的にはエラーと見なされます)。
• 新たに導入された端末が挿入されるように、生産ルールが変更される場合があります。
• 文法は、少なくとも Lex/Yacc のようなツールで処理できる LALR(1) でなければなりません (Lex/Yacc と互換性があるにもかかわらず、ダングリング else 問題は非 LALR(1) を必要とすることを思い出すと)。

さらに、さまざまな種類のエラー (2 項演算の引数の欠落、括弧の欠落 - 左または右 - 許容可能な式を超える余分なトークンなど) に対応する追加のルールが必要です。私の質問に答えて、そうでなければエラー報告には役に立たないすべての入力を「受け入れる」簡単な方法があるかもしれないからです。

これらのルールが有用であることがわかりましたが、それらが私の制約に違反しているかどうかはわかりません:

ここ$で、 は明示的なEOFトークンで、@は空の文字列です。

私の質問が明確ではなかった場合: 制約内で文法を変更して、すべての入力を受け入れるという目標を達成するにはどうすればよいですか? ルールは目標を満たしていますか?

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 文法ファイルを使用する以外に) はありますか?

私は現在、いくつかの言語のパーサーを作成中です。私はこの言語の文法を与えられましたが、この文法にはいくつかの左再帰と非 LL(*) 構造が含まれているため、ANTLR はバックトラッキングを使用してもうまく機能しません。

これらの左再帰と非 LL(*) 構成を削除することは、一見したよりも難しいため、LR(k) または LALR(k) パーサー ジェネレーターを試してみたいと思います。k が高いほど良い。

これらの要件を満たすパーサージェネレーターを誰かに勧めてもらえますか?

• 生成されたパーサーは、ある程度高い（または任意の）ｋを持つＬＲ（ｋ）パーサー、または少なくともある程度高いｋを持つＬＡＬＲ（ｋ）パーサーであることが好ましい。
• 生成されたパーサーは C または C++ で記述されており、C で記述されている場合は C++ コードにリンク可能です。
• ANTLR に似た機能セット (特に AST の書き換え) があればよいでしょう。
• パフォーマンスは最も差し迫った問題ではありません。生成されたパーサーは、多くのメモリと CPU パワーを備えたデスクトップ マシンで使用することを目的としています。

ありがとう、
ジョスト

PS: 自分でググることができないので質問しているわけではありませんが、自分でいくつかのジェネレーターをテストする時間が残っていないためです。したがって、推奨されるパーサー ジェネレーターの使用経験がある場合にのみ回答してください。

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

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

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

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

たとえば、scala プロジェクトで bison によって生成された Java ファイルを使用できることはわかっていますが、ネイティブの「文法から scala」への LALR(1) ジェネレーターはありますか?

これは、実際的な問題というよりも、「原則として」の問題です。Yacc がプロダクションを削減し、定義されたレクサーから新しいトークンを読み取る順序です。つまり、次のトークンのセットがあるとします。

Yacc は、そのセマンティクス内で、レクサーからトークンを読み取ることができますか?次のような一連のプロダクションが与えられた場合、単一のものにLESS_THAN還元される前に、レクサーからトークンを読み取ることができますか?INTEGER BEGIN INTEGER_VALUE

これらがセマンティックアクションで定義されている場合、この変更のルールはありますか?