实现一门超简单的编程语言最快需要多久？

籍靖

2023-12-01

这是宫文学老师的第一节课程，本次课程的内容读完，并没有完全清楚我自己要做什么，该怎么做，经过读配套的原码，终于明白需要做一些什么事情，此处仅作为记录，梳理思路。以下为正文：

0x00

本次课程需要做的事情是进行一次简单的语法分析，将输入的 Token 数组，转换成一个语法树，紧接着处理函数与函数调用之间的关系，让函数与函数调用建立联系，最后在运行生成的语法树。（文中我使用的 Java 语言去实现的）

首先，来看一下我们需要解析的代码段内容：

function sayHello() {
  println("Hello World!");
}
sayHello();

以上代码，可以很简单的读懂，定义了一个函数 sayHello, 在这个函数中，调用了内置函数 println ，用来输出 Hello World! 这个字符串，在代码的最后，调用了这个定义的 sayHello 函数。

0x01

首先，我们手动将这个代码段拆分为 Token 数组。对于 Token 来说，有几种类型：

关键字 TokenKind.KeyWord ，例如 function
标识符 TokenKind.Identifier ，例如 sayHello, println
字符串 TokenKind.StringLiteral，例如 “Hello World!”
分隔符 TokenKind.Separator ，例如空格，{}， ;
终止符 TokenKind.EOF ，在 Token 数组最末尾，表示代码结束

将上面的代码段拆分为 Token 数组后就会变成下面这样：

static Token[] tokenArray = new Token[]{
  new Token(TokenKind.KeyWord, "function"),
  new Token(TokenKind.Identifier, "sayHello"),
  new Token(TokenKind.Separator, "("),
  new Token(TokenKind.Separator, ")"),
  new Token(TokenKind.Separator, "{"),
  new Token(TokenKind.Identifier, "println"),
  new Token(TokenKind.Separator, "("),
  new Token(TokenKind.StringLiteral, "Hello World!"),
  new Token(TokenKind.Separator, ")"),
  new Token(TokenKind.Separator, ";"),
  new Token(TokenKind.Separator, "}"),
  new Token(TokenKind.Identifier, "sayHello"),
  new Token(TokenKind.Separator, "("),
  new Token(TokenKind.Separator, ")"),
  new Token(TokenKind.Separator, ";"),
  new Token(TokenKind.EOF, "")
};

0x02

在回到语法解析，需要遍历整个 Token 列表，来生成语法树。语法树是把整个程序代码，按照一定的规则进行推导，形成一个树型结构。

回到本例中，为简化理解这个过程，我们的代码中，只包含简单的函数、函数调用的代码，以及系统打印函数 println 的调用。在我解析的代码片段中，使用 ; 来表示一行代码结束。

简单的函数表示的是，以关键字 function 开头，跟函数名，并且函数不包含参数。在函数的函数体中，仅可包含任意多个函数的调用（代码中定义的函数，以及系统打印函数 println 的调用）。函数的函数体包含在分割符 { } 中问。函数名称后需要跟分隔符 ( ) 。
系统打印函数 println 的定义为println(String... args) ，即我们在调用这个函数的时候，可以传递任意多个字符串给它，用于在控制台进行打印输出。调用示例如下：
```
println(); // 不输出任意值
println("Hello World !"); // 传递一个参数, 打印结果为： Hello World !
println("Hello", "World", "!")// 传递多个参数, 打印结果为： Hello World !
```

注意，在本例中， "Hello World!" 在转成 Token 的时候，把 "" 去掉，得到如下结果

new Token(TokenKind.StringLiteral, "Hello World!"),

0x03

经过上面的分析，能够很清楚明白的知道，语法解析程序需要干什么事情。

拿到 Token 数组后，需要从头遍历每一个 Token ，对于一段代码，需要知道当前代码应该按照函数定义来解析还是函数调用来解析，要解决这个问题很简单，那就是一种一种试，先把代码给到解析程序，先按照 函数定义 来解析，如果解析的过程中，发现他不是函数定义，就继续下一种可能，即按 函数调用 来解析。如果依然不是，在本例中，就需要报错，提示代码写错了。

函数定义

以关键字 function 开头，后面会跟一个标识符来作为函数名，在本例中，定义函数中不支持参数，因此在函数名后会紧接着会跟 ()，在后面便是由 {} 括起来的函数体内容，当然函数体里面可以为空，比时就会只剩下 {}。
函数调用

以标识符开头，这个标识符为要调用函数名称，紧接着是(，在它后面可能会跟任意多个字符串（仅在系统打印函数中使用），最后会跟一个 )，在代码的最后，还需要有 ; 号来结尾。
函数体

如上面第二节描述，函数体中包含多个函数调用，直接向后进行遍历 Token，按函数调用方式持续解析，直到下一个 Token 为 } 结束。

如果在上述解析过程中，出现错误，可直接抛出异常。

从上面的描述，可以使用 EBNF 格式，进行更加专业的表达：

prog = (functionDecl | functionCall)* 
functionDecl: "function" Identifier "(" ")" functionBody 
functionBody: "{" functionCall* "}"
functionCall: Identifier "(" parameterList? ")"
parameterList: StringLiteral ("," StringLiteral)*

0x04 代码实现

根据上面的描述，程序代码会循环遍历所有代码，并尝试按照函数定义、函数调用两种规则去解析代码，构建语法树，因此最上层代码如下：

while (true) { 
  // 1. 先按照函数定义解析
  Statement statement = this.parseFunctionDecl();
  if (statement != null) {
    // 解析到函数定义后，存储起来，进行后面的 Token 解析
    statements.add(statement);
    continue;
  }
  // 2. 函数定义解析失败后，尝试按函数调用解析
  statement = this.parseFunctionCall();
  if (statement != null) {
    // 解析到函数调用后，存储起来，
    statements.add(statement);
    continue;
  }
  // 3. 既不是函数定义，也不是函数调用， 会解析不成功，终止本次解析
  if (statement == null) {
    break;
  }
}

