简介

练习和实践编译原理、虚拟机、AOT、JIT。

项目列表

pythonvm: python 2 虚拟机

Parser: 自低向上的语法解析引擎

regex: 正则表达式引擎

c_compiler: C语言编译器

c_interpretor: C语言解释器

c2j: 将C语言代码编译成java汇编代码

Pythonvm

用简单直白的方式实现python虚拟机各种特性，用于学习和研究。

cd pythonvm
mkdir build 
cd build
cmake ..
make
./test ../test_case/24_test_enclosing.pyc

commit列表

整理虚拟机每个特性实现相关的commit便于学习。

垃圾回收

实现copy gc算法框架和主流程 | 完成垃圾回收遍历算法和根节点遍历 | 处理普通对象 | 回收List和Map | 在堆中创建对象 | bugfix | bugfix | bubfix: PyObject oops_do 中调用错了klass的oops_do方法 | bugfix: IntegerKlass的mod方法实现方式会导致gc引起的除o异常 | fixbug: 执行BINARY_MODULO指令时IntegerKlass mod操作触发gc会导致PUSH入栈调用的是gc前的PyList | fixbug:忘记处理CodeObject的内存回收，导致gc后所有引用的堆内对象的内存都被置为0，会直接退出解释执行流程

类和对象

实现type object | 实现isinstance函数 | 实现type函数 | 实现通过类型创建对象的机制 | 添加__name__局部变量 | 将部分list和map替换成pyobject | 实现自定义类型 | 动态设置对象属性 | 添加类方法的测试用例 | 实现类的构造方法 | 对象属性 | 修复类方法调用bug，添加bound function 和 unbound function 测试用例 | 实现操作符重载 | 实现内建函数重载 | 函数调用操作符 | 实现取下标 | 完成取属性机制 | 实现类继承

列表和字典

开发内建列表类型 | 开发列表取下标的功能 | 实现查找 in 和 not in 指令 | 开发python 内置list 的append方法 | 实现list通过下标修改的机制 | 实现list index 方法 | 实现list pop方法 | 实现list del 指令 | 实现list remove方法 | 实现list reverse方法 | 开发list sort方法 | 实现迭代器 | 保存频繁使用的字符串, 避免重复创建销毁 | 实现list add 方法 | 实现list mul方法 | 实现字典定义相关机制 | 实现dict setdefault方法 | 实现字典删除机制 | 实现dict keys方法 | 实现dict value方法 | 实现dict items方法和unpack sequence 指令 | 实现dict遍历 | 实现函数扩展参数 | 实现闭包 |

函数和方法

开发函数执行的栈帧FrameObject | 条件判断错误，坑死人，只能单步调试一步一步分析 | 实现makefunction指令执行 | 实现call function 和 return value 指令 | 开发全局变量和builtin变量机制 | 实现函数传参机制 | 实现函数默认参数机制 | 实现native函数机制 | 开发类方法调研机制

基本数据类型

使用Klcass Oop二元结构实现类机制 | 完成整数和string改造

控制流

创建解析器,搭建基础执行逻辑 | 完成加和print指令执行 | 完成分支结构所需字节码解析执行 | 实现全局的true false none | 实现map | 修复map实现的bug，主要是get时比较key是否相等的逻辑错误 | 实现string equal方法，不然无法用作map的key | 开发while循环和变量指令执行功能 | 实现break语句

pyc文件解析

创建python虚拟机项目，开发文件读取模块 | 开发arraylist | 定义对象基类 | 定义字符串类 | 定义整数类 | 定义codeobject类 | 定义pyc文件解析类 | 调通项目 | 完成读取字节码 | 解析常量列表，完成int和string类型数据的读取 | 补充元组几种数据类型的解析 | 定义字节码 | 完善codeobject解析

parser

自己动手实现编译前端词法解析语法分析相关算法

词法分析

通常都是用‘硬编码’的方式实现，特定语言的编译器前端都是这种方式，比如javac gcc clang等。为了更通用可以使用模式识别匹配算法，定义自己的词法规则，就可以支持多种语言的词法分析，最终可以做成Flex这样的项目，生成词法解析器。其中用到的技术就是正则表达式。为了研究算法，这里主要关注正则表达式的实现。

使用有限状态机实现整形和浮点型数值识别器

cd FinitStateMachine
mkdir build
cd build
cmake ..
make
./FinitStateMachine 123.45

commit

