接頭辞表記の後の利点

Question

私のコンパイラ設計教授は、ステートメントを評価する際に、すべてのトークンを後置記号に変換します。関数呼び出し以外はすべて中置表記になっているので、後置に変換する必要があります。関数は接頭辞と中置表記ではありません。だから彼らも改宗する必要があります。 これは、+(a,b)または+abの接頭辞表記に相当する中置のa+bとして示されます。

しかし、私はすべてを後置に変換して表記法を変えなければならない理由を理解していませんか？関数はすでにプレフィックスになっているので、非関数エンティティを接頭辞表記に変換して逆に実行する方が速いはずはありませんか？

Answer 1

インストラクタが記述しているアプローチは、式を解析するアプローチの1つですが、それだけではありません。基本的に、構文解析の目的は、式を演算や解釈が容易な形式にし、接頭辞と接尾辞の両方の記法がこれらの要件を満たすことです。実際のコンパイラでは、抽象構文木、すなわち入力の構造をコード化する木を構築するのがはるかに一般的です。接頭辞と接尾辞の両方の記法を、その木のプリオーダーまたはポストオーダーのいずれかと考えることができます。

効率に関しては、プレフィックスとポストフィックスの表記法を使用する間のコストの差はごくわずかであり、コンパイラのボトルネックになることはありません。一般的に、最も時間がかかるコンパイラの段階は最適化であり、解析にはほとんど時間がかかりません。問題を引き起こしているという具体的な証拠が得られるまで、解析の効率化を心配しません。