10

私はコンパイラの世界に不慣れで、最近、パーサー ジェネレーターと呼ばれるものについて耳にしました。私が理解した (と思う) ことから、パーサー ジェネレーターは構文ファイルを取り込み、指定された構文でファイルを解析できるソース コード ファイルを出力します。

いくつかの質問：

  1. 私はそれを正しく理解しましたか？

  2. もしそうなら、ラゲルはそのようなツールですか？

  3. そうである場合、Ragel は D パーサーを D ソース コードに出力できますか?

ありがとうございました！

4

3 に答える 3

19

  1. 基本的にはそれだけです。パーサー ジェネレーターは、文法によって定義された言語のメンバーである文字列を認識するために使用できるソース ファイルに文法を変換します。常にではありませんが、多くの場合、パーサー ジェネレーターは、作業を行う前にテキストをトークンに分解する字句解析器を必要とします。Lex と Yaccは、対になった字句解析器とパーサー生成器の典型的な例です。

    最新のパーサー ジェネレーターは追加機能を提供します。たとえば、ANTLRは、語彙分析、文法分析、さらには生成された抽象構文ツリーをたどるためのコードを生成できます。Elkhoundは、 GLR解析アルゴリズムを使用するパーサーを生成します。これにより、一般化されていない解析アルゴリズムよりも広い範囲の言語を認識することができます。PEG パーサーは、別の字句解析器を必要としません。

  2. Ragel は、実際には有限状態マシンの形で字句解析器を生成します。通常の言語は認識できますが、文脈自由言語は認識できません。これは、D を含むほとんどのプログラミング言語を認識できないことを意味します。

  3. 高速な字句解析器が必要な場合、Ragel は D コードを生成します。

パーサー ジェネレーターの機能を完全に理解するには、形式的な言語と構文解析理論が必要です。The Dragon Bookよりも開始するには悪い場所があります。参照:コンパイラの書き方を学ぶ.

勇気があれば、DMD コンパイラーと一緒に配布されている字句解析および解析コード (/dmd2/src/dmd/) lexer.c および parse.c を確認してください。

于 2011-01-18T05:31:28.993 に答える
13

Ragel は正規表現に基づいていますが、単なる正規表現 FSM ジェネレーターではありません。追加の call/return 構文を使用した再帰と、非正規言語の解析を可能にするその他の機能を使用できます。そのため、Ragel は FSM を生成しますが、複数の異なる FSM を生成し、任意のポイントでそれらの間をジャンプしたり、特別なマシン遷移構文を使用したりするメカニズムを提供します。また、状態遷移時に任意のコードを実行することもできます。

Ragel のもう 1 つのユニークな点は、オンラインであることです。つまり、ノンブロッキング ソケットなどの非同期ソースからデータをスキャンするのに簡単に使用できます。また、動的リソースも使用しませんが、call/return ではスタックに静的、自動、また​​は動的メモリを使用できます。しかし、あなたが望む。グローバルな状態もありません。

Ragelは非常にユニークです。ほとんどの (すべて?) 従来のジェネレーターとは異なり、ネットワーク プログラミング用に作成されました。

于 2011-03-27T03:52:37.287 に答える
1

になり得る：

MySourceCode --> (スキャナー) --> MyScannerDataFile MyScannerDataFile --> (パーサー) --> MyParserDataFile MyParserDataFile --> (CodeGenerator) --> MyExecutableFile

また：

MySourceCode --> (ScannerAndParser) --> MyScannerAndParserDataFile MyScannerAndParserDataFile --> (CodeGenerator) --> MyExecutableFile

于 2011-04-08T15:14:33.780 に答える