编译原理分析器实验
使用自动机理论编写C语言词法分析器，并使用自上而下或者自下而上的语法分析方法编写语法分析器。我们选择使用vue.js纯前端的方法完成编写，具体的分析器代码使用js完成🥂。
效果演示
点击下方链接即可查看分析器最终效果
词法分析器
实验要求
完成 C—语言的词法分析器，词法分析器的输入为 C—语言源代码，输出识别出单词的二元属性，填写符号表。单词符号的类型包括关键字，标识符，界符，运算符，整数， 浮点数，单字符，字符串。每种单词符号的具体要求如下：
- 关键字：while,for,continue,break,else,if,float,int,char,void,return
- 运算符(OP)：+、-、、/、%、=、>、<、==、<=、>=、!=、++、—、&&、||、-=、+=、=、*=、/=等
- 界符(SE)：（、）、{、}、；、，、[、]等
- 整数(IDN)、浮点数（FLOAT）的定义与C相同
- 单字符(CHAR)定义与C语言相同为单引号字符，例如’C’
- 字符串(STR)定义与C语言相同为双引号字符串，例如’STRING’
要能够对输入进行识别分析并生成词素和token序列，一个demo如下：
设计原理
识别表达式
首先我们先给出不同类型词法单元的识别表达式，如下图：
NFA
然后我们采用识别自动机原理，首先根据上图绘出NFA图如下
最简DFA
然后我们对他进行确定化为DFA再进行最小化得到最简DFA图如下
代码设计
因此我们就得到了不同类型词法单元的识别流程，接下来我们参考上面的最简DFA进行代码设计，我们设计了如下几个方法，他们的功能如下
- analyze()：词法分析器入口方法，负责对接收的程序字符串进行分割等操作，然后逐字符读取，当遇到空格即空字符时停止读取进行简单关键字的判断
- isKeyWord(str)：具体是否为关键字的判断方法，原理很简单，读取的str和已定义好的集合进行包含关系判断即可完成
- updateComponentAndToken(str)：生成词素和token序列的方法
具体的工作流程图如下
同时我们对简单的错误进行了判断处理，可以在词法分析阶段就识别出非法变量，字符串、字符错误并进行报错。同时优化程序输入方式，可以在线使用云编辑器编辑或者上传txt程序文件进行程序输入。
语法分析器
实验要求
采用LL(1)自上而下的方法完成语法分析，要能够根据动态输入的文法进行分析，生成First集合Follow集，同时要能够根据生成的First集合Follow集自动生成预测分析表。最后要能够输入自上而下的归约序列。一个简单的示例如下
原理设计
首先我们给出First集和Follow集的求解算法
First集求解算法
Follow集求解算法
预测分析表求解算法
数据结构设计
| 数据结构名称 | 类型 | 功能 |
|---|---|---|
| grammarStr | Array | 存储输入文法 |
| production | Map | 存储非终结符的产生式 |
| FirstMap | Map | 存储每一个符号的First集合 |
| FollowMap | Map | 存储每一个符号的Follow集合 |
| VnSet | Set | 存储非终结符 |
| VtSet | Set | 存储终结符 |
| stack | Array | 用数组模拟预测分析时使用的栈 |
| inStr | String | 要进行分析的语句 |
| table | Array | 预测分析表 |
| token | Array | 存储归约序列 |
代码设计
我们使用了如下的几个方法，他们的功能分别如下：
- dividechar()：对输入的文法进行处理，首先是对复杂的文法语句进行分解，然后识别出非终结符和终结符并存储到VnSet和VtSet并且将每一个非终结符的右侧推导产出式存储到production表中。
- First()：求解First并赋值给FirstMap的入口程序
- getFirst(ch)：具体的对每一个符号进行First集合求解的方法
- getFirstX(s)：具体的对一个字符串进行First集合求解的方法
- Follow()：求解Follow并赋值給FollowMap的入口程序
- getFollow(ch)：具体的对每一个符号进行Follow集合求解的方法
- createTable()：创建预测分析表并对预测分析表进行初始化，插入生成式的入口程序
- insert(X,a,s)：向预测分析表插入生成式的方法
- processLL1()：生成归约序列的入口程序
- displayLL()：将每一个归约步骤存储到token数组中
具体的工作流程图如下
致谢
历时将近两个月的时间终于完成了编译原理大作业，在开发过程中遇到了许多的困难和障碍，但是在开发小组的共同努力下我们最终圆满完成了实验，非常感谢两位开发者wenchog😁和yizhe😣。同时本次作业的完成离不开姜佳君老师👨💼的支持与帮助，在此向您辛勤的付出表示衷心的谢意！
本文由 Langwenchong 创作，如果您觉得本文不错，请随意赞赏🌹
本文永久链接是：https://coolchong.cn/2021/11/15/CompilationPrinciple/
博客内容遵循署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议
您的喜欢是作者写作最大的动力😁！
