2024/05/10 工作日志

好久不见！

在二月份的时候，本项目就已经开发完成，并投稿至一个科创比赛。令人震惊的是：现在本项目已经一路过关斩将参与国家级评选了。

为了让项目准备更充分，我决定进行更新。

本次的更新将会从语法分析器直接跳跃到完整的编译器、虚拟机。

更新了依赖库

本次新增了BinaryReader.hpp、BinaryWriter.hpp和ByteMap.hpp。

这三个库的接口定义都较为简单，故不详解，只需花费两分钟即可了解新增的库。

ByteMap的接口定义和其他Map类的差别不大。我认为唯一要解释的就是BinaryWriter中的write_i是 Write Integer（写入整形） 的缩写。

虽然新增的内容不多，但是在标准C实现的依赖库中（即stdc_implemented目录下的源码），我进行了大量的翻新，其翻新的目的主要是为了优化。

下面我将挑选变动最大的ArrayList.hpp和String.hpp进行讲解。

1. 首先是ArrayList

原先的ArrayList采用用多少给多少的内存分配机制：新增一个元素，就realloc一次，删除一个元素，还是realloc一次。

显然这种机制在理论上不浪费一丁点内存，但在实际上容易造成大量的内存碎片，并且性能损耗太多。

在此基础下，我根据min0911_的建议（感谢），采取了双倍扩容法。

双倍扩容法的机制能概括为：

• 内存占用只增不减
• 如果内存不够用，就按照原内存占用大小进行双倍扩容

这可以使整个程序关于ArrayList内存分配的时间复杂度从线性级降为对数级。

1. 其次是String

String也曾和ArrayList一样，所以我进行了优化。

String的优化则采用栈缓存法。

栈缓存法的机制能概括为：

• 设立一个位于栈的内存块S（默认S的大小为32字节，该大小可自定义）
• 如果S能够存的下数据（即数据占用的大小小于S的大小），就用S存储，否则使用内存分配

在程序运行当中，经常出现一些长度较小的String，完全可以使用栈进行缓存，这样甚至用不到内存分配。

1. 最后我们来看看优化成果

本次统计了虚拟机运行程序时在后台的内存分配次数，当时采用了计数器来计数内存分配次数，不过由于年代久远，具体数据可能会记错，所以会有微小差别，实验并不严谨，仅供参考。

||String|ArrayList| |--|--|--| |优化前|270300次|5785次| |优化后|0次|837次|

值得注意的是，String的内存分配次数在优化后达到了0次！这也就意味着程序在运行过程中，单个String的内存占用都没有超过32字节。

去除了预处理器

我去除了预处理器，并更改了架构。

更新了Ast

src/ast目录下的变动较大，删除了SFNName节点，并新增了DefVar节点，最后补充了所有Ast类的构造函数。这些节点主要是为了运行时而变动的。

但是Ast的理论架构有变：编译时生成的Ast和运行时的Ast在叶子节点上有略微差别，后续的写了Ast与AstIR之间的互转工具部分会提及，为了区分，我们将运行时的Ast称为Running-Ast。

更新了DataType

src/data_type目录下的变动不多，主要变动位于MethodType。下面讲解一下与MethodType有关的原理。

在Stamon中。所有的函数对象都拥有自己的容器，对全局函数而言，它的容器为null；对类成员函数而言，它的容器就是它所在的类对象。

例如有一下stamon源码：

``` func f {}

class cls { func f(self) {} }

def obj = cls.new; ```

其中f的容器就为null，而obj.f的容器则是obj本身。

利用容器的机制，在调用类成员函数时，可以将其容器传给self，从而实现类成员函数访问其他成员。

而在MethodType当中，容器的实现则是： C++ ObjectType* container; //容器

完成了编译器

这些源码位于src/compiler目录下

我们规定：Stamon源码的文件后缀为.st

词法分析器的变动不大。所以我们先来看看语法分析器。

目前的语法分析器已经没有已知bug了。本次的更改也着重于实现对多文件的语法分析。

最重要的是新增的Compiler.hpp，Compiler主要对编译器进行了封装。你只需要向Compiler提供相应的参数，就能实现编译。

以下是Compiler的讲解：

• Compiler(STMException* e)：构造函数，需要传入异常类。
• void compile(String filename, bool isSupportImport)：编译源码，filename为需要编译的源码文件名，isSupportImport声明了是否支持导入其他源码（有些平台并不支持多文件操作，所以我设置了这个参数），如果源码当中需要导入源码，则报错。在执行该函数之后应该要检查是否存在异常。编译出的结果会存入src成员。
• 这里需要补充的是：src成员的类型为ArrayList<SourceSyntax>，其中，SourceSyntax定义于Parser.cpp。SourceSyntax由ast::AstNode* program（单个文件的语法树）和String filename（文件名）构成。

