C++实现的LR编译器及C语言虚拟机。总代码量(虚拟机代码+客户端代码):约40k。
为什么采用编译执行而非解释执行?主要原因是:
- 性能考虑
- 编译的话整个代码可以打成一个二进制包扔给虚拟机去执行,实现隔离
- 对内存的要求降低,由于虚页机制,虚拟机内存虚页可动态扩容
- 可以定制一个虚拟机,并进行指令扩展,降低交互API的实现难度
- 文法书写方式:以C++重载为基础的Parser Generator。
- 语义分析:在LR解析的过程中,状态机向符号表提供分析接口,使得状态转换可手动干涉,解决“
A*b
”问题 - 识别方式:以下推自动机为基础,向看查看一个字符、带回溯的LR分析。
- 内存管理:自制内存池。
- 自建库函数:已实现itoa和dtoa,sprintf(待实现)。
- 高精度运算:见
number.cpp
,实现四则运算。 - 网络路径:如查看
google.com
可以输入命令cat /http/www.google.com
,暂时只支持http路径,底层用ASIO实现。目前的方式是阻塞式的。
依赖:
- freeglut
- opengl32
- glu32
- asio
- ws2_32
仿制了exec和fork调用,自动运行code文件夹下的代码。
【管道示例】
【文件操作】
【控制台颜色】
【文件树】
【命令行读写】
【动态IPS调整】
【badapple动画】
【画爱心】
- 第一阶段:实现基本的C++编译器和虚拟机,支持控制流语句,模拟虚页机制。后续支持结构体、指针和汇编。
- 第二阶段:实现最小化标准库,搭建虚拟操作系统。
- 第三阶段:实现图形化用户界面,制作桌面。
- 【Parser系列】实现LR分析——开篇
- 【Parser系列】实现LR分析——生成AST
- 【Parser系列】实现LR分析——支持C语言文法
- 【Parser系列】实现LR分析——完成编译器前端!
- 【Parser系列】实现LR分析——识别变量声明
- 【Parser系列】实现LR分析——解决二义性问题
- 【虚拟机系列】C语言虚拟机诞生!
- 【虚拟机系列】实现Fork!
- 词法分析阶段由lexer完成,返回各类终结符。
- 语法分析阶段由parser完成,输入产生式,通过生成LALR表来进行分析。
- LR识别完成,生成AST完成。
- C语言文法基本实现!请参阅cparser.cpp!支持多种基本数据类型。
- 虚拟机指令生成。
- 图形界面初始化。
文法支持顺序、分支、可选、跳过终结符。目前可以根据LR文法自动生成AST。后续会对AST进行标记。
目前已完成:
- Shell
- 测试用例
代码均在code文件夹下,运行时从该文件夹中读取C文件。
Shell界面:
实现C语言的解析。
生成NGA图,去EPSILON化,生成PDA表,生成AST。
以下为下推自动机:
由于太长,文法定义和下推自动机在根目录下的grammar.txt文件中!
宏的使用(将值改为1即可)
LR分析的调试,修改cparser.cpp中的:
// 输出LR状态转换过程
#define TRACE_PARSING 0
// 输出下推自动机
#define DUMP_PDA 0
// 输出语法树
#define DEBUG_AST 0
// 检查语法树的指针是否正确
#define CHECK_AST 0
虚拟机的调试,修改cvm.cpp中的:
// 输出当前虚拟机指令
#define LOG_INS 0
// 输出当前虚拟机栈和寄存器
#define LOG_STACK 0
// 输出当前虚拟机日志
#define LOG_SYSTEM 1
解析文件的调试,修改cgui.cpp中的:
// 输出解析C语言文件后的合法AST
#define LOG_AST 0
// 输出C语言的include依赖列表
#define LOG_DEP 0
指令生成的调试,修改cgen.cpp中的:
// 输出解析C语言文件中的关键信息,包括类型,函数,参数,表达式等
#define LOG_TYPE 0
LR文法自动机构建的调试,修改cunit.cpp中的:
// 输出规则
#define SHOW_RULE 0
// 输出LR项目
#define SHOW_LABEL 0
// 输出闭包
#define SHOW_CLOSURE 0
虚拟机运行中对于malloc/free的调试,修改cmem.cpp中的:
// 输出内存申请与释放过程中的内存池信息
#define LOG_MEM 0
采用Antlr 4 - C test中的9个c文件。
最新:支持结构体和指针(位置:/code/usr/test_struct,命令:/usr/test_struct)
#include "/include/io"
#include "/include/memory"
#include "/include/string"
struct node {
int value;
node *next;
};
node *create(int n) {
if (n <= 0)
return (node *) 0;
node *new_node = (node *) malloc(sizeof(node));
new_node->value = n;
new_node->next = create(n - 1);
return new_node;
}
int print(node *head) {
while (head) {
put_int(head->value); put_string(" ");
head = head->next;
}
}
int destroy(node *head) {
node *old;
while (head) {
old = head;
head = head->next;
free((int) old);
}
}
int case_1() {
put_string("-- CASE #1 --\n");
node *head = create(10);
print(head);
destroy(head);
put_string("\n");
}
struct node2 {
int a, b;
};
union node3 {
struct _1 {
int a, b;
} A;
struct _2 {
char a, b, c, d;
char e, f, g, h;
} B;
};
int case_2() {
put_string("-- CASE #2 --\n");
node2 *n1 = (node2 *) malloc(sizeof(node2));
strncpy((char *) n1, "ABCD1234", 8);
put_int(n1->a); put_string(" ");
put_int(n1->b);
free((int) n1);
put_string("\n");
node3 *n2 = (node3 *) malloc(sizeof(node3));
strncpy((char *) n2, "1234ABCD", 8);
put_int(n2->A.a); put_string(" ");
put_int(n2->A.b); put_string(" ");
put_char(n2->B.a); put_string(" ");
put_char(n2->B.h);
free((int) n2);
put_string("\n");
}
int main(int argc, char **argv) {
put_string("========== [#6 TEST STRUCT] ==========\n");
case_1();
case_2();
put_string("========== [#6 TEST STRUCT] ==========\n");
return 0;
}
测试文件在test.cpp中,编译为clibparser-test。
9个测试用例均通过。
当前进展:
- 词法分析(LL手写识别)
- 识别数字(科学计数+十六进制)
- 识别变量名
- 识别空白字符
- 识别字符(支持所有转义)
- 识别字符串(支持所有转义)
- 识别数字(除去负号)
- 识别注释
- 识别关键字
- 识别操作符
- 错误处理
- 生成文法表达式
- 生成LR项目
- 生成非确定性文法自动机
- 闭包求解
- 去Epsilon
- 打印NGA结构
- 生成下推自动机
- 求First集合,并输出
- 检查文法有效性(如不产生Epsilon)
- 检查纯左递归
- 生成PDA
- 打印PDA结构(独立于内存池)
- 生成抽象语法树
- 自动生成AST结构
- 美化AST结构
- 美化表达式树(减少深度)
- 设计语言
- 使用C语言文法
- 实现回溯,解决移进/归约冲突问题,解决回溯的诸多BUG
- 调整优先级
- 【关键】解决“
A*b
”问题,部分语义分析嵌入到LR分析之中
- 宏
- include指令(包含代码)
- 对依赖进行拓扑排序,解决菱形依赖问题(包含自身会报错)
- 语义分析
- 识别重名
- 输出错误单词的位置
- 基本类型(单一类型及其指针,不支持枚举、函数指针和结构体)
- 识别变量声明(类型可为结构体)
- 识别函数声明(识别返回类型、参数)
- 识别结构体声明和类型
- 计算变量声明地址
- 识别语句
- 识别表达式
- 代码生成
- 全局变量及初始化
- 局部变量及初始化
- 形参
- 函数调用(及递归)
- 数组寻址(及左值),多维数组定义,一维数组使用
- 数组初始化列表
- 枚举
- 结构体成员(点和指针),嵌套
- 一元运算
- 二元运算
- 短路运算
- 三元运算
- 赋值语句
- 返回语句
- if语句
- for语句
- sizeof
- while语句和do..while语句
- switch语句(default和case)
- break和continue
- 取址和解引用(及左值)
- 强制类型转换
- 类型转换指令
- 运算时类型提升(隐式转换)
- float和double
- 函数指针及调用(调用时不检查类型)
- 支持结构体传参或作为返回值
- 虚拟机
- 设计指令(寄存器式分配)
- 设计符号表
- 解析类型系统
- 生成指令
- 虚页分配(已实现)
- 虚页权限管理
- 运行指令
- 中断指令
- 自动调整IPS
- 扩展指令
- 操作系统
- 多任务机制
- 读取并执行C文件
- exec、wait、fork调用
- 命令行参数
- 用户态禁止修改代码段
- 只有代码段可以执行指令
- 键盘输入接口
- 句柄管理
- 共享代码区
- 内核与用户态分离
- 内存权限管理
- 中断机制
- 虚拟文件系统
- 命令行管道
- 库代码文件
- exec
- fs
- io
- memory
- proc
- string
- sys
- shell
- math
- vector(动态数组)
- itoa(参考自itoa-benchmark)
- dtoa(参考自dtoa-benchmark)
- map(红黑树,设计中)
- 用户例程
- Shell(
sh
, 支持“>”“>>”,历史记录与查询) - 测试用例(
/usr/test
) - 测试用例-控制台绘画(
/usr/draw
) - echo
- pwd, whoami
- VFS: cd, mkdir, touch, cat, ls(-l), ll, rm, tree, write, append
- wc
- range
- head, tail
- grep(only KMP)
- ps(
cat /sys/pc
) - badapple(黑白动画)
- number(高精度四则运算,已实现:加、减、乘、除)
- http_get(
cat /http/path/to/the/host
)
- Shell(
- 虚拟文件系统
- 数据结构
- 账户
- 读取
- 限定操作
- 语义接口(:ls,:ll)
- 存储
- 设备(
/dev/random
,/dev/null
) - 权限
- 锁定
- 链接
- 网络路径(设计中,最好能异步)
- 图形用户界面
- 用OpenGL创建窗口
- 实现控制台输出接口
- 延时功能
- 支持设置缓冲区大小
- 输入功能
- 键盘输入(任务独占)
- 支持前景色
- 支持背景色
- '\7'标记全黑方块
- 支持Ctrl-C中止前台任务
- 支持输入时按左、右、Home、End键移动光标
- 将文法树转换表(完成)
- 根据PDA表生成AST(完成)
- 生成LR项目集时将@符号提到集合的外面,减少状态
- PDA表的生成时使用了内存池来保存结点,当生成PDA表后,内存池可以全部回收
- 生成AST时减少嵌套结点
- 优化回溯时产生的数据结构,减少拷贝
- 解析成功时释放结点内存
- 将集合结点的标记修改成枚举
- 可配置归约与纯左递归的优先级
- LR分析阶段提供语义分析接口
- 美化表达式树(减少深度)
- 解决了字符串转义的问题
- 指针解引用的问题
- 用户键盘输入交互功能
- 解决命令行参数的读取问题
- 解决显示缓存因异常时出错的问题
- 进程退出时管道未及时处理的问题
- 解决词法分析时数字识别问题
- 输入缓冲区上移时的对齐问题
- 回溯式LR分析时遇到错误耗时很长的问题
- malloc和free的问题
- 进制转换时有符号扩展的问题