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 0LR文法自动机构建的调试，修改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的问题
- 进制转换时有符号扩展的问题