7

私はある言語のパーサーを書いていますが、スキャナーは次のように設計されています

  1. 不要な端末も返す(例:ホワイトスペース)または
  2. そうしないでください

ブールフラグに基づいています。

さて、パーサーでは、これらすべての端末で文法を乱雑にしたくありません。構築している解析ツリーに「自動的に」飲み込まれる必要があります。

この「魔法」を行うには、端末をチェーン化して(単純にリンクされた循環リスト)、削減が行われるときにそれらを繰り返して「空白を埋める」ことができると思いました(LALR(1)パーサジェネレーターを使用しています) 。

問題が1つありますが、それは正気のアイデアのように聞こえます。私が「戻るかどうか」と言ったことを覚えていますか?シナリオ(2)では、次に何が来るか誰が知っているので、端末を解放しますか?そして、メモリリークは必要ありません。

しかし、シナリオ(1)では、ターミナルを解放できません。これに基づいて、「空白を埋める」プロセスを停止する場所をさらに削減することを決定するためです。

同じ理由で、条件付きで解放することもできません。次に何が来るかわかりません。「空白を埋める」プロセスがトリガーされない場合はどうなりますか?それ以上の削減がまったくない場合はどうなりますか?

同様の問題がありましたか?どのようにそれを解決しましたか?

:これはすべて私の頭の中にあり、十分に明確に説明していない可能性があります。質問してください。質問を編集します。シナリオは実際にはもう少し複雑です。私はこれを最初から書いているのではなく、想像力を使って他の何かに統合しているので、「それはできません。環境の制約のため」。


補遺

私の頭に浮かぶ唯一の本当に良いアイデアは、パーサージェネレーターをフォークして改善することです。これは、私が上で述べた制限のいくつかを克服するために、あちこちのいくつかのマイナーな場所ですでに行っています。

4

1 に答える 1

3

あなたの語彙は少し変です。ほとんどのパーサーは、言語の構文を認識するように設計されています。通常、言語定義は端末のいくつかの概念を定義し、空白、タブ、およびさまざまな種類の独立したコメントを含む、端末のテキスト間の面白くない一連のテキストで構成される「空白」を明示的に除外します。したがって、解析で使用される「端末」という言葉は、通常、「空白ではない言語アトム」を意味します。空白を含めるように暗黙的に定義しましたが、それがあなたの悲しみを引き起こしていると思います。

この観点から、パーサーが使用する文法定義が空白で煩雑になるのを避ける最も簡単な方法は、レクサーが空白をパーサーに渡さないようにすることです。そうすれば、文法はそれらがどのように処理されるかを示す必要はありません (そうです、そうする文法は本当に面倒です)、パーサーはそれらを気にする必要がなく、ツリーに表示されません。

コンパイラまたはインタープリタを構築している場合は、空白を無視するのが最も簡単です。

リエンジニアリング パーサーを構築している場合 ( DMS ソフトウェア リエンジニアリング ツールキットを参照)、AST で (少なくとも) コメントをキャプチャすることが重要です。最終的には、構築された AST からテキストを再生成する必要があるためです。コメントも [これは他の方法でも実行できますが、それほど簡単ではありません]。

DMS lexer は、言語トークン、空白、およびコメントの概念である「マイクロ」トークンを内部的に生成します。空白のマイクロトークンは単に何も追加しないため、破棄されます (上記の説明を参照)。ご想像のとおり、従来のトークンをパーサーに渡します。トークンの種類と検出された場所に応じて、コメント トークンを前後の言語トークンに接着します。C の場合、/* ... */ はトークンがそれに付けられる前に見られ、// ... コメントは前のトークンに付けられます (ここでは説明されていないいくつかの微妙な詳細があります)。その場合、解析ではまだ言語トークンしか認識されないため、文法が不必要に複雑になることはありません。また、トークンに関連付けられているすべての情報がツリーに配置されている場合、コメントはうまくいきます。

現在、「抽象」構文ツリーが必要になることがよくあります。彼らは「(」や「)」のようなものを除外したいと考えています。上で説明したスキームは、このような具体的なトークンにもコメントを付けています。ここで複雑な問題があります: ( .. ) トークンをツリーから除外すると、添付されたコメントが消えてしまいます。おっとっと。そのため、DMS パーサーは複雑なことを行います。ツリー内に論理的な場所があるが実際には存在しないトークンに添付されたコメント (「削除されたターミナル」) は、欠落している子トークンに属していることを示す注釈とともに、親ツリー ノードに持ち上げられます。はい、これを実装することは確かに PITA です。良いニュースは、DMS の一般的な解析機構で一度だけ実行する必要があり、非常に多くの言語で機能することです。しかし、これは、通常とは異なる (「リエンジニアリング」) パーサーを作成する必要があることを意味します。

編集:OPがこれを望んでいる理由は明らかではありませんが、彼はツリー内の空白をキャプチャすることを主張しています。彼は理由を教えてくれなかったので、私は推測します: 彼はトークン/ツリー ノードの正確な列情報を望んでいます。それは難しいことではありません: レクサーに位置 (行/列) を追跡するように教え、各トークン (コメントなどのマイクロトークン) に開始/終了位置をスタンプし、解析にその情報を木。この方法では、ツリー内に空白が残ることも回避されます。(問題を報告するときは正確な情報が役立ち、コードを再生成するときはコードを元の位置 (少なくとも同じ列) に戻すことが望ましいことが多いため、DMS もこれを行います)。

EDIT2:OPが空白をキャプチャすることを主張する場合、彼はスキャナレスGLR解析を検討することを検討するかもしれません. これにより、空白を含むすべての文字が入力ストリームに保持されます。

于 2011-08-07T21:55:05.807 に答える