問題タブ [parse-tree]

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

再帰降下パーサーを使用してデータが文法に一致するかどうかを確認すると同時に、解析ツリーを生成することはできますか?

もしそうなら、再帰的に降下するときにツリーを構築するためにどのようなアプローチを使用しますか?

ありがとう、ボダ・シド。

注：私は解析が初めてです。（すでにSOについていくつかの質問をしましたが、私はそれで良くなっています。）

ロシア語のセマンティックパーサーを知っている人はいますか? link-grammar サイトから入手できる link-parser を設定しようとしましたが、うまくいきませんでした。

私は、Mac 上で実行でき、プロローグまたは Lisp のような解析ツリーの表現を生成できるシステムを望んでいます (ただし、XML 出力も問題ありません)。

単純な数学演算子（+、-、*、/、および括弧）を使用して、特定の文字列に対して構文ツリーを生成しようとしています。文字列「1+2 * 3」が与えられた場合：

次のような配列を返す必要があります。

[1、 "+"、2、 "*"、3]の "1 + 2*3"を変換する関数を作成しました。

問題は、特定の操作を優先するかどうかわからないということです。

私のコードは次のとおりです。

Qi と Karma を使用して、いくつかの小さな言語で処理を行ってきました。ほとんどの文法はかなり小さい (20 ～ 40 のルール)。私はオートルールをほぼ排他的に使用することができたので、解析ツリーは完全にバリアント、構造体、および std::vector で構成されています。

このセットアップは、一般的なケースでうまく機能します:
1) 何かを解析する (Qi)、
2) 解析ツリーに小さな操作を行う (ビジター)、
3) 何かを出力する (カルマ)。

ただし、大きなサブツリーを移動するなど、構文ツリーに複雑な構造変更を加えたい場合はどうなるか心配です。次のおもちゃの例を考えてみましょう。

自動規則を使用する s-expr スタイルの論理式の文法...

...これは、次のような解析ツリー表現につながります...

次のような解析ツリーがあるとします。

(省略記号は、「 の同様の形状の子がさらに多く」を意味しpandます。)

porここで、最終結果が次のようになるように、各ノードを無効にしたいとします。

por直接的なアプローチは、サブツリーごとに次のようになります。
-pnotノードを作成します
(作成中のコピーpor)。-ノード
内の適切なベクトル スロットを再割り当てします (ノードとそのサブツリー を コピーします)。pand
pnotpor

別の方法として、別のベクターを構築し、そのpandベクターを大規模に置換 (スワップ) して、2 回目のコピーをなくすこともできます。

pnotこれはすべて、既存のノードをコピーせずにノードを挿入できるポインターベースのツリー表現と比べると面倒に思えます。私の質問：

自動規則に準拠したデータ構造を使用して、コピーの多いツリー操作を回避する方法はありますか? 弾丸をかじって、自動規則以外を使用してポインターベースの AST を構築する必要がありますか (たとえば、http://boost-spirit.com/home/2010/03/11/s-expressions-and-variants/ )?

文脈自由文法から生じる解析ツリーを描画するための優れたツールを持っている人はいますか? この質問がありますが、解析ツリーではなく有限オートマトンを具体的に扱っています。これまでgraphvizを使ってきたのですが、ノードごとに個別にラベルを付けないといけないなどちょっと面倒です。

それらはコンパイル プロセスのさまざまな段階で生成されますか? それとも同じものの名前が違うだけですか？

重複の可能性:
解析ツリーと AST の違いは何ですか?

抽象解析ツリーと解析ツリーの違いを知る必要があります。

コンパイラの設計書で2つの用語を見つけましたが、それぞれが何を表しているのか、そしてそれらがどのように異なっているのかを知りたいと思います。

インターネットで検索したところ、解析ツリーは具体的な構文ツリー（CST）とも呼ばれていることがわかりました。

いくつかのjavascriptコードで解析ツリーを生成して使用できるように、antlr3APIを理解するのに問題があります。antlrWorks（IDE）を使用して文法ファイルを開くと、インタープリターは解析ツリーを表示でき、それも正しいです。

antlr3ランタイムを使用して、コードでこの解析ツリーを取得する方法に関するリソースを追跡するのに多くの問題があります。私はランタイムファイルとパーサーファイルのさまざまな関数をいじり回してきましたが、役に立ちませんでした。

antlrWorksは自分自身のツリー文法なしで解析ツリーを表示でき、antlrが文法ファイルから解析ツリーを自動的に生成することを読んだので、私はこの基本的な解析ツリーにアクセスできると思います。おそらく気づいていません。私はこの考えで正しいですか？