基于Java实现的编程系统实验【100013088】

# 编译原理课程实验报告 ## 1.课程主要目的 - 加深对编译原理及编译程序构造过程的理解 - 增强程序设计能力 - 学会编写工具软件 ## 2.课程要求 ### SeuLex - Lex输入文件的解析 - 正规表达式的解析 - 一个正规表达式到NFA的转换算法实现 - 多个NFA的合并 - NFA的确定化和最小化算法实现 - 返回状态与返回内容的对应 - SeuLex应用 ### SeuYacc - Yacc输入文件的解析 - 上下文无关文法到对应LR(1)文法的下推自动机的构造 - LR(1)文法的下推自动机到相应分析表的构造 - LR(1)总控程序的构造(查表程序) - LR(1)到LALR(1)的映射 - 符号表的构建与相应管理程序 - 语义动作程序的加入 - SeuYacc的应用 ## 3.工具使用 > 本次实验, 使用了众多的开源工具进行辅助, 下面我将列出最主要的几种. 这一节可以完全跳过阅读. ### Linux [](https://rawforcorvofeng.cn/linux.png) - 操作系统 在此次开发中, 为了大家环境的统一, 也为了使用已有的成熟的开发工具 我们全组使用了Linux作为系统开发环境. ### GCC - 编译器 作为编译器被使用: 项目中也大量使用了`C++11`的新特性, 使用成熟编译器极大的提高了 开发效率 ### GDB - 调试工具 内存泄露以及`Segmentation fault`调试的利器, 有些时候针对某个断点的透彻调试更有 效率, GDB的命令行模式有时更加清晰明了 ### Git [](https://rawforcorvofeng.cn/git.png) - 版本控制 使用Git轻松进行了协作, 即使组很小, 我们也采用了协作方式, `Git`的使用大大减轻了 交流的困难 ### CMake(Makefile) - 编译安装工具 整个项目构建均使用CMake, 跨平台支持性良好, 可以支持众多的IDE构建项目. 动态链接库, 静态链接库的使用支持大大简化了项目构建难度, 使得开发者能够尽快的专注于代码 ### Qt Creator [](https://rawforcorvofeng.cn/qtcreator.png) - IDE 与CMake相仿的跨平台开发利器, 组员均在Linux上进行开发. 相比于`Eclipse`, `Qt Creator`对`CMake`优秀的支持减轻了我们生成项目的烦恼 ### valgrind [](https://rawforcorvofeng.cn/valgrind.jpg) - 软件分析工具 由于项目使用C++进行编写, 内存控制十分头疼, 使用`valgrind`. 可以方便分析泄露, 在 项目进行过程中, 有不止一处的内存泄露, 凭借`valgrind`可以很快找到泄露位置, 由于 我们水平所限, 仅用来进行泄露分析 ### lex&yacc - 编程工具 项目中使用了lex与yacc进行了语法与语义分析示例, 在项目尚未开始时, 我们需要首先对 Lex与Yacc进行理解, 而已有的工具可以帮助我们快速入门 ## 4.Lex设计 > Lex为整个项目的第一个核心组件, 下面本文档将会分为 进行介绍 ### Lex架构分析 [](http://rawforcorvofeng.cn/用lex创建一个词法分析器.png) > 此图形象的介绍了`Lex`的使用场景以及我们将要实现的目标: `Lex`编译器, 一个可以读 取`Lex`源程序(lex.l), 并生成lex.yy.c的工具, 抛开`NFA`, `DFA`这些专业术语不说, 我们已经对当前所做的项目的输入输出了解, 剩下的实现细节将由文档后文慢慢道来. ### 输入文件(lex源程序) - 由于实现难度, 本项目中使用的源程序与标准lex源程序有所不同, lex源程序存放在 `./input/require.l`中, (源程序片段) ``` %{ # include "stdio.h" # include "y.tab.h" # define LT 1 extern int lineno; int isDigit(char ch) { if(ch <= '9' && ch >= '0') return 1; return 0; } int isLetter(char ch) { if((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) return 1; return 0; } %} %! letter=isLetter digit=isDig %! %% ({letter}|_)({letter}|_|{digit})* { int id = getKeyId(SYLEX_TEXT); if(id != 0) printf("<%s,->\n", SYLEX_TEXT); else { printf("<$ID,%s>\n", SYLEX_TEXT); } } %$ {digit}+(%.{digit}*)?((E|e)(%+|-)?{digit}+)? { printf("<$NUM,%s>\n", SYLEX_TEXT); } %% ``` > 标准的`lex源文件`是没有中间的`%! %!`段的, 自行编写程序时, `[0-9], [a-zA-Z]` 很难进行表述, 所以这里采用一种事先定义函数的形式, 可以由自定义程序进行单个 字符的解析 ### 输出文件(lex词法解析程序) - 该输出文件中, 主要由`scaner`函数构成 ``` //扫描函数 void SYLEX_scanner(char *str) { char ch = ' '; while(ch != '\0') { //printf("%c %d\n", ch, SYLEX_STATE); switch(SYLEX_STATE) { case 0: { //篇幅原因不进行展开 //... break; } case 1: { ch = *str++; SYLEX_TEXT[SYLEX_TEXT_LEN++] = ch; if(isLetter(ch)){ SYLEX_STATE = 30; } else if(isDigit(ch)){ SYLEX_STATE = 31; } else if(ch == '_'){ SYLEX_STATE = 32; } else { SYLEX_TEXT[SYLEX_TEXT_LEN-1] = '\0'; SYLEX_TEXT_LEN = 0; SYLEX_STATE = 0; str --; //--------------------- { int id = getKeyId(SYLEX_TEXT); if(id != 0) printf("<%s,->\n", SYLEX_TEXT); else { printf("<$ID,%s>\n", SYLEX_TEXT); }} //--------------------- } } break; } } } int main(int argc, char **args) { if(argc == 1) { printf("没有输入源文件名"); return 0; } else if(argc == 2) { strcpy(SYLEX_FILE_NAME, args[1]); sprintf(SYLEX_OUT_FILE_NAME, "%s.out", SYLEX_FILE_NAME); } else { strcpy(SYLEX_FILE_NAME, args[1]); strcpy(SYLEX_OUT_FILE_NAME, args[2]); } FILE* file = fopen(SYLEX_FILE_NAME, "r"); while(NULL != fgets(SYLEX_BUFF, SYLEX_MAXSIZE_BUFF, file)) { ++SYLEX_LINE; SYLEX_scanner(SYLEX_BUFF); } return 0; } ``` > 此文件为`Lex`程序的输出文件, 可以看到`case 1`中添加了有关解析式的使用, 在Lex运行 过程中, 将上方的`lex源文件`进行了正则解析, 并对匹配到的正则表达式进行操作, 在case1中, 我们可以得到下面的正则表达式所对应的操作输出 ``` ({letter}|_)({letter}|_|{digit})* { int id = getKeyId(SYLEX_TEXT); if(id != 0) printf("<%s,->\n", SYLEX_TEXT); else { printf("<$ID,%s>\n", SYLEX_TEXT); } } ``` ### 处理流程 - 当我们已知了`Lex`程序的输入输出后, 接下来要介绍流程的介绍, 接下来, 文档将 会通过简单的示例介绍从正则表达式开始的整个流程, 1.假设我们有如下正则表达式`a*(b|(cd?))+`与表达式`ef` 2.进行正则表达式到`NFA`转换 [](http://rawforcorvofeng.cn/a-nfa.jpg) [](http://rawforcorvofeng.cn/ef-nfa.jpg) > 转换过程 在Re2NFA类中, 定义有`re2post`与`post2nfa`函数, 分别完成中缀正则表达式转为后缀, 以及后缀表达式转换为NFA, 具体实现敬请查看项目代码中`./lex/nfa.h` 3.进行`NFA`表达式合并 [](http://rawforcorvofeng.cn/a-ef-merge-nfa.jpg) > 合并过程 由于合并过程也