接下来，进行函数定义的解析，代码如下：

if (token.kind == TokenKind.KeyWord && "function".equals(token.text)) {
  // 获取函数名称
  token = this.tokenizer.next();
  // 此处 token 应该为函数名称，在本示例中，应该紧跟左右括号
  if (token.kind == TokenKind.Identifier) {
    Token leftBracketsToken = this.tokenizer.next(); // 左括号
    Token rightBracketsToken = this.tokenizer.next(); // 右括号
    if ("(".equals(leftBracketsToken.text) && ")".equals(rightBracketsToken.text)) {
      // 解析函数体
      FunctionBody body = this.parseFunctionBody();
      return new FunctionDecl(token.text, body);
    } 
  }
}

下一步是实现函数调用的解析，代码如下：

if (token.kind == TokenKind.Identifier) {
  Token leftBracketsToken = this.tokenizer.next(); // 左括号
  if (leftBracketsToken.text.equals("(")) {
    Token nextToken = this.tokenizer.next();
    // 不为 ) 时，里面可能会存在 String 的多个参数，在系统打印函数中定义。
    while (!")".equals(nextToken.text)) {
      if (nextToken.kind == TokenKind.StringLiteral) {
        params.add(nextToken.text);
      } 
      nextToken = this.tokenizer.next();
      if (!")".equals(nextToken.text)) {
        if (",".equals(nextToken.text)) {
          nextToken = this.tokenizer.next();
        }
      }
    }
    // 消耗一下语句末尾的 ; 号
    nextToken = this.tokenizer.next();
    if (";".equals(nextToken.text)) {
      return new FunctionCall(token.text, params);
    }
  }
}

最后是函数体的解析，代码如下：

// 函数体包含在 {} 内
if ("{".equals(token.text)) {
  // 函数体中仅包含函数调用，所以循环一直调用函数调用解析方法，去解析函数调用，只到没有找到函数调用语句为止。
  FunctionCall functionCall = this.parseFunctionCall();
  while (functionCall != null) {
    calls.add(functionCall);
    functionCall = this.parseFunctionCall();
  }
  token = this.tokenizer.next();
  // 判断最后一个 token 是否为 }, 如果不是，说明代码语法错误。
  if (!"}".equals(token.text)) {
    System.err.println("Expecting '}' in FunctionBody, while we got a " + token.text);
  } else {
    return new FunctionBody(calls);
  }
}

0x05 引用消解

在前文中，包含了很多函数定义以及函数调用，那函数调用处调用的函数是否有被定义呢？所以，需要将函数调用与函数定义的树节点建立关联关系，一方面可以判断当前函数调用是否合法，另一方面，也可以加速代码运行时的效率，避免重复查询函数定义。

针对本次示例中的语法数，需要遍历根节点下的方法调用，以及函数体中的方法调用。代码示例如下:

public void visitProg(Prog prog) {
  this.prog = prog;
  // 遍历当前 prog 下面的所有节点
  for (Statement stmt : this.prog.getStmts()) {
    if (stmt instanceof FunctionCall) {
      this.resolveFunctionCall((FunctionCall) stmt);
    } else {
      this.visitFunctionDecl(((FunctionDecl) stmt).getBody());
    }
  }
}

public void visitFunctionDecl(FunctionBody body) {
  // 遍历函数体里面的所有函数调用
  for (FunctionCall functionCall : body.getFunctionCalls()) {
    this.resolveFunctionCall(functionCall);
  }
}

private void resolveFunctionCall(FunctionCall call) {
  FunctionDecl decl = this.findFunctionDecl(call.getName());
  if (decl != null) {
    call.setDefinition(decl);
  } else {
    if (!"println".equals(call.getName())) {  
    	// 如果不是内置函数，直接报错
    }
  }
}

private FunctionDecl findFunctionDecl(String name) {
  // 第一版本，自定义函数中，不包含参数，所以直接匹配名称。
  for (Statement stmt : this.prog.getStmts()) {
    if (stmt instanceof FunctionDecl && ((FunctionDecl) stmt).getName().equals(name)) {
      return (FunctionDecl) stmt;
    }
  }
  return null;
}

0x06

最后的最后，是让解析出来的代码跑起来，怎么跑？函数调用就去执行对应的函数。那我们定义好的函数怎么运行呢？定义的函数是由 N 个函数调用形成的，如此往复，就跑起来了。代码示例如下：

public void visitProg(Prog prog) {
  for (Statement stmt : prog.getStmts()) {
    if (stmt instanceof FunctionCall) { // 找到函数调用，去执行这个函数调用
      this.runFunction((FunctionCall) stmt);
    }
  }
}

private void visitFunctionBody(FunctionBody body) {
  // 执行函数体中的方法调用
  for (FunctionCall functionCall : body.getFunctionCalls()) {
    this.runFunction(functionCall);
  }
}

private void runFunction(FunctionCall stmt) {
  // 如果是系统打印函数，直接遍历参数进行打印
  if ("println".equals(stmt.getName())) { 
    for (String parameter : stmt.getParameters()) {
      System.out.print(parameter + " ");
    }
    System.out.println();
  } else {
    // 判断当前函数调用是否已经有申明好的函数，如果有，则执行函数体中的函数调用。
    if (stmt.getDefinition() != null) {
      this.visitFunctionBody(stmt.getDefinition().getBody());
    }
  }
}

实现一门超简单的编程语言最快需要多久？

相关阅读

相关文章

相关问答

相关文档