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语句；