90分钟实现一门编程语言(极简解释器教程)

2019-12-30 14:54:22王冬梅

最后在 Main 中调用该解释/求值循环:


static void Main(String[] cmdArgs) {
  new SScope(parent: null)
    .BuildIn("+", (args, scope) => (args.Evaluate<SNumber>(scope).Sum(s => s)))
    // 省略若干内置函数
    .BuildIn("empty?", (args, scope) => args.RetrieveSList("empty?").Count() == 0)
    .KeepInterpretingInConsole((code, scope) => code.ParseAsScheme().Evaluate(scope));
}

运行程序,输入一些简单的表达式:

c#,极简解释器

看样子还不错 :-)

接下来开始实现iScheme的执行(Evaluation)逻辑。

执行逻辑

iScheme 的执行就是把语句(SExpression)在作用域(SScope)转化成对象(SObject)并对作用域(SScope)产生作用的过程,如下图所示。

c#,极简解释器

iScheme的执行逻辑就在 SExpression#Evaluate 里面:


public class SExpression {
  // ...
  public override SObject Evaluate(SScope scope) {
    // TODO: Todo your ass.
  }
}

首先明确输入和输出:

    处理字面量(Literals): 3 ;和具名量(Named Values): x 处理 if :(if (< a 3) 3 a) 处理 def :(def pi 3.14) 处理 begin :(begin (def a 3) (* a a)) 处理 func :(func (x) (* x x)) 处理内置函数调用:(+ 1 2 3 (first (list 1 2))) 处理自定义函数调用:(map (func (x) (* x x)) (list 1 2 3))

此外,情况1和2中的 SExpression 没有子节点,可以直接读取其 Value 进行求值,余下的情况需要读取其 Children 进行求值。

首先处理没有子节点的情况:

处理字面量和具名量


if (this.Children.Count == 0) {
  Int64 number;
  if (Int64.TryParse(this.Value, out number)) {
    return number;
  } else {
    return scope.Find(this.Value);
  }
}

接下来处理带有子节点的情况:

首先获得当前节点的第一个节点:

SExpression first = this.Children[0];
然后根据该节点的 Value 决定下一步操作:

处理 if

if 语句的处理方法很直接——根据判断条件(condition)的值判断执行哪条语句即可:


if (first.Value == "if") {
  SBool condition = (SBool)(this.Children[1].Evaluate(scope));
  return condition ? this.Children[2].Evaluate(scope) : this.Children[3].Evaluate(scope);
}

处理 def

直接定义即可:


else if (first.Value == "def") {
  return scope.Define(this.Children[1].Value, this.Children[2].Evaluate(new SScope(scope)));
}