编写了Ast与AstIR之间的互转工具

这些工具位于src/ir目录下

AstIR是一种中间代码表示形式，可以将Ast展开为一个数组。这样就可以把Ast转为AstIR，并将AstIR以字节码的方式写入。读取时也只需要读取AstIR，并重组成Ast即可。

AstIR的格式和HTML的格式类似：由逻辑单元、数据单元和结束单元组成。一棵Ast可以通过深度优先遍历转为AstIR。

这样的描述也许会较为拗口，我们来看一个示例：

考虑以下Ast: Add |-a |-Sub |--b |--1 该Ast可以转为以下AstIR： <Add> //此为逻辑单元，以此类推 <data val=a> //此为数据单元，以此类推 <Sub> <data val=b> <data val=1> <end> //此为结束单元，以此类推 <end> 这段AstIR和上面的Ast本质上是等价的。这样只需将Ast转为AstIR，就能获得一系列单元，方便存入文件。

逻辑单元本质上就是Ast节点的非叶子节点，数据单元本质上就是Ast节点的叶子节点。

我们先来讲一讲AstIR.cpp。

AstIR单元的实现是：

C++ class AstIR { public: int type; /* * 一些特别的规定 * 当type为-1，代表这是一个结束符，即 */ int data; //如果这个IR是字面量或标识符，则data存储着其在常量表中的下标 //否则存储这个IR的具体信息（例如运算符类型） String filename; //IR所在的文件名 int lineNo; //IR所在的行号 };

由于Ast当中的叶子节点只有两种可能：标识符或字面量，所以我把两者统一了起来，设立了DataType的子类IdenConstType，这样常量表里也能存储标识符了。

而数据单元作为Ast的叶子节点，他的type统一为AstLeafType。其中AstLeaf是专门为了运行时而定制的。

Ast和Running-Ast的区别就在于：Running-Ast的叶子节点皆为AstLeaf，而Ast非然。

AstIRGenerator类用于将Ast数据生成为AstIR（同时兼任着AstIR转Running-Ast的任务），它值得关注的接口有：

• ArrayList<AstIR> gen(AstNode* program)：迭代遍历语法树，编译成AstIR
• AstNode* read(ArrayList<AstIR> ir)：AstIR转Ast，如果ir不正确，程序会运行时错误，所以请在运行该函数前检查ir

至此，Stamon的源码将会被转为AstIR，接下来则是写入AstIR至文件了，这一部分的内容位于src/Stamon.hpp，暂时按下不表，在介绍完解释器后会解释。

完成了SFN机制

SFN机制在本项目原所在仓库中有提及，这里再次摘抄：

SFN，全程Stamon For Native（~~真的不是So Fck NVIDIA~~）。是StamonVM的一个调用外部功能的机制。你可以用它与解释器交互。

用不太准确但方便理解的说法是：SFN和JNI类似，都是一种本地库调用机制。

SFN的源码位于src/sfn/SFN.cpp。

SFN在Stamon中的语法规定为sfn port, arg;，其中port必须为整数（默认范围为0~65536），代表着端口号，使用不同的端口号会调用不同的本地库（类似于汇编中的IO），arg则是参数，在调用SFN后，arg可能会变为调用后的结果。

SFN中的本地库可以由用户自定义，可扩展性高，不过我认为应该要给SFN划分具体的标准，哪一部分端口保留用作标准的本地库，哪一部分交给用户自定义。我可能会在后续进行调整。

SFN类的主要接口有：

• SFN(STMException* e, vm::ObjectManager* objman)：构造函数，e为异常类，objman为当前运行时的ObjectManager对象。你可以在构造函数里绑定自己的本地库。详细请参见源码。
• void call(int port, datatype::Variable* arg)：根据端口号调用本地库。

完成了虚拟机

虚拟机的运行原理为：将二进制文件读取为AstIR，交给AstIRGenerator类解析为Running-Ast，最后交给vm/AstRunner.cpp递归运行。

我们规定：Stamon编译后的二进制文件为STVC文件，文件后缀为.stvc

我们来逐步讲解。

首先是二进制文件读取为AstIR，这部分的实现位于src/vm/STVCReader.cpp，STVCReader类的主要接口有：

• STVCReader(char* vmcode, int code_size, STMException* e)：构造函数，vmcode为字节码在内存中的地址，code_size指字节码的大小，e为异常类
• bool ReadHeader()：读取字节码头，读取失败则抛出异常并返回false，否则返回true
• ArrayList<AstIR> ReadIR()：读取AstIR，返回由AstIR组成的ArrayList

想要完整的读取一个STVC文件，应该要先创建一个STVCReader对象，然后先调用ReadHeader读取文件头信息，接着调用ReadIR来读取AstIR。调用这两个函数之后要分别检查是否有异常抛出。

接着是让AstIRGenerator类解析为Running-Ast，这一部分在写了Ast与AstIR之间的互转工具部分里已经详细提及过了，故不再赘述。

最后是交给vm/AstRunner.cpp递归运行，AstRunner类采用了和语法分析器类似的结构，下面我们来看看重点的数据接口及接口：

AstRunner在递归执行Ast时的返回值为RetStatus类。RetStatus，全称Return-Status（返回状态），用于指示当前代码运行状况，我们来看看RetStatus的定义：

C++ class RetStatus { //返回的状态（Return Status） //这个类用于运行时 public: int status; //状态码 Variable* retval; //返回值（Return-Value），无返回值时为NULL RetStatus() {} RetStatus(const RetStatus& right) { status = right.status; retval = right.retval; } RetStatus(int status_code, Variable* retvalue) { status = status_code; retval = retvalue; } };

其中的int status一行用于存储状态码，状态码有以下几类：

C++ enum RET_STATUS_CODE { //返回的状态码集合 RetStatusErr = -1, //错误退出（Error） RetStatusNor, //正常退出（Normal） RetStatusCon, //继续循环（Continue） RetStatusBrk, //退出循环（Break） RetStatusRet //函数返回（Return） };

AstRunner的主要接口有：

1. 抛出运行时异常，这些异常分别是：

C++ void ThrowTypeError(int type); void ThrowPostfixError(); void ThrowIndexError(); void ThrowConstantsError(); void ThrowDivZeroError(); void ThrowBreakError(); void ThrowContinueError(); void ThrowArgumentsError(int form_args, int actual_args); void ThrowReturnError(); void ThrowUnknownOperatorError(); void ThrowUnknownMemberError(int id);

1. 利用excute方法执行Running-Ast，它的函数原型是：

C++ RetStatus excute( AstNode* main_node, bool isGC, int vm_mem_limit, ArrayList<DataType*> tableConst, ArrayList<String> args, STMException* e );

虚拟机在执行过程中会向ObjectManager申请对象，来实现GC机制。

编写了命令行工具

命令行工具的内容主要位于src/Main.cpp和src/Stamon.hpp

我们先来看一看Stamon类。

以下是他的主要接口：

• Stamon()：构造函数
• void Init()：初始化
• void compile(String src, String dst,bool isSupportImport)：编译程序，src为源码名，dst为目标二进制文件名，isSupportImport表示是否支持导入源码
• void run(String src, bool isGC, int MemLimit)：运行程序，src为运行的二进制文件名，isGC表示是否支持GC机制，MemLimit表示如果支持GC机制的话，对象占用内存的最大限制。

Main.cpp的内容主要是命令行解析之类，不再赘述。但是值得注意的是：Main.cpp并不是完全可移植，由于涉及到了平台函数，所以目前仅支持Linux、Windows、MacOS。开发者可以参考该文件自定义命令行工具。

合并原先的文档

我把项目所在的原仓库的工作日志也加入了进来。

运行环境

本项目于Windows环境上调试并具有可移植性，所以如果作为用户，请尽量选择在Windows平台上运行以确保最佳体验。

在运行时，请确保您以配置环境变量，具体的配置方法为：设置一个新的名为STAMON的环境变量，其变量值为可执行文件所在目录的路径，路径末尾不要有类似"\"或"/"的分隔符！

可执行文件架构

可执行文件位于bin/目录下，bin/include目录下为标准库。

在命令行中键入"stamon --help"即可获取stamon的具体使用方法。

编译方法

改自20230916.md：

我在根目录下编写了Makefile。

其中，Makefile的主要用法是： * make release：编译发行版

目前，Makefile能在Windows系统下使用，如果想要在其他系统编译，可以更改Makefile。

编译项目之前，需要确保拥有以下工具（附我的工具版本，可以参考）：

1. make：GNU Make 3.82.90
2. gcc：gcc (x86_64-posix-seh-rev1, Built by MinGW-Builds project) 13.1.0
3. strip：GNU strip (GNU Binutils) 2.39
4. upx：upx 4.0.2

接下来要做的事

1. 编写AST的解释器
2. 编写词法分析的保存功能
3. 编写AST的O1优化器
4. 完善标准库

后记

这一次的文档编写花费了我将近两天的时间，现在回过头来，回想项目成立之初的7月份，我压根没敢想象现在的盛况，无数次的实践都让我有了一丝向前看的底气。

这个项目此时并不是一次练习、一个发明了，而是一种态度。