创建编译器必须生成 AST 吗？

Question

我想知道 AST 的生成是否是实现语言所必需的，例如通过编译器。我问过几次，每次都强烈建议在代码的 parsing/lexing 期间生成 AST。例如，这个：

int i = 2 + 3;

必须给这个：

但是这种简单的条件还不够吗？ :

if (statement == variable_declaration){
    if (NotDeclaredInCurrentBlock(NameOfVariable)){
        // ...
    }
    else
        Throw "Error: The '" << NameOfVariable << "' variable is already declared";
}

我真的不知道如何制作一个好的 AST，我想知道什么更简单 AND/OR 作为 PARSING 解决方案性能更好。例如，使用哪种解决方案更容易生成 ASM 代码？

我在这个领域并不是全新的，而且我访问过很多关于它的网站。我只想知道哪种解决方案（或另一种解决方案）对于玩具语言来说是最简单和最有效的；因为我猜它是 "the AST that wins" 的 "real" 语言。

Answer 1

你可以为此使用定制的调车场算法，这将产生这样的中间体：

<i> create_int <i> 2 3 + :=

其中 <i> 是某种标识符。您可以通过一个符号列表来实现这一点，您可以在其中查找现有符号的 ID 或使用当前计数器值添加新符号作为 id 并递增此计数器。

您可以像这样将其转换为 x86 代码：

code:
  push 0 ;id of <i>
  push 2
  push 3
  pop eax
  pop edx
  add eax, edx ; +
  push eax
  pop eax
  pop edx
  mov dword [ data + 4 * edx ], eax ; :=
  jmp finally
data:
  vars rd 1 ;number of variables, maximum variable-size is dword

如您所见，这会产生错误的代码，需要进一步优化。尽管如此，此代码并未使用 ASt，而是使用了基于堆栈的中间代码。

创建编译器必须生成 AST 吗？

Is the generation of an AST mandatory to create a compiler?

c++

assembly

parsing

abstract-syntax-tree