2周自制脚本语言
1.前言与说明
开始时间:2021年6月13日
目的:以实践的形式了解编译原理的部分知识,动手自制改进脚本语言
后来发现理解代码太难太难,最终选择将能看懂的代码进行注释
本文没有什么参考价值,完全是我在学习过程中的无聊笔记。排版也比较乱。
开始注释
第三章代码注释完成
实现词法分析功能。
第四五章代码注释完毕
实现语法分析
有很多东西虽然可以猜到是什么意思,但还是理解不够透彻,不知道具体每一步骤实在做什么。
整体介绍
/ast
包含abstract syntax tree(ast) 的数据结构
/stone
**Token.java**
是每个token的抽象类
**Lexer.java**
词法分析器,通过正则表达式分析出一个一个语法单位。其中还包括Token的三个子类 NumToken IdToken StrToken
**CodeDialog.java**
Reader的子类,为词法分析器做了一些预处理。
**Parser.java**
作者提供的类库 用于语法分析的类,提供了语法分析的方法
**ParseException**
重写的异常处理类
**BasicParser**
用于执行语法处理的类
实际上上述做的就是 构造出一个具体的抽象语法树。
继续继续
第六章代码注释完毕
主要功能是对抽象语法树进行解释和计算。
整体介绍
- 通过gluonj 扩展AST类中的数据结构源代码,使每一个节点都有eval方法,用于计算
- 计算的过程是从上到下递归,类似于深度优先遍历
- 在eval中对常用的运算符:+ = == > 等,以及if while 代码块做具体的处理。
- 至此,stone语言可以是实现基本的运算功能。
关于gluonj
gluonj is a sample of AOP,it provide a way to extend a Class
such as:
@Reviser public static class ASTLeafEx extends ASTLeaf{
public ASTLeafEx(Token t) { super(t); }
}
it extend a function to class ASTree
上述代码中,ASTLeafEx是对ASTLeaf的扩展,虽然形式上看起来像是子类,它并不是子类。
这么做的好处是不用直接对ASTree的源代码进行修改。
/chap6
Environment.java
环境变量类的接口
BasicEnv.java
对Environment接口的实现,用HashMap存储环境变量
BasicEvaluator.java
在这个类中通过gluonj对原AST进行扩展
Runner.java
开始运行整个程序
BasicInterpreter.java
解释程序,控制整个流程:先词法分析,然后语法分析构造出一个一个AST,每个AST构造出来后就调用eval方法进行运算。
每次生成一个AST就直接执行,这是解释程序的特点
继续继续
第7章代码代码注释完毕
主要功能是增加了函数和闭包两个功能
整体介绍
- 还是利用gluonj对原有AST进行扩展,同时新增了许多与方法有关的AST类
/stone
FuncParser
支持函数的语法分析器扩展
ClosureParser
支持闭包的语法分析器扩展
/ast
Postfix.java
ASTList的子类。
Arguments.java
Postfix的子类,可能是存储参数列表的大小。
DefStmnt.java
一个ast中的非叶子节点,表示一个整个函数定义的代码
ParameterList.java
参数列表
Fun.java
应该是表示闭包的非叶子节点
/chap7
FuncEvaluator.java
给AST中的关于函数的类添加eval方法
FuncInterpreter.java
加上函数功能之后的解释流程控制
FuncRunner.java
加上函数功能之后的运行开始程序
Function.java
一个具体的Function类,区别于AST中的类,例如 a=fib(b){b} a的类型就是Function
NestedEnv.java
遍历的环境变量类,在寻找变量时,现在当前环境变量中找,找不到就往上一层寻找
ClosureEvaluator.java
给AST中的关于闭包的类添加eval方法
ClosureInterpreter.java
加上闭包功能之后的解释流程控制
ClosureRunner.java
加上闭包功能之后的运行开始程序
虽然我可以在这里瞎扯这么多,但实际上很多代码包括整个设计,我都不是很能理解。
继续继续
第8章代码注释完毕
主要是增加原生函数功能,利用java的反射功能,使stone可以调用一些java函数。
整体介绍
- 解释程序时,将原生方法放入环境变量中
- 在处理到一个方法时,判断是不是原生函数,如果是
- 收集参数
- 调用java提供的invoke方法
/chap8
Natives
用于将支持的原生函数放入环境变量中去。
NativeFunction
原生方法类,通过调用java的invoke方法,实现当前NativeFunction对象到java的函数之间的转换。
NativeEvaluator
扩展器,扩展FuncEvaluator.ArgumentsEx,使其可以处理原生函数。
NativeInterpreter
解释器,在这一步中,需要通过Natives将支持的原生函数放入到环境变量中。
NativeRunner
执行器,运行开始程序
继续继续
第9章代码注释完成
增加了面向对象的功能,可以单一继承,没有接口。
整体介绍
- 字段与方法之间没有明确的区别,方法是一种以Function对象为值得字段。
- 对象实际上可以看做一个特殊的环境,因此StoneObject中实际上存放一个环境。
- 通过.new创建新的StoneObject时,解释器首先创建新的环境,并且将 this-新创建的StoneObject 这个键值对存入环境中。
/stone
ClassParser
支持类的语法分析器扩展
/ast
ClassStmnt.java
在语法分析时产生的Class块的AST
ClassBody.java
类中间的具体代码的AST
Dot.java
点(.)的AST
/chap9
ClassInfo.java
表示stone中的类。
StoneObject.java
表示stone中的对象,实际上和环境一样,有HashMap实现,提供write和read方法。
ClassEvaluator.java
扩展器,为AST中的结构添加支持面向对象的运算。
ClassInterpreter.java
解释器
ClassRunner.java
执行器
继续继续
第10章代码注释完成
添加了数组功能。
整体介绍
- 使用java中的Object[]实现,因此一个数组中可以存放不同类型的数据。
/stone
ArrayParser.java
支持数组的语法分析器扩展
/ast
ArrayLiteral.java
表示数组字面量
ArrayRef.java
表示数组元素的指代
/chap10
ArrayEvaluator.java
扩展器,为AST中的结构添加支持数组的运算。
ArrayRunner.java
执行器
继续继续
第二部分
第11章代码注释完成
对于局部变量,使用数组保存环境。同时,使用位置信息来查找变量。
/chap11
ArrayEnv.java
使用数组实现的记录局部变量的环境
ResizableArrayEnv.java
记录全局变量的环境
Symbols.java
一张哈希表,用于记录变量名与保存位置之间的对应关
系
EnvOptimizer.java
扩展器,扩展lookup方法,在执行eval之前先执行lookup找到变量
OptFunction.java
使用ArrayEnv作为执行环境的function
EnvOptInterpreter.java
解释器
EnvOptRunner.java
执行器
继续继续
第12章代码注释完成
通过将同一个类的所有对象共用的字段和方法保存在ClassInfo中减少内存消耗。
使用内联缓存:在引用字段时,信息将由与该字段引用表达式对应的抽象语法树缓存,具体来说,是
保存在语法树节点对象的相应字段中。
/chap12
OptClassInfo.java
优化后的ClassInfo
OptStoneObject.java
优化后的StoneObject
SymbolThis.java
保存有效的本地变量名在类定义体中
MemberSymbols.java
记录字段名和方法名
ObjOptimizer.java
扩展器,扩展支持内存优化的eval和lookup方法
ObjOptInterpreter.java
解释器
ObjOptRunner.java
执行器
InlineCache.java
扩展器,扩展支持内联缓存的方法
InlineRunner.java
执行器
继续继续
第13章代码注释完成
构造虚拟机对部分stone代码进行编译,生成中间代码,然后执行中间代码。
/chap13
Opcode.java
虚拟机使用的关键字
StoneVM.java
虚拟机类
HeapMemory.java
堆的接口,虚拟机使用堆作为全局变量环境
StoneVMEnv.java
虚拟机使用的环境,实现HeapMemory接口,是ResizableArrayEnv的子类
如前所述,实际执行编译操作的是定义了函数的 .def 语句的 eval方法。该方法将进一步调用 .compile方法。函数在编译后,将由Arguments 类的 eval方法执行。
第14章代码注释完成
添加静态类型支持
将函数部分转化为java二进制代码,利用java虚拟机执行
/stone
TypedParser.java
对语法规则进行一些修改
/ast
VarStmnt.java
新定义的抽象语法树节点的对象类型
TypeTag.java
新定义的抽象语法树节点的对象类型
/chap14
TypedEvaluator.java
扩展器,扩展处理带有类型的处理
TypeChecker.java
类型检查
TypeEnv.java
数据类型的环境
TypeException.java
类型检查中抛出的异常类型
TypeInfo.java
stone支持的数据类型
TypedInterpreter.java
添加上述功能后的解释器
TypedRunner.java
添加上述功能后的执行器
TypedNatives.java
对来自于java的原生函数的支持
currentTime.java
原生函数
length.java
原生函数
print.java
原生函数
read.java
原生函数
toInt.java
原生函数
InferTypes.java
扩展器,增加类型推断
InferFuncTypes.java
在函数体执行结束后将UnKnow类型转换为any类型
InferRunner.java
添加上述功能后的执行器
JavaLoader.java
通过javassist来定义新的方法
JavaFunction.java
它的对象用于表示stone中的函数
ToJava.java
将函数转换成java二进制代码
Runtime.java
解决ToJava转换中的一些问题
JavaRunner.java
执行器,最新的启动程序
虽然基本上完全看不懂这一章的代码,但是先这样吧,继续后几章的只是内容。
第19章设计模式介绍
Interpreter设计模式
我们无需在意实际的对象究竟是NumberLiteral还是BinaryExpr只需直接调用eval方法即可。调用eval方法后,语言处理器将根据对象的实际类型选择合适的eval 方法执行。这种方式称为动态方法分派,是面向对象语言具备的基本功能。优点:
如果之后因扩充而新增了一些ASTree类的子类,原有程序也无需做太多修改。
缺点:
随着ASTree的子类的增加,eval方法的数量也会不断增加。由于这些方法分别位于不同的源文件中,因此很难理清全体eval方法具体实现了怎样的功能,可读性较差。
Visttor设计模式
首先,我们无需直接在抽象语法树的相关类中定义eval等方法。为此,我们需要为各个类逐一定义accept这一通用的方法作为替代。另一方面,具体的处理操作将由Visito类型的对象中的方法实现accept方法将接收该对象作为参数,选择该对象中合适的visit方法并执行。 在visitor模式下,各个类的eval方法将汇总于EvalVisitor类,同时,方法名变为visit。EvalVisitor类通过不同的方法,描述了它在访问(visit)NumberLiteral类或BinaryExpr 类等各种不同的类时,应具体执行哪些操作。优点:
能够轻松地添加处理逻辑,假设我们希望实现lookup处理,我们不需要进行这类修改。我们只需定义一个实现了Visitor接口的LookupVisitor类,并在其中定义NumberLiteral类与BinaryExpr类所需的visit方法即可。
缺点:
在添加子类时,比较麻烦。
Visttor设计模式可以利用java的反射,扩展。
这两种设计模式都是非常优秀的面向对象程序设计手法,但都有优缺点。
面向切面编程
本书中采取GluonJ来实现,通过修改器对原有类进行扩展或修改,而不用改变源代码。