定义词法分析模块接口 | 完成词法解析简单实现 | 定义有限自动机接口 | 完成状态机状态初始化 | 完成状态装换逻辑 | 搭建有限状态自动机执行流程 | 完成状态机识别逻辑

正则表达式

将正则表达式转换为有限状态自动机

大多数正则表达式识别程序，基本上都是先将其转换为自动机，然后通过驱动自动机来识别输入的，一般是将正则表达式转换为NFA, 将NFA转换为DFA。将正则表达式转换为NFA的算法是由贝尔实验室的Ken Thompson 给出的。连接表达式ab 可以表示如下：

两个表达式进行 OR操作的时候 | 构造图如下：

exp* 的NFA:

如果是自我从复0次，那直接从下面的边走到末尾节点。

exp+（至少重复一次）的NFA:

exp? (重复0或1次)的NFA:

任何复杂的正则表达式它的NFA的构造都是上面几种构造的组合

宏替换

宏定义即：D [0-9]在转换前，需要将正则表达式中的宏进行替换，也就是要将{D}+转换成：{[0-9]}。它有一个难点是需要处理宏定义的间套情况，例如：

D [0-9]

A [a-z]

AD {D}|{A}

替换了宏AD之后，还需要继续替换D 和A.

cd regex
mkdir build
cd build
cmake ..
make
./regex ../test_macro.txt {AD}.{AD}+

commit

创建正则表达式项目 | 开发宏扩展功能 | 开发正则表达式宏预处理逻辑 | 项目重构 | 重构LexerBuffer | 将词法解析逻辑封装到单独模块

正则表达式词法解析

正则表达式其实是由一组由普通字符和特殊字符组合而成的一种表达形式。特殊的字符有特殊的含义，在正则表达式中，特殊字符有：+ ? { } [ ] ( ) . ^ $ “ \ 。普通字符和特殊字符结合在一起时，需要进行不同的解读，正则表达式词法解析麻烦的就是处理这种情况。

cd regex
mkdir build
cd build
cmake ..
make
./regex ../test_macro.txt {AD}.{AD}+
# ./regex ../test_macro.txt "[\b\r\n]"
# ./regex ../test_macro.txt [\"+*?\"]
# ./regex ../test_macro.txt [\\x1F]

commit

开发正则表达式词法解析逻辑 | 开发正则表达式词法解析功能测试逻辑 |

构造简单的正则表达式对应的NFA状态机

term ->  character | [...] | [^...]

任何复杂的形式，都建立在多种简单的形式组合之上。

cd regex
mkdir build
cd build
cmake ..
make
# 单字符
./regex ../test_macro.txt a
# 匹配任意字符
# ./regex ../test_macro.txt .
# 字符集匹配
#./regex ../test_macro.txt [a-zA-Z]
# 字符集取反
# ./regex ../test_macro.txt [^a-zA-Z]

commit

开发构造nfa需要的基础数据结构和状态节点管理模块 | 开发单字符匹配规则构造 | 开发正则表达式‘.’匹配规则构造逻辑 | 开发正则表达式字符集构造逻辑 | 开发正则表达式字符集取反逻辑 | 打印nfa和测试nfa构造逻辑

构建复杂的正则表达式对应的NFA状态机（闭包连接OR）

正则表达式解析语法：

expr -> expr “|” cat_expr

| cat_expr

cat_expr -> factor cat_expr

| factor

factor -> term* | term+ | term?

term -> [string] | . | character | (expr) | [ ^string]

cd regex
mkdir build
cd build
cmake ..
make
# *
./regex ../test_macro.txt [0-9]*
# +
# ./regex ../test_macro.txt [0-9]+
#?
# ./regex ../test_macro.txt [0-9]?
#& 连接
# ./regex ../test_macro.txt [0-9]*[a-z]
# | OR操作
# ./regex ../test_macro.txt "[0-9]*|[a-z]+"
# ()
# ./regex ../test_macro.txt "([0-9])*|([a-z])+"

commit

实现正则表达式*闭包的nfa构造 | 实现正则表达式+闭包的nfa构造 | 实现正则表达式？选择操作的nfa构造 | 将正则表达式闭包操作整合到factor中 | 实现正则表达式连接操作的nfa构造 | 实现正则表达式OR操作的nfa构造 | 实现正则表达式()处理机制

NFA 状态机识别字符串

对应给定的一组初始状态，通过他们的ε边所能达到的状态的集合，我们称之为ε闭包记做ε-Closure，从输入中，读入字符后，得到的跳转状态要从ε闭包集合中找能够读取字符的状态，得到转移状态集合。得到转移状态集合后，求转移状态集合的ε闭包。继续读入字符，求转移状态集合。就这样循环直到处理完所有输入字符，最终的集合中如果有接受状态就识别成功。

