编译原理实验1

¶实验内容与要求

设计一种程序设计语言并定义其词法，输入使用该程序语言编写的源程序，输出经过词法分析生成的符号表及将源程序的字节流转换成单词的单词流。

创建一个词法分析程序，它支持对正规文法的分析。必须使用DFA（确定性有限自动机）或NFA（非确定性有限自动机）来实现这一项目。该程序的输入是一个文本文件，包括一组由该正规文法产生的产生式以及待识别源代码字符串。该程序的输出是一个符号表（二元式），它由5种类型符号：关键词，识别符，常量，界符和操作符。

¶实验目的：

通过实验理解文法及文法在编写词法分析中的应用、理解符号表及掌握符号管理技术。

¶实验准备：

¶程序设计语言：

程序设计语言为PL0语言，其特点是数据类型只有整数类型，具有三种程序结构（顺序、分支及循环），有过程定义，但过程无参数，允许分程序嵌套定义。具有常量定义、变量定义等。PL0语言的单词分类：分隔符、运算符、常数、标识符及保留字，具体如下

1. 分隔符：.(圆点)、,(逗号)、;(分号)、((左圆括号)、)(右圆括号)、=(等号)及:=(赋值号)；
2. 运算符：分为算术运算符和关系运算符；
3. 算术运算符：+(加)、-(减)、*(乘)、/(除)及+(取正)、-(取负)；
4. 关系运算符：=(等于)、#(不等)、<(小于)、<=(小于等于)、>(大于)、>=(大于等于)及odd(是否为偶数)；
5. 常数：由0到9组成的整形常数；
6. 标识符：由字母开始由字母及数字组成的符号串；
7. 保留字：保留字不分大小写，有如下这些：begin、call、const、do、end、if、odd、procedure、read、then、var、while、write、else、BEGIN、CALL、CONST、DO、END、IF、ODD、PROCEDURE、READ、THEN、VAR、WHILE、WHILE、ELSE；

char *kword[28]={“begin”,“call”,“const”,“do”,“end”,“if”,“odd”,“procedure”,“read”,“then”,“var”,“while”,“write”,“else”,“BEGIN”,“CALL”,“CONST”,“DO”,“END”,“IF”,“ODD”,“PROCEDURE”,“READ”,“THEN”,“VAR”,“WHILE”,“WHILE”,“ELSE”};

• 常数的文法定义：

N::=DDN

D::=[0…9]；

• 标识符的文法定义：

ID::=LTL

L::=[a…z]

T::=LTLD

D::=[0…9]；

1. 单词的处理：一个单词由单词类别及单词值组成。分隔符、运算符及保留字一个单词一个类别，常数一个类别，标识符一个类别，每个类别使用一个整数编码。标识符、运算符及保留字保存在符号表中；
2. 单词表示：使用结构体表示一个单词，结构体的组成如下：

单词类别：使用一个整数编码；

单词值：如果是分隔符、运算符则单词值无意义，如果是标识符或保留字，则单词值为其存储在符号表中的下标，如果是常数，则单词值为常数值；

1. 存储NFA的数据结构为二维结构体，结构体定义如下

struct NFA_set

{

char set[100];

int len=0;

};

用子集法将NFA转化为DFA。

¶实验过程：

• 源程序

Randall Chu / 编译原理实验一 · GitLab (zhuanjie.ltd)

• 运行结果之载图

¶实验总结：

通过本次实验，我学到了很多东西。首先是加深了对编译原理课程的理解，对词法分析有了更进一步的掌握，其次是编程能力的提高。这一次的编译原理课程实验，我更注重数据结构的使用，数据结构的好坏直接决定了代码的复杂度和代码量，有一些可以用链表结构的地方尽量避免用链表，换用数组和一个表示长度的整型变量的数据结构来表示，因为链表虽然方便灵活，但是链接的使用会导致后台运算量的增加。通过这一段时间写词法分析器，我对一个编译器的组成有了更深层次的认识。

如果增加判断数据的类型，新增单精度和双精度数据。单精度：取值范围在正负1.5X10的负45次方到3.4X10的38次方之间，精度为7位数。双精度：取值范围在正负5.0X10的负324到1.7X10的308次方之间，精度为15到16位数。增加科学计数法表示数字的模式，在运算符中新增符号e。如果整数类型引入八进制整数、十六进制整数、长整数及短整数应该在判断数字之前增加判断，新增前缀判断0b、0B为二进制，0开头为八进制，0x、0X开头为十六进制，在判断为几进制数后还要新增判断该数字中的每个数字是否都有该进制的有效的数字。词法分析器的主要任务是读入源程序的输入字符、将它们组成词素，生成并输出一个词法单元序列。过滤掉源程序中的注释和空白，将编译器生成的错误消息和源程序的位置联系起来。有时，词法分析器可以分成两个级联的处理阶段：1）扫描阶段主要负责完成一些不需要生词词法单元的简单处理，比如删除注释和将多个连续的空白字符压缩成一个字符2）     词法分析阶段是较为复杂的部分，它处理扫描阶段的输出并生成词法单元用子集法将NFA转化为DFA。转化过程与课本中子集法的转化过程是一致的。我的程序中，int Is_in(NFA_set temp)函数用于判断新产生的一个子集是否是已经存在的，防止重复。不重复则返回-1，重复则返回重复的编号。void get_closure(NFA_set &temp)函数用于计算ε-closure。bool Is_contained_Y(NFA_set temp)函数用于判断该状态是否是终态。

转化过程是具体实现是：做一个NFA_set类型的栈，新状态不停的进栈，每次从堆栈中弹出一个，计算其转换的结果，是新状态就进栈，重复则丢弃，只记录好dfa的转换，直到栈空。最后成功构造出DFA。对输入源程序的扫描过程很简单，一次读入一个字符，成串的送入匹配和DFA判断其合法性。给出输出结果。

删除注释需要读取到“//”直接跳过本行后面的内容，读取到“/*”则暂停分析程序一路扫描跳过，直到扫描到“*/”恢复程序运行。

宏替换需要在调用宏时，首先对参数进行检查，看看是否包含任何由#define定义的符号。如果是，它们首先被替换。替换文本随后被插入到程序中原来文本的位置。对于宏，参数名被它们的值替换。最后，再次对结果文件进行扫描，看看它是否包含任何由#define定义的符号。如果是，就重复上述处理过程。

宏展开是一个替换的过程，考虑对上述宏的调用则是一个无限递归的展开过程；为了防止无限递归这种情况的产生，宏展开时会做一个标记，再次对于展开时就不再对其进行替换，这种情况同样适用于非直接自引用的情况。如果宏的参数不是被字符串化或与其它token进行拼接，则宏的参数是完全进行替换的。一旦替换完成，替换后的宏体会被再次扫描完成宏体部分的宏展开。