编译原理

假如我们有一段某种编程语言的 stack-based 字节码： const1 ; 将常量 1 压入栈顶 const3 add const3 mult halt 在一个经典的 C 编写的解释器中，我们可能会有一个用类似 switch 的东西实现的循环，来解释执行这段计算 (3 + 1) * 3 的字节码。 enum { OP_CONST1, OP_CONST2, OP_CONST3, OP_ADD, OP_MULT, OP_HALT, }; void interpret(uint8_t insn[], uint32_t stack[]) { int pc = 0; uint32_t *st = stack; next: switch (insn[pc++]) { case OP_CONST1: *st++ = 1; goto next; case OP_CONST2: *st++ = 2; goto next; case OP_CONST3: *st++ = 3; goto next; case OP_ADD: st[-2] = st[-1] + st[-2]; st--; goto next; case OP_MULT: st[-2] = st[-1] * st[-2]; st--; goto next; case OP_HALT: return; } } 有很多原因导致这段代码性能不佳：...

AST是用来表示语法构造的数据结构，而在大多数语言中都有“变量”的概念。 那么应在AST中用什么方式表示一个“变量”呢？ 怎么进行变量的替换呢？ 怎么进行变量作用域的检查呢？ First-Order Abstract Syntax 最简单直接的方法就是直接用字符串保存变量名，以lambda calculus为例： type Name = String data Expr = Var Name | App Expr Expr | Lam Name Expr 这种AST被称为FOAS，一般是parse完得到的。但这种裸的AST几乎不包含任何信息，变量和作用域之间没有直接的关系，bindings也只是由匹配字符串来表示。 在这个层面上对AST操作是十分不安全的，稍不注意就可能改变了语义。比如说不带更名的substitution：(λy.λx.y)x→λx.x。 若要写出正确的substitution还得花点小心思，这是wiki上lambda calculus的substitution的定义（少了一种情况）： x[x := N] ≡ N y[x := N] ≡ y, if x ≠ y (M1 M2)[x := N] ≡ (M1[x := N]) (M2[x := N]) (λx.M)[x := N] ≡ λx.M (λy.M)[x := N] ≡ λy.(M[x := N]), if x ≠ y, provided y ∉ FV(N) “翻译到”haskell：...