7

入力からトークンをストリーミングするレクサーを構築しましたが、プロセスの次のステップである解析ツリーを構築する方法がわかりません。これを達成する方法に関する良いリソースや例はありますか?

4

4 に答える 4

4

http://www.antlr.org/と、もちろん古典的な Dragon Compilers の本をお勧めします。

JavaScript のような簡単な言語の場合、再帰降下パーサーを手動で作成することは難しくありませんが、ほとんどの場合、yacc や antlr などのツールを使用する方が簡単です。

質問の基本に戻ると思いますが、BNF 風の文法構文を勉強して、ターゲットの構文を選びたいと思っています。あなたがそれを持っているなら、構文木はその文法の「インスタンス」表現であるはずです。

また、解析ツリーの作成を最終的な解決策 (コードの生成など) に変えようとしないでください。それは実行可能で、より効率的であるように見えるかもしれません。しかし、その解析ツリーを「そのまま」置いておきたいと本当に思う時が必ず来るでしょう。

于 2009-01-19T04:51:56.177 に答える
3

プラットフォームのパーサー生成ツールを調査する必要があります。パーサー ジェネレーターを使用すると、言語の文脈自由文法を指定できます。この言語は、一連の記号を新しい記号に「縮小」する多くの規則で構成されています。通常、さまざまなルールの優先順位と結合性を指定して、言語のあいまいさを排除することもできます。たとえば、非常に単純な電卓言語は次のようになります。

%left PLUS, MINUS           # low precedence, evaluated left-to-right
%left TIMES, DIV            # high precedence, left-to-right

expr ::= INT
| expr PLUS expr
| expr MINUS expr
| expr TIMES expr
| expr DIV expr
| LEFT_PAREN expr RIGHT_PAREN

通常、少しのコードを各ルールに関連付けて、そのルールの他のシンボルから新しい値 (この場合は式) を作成できます。パーサー ジェネレーターは文法を取り込み、トークン ストリームを解析ツリーに変換するコードを言語で生成します。

ほとんどのパーサー ジェネレーターは言語固有です。ANTLR はよく知られており、C、C++、Objective C、Java、および Python をサポートしています。使いにくいとは聞いたことがありますが、C/C++ には bison、Java には CUP、OCaml には ocamlyacc を使用しましたが、どれも非常に優れています。レクサー ジェネレーターを既に使用している場合は、特に互換性のあるパーサー ジェネレーターを探す必要があります。

于 2009-01-19T05:36:20.890 に答える
0

上記の Marcos Marin によって説明されているように、BNF の言語ルールを使用してトークン リストを解析するステート マシンは、自分でやりたい場合にうまく機能します。上記の Paul Hollingsworth のコメントで述べたように、簡単な方法は、単純な FiFo メモリ スタックを持つプッシュダウン オートマトンを使用することです。トークンのすべてのクラスには、文法で次の予想されるトークンがあり、これはステートマシンでも表されます。スタックは、以前のトークン クラスが何であったかを「記憶」し、必要な状態を減らすために使用されます (スタックなしで実行できますが、文法ツリー内のクラスとサブクラスの分割ごとに新しい状態が必要になります)。受け入れ状態は (自然言語やほとんどのプログラミング言語でも) 開始状態であり、特定のケースでは他の状態になる可能性があります。

ツールを使用したい場合は、Antlr をお勧めします (waaay はより高速で、あまり広範囲ではありません) 。幸運を！

于 2014-04-22T10:18:14.967 に答える
0

一般的なアプローチは、Finite State Machineを使用することだと思います。たとえば、オペランドを読み取ると、次に演算子が必要な状態になり、通常はオペランドなどのルート ノードとして演算子を使用します。

于 2009-01-19T04:52:54.800 に答える