C++实现的LR编译器及C语言虚拟机。代码量：约11k。

• 文法书写方式：以C++重载为基础的Parser Generator。
• 语义分析：在LR解析的过程中，状态机向符号表提供分析接口，使得状态转换可手动干涉，解决“A*b”问题
• 识别方式：以下推自动机为基础，向看查看一个字符、带回溯的LR分析。
• 内存管理：自制内存池。

仿制了exec和fork调用，自动运行code文件夹下的代码。

【管道示例】

【文件操作】

【控制台颜色】

【文件树】

• 第一阶段：实现基本的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进行标记。

目前已完成：

1. Shell
2. 测试用例

代码均在code文件夹下，运行时从该文件夹中读取C文件。

Shell界面：

实现C语言的解析。

生成NGA图，去EPSILON化，生成PDA表，生成AST。

以下为下推自动机：

由于太长，文法定义和下推自动机在根目录下的grammar.txt文件中！

以下为下推自动机的识别过程（太长，略），如需查看，请修改cparser.cpp中的：

#define TRACE_PARSING 0
#define DUMP_PDA 0
#define DEBUG_AST 0
#define CHECK_AST 0

将值改为1即可。

虚拟机的调试，修改cvm.cpp中的：

#define LOG_INS 0
#define LOG_STACK 0

将值改为1即可。

采用Antlr 4 - C test中的9个c文件。

测试文件在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
  • 取址和解引用（及左值）
  • 强制类型转换
• 虚拟机
  • 设计指令（寄存器式分配）
  • 设计符号表
  • 解析类型系统
  • 生成指令
  • 虚页分配（已实现）
  • 虚页权限管理
  • 运行指令
  • 中断指令
  • 扩展指令
• 操作系统
  • 多任务机制
  • 读取并执行C文件
  • exec、wait、fork调用
  • 命令行参数
  • 用户态禁止修改代码段
  • 只有代码段可以执行指令
  • 键盘输入接口
  • 句柄管理
  • 共享代码区
  • 内核与用户态分离
  • 内存权限管理
  • 中断机制
  • 虚拟文件系统
  • 命令行管道
• 库代码文件
  • exec
  • fs
  • io
  • memory
  • proc
  • string
  • sys
  • shell
• 用户例程
  • Shell(sh)
  • 测试用例(/usr/test)
  • echo
  • pwd, whoami
  • VFS: cd, mkdir, touch, cat, ls(-l), ll, rm, tree
  • wc
• 虚拟文件系统
  • 数据结构
  • 账户
  • 读取
  • 限定操作
  • 语义接口（:ls,:ll）
  • 存储
  • 权限
  • 互斥
  • 链接
• 图形用户界面
  • 用OpenGL创建窗口
  • 实现控制台输出接口
  • 延时功能
  • 支持设置缓冲区大小
  • 输入功能
  • 键盘输入（任务独占）
  • 支持前景色

1. 将文法树转换表（完成）
2. 根据PDA表生成AST（完成）

• 生成LR项目集时将@符号提到集合的外面，减少状态
• PDA表的生成时使用了内存池来保存结点，当生成PDA表后，内存池可以全部回收
• 生成AST时减少嵌套结点
• 优化回溯时产生的数据结构，减少拷贝
• 解析成功时释放结点内存
• 将集合结点的标记修改成枚举
• 可配置归约与纯左递归的优先级
• LR分析阶段提供语义分析接口
• 美化表达式树（减少深度）
• 解决了字符串转义的问题
• 指针解引用的问题
• 用户键盘输入交互功能
• 解决命令行参数的读取问题
• 解决显示缓存因异常时出错的问题

1. CParser
2. CMiniLang
3. vczh GLR Parser
4. antlr/grammars-v4 C.g4