抽象構文木または具象構文木をいつ使用するか？

Question

私はコンパイラに関する研究を行ってきました。レクサーは非常に単純なようです：「文章」を取り出し、それを単語（またはトークン）に分解してください。正しい文法を保証するためには、パーサーが必要です。パーサーは一般にトークンを取り、ルートノード（文章、段落、ページなどの単語）を生成するツリーを構築します。

this questionからパーサがASTを構築するようです。 ASTにはコードを実行するために必要なものだけが含まれているため、演算子の優先順位がASTに組み込まれているため、かっこのようなものは不要です。 ASTはおそらくすべてのコンパイラに必要です。

しかし、ある言語から別の言語へのコードの変換はどうですか？作成された言語（文法）または既存の文法をとり、それを別のものに変換すると、演算子優先順位の規則は異なる場合があります。演算子の優先順位はCSTにも組み込まれていますか？

たとえば、言語を作成し、それをPHPコードに翻訳したかったとします。ほとんどの言語の三項演算子には、右から左への連想があります。 PHPでは、左から右への結合性が間違って使用されています（see more about this here）。私は "私の言語"を右から左に使いたいが、結果のPHPコードは括弧を入れてPHPで正しい結果を得なければならない（link to Wikipediaで結果は "馬"の代わりに "train"にする必要がある）。

言語変換のためにCSTは良いでしょうか？演算子の優先順位は通常CSTに組み込まれていますか？間に何かがありますか？両方の木を単純な代数方程式と比較する例はありますか？三項演算子を示す例は何ですか？

は（？。Google検索がメディアを変換立ち上げる「トランスコード」「プログラミング言語翻訳」の正しい用語です）

私が把握しようとしている何である：1を使用することがより適切である場合にはもう一方では？

Answer 1

ソース言語のすべてのセマンティックな詳細をモデル化したASTは、必要なものだけです。定義によって、セマンティクスが正しくモデル化され、ランゲージに三項演算子が含まれている場合、演算子が適用される特定の順序（例えば、括弧などのモジュロオーバーライドの結果）も正しくモデル化されます。

あなたの問題はASTにはありません。優先順位の異なる類似（3進）演算子を使用して別の言語に生成しています。

これはコード生成に古くからある問題です。ターゲットの演算子はソースの演算子とよく一致しないため、出力は一対一ではありません。あなたのケースでは、元のセマンティクスを達成するための順序を制御するために、カッコで囲まれたPHP三項演算子を生成することによって問題を解決できるはずです。したがって、これは大きな問題ではありません。

一般に、望ましい結果を達成するコードの生成シーケンスは、かなり複雑になる可能性があり、それを実行する方法はたくさんあります。だからこそ、コンパイラの本は薄くてむしろ厚い。あなたは暗黙のうちに "ASTを取得し、ASTを歩いて、コードを吐き出す"ことに決めたようです。これはほぼオンザフライのコードジェネレータです。生成されたコードが特に優れていて、ターゲット言語が元の言語に非常に近いかどうか気にしなければ、これは適切に機能します。

コード生成の問題がより複雑な場合、通常はASTを使用して演算のデータフローモデルに相当するものを生成し、結果を生成し、以前の演算子の結果を消費し、変数値と定数をフェッチする "演算子"の中で。次に、データフロー表現を走査してコードを生成する。これには、データフロー表現で演算子を選択し、ターゲット言語で一致するコードシーケンスを見つけ出し、生成し、オペランドの収集方法を心配するという利点があります。より良いスキームは、生成されたデータフローグラフにデータフローサブグラフ（同等の複合ターゲット言語構成を表す）を一致させる。これにより大幅に優れたコードが生成されます。多くの場合、未加工コード生成後にターゲット言語固有の最適化を適用して、より良いコードを生成することができます。どちらの場合も、演算子の結果を管理することを心配する必要があります。次のターゲット言語演算子に直接供給することができますか、または何らかの種類の一時記憶領域に入れる必要があります（マシンコードの場合は別のレジスタまたはメモリの場所になります）。これをすべて行うことは容易ではありません。コンパイラの本は薄いわけではありません。

このアイデアのバリエーションは、ソースからソースへのプログラム変換です。これは、ソースコード中の構造体をターゲットコード内の構造体に「直接」マッピングしますが、解析されないプログラミング言語のテキストは一致しないため、AST上で操作することによって裏返しに行われます。私たちのDMS Software Reengineering Toolkitはこの種のシステムの例です。このようなツールを使用すると、ソース言語（パースツリーと暗黙的に一致する）とターゲットランゲージの対応するパターン（暗黙的にターゲット言語ASTを生成する）でパターンを記述します。上記のデータフローグラフの効果の大部分を与える複雑なソースまたはターゲット構造を書くことができます。ポスト・ジェネレーションの最適化は、ターゲット・コードをターゲット・コードに変換するより多くのリライト・ルールで構成されます。

ボトムライン：あなたの翻訳が本当に些細なものでなければ、ASTを持つことは本当に十分ではありません。 あなたはこのSO答えで必要なものについてもっと読むことができます：https://stackoverflow.com/a/3460977/120163

警告：大きな意見は次のとおりです。

Re：「トランスコーダー」：「コンパイル」、「翻訳」、または「ソースからソース」コンパイラという用語を好む。私はプログラム分析と操作ツールを40年近く構築してきました。私はこの質問に遭遇するまで用語 "トランスコーダ"を聞いたことがありませんでした：Experience migrating legacy Cobol/PL1 to JavaとIMHOを記述する応答はNACAと呼ばれる本当にひどいコード変換スキームです。私はこの言葉が牽引力を得て以来、聞いてきました。なぜ私たちは完全に適切なものを持っているときに別の用語を発明しなければならなかったのかわかりません。通常、これは誰かが高い神権を発明していることの兆候です。 "光栄な新しい用語を発明して、人々が私たちがやっていることを本当に理解できないようにしましょう"。私はそのような本当にひどい翻訳にその言葉を残してうれしいです。