解析ルール - それらをうまく連携させる方法

Question

そこで私はパーサーを作成しています。速度よりも柔軟性を優先し、文法を簡単に記述できるようにしたいと考えています。トリッキーな回避ルールはありません（yacc/bison などで行う必要がある、競合などを解決するための偽のルール）

トークンの固定セットを使用して手動でコーディングされたレクサーがあります (例:PLUS、DECIMAL、STRING_LIT、NAME など)、現時点では 3 種類のルールがあります。

• トークンルール:特定のトークンに一致します
• シーケンスルール:ルールの順序付きリストに一致します
• グループルール:リストの任意のルールに一致します

たとえば、トークン NAME (おおよそ /[A-Za-z][A-Za-z0-9_]*/) に一致する TokenRule 'varAccess' と、[ に一致する SequenceRule 'assignment' があるとします。式、TokenRule(PLUS)、式]。

Expression は、「assignment」または「varAccess」のいずれかに一致する GroupRule です (テストしている実際のルールセットはもう少し完全ですが、この例ではそれで十分です)

しかし今、解析したいとしましょう

var1 = var2

そして、パーサーがルール式で始まるとします (定義される順序は重要ではありません - 優先順位は後で解決されます)。そして、GroupRule 式が最初に「割り当て」を試みるとします。次に、「式」が「割り当て」で一致する最初のルールであるため、式の解析が再度試行され、スタックがいっぱいになり、コンピュータが - 予想どおり - きらきらとしたセグメンテーション違反で単純に諦めるまで繰り返されます。

そこで私がやったことは、SequenceRules 自体を最初のルールに「リーフ」として追加し、非ルート ルールになるということです。ルート ルールは、パーサーが最初に試行するルールです。これらのいずれかが適用されて一致すると、一致するまでそのリーフのそれぞれを 1 つずつサブ適用しようとします。次に、一致するリーフのリーフを試し、一致するものがなくなるまで続けます。

次のような式を解析できるようにする

var1 = var2 = var3 = var4

ちょうどいいです =) さて、興味深い内容です。このコード:

var1 = (var2 + var3)

解析しません。何が起こるかというと、var1 が解析され (varAccess)、assign がサブ適用され、式を探し、'括弧' を試し、開始し、'(' の後の式を探し、var2 を見つけ、その後 '+ でチョークします。 ')' を期待していたためです。

「var2 + var3」と一致しないのはなぜですか?(はい、質問する前に、「追加」SequenceRule があります)。「add」はルートルールではなく（parse-expression-beginning-with-expression-etc.による無限再帰を避けるため）、リーフはSequenceRulesでテストされないため、そうでない場合は次のように解析されます。

reader readLine() println()

として

reader (readLine() println())

（例えば。「1 = 3」は、add によって予期される式であり、varAccess a) のリーフです。

一方、私たちはそれを左結合にしたいと考えています。として解析

(reader readLine()) println()

とにかく、SequenceRules 内で「1 + 2」などの式を解析できるようにする必要があるという問題が発生しました。何をするか？SequenceRules が TokenRule で始まる場合、それに含まれる GroupRules がリーフについてテストされるという特殊なケースを追加します。その特定の例以外でもそれは意味をなすでしょうか?それとも、SequenceRule の各要素でリーフをテストする必要があるかどうかを指定できる必要がありますか?あなたの意見をお聞かせください (システム全体を廃棄する以外は - おそらく数か月以内にそうなるでしょう)

追伸：どうか、お願いですが、「この 400 ページの本を読みに行ってください。そうしないと、私たちの時間に値する価値さえありません」などと答えないでください。もし必要を感じたら、遠慮して reddit でバッシングしてください。わかった？前もって感謝します。

Answer 1

LL（k）のパーサは（トップダウン再帰、自動または手動で書かれたかどうかは）左再帰を避けるために、あなたの文法のリファクタリングを必要とし、多くの場合、K-トークン先読みを扱うことができるように（例えばANTLR）先読みの特殊仕様を必要とします。文法は複雑なので、あなたが避けたい正確なものである、実験によってKを発見するために取得します。

YACC / LALR（1）大きな前進である左再帰の問題をaviod文法。悪いニュースは、LALR（1）されている（ワースのオリジナルPASCAL以外の）本当のプログラミングlangaugesが存在しないということです。したがって、あなたは再び奇妙な例を公開実験を受けるためにあなたを強制的に、そして時にパーサK-先読みを処理しようとする文法削減ロジックをハッキング、LALR（1）にLR（k）とから、それを変更するには、あなたの文法をハックしてもらいます発電機（YACC、BISON、...あなたはそれに名前を付けるには）1-先読みパーサを作成ます。

GLR法（ http://en.wikipedia.org/wiki/GLR_parserする）あなたは、ほぼすべてこのナンセンスのを避けることができます。あなたが最も実用的な状況下では、文脈自由パーサを書くことができた場合は、GLR法はさらに努力することなく、それを解析します。あなたは、任意の文法を記述しようとすると、それは巨大な救済です。そして、本当に良いGLR法は直接ツリーを生成します。

BISONは一種の、GLRの解析を行うために強化されました。あなたはまだあなたの希望ASTを生成するために、複雑なロジックを記述する必要があり、あなたが失敗したパーサを処理し、それに対応する（失敗した）木の削除/クリーンアップする方法を心配する必要があります。任意の文脈自由文法のための標準的なGLR法を提供する DMSソフトウェアリエンジニアリングTookit、および自動的にあなたの部分の任意の追加的な努力なしのASTを構築します。あいまいな木が自動的に構築され、後の解析セマンティックanalyisによってクリーンアップすることができます。我々は、C ++などのCを含む30+言語の文法を定義行うためにこれを使用しました（広範囲に解析することは困難であると考えられている[YACCで解析することはほとんど不可能である]が、実際のGLRと簡単です）。 DMSに基づいて C +++フロントエンドパーサーとASTビルダを参照してください。

ボトムライン：あなたは、簡単な方法で文法規則を書き、それらを処理するパーサを取得し、GLRの解析技術を使用したい場合。バイソンのほとんどの作品。 DM 本当にの働きます。

Answer 2

私のお気に入りの解析手法は、PEGの文法仕様から再帰下降（RD）パーサを作成することです。彼らは通常、非常に、高速でシンプル、かつ柔軟です。一つの素敵な利点は、あなたが別のトークン化のパスを心配する必要はありませんし、何らかのLALRフォームに文法を絞るの心配することは非存在です。いくつかのPEGライブラリは[こちら] [1]記載されています。

申し訳ありませんが、私はこれは捨てシステムに該当するが、知っているあなたは、あなたの問題とPEG RDパーサに切り替えるとゲートの外にかろうじてあり、ちょうど今、あなたの頭痛の種を排除するであろう。