ε-Closure({17}) = { 5,9,17,1,3,4 }

move({5,9,17,1,3,4}, ‘1’) = {2, 10}

ε-Closure({2, 10}) = { 10,5,2,11,1,4 }.

.....

cd regex
mkdir build
cd build
cmake ..
make
./regex ../test_macro.txt "{D}*\.{D}|{D}\.{D}*"
# 控制台输入要识别的数字
#Input string:
#1.2

commit

实现求集合的ε-Closure | 实现求对应字符的跳转集合 | 实现nfa 识别字符串

NFA转DFA

nfa转dfa的过程和使用nfa识别字符串的过程类似，先求初始状态ε-Closure，得到初始状态集合，一个nfa状态集合对应一个dfa节点，将新产生的dfa节点加入到一个列表中，然后遍历dfa节点对应nfa集合中所有状态的可接受的输入，求得每个输入的转移集合，求这些转移集合的ε-Closure，这些ε-Closure对应新的nfa节点，再将这些新的dfa节点入到列表中，加入时需要判断列表中是否已经存在同样的dfa节点（判断两个dfa节点对应的nfa集合是否相同），不存在才加入，如果存在则不产生新的dfa节点。继续求新加入的集合的转移集合，如此循环直到没有新的集合产生。

cd regex
mkdir build
cd build
cmake ..
make
./regex ../test_macro.txt "{D}*\.{D}|{D}\.{D}*"

commit

创建构建DFA所需的基础数据结构和dfa节点管理模块 | 将nfa相关逻辑从regex类中挪到nfa类里 | 实现nfa转dfa算法

DFA最小化

NFA转化的DFA不是最优的其中有些节点可以合并，DFA最小化就是要去掉和合并不必要的节点。

1.把所有状态节点分成两分区，接收状态为一分区，非接收状态为一分区

2.根据每一个状态节点对应输入字符后的跳转情况，进行下一步分区。将那些根据输入字符跳转到的节点不在同一分区（不在本分区）的节点切分成新的分区。

不断的迭代，直到所有分区无法再分割，根据分割后的情况，我们把点到点的转移关系转化成分区与分区的转移关系，就得到一个新的DFA。

cd regex
mkdir build
cd build
cmake ..
make
./regex ../test_macro.txt "{D}*\.{D}|{D}\.{D}*"

commit

实现dfa节点分区算法 | 构建最小化后的dfa的跳转表

后续

1.使用更高效的算法 An Efficient and Elegant Regular Expression Matcher in Python.

2.使用Jit加速

3.支持更多的规则

语法分析

语法规则有一种固定的表现形式称之为Backus-Naur 形式，简称为 BNF. BNF 的格式化表现为，Symbol -> definition. definition 是对Symbol 的解释，例子：

句子 -> 主语动词谓语从句

具体的说，-> 左边是一个抽象概念，右边是对抽象概念的解释，解释中又可能包含抽象概念，其中包含的抽象概念又必须以 Symbol -> definition 的格式来继续展开。-> 左边的是非终结符，右边的不能再继续推导的称为终结符。这样的一条规则称为推导。语法规则包含一组有限的推导。例子：

句子 -> 主语动词谓语从句
主语 -> 名词
动词 -> “看见” | “唱歌”
谓语从句 -> 名词动词
名词 -> “我” | “刘德华”

给定一个句子，判断句子是否符合语法规定的过程，我们称之为语法推导。推导的过程是用-> 右边的内容去替换左边的非终结符，反复进行，直到不能继续替换为止。推导过程，我们总是从最左边开始，找到最左边的第一个非终结符，然后进行替换，这种推导方式叫 left most derivation. 简称LR. 同时，推导的过程是从最顶端的的推导表达式开始进行替换，先替换句子，然后替换主语，然后替换动词，这种由上到下的过程，也叫作自顶向下的分析。

我们可以将每一个非终结符定义一个函数，替换的过程就是调用对应的函数，用计算机伪码表示是这样的：

句子(buffer) {
  主语(buffer);
  动词(buffer);
  谓语从句(buffer);
}

主语(buffer) {
  名词(buffer);
}

名词(buffer) {
  if (buffer[0] == “我”) {
    buffer = buffer.substring(1);
    return;
  }
   if (buffer[0,1,2] == “刘德华”) {
     buffer = buffer.substring(3);
     return;
   }
}

