トークンストリームを解析ツリーに変換する方法[終了]

Question

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

Answer 1

http://www.antlr.org/ と、もちろん古典的なドラゴンをお勧めしますコンパイラブック。

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

質問の基本に戻って、本当にBNF風の文法構文を勉強して、ターゲットの構文を選びたいと思います。それがある場合、構文解析ツリーは、その文法の「インスタンス」表示であるように、一種のフォールアウトになるはずです。

また、解析ツリーの作成を最終的なソリューション（コードの生成など）に変えようとしないでください。それは実行可能かつ効率的に見えるかもしれません。しかし、常に、解析ツリーが「そのまま」存在することを本当に望む時が来るでしょう。

Answer 2

プラットフォームのパーサージェネレーターツールを調査する必要があります。パーサージェネレーターを使用すると、言語のコンテキストに依存しない文法を指定できます。この言語は、<！> quot; reduce <！> quot;新しいシンボルへの一連のシンボル。通常、異なるルールの優先度と結合性を指定して、言語のあいまいさを排除することもできます。たとえば、非常に単純な電卓言語は次のようになります。

%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を使用しましたが、どれも非常に優れています。すでにレクサージェネレーターを使用している場合は、特に互換性のあるパーサージェネレーターを探す必要があります。

Answer 3

一般的なアプローチは、 Finite State Machine を使用することです。たとえば、オペランドを読み取った場合、次に演算子を期待する状態になり、通常は演算子をオペランドのルートノードとして使用します。

Answer 4

上記のMarcos Marinが説明したように、BNFの言語ルールを使用してトークンリストを解析するステートマシンは、自分でやりたい場合にトリックを行います。ポール・ホリングスワースによる上記のコメントで述べたように、より簡単な方法は、プッシュダウン自動化を使用することです単純なFiFoメモリスタックがあります。 トークンのすべてのクラスには、文法で次に期待されるトークンがあり、これもステートマシンで表されます。スタックは<！> quot; remember <！> quot;に使用されます。必要な状態を減らすために、以前のトークンクラスは何でしたか（スタックなしで実行できますが、文法ツリーで分割されたすべてのクラスとサブクラスに対して新しい状態が必要になります）。 受け入れ状態は、（自然言語およびほとんどのプログラミング言語でも）開始状態になり、特定の場合には他の状態になります。

ツールを使用したい場合は、

Antlr をお勧めします（waaayはより高速で、それほど広範囲ではありません）。がんばって！