パーサー ジェネレーターと Ragel… 独自の D パーサーを作成する
-
12-10-2019 - |
質問
私はコンパイラの世界には慣れていませんが、最近パーサー ジェネレーターと呼ばれるものについて聞きました。私が理解した (と思う) ことから、パーサー ジェネレーターは構文ファイルを受け取り、指定された構文でファイルを解析できるソース コード ファイルを出力します。
いくつかの質問:
私はそれを正しく理解しましたか?
もしそうなら、Ragel はそのようなツールですか?
もしそうなら、Ragel は D パーサーを D ソース コードに出力できますか?
ありがとう!
解決
それは基本的にそれです。パーサージェネレーターは、文法を使用して、のメンバーである文字列を認識するために使用できるソースファイルに変換します 言語 文法によって定義されています。多くの場合、常にではありませんが、パーサージェネレーターは、作業を行う前にテキストをトークンに分解するために語彙アナライザーを必要とします。 LexとYacc ペアの語彙分析器とパーサージェネレーターの古典的な例です。
最新のパーサージェネレーターは追加機能を提供します。例えば、 antlr 語彙分析、文法分析のためのコードを生成し、生成された抽象的な構文ツリーを歩くことさえできます。 エルクハウンド を使用するパーサーを生成します GLR 解析アルゴリズム。これにより、非一般化された解析アルゴリズムよりも幅広い言語を認識できます。 ペグパーサー 個別の語彙アナライザーは必要ありません。
Ragelは、実際に有限状態マシンの形で語彙分析器を生成します。それはaを認識できます 通常の言語 しかし、ではありません コンテキストフリー 言語。これは、Dを含むほとんどのプログラミング言語を認識できないことを意味します。
高速の語彙アナライザーが必要な場合、RagelはDコードを生成します。
パーサージェネレーターがあなたのために何をするかを完全に理解するには、正式な言語と解析理論が必要です。より悪い場所があります ドラゴンの本. 。参照: コンパイラを書くことを学ぶ.
勇敢だと感じている場合は、DMDコンパイラ - /dmd2/src/dmd/-lexer.cおよびparse.cに配布されたレクシングと解析コードを必ずチェックしてください。
他のヒント
Ragel は正規表現に基づいていますが、そうではありません。 ただ 正規表現 FSM ジェネレーター。これにより、追加の呼び出し/戻り構文を使用した再帰や、非正規言語の解析を可能にするその他の機能が可能になります。したがって、Ragel は FSM を生成しますが、複数の異なる FSM を生成することができ、任意の点で FSM 間をジャンプしたり、特別なマシン遷移構文を使用したりするためのメカニズムを提供します。また、状態遷移時に任意のコードを実行することも可能になります。
Ragel のもう 1 つのユニークな点は、オンラインであることです。言い換えれば、ノンブロッキングソケットなどの非同期ソースからのデータを簡単にスキャンできます。また、呼び出し/戻りの場合、スタックに静的メモリ、自動メモリ、または動的メモリのいずれかを使用できることを除いて、動的リソースも使用しません。あなたが望むように。グローバルな状態もありません。
ラジェルはとてもユニークです。ほとんど (すべて?) 従来のジェネレーターとは異なり、ネットワーク プログラミング用に作成されました。
になり得る:
mySourcecode->(scanner) - > myscannerdatafile myscannerdatafile->(parser) - > myparserdatafile myparserdatafile - >(codegenerator) - > myexecutablefile
また:
mySourcecode->(scannerandparser) - > myscannerandparserdatafile myscannerandparserdatafile - >(codegenerator) - > myexecutablefile