【编译原理】学习笔记以及课程设计

编译原理

教材用的是《编译原理》（第三版）陈火旺著，电子版戳这里密码：x4ut
课后习题答案戳这里密码：nkv9
教学PPT戳这里密码：0tfz
PPT习题答案戳这里密码：v9ct
（侵删）

课程设计1——词法分析器

设计题目：手工设计c语言的词法分析器（可以是c语言的子集）
设计内容：处理c语言源程序，过滤掉无用符号，判断源程序中单词的合法性，并分解出正确的单词，以二元组形式存放在文件中。
设计目的：了解高级语言单词的分类，了解状态图以及如何表示并识别单词规则，掌握状态图到识别程序的编程。

定义

词法分析器的功能输入源程序，按照构词规则分解成一系列单词符号。单词是语言中具有独立意义的最小单位，包括关键字、标识符、运算符、界符和常量等。
(1) 关键字 是由程序语言定义的具有固定意义的标识符。例如，C语言
中的void，if，while都是保留字。这些字通常不用作一般标识符。
(2) 标识符 用来表示各种名字，如变量名，数组名，过程名等等。
(3) 常数 常数的类型一般有整型、实型、布尔型、文字型等。
(4) 运算符 如+、-、*、/等等。
(5) 界符 如逗号、分号、括号、等等。

输出设计

词法分析器所输出单词符号常常表示成如下的二元式：
(单词种别，单词符号的属性值)
单词种别通常有：
标识符一般统归为一种；
常数则宜按类型（整、实、布尔等）分种；
关键字可将其全体视为一种；
运算符可采用一符一种的方法；
界符一般用一符一种的方法。
对于每个单词符号，除了给出了种别编码之外，还应给出有关单词符号的属性信息：
单词符号的属性是指单词符号的特性或特征。

分解出正确的单词

过滤掉无用符号

当读入源程序文本，由于空格、换行符视为终态的标志，或者没有对应的状态，所以可以很自然的被过滤掉。

词法分析状态图设计

本算法是c语言的子集词法分析，状态图设计如下：

单词种别码及其表内位置

本词法分析器的单词种别有：关键字，标识符，数值（整形、实型），界符，运算符，字符，字符串。
某些种别的单词有初始化的表：

算法设计

全局变量

int state;//全局变量 bool flag = 0;//编译逻辑检验 string input_str;//输入的字符串 string str;//已确定状态的字符串

数据结构

struct TOKEN { 
    int i; //对应分词的种类 int j; //对应分词在相应表中的位置 int Vt_id; //记录分词在文法中的终结符信息 TOKEN(int a = 0, int b = 0,int c = 0) { 
    i = a, j = b, Vt_id = c; } }; vector<string>TOKEN_k; //关键字表 vector<string>TOKEN_p; //界符表 vector<string>TOKEN_o; //运算符表 vector<string>TOKEN_i; //标识符表 vector<string>TOKEN_c; //常数常量表 vector<string>TOKEN_strc; //字符串常量表 vector<string>TOKEN_charc; //字符常量表 vector<pair<string,int> >ans; //将结果以数据对的形式保存

算法伪代码

 初始化变量； While 从文件中按行读入数据： If 读入字符串 != “#”： i=0： While i< input_str.size()： next_state(input_str[i])； If is_KI()： 查询TOKEN_k表； If 在TOKEN_k表中：生成关键字Token字 Else： 查询TOKEN_i表； If 在TOKEN_i表中：生成标识符Token字 Else： 将当前分词加入TOKEN_i表中，生成Token字 If is_P()： 查询TOKEN_p表； If 在TOKEN_p表中：生成界符Token字 Else：编译程序出错，break If is_C()： 查询TOKEN_c表； If 在TOKEN_c表中：生成常数常量Token字 Else： 将当前分词加入TOKEN_c表中，生成Token字 If is_STRC()： 查询TOKEN_strc表； If 在TOKEN_strc表中：生成字符串常量Token字 Else： 将当前分词加入TOKEN_strc表中，生成Token字 If is_CHARC()： 查询TOKEN_charc表； If 在TOKEN_charc表中：生成字符常量Token字 Else： 将当前分词加入TOKEN_charc表中，生成Token字 i++； If 编译出错：报错，break While end； While end；

算法流程图

参考资料

课程设计一的报告借鉴了在github上找到的某位同学的课程设计报告，具体戳这里密码：oxx4

课程设计2——赋值语句的解释程序

实验目的：了解掌握算符优先分析的基本方法、内容；学会科学思考并解决问题，提高程序设计能力。
实验内容与要求：用算符优先分析方法设计一个分析解释程序，对输入的赋值语句、输出语句、清除语句进行词法分析、语法分析、表达式求值并存储于指定变量中；
若存在错误，提示错误相关信息。
文法表示：
S→v=E|E?|clear
E→E+T|E-T|T
T→T*F|T/F|F
F→ (E)|v|c
语法分析：
单词种别码设计：

算符优先分析法

算符优先分析法是一种简单实用的自下而上分析方法，定义如下：
定义1:若一个文法 G 的任何产生式右部,都不含两个相继出现的非终结符, 则称G为算符文法。
定义2：设G是一个算符文法，任何相继出现的中介符对之间存在如下三种归约优先顺序：

