编译原理课程设计说明书题目：编译器原型设计与开发院（系）：计算机科学与工程学院专业：计算机科学与技术目录1 引言 (1)1.1 设计概述 (1)1.2 设计目标 (2)1.3 小组分工 (3)2 开发过程 (3)2.1 词法分析 (3)2.1.1 消除白空格以及注释 (3)2.1.2 词法分析 (6)2.2 .语法分析 (8)2.2.1 递归下降手工编码 (8)2.2.2 first集合的计算 (8)2.2.3 左递归消除 (9)2.2.4 selection表自动生成 (10)2.2.5 LL(1)手工编码 (11)2.3 语义分析 (11)2.3.1 表达式求值LR(1) (11)2.3.2 四元式 (13)3 测试过程 (14)4 总结 (19)5 参考文献 (20)6 代码附录 (20)1引言编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都配有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。
从功能上看，一个编译程序就是一个语言翻译程序。
语言翻译程序把一种语言（称作源语言）书写的程序翻译成另一种语言（称作目标语言）的等价程序。
一个编译程序的重要性体现在它使得多数计算机用户不必考虑与机器有关的繁琐细节，使程序员和程序设计专家独立于机器，这对于当今机器的数量和种类持续不断地增长的年代尤为重要。
编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。
将编译过程划分成词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段。
1.1设计概述编译原理程序结构框图词法分析词法分析是编译过程的第一个阶段。
这个阶段的任务是从左到右有一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词（也称单词符号或符号）。
这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符基友具体含义。
比如标识符是由字母字符开头，后跟字母、数字字符的字符序列组成的一种单词。
保留字（关键字或基本字）是一种单词，此外还有算符、界符等。
语法分析语法分析是编译过程的第二个阶段。
语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”、“语句”、“表达式”等。
一般这种语法短语，也称语法单位，可表示成语法树。
语法分析所依据的是语言的语法规则，即描述程序结构的规则。
通过语法分析确定整个输入串是否构成一个语法上正确的程序。
语义分析语义分析是审查源程序有无语义错误，为代码生成阶段收集类型信息。
比如语义分析的一个工作是进行类型审查，审查每个算符是否具有语言规范允许的运算对象，当不符合语言规范时，编译程序应报告错误。
中间代码生成在进行了上述的语法分析和语义分析阶段的工作之后，有的编译程序将源代码变成一种内部表示形式，这种内部表示形式叫做中间语言或中间代码。
所谓“中间代码”是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的设计原则为两点：一是容易生成；二是容易将它翻译成目标代码。
很多编译程序采用了一种近似“三地址指令”的“四元式”的中间代码，这种四元式的形式为：（运算符，运算对象1，运算对象2，结果）。
1.2设计目标鉴于我们需要完成编译器的词法分析、语法分析、语义分析、中间代码生成的设计开发，本次课程设计主要完成以下任务：词法分析：1.消除白空格2.消除注释3.词法分析语法分析：4.递归下降手工编码5.first集合的计算6.follow集合的自动计算7.selection表自动生成8.递归下降自动生成9.LL（1）分析手工编码10.LL（1）自动生成11.LR（1）分析手工编码12.左递归消除语义分析以及中间代码生成：13.中缀式转后缀式递归下降编码14.中缀式转后缀式LL(1)编码15.中缀式转后缀式LR1)编码16.表达式求值LL(1)17.表达式求值LR(1)18.四元式1.3小组分工2开发过程2.1词法分析2.1.1消除白空格以及注释这个模块实现的功能主要是对代码中多余的白空格以及注释进行消除。
在文本中输入一段代码，其中可以有多余的空格和注释，经过这个程序运行后，将实现多余空格，注释去除。
设计思路：这个模块一共有6个状态，设为0,1,2,3,4,5，其中状态转换图：字符转换表Ch_Type_Table：为了消除注释需要。
其中在程序中f_留表示为f_save；f_改表示为f_change；f_补表示为f_add；f_删表示为f_delete；Action_Table表示为void(*Action_Table[6][6])(void)。
2.1.2词法分析设计思路：1、把消除白空格、消除注释、识别标识符id，识别整数di，识别运算符、识别界符、识别双引号内的注释分层次画状态机，使状态机清晰易懂，方便其他同学学习；2、以0状态为中转，每一层次的状态机遇到不是该层次的内容（识别了一个词元，当前输入不是该词元的内容了），回到0状态去判断该字符应转向的状态。
3、使用了ungetc（）函数，输入回退一个字符，回到0状态中转之前，如果该字符并没有做处理，要ungetc，回退到输入流，那么从0状态会再读出之前没有处理的字符，再判断转换；4、词元存储，用结构体存储数组存储；不同类型的词元对应不同的表，词元结构体中存储的是，该词元的类型（也即表的类型）、在该表中的下标（可以通过该下标找到对应词元的相关信息，便于后期扩展）、该词元在测试代码中的坐标（x，y）。
不同类型的词元表有程序动态维护。
表的动态维护对与整个编译程序很重要。
struct Data{int type; //表类型：id=0,num=1,运算符2 界符3int value; //在表中的下标int pos_x,pos_y;//源代码位置};本模块一共有13个状态，0—12，其中词法分析状态转换图为：说明：1、字符转换表：字母，下划线（_）化为一类，为识别标识符用。
0单独处理是用于识别单个0和以0开头的错误整数；这里的运算符是指可以和“=”连在一起作为一个词元的，如>=,<=,+=,-+,*=,/=；界符是指一个字符做为一个词元的，如｛｝（）；，等。
2、函数说明：f_留，表示将当前字符存到缓冲数组里面；f_读，提取词元，从缓冲数组里面读出当前词元，并将缓冲数组清空；f_回，转到中转0状态之前，将当前字符回退到输入流中。
f_留2：为后面添加，单个字符组成的词元，不用存到缓冲数组里面，直接提取成一个词元，存到词元结构体数组里面。
2.2.语法分析2.2.1递归下降手工编码这个模块是给定状态转换表，action表，之后对输入的表达式进行词法分析，判断表达式正误。
其中文法如下：E:=TE’E’:=+TE’|@T:=FT’T’:=*FT’|@F:=id|di|(E)所定义的函数为：void f_exp();void f_term();void f_factor();void f_term_remains();void f_exp_remains();2.2.2first集合的计算这个模块进行的是first集合的计算。
定义的文法存储数据结构为：struct define {char left;string right;};设计思路：整体上采用不动点算法依次扫描每条文法右部，若遇到终止符，则将该终止符加入文法左部非终止符的first集中。
如果遇到非终止符，则先判断该终止符的first集合中是否包含@（“@”代表“可空”），如果不包含@，则将该非终止符的first集加到文法左部的非终止符的first集中；如果包含@，并且该非终止符不是最后一个非终止符，则将该非终止符的first集合去掉@后，加到文法左部的first集合中；否则直接将此非终止符的first集合加到文法左部的first集合中。
具体描述如下：对于任意给定的LL(1) 文法G,为了构造它的预测分析表M,我们就必须构造与文法G有关的集合First和fellow.首先我们对每一个X∈VT U Vn ,构造FIRST(X),办法是,连续使用下面的规则,直至每个集合FIRST不再增大为止. (1)若X∈VT,,则FIRST(X)={X}.(2)若X∈Vn ,且有产生式X->a……,则把a加入到FIRST(X)中,若X->ε,也是一条产生式,则把ε也加到FIRST(X)中.(3)若X->Y……是一个产生式且Y∈Vn,则把FIRST(Y)中所有非ε-元素都加到FIRST(X)中,若X->Y1Y2……YK ,是一个连续的产生式, Y1Y2……Yi-1 都是非终结符,而且,对于任何j,1≤j≤i-1,FIRST(Yj) 都含有ε(即Y1Y2……Yi-1=>ε),则把FIRST(Yi) 中的所有非ε-元素都加到FIRST(X)中,特别是,若所有的FIRST(Yj)均含有ε,j=1,2,……,k,则把ε加到FIRST(X)中.辅助函数：/*统计文法条数，非终止符个数，终止符个数，并把非终止符，终止符弄成一个字符串，用于查找下标*/void get_gene() //获得产生式，并统计int get_index(char b); //得到终止符或非终止符的统一下标void add(string &tLeft , string s);将s添加到tLeft中，即将右边的字符串添加到左边的字符串中，去掉重复，如果右边存在新的字符，要将flag置为 1 ，用于不动点算法。
2.2.3左递归消除设计思路：将间接左递归变成左递归，然后消除直接左递归。
（1）把文法的所有非终止符按某一顺序排序，如：A1，A2，…….An；（2）从A1开始消除都为A1的产生式的直接左递归，然后把左部为A1的所有规则的右部逐个替换为A2开始的产生式中的A1，并消除左部位A2的产生式中的直接左递归，继而以同样的方式吧A2的右部代入左部为A3右部以A1或A2开始的产生式中，消除左部为A3的产生式之直接左递归，直到把左部为A1，A2，…….An-1的右部代入左部为An的产生式中，从An中消除直接左递归。
把上述算法归结为：如非终止符的排序为：A1，A2，…….AnFOR i:=1 TO N DOBEGINFOR j:=1 TO i-1 DOBEGIN如Aj的所有产生式为：Aj->a1|a2|….|ak替换形成Ai->Ajr的产生式变为：Ai->a1r|a2r|….|akrEND消除Ai中的一切直接左递归.END.（3）去掉无用产生式。
2.2.4selection表自动生成设计思路：扫描文法，计算文法右部的first集合（“@”不计算在内），直接将文法去右部填入文法右部计算得到的相应first集合和文法左部对应的selection表项中。