antlr: 实现BrokenScript(一)

开篇

本系列是一个前端探索编译原理的笔记开篇，将设计一个脚本语言BrokenScript（预计会实现块作用域，函数，面向对象，闭包）, 然后使用js来解析执行；在词法分析和语法分析阶段直接使用的antlr来生成，由于时间与能力有限，只是将此阶段简单解释，后面看时间再补充相关知识；如有错误，请在下方留言评论，我会于第一时间修正；

编译原理前端

本系列将主要涉及编译原理的前端；其主要分为几个阶段

词法解析阶段

维基百科定义

词法分析（英语：lexical analysis）是计算机科学中将字符序列转换为记号（token）序列的过程。进行词法分析的程序或者函数叫作词法分析器（lexical analyzer，简称lexer），也叫扫描器（scanner）。词法分析器一般以函数的形式存在，供语法分析器调用。

也就是对于一个字符串的输入，将其切割成一个Token数组;

interface Token {
    text: string; // 切割出的字符串单元
    type: TokenType; // 是数字，字符串，还是变量标识符，操作符等；
    line: number; // 行号
    start: number; // token在该行的开始字符位置
    end: number;
}

例如对于输入

int a = 45;

输出的token

[@0,0:2='int',<'int'>,1:0]
[@1,4:6='age',<Id>,1:4]
[@2,8:8='=',<'='>,1:8]

这个过程可以通过有限自动机算法完成：

简单的画了一下将输入的字符串切割为string token 和 数字 token的流程（大概知道意思就行，后面我们会用工具生成，不要跑偏）；

语法分析阶段

维基百科定义

在计算机科学和语言学中，语法分析（英语：syntactic analysis，也叫 parsing）是根据某种给定的形式文法对由单词序列（如英语单词序列）构成的输入文本进行分析并确定其语法结构的一种过程。

这个阶段我们主要用上下文无关文法（相当于递推公式）来描述语法；用递归等算法来构建AST；

例如加法的文法描述我们可以写为

add = int | int + add;
int = ‘0’ | [1-9][0-9]*;

3 + 5 + 7 的推导过程：-> int + add; -> int + int + add; -> int + int + int; 就是将非终结符替换为终结符的过程；这个过程比较重要，可以尝试找一些demo来练习；

代码：

let tokenList = ["3", "+", "5", "+", "7"]; //真实情况应该是对象;
function Node(value) {
  this.parent = null;
  this.child = [];
  this.value = value;
}
Node.prototype.addChild = function (child) {
  child.parent = this;
  this.child.push(child);
};
const getToken = () => tokenList[0];
const add = () => {
  let child1 = int();
  let node = child1;
  let token = getToken();
  if (token === "+") {
    token = tokenList.shift();
    node = new Node(token);
    child2 = add();
    if (child2 === null) {
      throw new Error("语法错误");
    }
    node.addChild(child1);
    node.addChild(child2);
    return node;
  }
  return node;
};
const int = () => {
  let token = getToken();
  if (/^\d$/.test(token)) {
    // 只做演示用
    tokenList.shift(); // 消耗掉token
    return new Node(token);
  }
  return null;
};

let node = add();

const calc = (node) => {
  if (node.value === "+") {
    return calc(node.child[0]) + calc(node.child[1]);
  } else {
    return Number(node.value);
  }
};

console.log(calc(node)); // 15

过程大概如此，这里我们是用的右递归推导（add -> int + add）的; 生成的AST也是右递归的，计算的时候会有结合率的问题，先玩起来要紧，想深入可以看这里# 04 | 语法分析（二）：解决二元表达式中的难点

语义分析阶段

语义分析也称为类型检查、上下文相关分析。它负责检查程序（抽象语法树）的上下文 相关的属性，这是具体语言相关的，典型的情况包括：

• 变量在使用前先进行声明
• 每个表达式都有合适的类型
• 函数调用和函数的定义一致

我们这个系列主要也是此部分内容，后面会详细展开,其实我们用的eslint很大一部分规则也是涉及到这个的；

安装antlr 并运行

首先电脑上要有java环境，如果没有，可以利用搜索工具安装一下，我的m1 max使用的如下链接来安装的# Mac M1 安装Java 开发环境（极其简单的操作）

mac 上安装antlr

brew install antlr 

设置CLASS PATH变量：

export CLASSPATH=".:/usr/local/lib/antlr-4.7.2-complete.jar:$CLASSPATH"

此处要注意 m1 的安装目录在opt下面，解析在这里在 M1 芯片 Mac 上使用 Homebrew;

m1 设置如下：

export CLASSPATH=".:/opt/homebrew/Cellar/antlr/4.11.1/antlr-4.11.1-complete.jar:$CLASSPATH"

编写语法规则文件Hello.g4;

grammar Hello; // 语法名称名Hello 应该与文件名相同；

add
  : Interger
  | add '+' Interger
  ;

Interger: '0' | [1-9][0-9]*;

执行命令生成词法分析器和语法分析器：

antlr Hello.g4 -Dlanguage=JavaScript -visitor

目录如下：

编写解释器代码index.js并运行

import HelloLexer from "./HelloLexer.js";
import HelloParser from "./HelloParser.js";
import HelloVisitor from "./HelloVisitor.js";
import antlr4 from "antlr4";

const input = "3+5+7";
const chars = new antlr4.InputStream(input);
const lexer = new HelloLexer(chars);

const tokens = new antlr4.CommonTokenStream(lexer);

const parser = new HelloParser(tokens);
parser.buildParseTrees = true;

class ASTEvaluator extends HelloVisitor {
  constructor() {
    super();
  }
  visitAdd(ctx) { // 为每一个规则生成一个visit方法 即：visit+ruleName
    if (ctx.children.length === 3) {
      // int + add;
      return this.visitInterger(ctx.Interger()) + this.visitAdd(ctx.add());
    } else {
      // int
      return this.visitInterger(ctx.Interger());
    }
  }
  visitInterger(ctx) {
    return Number(ctx.getText());
  }
}

const tree = parser.add();
const visitor = new ASTEvaluator();
const result = visitor.visit(tree);
console.log({ result }); // 输出15；

我们发现正常输出了结果；并且antlr为我们处理了左递归，而且加法的运算顺序也是正确的；ast树如下图：

先写到这里，下一节我们将实现变量声明语句，循环语句，if语句；