优先关系可以用矩阵表示，称为优先关系表。
定义3: 若文法 G 的任何相继终结符对至多只满足以上关系之一,称该文法为算符优先文法。

FIRSTVT及LASTVT

定义：

对实验给出的文法G进行分析：

对每个非终结符求出这两个集合后,可按如下规则求出各终结符对之间的优先关系:

优先关系表的构建

构造的算符优先关系如下：

算符优先分析的实现

（1）根据实验一，现在的情况是已经分析出了句子的单词，并且变成了单词块，存放在smbol栈中，单词的形式是（种别码，常数值）。
（2）并且分析出了标识符存放在了IDentifierTable idTbl[30]中。标识符的形式是（标识符名字，标识符的值），用-1表示暂未被赋值。
（3）分析出了算符优先分析的优先关系表存放在char
PriorityTable[20][20]中。
（4）归约栈：进行移入、归约操作。

程序设计

首先将符号表的第一个元素#,对应的（种别码，-1）压栈，即

SymbolTbl temp_sym; temp_sym.syn=12; temp_sym.value=-1;//-1代表这个地方不需要 Reource_Symbol.push(temp_sym);//将#压栈

对于堆栈定义两个指针，一个指针pStackTop始终指向栈顶，在栈被修改（push,pop）之后都要修改。另一个堆栈指针是pScanStack，负责对整个堆栈的扫描，不断地查找可归约串的结束位置。
对于符号表，定义Sym_scan_pointer指针，从一开始，对符号表进行扫描。
因为现在不仅是语法分析，还包含了语义分析，我们要定义好语义子程序，比如说“清除语句”，#clear#，我们遇到这个东西时，就要清楚工作台。
因此，我们在进行其他分析之前，先把解决这个问题。
if(sym_length>=3&&(symbol[1].syn==11))
{//清除语句，清除屏幕并且清空标号表中的值
Clear_Symbol_Tbl();
}
下面比较栈中元素和符号表中元素的大小关系：
首先栈扫描指针和栈顶指针同时指向栈顶开始分析：

{

查看栈扫描指针pScanStack所指的元素和符号表指针所指元素的关系。
若为小于：
则将符号表指针所指元素压栈，修改栈的两个指针都指向栈顶。符号表指针下移。
若为等于：
此时要分两种情况：
@1.若是栈扫描指针pScanStack所指的元素和符号表指针所指元素都是#，则查看栈中是否只有两个元素且栈顶元素是否为N，若为真，则说明归约成功，输出栈顶的值，然后结束分析。否则，则报错。
@2.若不是上面的情况，则按照小于关系处理。
若为大于：
进行归约;
}

归约算法设计

1、若该元素为标识符：语义分析：判断标识符是否已定义；弹出栈顶元素，将N（13，标识符的值）压入栈中，这里取了一次巧，即是让N来承载归约的结果，更加方便。重新修改栈顶指针，栈扫描指针，将栈扫描指针指向从栈顶数第一个终结符的位置，即下移。
pScanStack=Reource_Symbol.getTopPointer()-1;
重新定位行列指针（列不变），修改关系。 row_prior=Search_Priority_Setxy(SearchSyn(Reource_Symbol.traverseStack(pScanStack).syn));
Prior_Relation=PriorityTable[row_prior][column_prior];
2、若该元素为常量，则分析的过程和标识符极其相似，唯一不同的是，N(13,值）中的‘值’，一个是从标识符表中查到的，另一个是直接就有的。
3、若该元素为‘=’，这时根据文法的要求，出现等号就应该满足“v=N”这种情况。首先判断是否满足，若不满足则报错，若满足，则将这三个元素归约为一个元素N（13，旧N.value),并且要反填符号表，将该变量的值赋为旧N.value。这一步语义分析十分重要，直接关系着以后引用这个变量时是否能够找到它的值。
idTbl[Reource_Symbol.traverseStack(pScanStack- 1).second].second = Reource_Symbol.gettop().second;//此时栈顶必为E
然后就是修改栈的两个指针，重新定位行列（列不变），修改关系。
4、若该元素为+、-、、/，则这四个的处理方式一样。首先判断栈顶是否满足N op N,op={+|-||/},若满足则归约，否则认为是错误的，进行报错处理。规约之后，同样的将N op N归约为N，并且将
N.value=(N1.value op N1.value)”
然后就是修改栈的两个指针，重新定位行列（列不变），修改关系。
5、若该元素为‘）’，这个时候栈顶一定为（N），若不是，则句子出错，进行错误处理，又因为 ‘(’是大于任何终结符的，因此需要归约将（N）归约为N，做相应的语义分析子程序:
N.value=（N1.value）
然后就是修改栈的两个指针，重新定位行列（列不变），修改关系。
6、若该元素为‘？’根据文法，出现这个东西，就是要打印N?中N的值了，因此先查看栈顶是否满足N？若满足，则归约，并作相应的语义动作，打印。
然后就是修改栈的两个指针，重新定位行列（列不变），修改关系。

参考资料

这篇课程设计参考了这位博主的这篇博文戳这里，谢谢ta

课程设计报告及源代码

戳这里密码：8kzk

复习资料

期末考试复习资料，戳这里密码：okbi
（侵删）