1

だから私はパーサーをやっていて、速度よりも柔軟性を優先し、文法を簡単に書きたいと思っています。 .)

トークンの固定セット (例: PLUS、DECIMAL、STRING_LIT、NAME など) を使用して手作業でコード化されたレクサーがあり、現在、3 つのタイプのルールがあります。

  • TokenRule: 特定のトークンに一致
  • SequenceRule: 規則の順序付けられたリストに一致します
  • GroupRule: リストの任意のルールに一致

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

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

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

var1 = var2

そして、パーサーがルール Expression で始まるとしましょう (それらが定義される順序は重要ではありません - 優先度は後で解決されます)。そして、GroupRule 式が最初に「代入」を試みるとしましょう。次に、「式」は「代入」で一致する最初のルールであるため、式を再度解析しようとします。スタックがいっぱいになり、コンピューターが - 予想どおり - キラキラした segfault で単にあきらめるまで、同様の処理が繰り返されます。

だから私がしたことは - SequenceRules は最初のルールに「葉」として自分自身を追加し、ルート以外のルールになります。ルート規則は、パーサーが最初に試行する規則です。それらのいずれかが適用されて一致すると、一致するまで、各リーフを 1 つずつサブ適用しようとします。次に、一致するリーフのリーフを試行し、一致するものがなくなるまで試行します。

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

var1 = var2 = var3 = var4

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

var1 = (var2 + var3)

解析しません。何が起こるかというと、var1 が解析され (varAccess)、代入がサブ適用され、式が検索され、「括弧」が試行され、開始され、「(」の後の式が検索され、var2 が検出され、「+」がチョークされます。 ')' を予期していたためです。

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

reader readLine() println()

なので

reader (readLine() println())

(たとえば、'1 = 3' は add が期待する式であり、varAccess a のリーフです)

一方、左結合にしたいのですが、たとえば、次のように解析します

(reader readLine()) println()

とにかく、SequenceRules 内で「1 + 2」などの式を解析できるはずであるという問題が発生しました。何をすべきか？SequenceRules が TokenRule で始まる場合、それに含まれる GroupRules がリーフについてテストされるという特別なケースを追加しますか? その特定の例の外でも、それは理にかなっていますか? または、葉についてテストする必要があるかどうかを、SequenceRule の各要素で指定できるようにする必要がありますか? あなたの考えを教えてください（システム全体を捨てることを除いて - それはおそらく数ヶ月以内に起こります）

PS: どうか、どうか、「この 400 ページの本を読みに行ってください。さもないと、私たちの時間にふさわしくありません」などと答えないでください。わかった？前もって感謝します。

4

2 に答える 2

2

LL(k) パーサー (自動化されているか手動で書かれているかにかかわらず、トップダウン再帰的) は、左再帰を避けるために文法のリファクタリングを必要とし、多くの場合、k-token 先読みを処理できるようにするために、先読みの特別な仕様 (例: ANTLR) を必要とします。文法は複雑なので、実験によって k を発見することになりますが、これはまさに避けたいことです。

YACC/LALR(1) 文法は左再帰の問題を回避します。これは大きな前進です。悪いニュースは、(Wirth のオリジナルの PASCAL 以外に) LALR(1) である実際のプログラミング言語がないことです。したがって、文法をハックして LR(k) から LALR(1) に変更する必要があり、奇妙なケースを明らかにする実験に苦しむことを余儀なくされ、パーサーがジェネレーター (YACC、BISON など) は、1 先読みパーサーを生成します。

GLR パーサー ( http://en.wikipedia.org/wiki/GLR_parser ) を使用すると、このナンセンスのほとんどすべてを回避できます。コンテキスト フリー パーサーを作成できる場合、ほとんどの実際的な状況では、GLR パーサーはそれ以上の労力をかけずにそれを解析します。任意の文法を書こうとするとき、これは非常に安心です。そして、本当に優れた GLR パーサーはツリーを直接生成します。

BISON は、一種の GLR 解析を行うように拡張されています。目的の AST を生成するために複雑なロジックを記述する必要があり、失敗したパーサーを処理する方法と、対応する (失敗した) ツリーをクリーンアップ/削除する方法について心配する必要があります。DMS Software Reengineering Toolkitは、あらゆる文脈自由文法に対応する標準の GLR パーサーを提供し、追加の労力を必要とせずに AST を自動的に構築します。あいまいなツリーは自動的に構築され、解析後のセマンティック分析によってクリーンアップできます。これを使用して、C、C++ を含む 30 以上の言語文法を定義しました (解析が難しいと広く考えられていますが [YACC で解析することはほとんど不可能です] が、実際の G​​LR では簡単です)。DMS に基づくC+++ フロント エンド パーサーと AST ビルダーを参照してください。

結論: 文法規則を簡単な方法で記述し、それらを処理するパーサーを取得する場合は、GLR 構文解析テクノロジを使用してください。バイソンはほとんど動作します。DMは本当に機能します。

于 2009-10-03T04:26:24.620 に答える
0

私のお気に入りの構文解析手法は、PEG 文法仕様から再帰降下 (RD) パーサーを作成することです。それらは通常、非常に高速で、シンプルで、柔軟です。優れた利点の 1 つは、個別のトークン化パスについて心配する必要がなく、文法を LALR 形式に圧縮することについて心配する必要がないことです。一部の PEG ライブラリは [こちら][1] にリストされています。

申し訳ありませんが、これがシステムを捨てることになることはわかっていますが、問題を抱えていて、PEG RDパーサーに切り替えることで、頭痛が解消されることはほとんどありません.

于 2009-10-15T03:06:56.297 に答える