动词(buffer) {
    if (buffer[0,1］== “看见” || buffer[0,1] == “唱歌") {
         buffer = buffer.substring(2);
         return; 
     }
}

整个解析过程形成一种树状结构，称为语法解析数。语法分析的实现如果只为特定语言服务，就可以使用以上描述的方式实现，像javac。这种方式类似“硬编码”，也可以做成一个通用的框架，实现语法分析的自动推导，只需要定义自己的语法规则，就可以支持多种语言的词法分析，最终可以做成yacc这样的框架可以生成语法解析器，

很多语法的推导过程，可以转换为压栈式DFA,称之为压栈式有限状态自动机(PDA)。就是DFA加一个堆栈，这个堆栈就是将解析过程函数调用隐含的堆栈调用转变为显示调用。类似用非递归方式实现二叉树后序遍历。

使用PDA做自顶向下的语法分析，在开始时，堆栈会先被压入语法推导的第一个非终结符节点，语法步骤如下：

如果解析堆栈是空的，那么语法解析结束。
如果栈顶端是非终结符，那么将它对应的右边推导以逆向的方式压入堆栈，例如如果有推导：

a -> b c d,那么我们先将d 压入栈，然后是c,然后是b.如果右边是ε，那么我们就将栈顶元素弹出即可。

如果栈顶是终结符，那么该终结符必须与当前读入的字符匹配，若不然，则出现语法错误，如果匹配，那么将它弹出栈顶，然后转到步骤1.

DFA的作用不再是状态跳转，当前状态（栈顶元素）和输入字符（token）不是对应跳转的下一个状态，而是对应于某个动作。这个动作一般是将指定的状态压入堆栈或弹出栈顶元素，编译器中的语义分析，代码生成等。

自低向上的语法解析

实现LALR(1)算法实现

cd Parser
mkdir build
cd build
cmake ..
make
./CParse ../test.c

执行过程每一步都会打印日志，可以通过日志查看推导和解析过程，执行完最终输出“The input can be accepted”表示正确解析。

commit

C语言编译器

cd c_compiler
mkdir build
cd build
cmake ..
make
./c_compiler ../test.c

执行过程每一步都会打印日志，可以通过日志查看推导和解析过程，执行完最终输出“The input can be accepted”表示正确解析。

commit

C语言解释器

在语法解析的过程中构造语法执行树，本质上也是一颗多叉树，一般来说，每一个非终结符都会对应一个节点。遍历这个树，然后在合适的节点，执行某种动作实现执行C语言源代码的效果。

cd c_interpretor
mkdir build
cd build
cmake ..
make
./c_interpretor ../test.c

commit

c2j

将c语言代码编译成java汇编代码后可以用java汇编编译器编译成class文件，然后通过java虚拟机执行。

一个hello world的jiava代码:

public class CSourceToJava {
  public static void main(string[]) {
    System.out.println("Hello World");
  }
}

对应的java汇编代码:

.class public CSourceToJava
.super java/lang/Object

.method public static main([Ljava/lang/String;)V
	getstatic	java/lang/System/out Ljava/io/PrintStream;
	ldc	"Hello World"
	invokevirtual	java/io/PrintStream/println(Ljava/lang/String;)V
	return
.end method
.end class

.class .super是宏指令，getstatic ldc invokevirtual是操作符指令, 所有的指令大概就是这两种指令的组合

运行项目:

cd c2j
mkdir build
cd build
cmake ..
make
./c2j ../test.c
java -cp ../oolong.jar COM.sootNsmoke.oolong.Oolong CSourceToJava.j
java CSourceToJava

commit

搭建代码生成基本框架，实现hello world程序生成 | 生成基本操作和函数定义声明的java汇编代码

huyu-tom/Compiler

简介

项目列表

Pythonvm

commit列表

垃圾回收

类和对象

列表和字典

函数和方法

基本数据类型

控制流

pyc文件解析

parser

词法分析

使用有限状态机实现整形和浮点型数值识别器

commit

正则表达式

将正则表达式转换为有限状态自动机

宏替换

commit

正则表达式词法解析

commit

构造简单的正则表达式对应的NFA状态机

commit

构建复杂的正则表达式对应的NFA状态机（闭包连接OR）

commit

NFA 状态机识别字符串

commit

NFA转DFA

commit

DFA最小化

commit

后续

语法分析

自低向上的语法解析

commit

C语言编译器

commit

C语言解释器

commit

c2j

commit