Antlr4系列⑦：自定义函数与调用栈
function定义/调用、递归、词法作用域、调用栈防死递归
在上一篇文章中我们给语言加上了作用域链，解决了变量定义和赋值混淆、代码块变量泄漏的问题。到目前为止，我们的小型DSL已经具备了变量、四则运算、字符串/布尔类型、分支、循环这些编程语言的基本要素，但还缺一样重要的东西——函数。本篇文章我们就来实现自定义函数：函数的定义、参数传递、return返回值，并支持递归调用。
一、语法设计
-
函数定义
参考主流语言设计
function 函数名(参数1, 参数2, ...) { 语句 }，为了不让本篇的内容过于膨胀，这里做一个简化：函数的参数和返回值统一按数值（calcu）处理，暂不支持字符串、布尔类型的参数和返回值。 -
函数调用
函数调用形如
函数名(参数1, 参数2, ...)，可以作为calcu表达式的一部分参与四则运算（比如n * factorial(n - 1)），也可以单独作为一条语句调用（不关心返回值，只是为了利用函数体内的副作用，比如打印）。 -
return语句
使用
return关键字返回一个值，也可以不带值，表示函数执行到此结束但没有返回值。 -
函数需要先定义后调用
和大多数脚本语言顶层代码从上往下顺序执行的习惯一致，函数必须写在调用它的代码之前，暂不支持前向引用。
二、语法定义
根据以上设计新增语法，完善后的结果如下（只列出本篇新增/改动的部分，完整文件见仓库）：
main: setArg SEMI?
| assignStmt SEMI?
| print SEMI?
| ifStmt
| whileStmt
| breakStmt
| continueStmt
| funcDecl // 新增
| returnStmt SEMI? // 新增
| calcu SEMI? // 新增：表达式语句，用于不关心返回值、单纯调用一个函数的场景
;
// 新增：函数定义，参数列表可以为空
funcDecl: FUNCTION name = ID '(' paramList? ')' block
;
paramList: ID (',' ID)*
;
// 新增：return语句，可以不带返回值
returnStmt: RETURN calcu?
;
calcu: calcu opt=(MUL|DIV) calcu # mulAndDiv
| calcu opt=(ADD|SUB) calcu # addAndSub
| '(' calcu ')' # parens
| NUMBER # number
| ID '(' (calcu (',' calcu)*)? ')' # funcCall // 新增
| ID # argValue
;
//以下为本篇新增词法
FUNCTION : 'function' ;
RETURN : 'return' ;
接下来对本次新增的部分进行解释。
-
main新增了三个分支：funcDecl（函数定义）、returnStmt（return语句）、calcu SEMI?（表达式语句）。其中calcu SEMI?这个分支值得说一下：print(...)这类写法本质上也是一种"只是为了产生副作用、不关心结果"的语句，这里我们用更通用的方式，让任意一个calcu表达式都可以独立作为一条语句出现，最直接的用途就是像tryReadY()这样单独调用一个函数而不使用它的返回值。 -
funcCall被定义成calcu的一个新分支，意味着函数调用可以出现在任何calcu能出现的位置——可以是number result = factorial(5)里等号右边的一部分，也可以是n * factorial(n - 1)这样嵌套在四则运算里的一部分，这也是后面能够写出递归函数的语法基础。 -
ID '(' ... ')'（函数调用）和ID（变量，即argValue）都是以ID开头，antlr4会根据紧跟在ID后面的到底是不是(来自动判断走哪个分支，不需要我们操心。
三、语法实现
接下来使用idea插件将定义好的.g4文件重新生成java文件覆盖之前的文件。函数的实现涉及三个关键设计点，逐一说明。
1. return如何跳出函数
return可能写在函数体内部很深的if/while嵌套里，和上一篇break/continue的处理思路完全一样：用异常把控制权一路传递回函数调用的地方。
/**
* return语句使用的控制流异常，命中return时抛出，携带返回值，由函数调用处捕获
*/
public class ReturnException extends RuntimeException {
private final VisitorResult value;
public ReturnException(VisitorResult value) {
this.value = value;
}
public VisitorResult getValue() {
return value;
}
@Override
public synchronized Throwable fillInStackTrace() {
return this;
}
}
2. 函数体的作用域：词法作用域 而不是 动态作用域
这是本篇最容易踩坑的地方。函数体执行的时候，新建的作用域parent应该指向谁？直觉上可能会写成new Scope(currentScope)——也就是"调用方当时所在的作用域"，这样写编译不会报错，简单的例子也能跑通，但存在一个严重的问题：如果调用方在自己的局部作用域里定义了一个变量，恰好和函数内部用到的某个变量重名，函数就会意外地读到调用方的局部变量，而不是报"未定义"的错误。这种"函数能看到调用它的地方的局部变量"的行为叫动态作用域，绝大多数现代编程语言都不是这样设计的。
正确的做法是词法作用域：函数只能访问自己定义时所在的作用域（在我们的实现里，函数只能在最外层定义，也就是全局作用域）和自己的参数，访问不到调用方的局部变量。因此函数执行时新作用域的parent要固定指向globalScope，而不是currentScope：
/**
* 最外层的全局作用域，函数体执行时的父作用域固定指向它，而不是调用者当时所在的作用域，
* 这样函数内部只能访问全局变量和自己的参数，访问不到调用者的局部变量（词法作用域而非动态作用域）
*/
private final Scope globalScope = new Scope(null);
private Scope currentScope = globalScope;
3. 调用栈：让死递归报错更友好
递归函数一旦忘了写终止条件，会无限调用下去，Java本身会抛出StackOverflowError，报错信息对使用者不太友好。这里自己维护一个简单的调用栈，记录当前调用链上的函数名，超过阈值就主动抛出一个更清晰的异常：
/**
* 已定义的函数，key为函数名，value为函数定义语法树节点，函数需要先定义后调用
*/
private final Map<String, RuleSetParser.FuncDeclContext> funcDefine = new HashMap<>();
/**
* 调用栈，保存当前调用链上的函数名，用于在递归层级过深时给出比Java原生StackOverflowError更友好的报错
*/
private final Deque<String> callStack = new ArrayDeque<>();
private static final int MAX_CALL_DEPTH = 1000;
把以上三点串起来，完整的函数定义、调用实现如下：
/**
* 函数定义，只是把函数名和语法树节点记录下来，真正的执行发生在被调用的时候，因此函数需要先定义后调用
*/
@Override
public VisitorResult visitFuncDecl(RuleSetParser.FuncDeclContext ctx) {
funcDefine.put(ctx.name.getText(), ctx);
return VisitorResult.nil();
}
/**
* return语句，把返回值包装进ReturnException抛出，由函数调用处捕获
*/
@Override
public VisitorResult visitReturnStmt(RuleSetParser.ReturnStmtContext ctx) {
VisitorResult value = ctx.calcu() == null ? VisitorResult.nil() : visit(ctx.calcu());
throw new ReturnException(value);
}
/**
* 函数调用：
* 1. 参数表达式必须在调用方当前作用域里求值，不能等切换到函数自己的作用域之后再算，
* 否则参数表达式里如果引用了调用方的局部变量将无法解析。
* 2. 函数执行时使用的新作用域的parent固定是globalScope而不是调用方的currentScope，
* 这样函数内部只能看到全局变量和自己的参数，看不到调用方的局部变量。
* 3. 用callStack记录调用深度，超过阈值主动抛出异常，避免死递归时让Java抛出不友好的StackOverflowError。
* 4. block执行时如果遇到return会抛出ReturnException，在这里捕获取出返回值；
* 如果一直执行到block结束都没有return，则函数调用的结果视为VisitorResult.nil()。
*/
@Override
public VisitorResult visitFuncCall(RuleSetParser.FuncCallContext ctx) {
String funcName = ctx.ID().getText();
RuleSetParser.FuncDeclContext funcDecl = funcDefine.get(funcName);
if (funcDecl == null) {
throw new RuntimeException("未定义的函数：" + funcName);
}
List<String> paramNames = funcDecl.paramList() == null
? Collections.emptyList()
: paramNames(funcDecl.paramList());
List<RuleSetParser.CalcuContext> argExprs = ctx.calcu();
if (argExprs.size() != paramNames.size()) {
throw new RuntimeException("函数" + funcName + "需要" + paramNames.size() + "个参数，实际传入" + argExprs.size() + "个");
}
if (callStack.size() >= MAX_CALL_DEPTH) {
throw new RuntimeException("函数调用层级超过" + MAX_CALL_DEPTH + "层，可能存在死递归：" + callStack);
}
List<Double> argValues = new ArrayList<>(argExprs.size());
for (RuleSetParser.CalcuContext argExpr : argExprs) {
argValues.add(visit(argExpr).getNumber());
}
Scope callerScope = currentScope;
Scope funcScope = new Scope(globalScope);
for (int i = 0; i < paramNames.size(); i++) {
funcScope.define(paramNames.get(i), argValues.get(i));
}
callStack.push(funcName);
currentScope = funcScope;
try {
visit(funcDecl.block());
return VisitorResult.nil();
} catch (ReturnException e) {
return e.getValue();
} finally {
currentScope = callerScope;
callStack.pop();
}
}
private List<String> paramNames(RuleSetParser.ParamListContext paramList) {
List<String> names = new ArrayList<>();
paramList.ID().forEach(id -> names.add(id.getText()));
return names;
}
关于参数求值的顺序：注意参数表达式
argValues是在切换currentScope之前求值的。如果先切换作用域再计算参数，参数表达式里但凡引用了调用方的局部变量（比如add(x + 1, y)里的x、y），就会因为找不到而报错——因为切换之后currentScope已经变成了只能看到全局作用域的函数作用域。
四、测试代码与执行结果
用三个例子分别验证：普通函数调用、递归函数、以及词法作用域是否生效。
String addExpression =
"function add(a, b) { \n" +
" return a + b \n" +
"} \n" +
"number sum = add(3, 4) \n" +
"print(sum)";
calcute(addExpression);
String factorialExpression =
"function factorial(n) { \n" +
" if (n <= 1) { \n" +
" return 1 \n" +
" } \n" +
" return n * factorial(n - 1) \n" +
"} \n" +
"number result = factorial(5) \n" +
"print(result)";
calcute(factorialExpression);
String scopeExpression =
"function tryReadY() { \n" +
" print(y) \n" +
"} \n" +
"if (true) { \n" +
" number y = 1 \n" +
" tryReadY() \n" +
"}";
calcute(scopeExpression);
执行结果如下：
执行:
function add(a, b) {
return a + b
}
number sum = add(3, 4)
print(sum)
7.0
执行:
function factorial(n) {
if (n <= 1) {
return 1
}
return n * factorial(n - 1)
}
number result = factorial(5)
print(result)
120.0
执行:
function tryReadY() {
print(y)
}
if (true) {
number y = 1
tryReadY()
}
Exception in thread "main" java.lang.RuntimeException: 未定义的变量：y
at cn.irule.MyRuleSetVisitor.visitPrintArg(MyRuleSetVisitor.java:127)
......
at cn.irule.MyRuleSetVisitor.visitFuncCall(MyRuleSetVisitor.java:408)
......
第一个例子add(3, 4)打印出7.0；第二个例子factorial(5)通过n * factorial(n - 1)递归计算阶乘，打印出120.0，说明函数调用可以正确嵌套在四则运算里，也支持递归；第三个例子里，y是在调用tryReadY()的if代码块里定义的局部变量，tryReadY函数体内直接访问y并没有"意外地"拿到调用方的1，而是正确地报出"未定义的变量：y"——证明我们的函数确实是词法作用域，而不是动态作用域，符合预期。
五、遗留的问题
到这里，我们的小型DSL已经是一门"五脏俱全"的编程语言了：变量、四则运算、条件、循环、作用域、函数递归，一应俱全。也正是因为有了函数调用和调用栈的概念，接下来终于可以着手实现一个有实际意义的功能——单步调试：设置断点、单步执行、查看调用栈和变量值。下一篇文章我们将实现调试器的第一部分：断点和单步执行的基础机制。