1、编译原理课程设计说明书词法分析语法分析语义分析编译原理课程设计说明书题 目： 编译器原型设计与开发院 （系）： 计算机科学与工程学院专 业： 计算机科学与技术1引言编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都配有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。从功能上看，一个编译程序就是一个语言翻译程序。语言翻译程序把一种语言（称作源语言）书写的程序翻译成另一种语言（称作目标语言）的等价程序。一个编译程序的重要性体现在它使得多数计算机用户不必考虑与机器有关的繁琐细节，使程序员和程序设计专家独立于机器，这对于当今机器的数量和种类持续不断地增长的年代
2、尤为重要。编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。将编译过程划分成词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段。1.1设计概述编译原理程序结构框图词法分析 词法分析是编译过程的第一个阶段。这个阶段的任务是从左到右有一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词（也称单词符号或符号）。这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符基友具体含义。比如标识符是由字母字符开头，后跟字母、数字字符的字符序列组成的一种单词。保留字（关键字或基本字）是一种单词，此外还有算符、界符等。语法分析 语法分析是编译
3、过程的第二个阶段。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”、“语句”、“表达式”等。一般这种语法短语，也称语法单位，可表示成语法树。语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。语义分析 语义分析是审查源程序有无语义错误，为代码生成阶段收集类型信息。比如语义分析的一个工作是进行类型审查，审查每个算符是否具有语言规范允许的运算对象，当不符合语言规范时，编译程序应报告错误。中间代码生成 在进行了上述的语法分析和语义分析阶段的工作之后，有的编译程序将源代码变成一种内部表示形式，这种内部表示形式叫做中间
4、语言或中间代码。所谓“中间代码”是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的设计原则为两点：一是容易生成；二是容易将它翻译成目标代码。很多编译程序采用了一种近似“三地址指令”的“四元式”的中间代码，这种四元式的形式为：（运算符，运算对象1，运算对象2，结果）。1.2设计目标鉴于我们需要完成编译器的词法分析、语法分析、语义分析、中间代码生成的设计开发，本次课程设计主要完成以下任务：词法分析：1.消除白空格2.消除注释3.词法分析语法分析：4.递归下降手工编码5.first集合的计算6.follow集合的自动计算7.selection表自动生成8.递归下降自动生
5、成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
6、_Type_Table：ASIC431310非白非/非*非r白/*r,n01234说明：白表示空格、TAB（t）；而 白是等于 白+r,n，把r,n独立出来是为了消除注释需要。状态转换表state_Trans_Table： 符号S_B01234001201101201200340333331444454544144Action_Table： S_AS_B0123450f_留f_改f_删/1f_留f_删f_删/2f_补/f_删f_删/3/f_改/f_删/4/f_删f_删5/f_改/f_删/其中在程序中f_留表示为f_save；f_改表示为f_change；f_补表示为f_add；f_删表示为f_
7、delete；Action_Table表示为void(*Action_Table66)(void)。2.1.2词法分析设计思路：1、把消除白空格、消除注释、识别标识符id，识别整数di，识别运算符、识别界符、识别双引号内的注释分层次画状态机，使状态机清晰易懂，方便其他同学学习；2、以0状态为中转，每一层次的状态机遇到不是该层次的内容（识别了一个词元，当前输入不是该词元的内容了），回到0状态去判断该字符应转向的状态。3、使用了ungetc（）函数，输入回退一个字符，回到0状态中转之前，如果该字符并没有做处理，要ungetc，回退到输入流，那么从0状态会再读出之前没有处理的字符，再判断转换；4、词
8、元存储，用结构体存储数组存储；不同类型的词元对应不同的表，词元结构体中存储的是，该词元的类型（也即表的类型）、在该表中的下标（可以通过该下标找到对应词元的相关信息，便于后期扩展）、该词元在测试代码中的坐标（x，y）。不同类型的词元表有程序动态维护。表的动态维护对与整个编译程序很重要。 struct Data int type; /表类型：id=0,num=1,运算符 2 界符 3 int value; /在表中的下标 int pos_x,pos_y;/源代码位置;本模块一共有13个状态，012，其中词法分析状态转换图为：说明：1、字符转换表：字母，下划线（_）化为一类，为识别标识符用。0单独处
9、理是用于识别单个0和以0开头的错误整数；这里的运算符是指可以和“=”连在一起作为一个词元的，如=,a,则把a加入到FIRST(X)中,若X-,也是一条产生式,则把也加到FIRST(X)中.(3)若X-Y是一个产生式且YVn,则把FIRST(Y)中所有非-元素都加到FIRST(X)中,若X-Y1Y2YK,是一个连续的产生式,Y1Y2Yi-1都是非终结符,而且,对于任何j,1ji-1,FIRST(Yj)都含有(即Y1Y2Yi-1=),则把FIRST(Yi)中的所有非-元素都加到FIRST(X)中,特别是,若所有的FIRST(Yj)均含有,j=1,2,k,则把加到FIRST(X)中.辅助函数：/*统
10、计文法条数，非终止符个数，终止符个数，并把非终止符，终止符弄成一个字符串，用于查找下标*/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的产生
11、式的直接左递归，然后把左部为A1的所有规则的右部逐个替换为A2开始的产生式中的A1，并消除左部位A2的产生式中的直接左递归，继而以同样的方式吧A2的右部代入左部为A3右部以A1或A2开始的产生式中，消除左部为A3的产生式之直接左递归，直到把左部为A1，A2，.An-1的右部代入左部为An的产生式中，从An中消除直接左递归。把上述算法归结为：如非终止符的排序为：A1，A2，.AnFOR i:=1 TO N DO BEGIN FOR j:=1 TO i-1 DO BEGIN 如Aj的所有产生式为： Aj-a1|a2|.|ak 替换形成Ai-Ajr的产生式变为： Ai-a1r|a2r|.|akrEN
12、D消除Ai中的一切直接左递归.END.（3）去掉无用产生式。2.2.4selection表自动生成设计思路：扫描文法，计算文法右部的first集合（“”不计算在内），直接将文法去右部填入文法右部计算得到的相应first集合和文法左部对应的selection表项中。此代码比较简单，附如下：void count_selection(define *p,string *first,string *follow,string *selection,int count,int count_T) for(int i = 0;icount;i+) string first_right = first_str
13、(pi.right); string rights = pi.right; char lefts= pi.left; for(int j = 0; j (first_right.length(); j+) selectionget_index(lefts)get_index(first_rightj) = rights; if( firstget_index(lefts).find()!=-1 ) /如果属于firstpi.left string follows = followget_index(lefts); for(j = 0; j产生式，而的长度为r（即| |=r），则从状态栈和文法符
14、号栈中自栈顶向下去掉r个符号，即栈指针SP减去r。并把A移入文法符号栈内，再把满足Sj=GOTOSi,A的状态移进状态栈，其中Si为修改指针后的栈顶状态（3）接受acc：当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是#，则为分析成功（4）报错：当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入串不是该文法能接受的句子。本模块功能主要对表达式进行LR(1)分析后，并对表达式进行求值。产生式存储结构定义为：struct define /产生式 char left; string right;；其他定义：stacks_sign; /符号栈stacks
15、_state; /状态栈char Get_ch100; /用于存储测试字符串define *p = new define10;int count=0; /用于记录测试字符串的长度int counts ; /产生式个数int tCount ; /终止符个数int ntCount ; /非终止符个数string s_NT=,s_T=;int get_index(char b);void get_gene();void get_ch();void init(); /初始化int parseInt(string); /将字符串转换为int2.3.2四元式本模块基于LR手工编码，主要是将表达式表示成四元
16、式，如运算符，运算对象1，运算对象2，结果）。四元式存储结构定义为：struct four_element /四元式结构体 char op; /操作符 string x1,x2; /两个操作数 string re; /结果;主要函数为：string test(string Action126,int Goto123,string input)；3测试过程消除白空格以及注释运行结果截图：原文件：输出文件：词法分析运行结果截图：递归自动生成运行结果截图：LR(1)手工编码运行结果截图：消除左递归运行结果截图：四元式运行结果截图：4总结这次的课程设计项目，我担任的是原型设计，并参与了部分编码工作。在
17、设计的时候遇到很多困难，并且由于编译原理本身的复杂性，系统性，让我在设计的时候对整体的把握和取舍上需要有一定的决策能力和判断能力。例如词法分析中真正要考虑完全，会发现很多问题，要处理的细节太多，这样状态也太多，转换表以及action表比较难画，也比较容易出错，不利于初次原形设计和小组学习，于是我选择一个这种的方式，只考虑了一些常规的词元，并且状态图采用层次型，清晰，便于小组学习和深入，虽然这样做代码效率不高。另外一些算法性、知识性较强的算法设计，如first、follow集合计算、消除左递归的，需要对上课讲诉的内容深入理解，并自己手工模拟才能深入理解，并设计原形。设计原形后设计与编码人员的沟通
18、问题；由于部分编码人员对算法思想不够理解，需要耐心沟通，并且对一些大家都要用到的数据结构进行统一，对某些通用的函数可以整合到一个.cpp文件，这样加强了小组代码的规整性。经过这次课程设计，不仅让我学习到了编译器的编译过程，词法分析，语法分析，语义分析，中间代码生成，代码优化。而且培养了我们的团队合作分工意识。使我们认识到了，进行项目开发，不是单靠个人力量可以成功完成的。按照每个人的专业擅长，给每个人分工，能力比较强的同学担任项目的原型设计工作，编码能力强的同学进行项目的编码工作，编码能力相对较弱的同学可以担任测试工作，管理能力较强的同学担任项目中组织以及管理的工作。只有整个团队分工细致地合作，
19、每个环节紧扣相应的环节，这样才能把项目做好，做强。这次的课程设计让我们能把所学的知识运用到实际的项目编码中来，真的让我们成长起来了，这样的教学方式是值得肯定和支持的。5参考文献编译原理（第2版） 张素琴 清华大学出版社 2012年5月6代码附录消除白空格以及注释：#include#includeusing namespace std;void f_save();void f_delete();void f_change();void f_add();char srcstr;ofstream out(test1.txt,ios:binary);int main() ifstream in(tes
20、t.txt,ios:in|ios:binary); char ch_in,ch_in_Type; int S_B = 0 , S_A = 0; int State_Trans_Table65 = 0,1,2,0,1,0,1,2,0,1,0,0,3,4,0, 3,3,3,3,1,4,4,4,5,4,4,4,1,4,4; char Ch_Type_Table128 = 0; Ch_Type_Tabler=Ch_Type_Tablen=4; /r,n Ch_Type_Table/=2; / Ch_Type_Table*=3; /* Ch_Type_Table =Ch_Type_Tablet=1; /
21、空格，/t /返回类型(指针变量名)（参数列表）；定义函数指针 void(*Action_Table66)(void)= f_save,f_change,f_delete,NULL,NULL,NULL,f_save,f_delete,f_delete,NULL,NULL,NULL,f_add,NULL,NULL,f_delete,f_delete,NULL,NULL,f_change,NULL,f_delete,NULL,NULL,NULL,NULL,NULL,NULL,f_delete,f_delete,NULL,f_change,NULL,NULL,f_delete,NULL; while(in) /当文件读取没有结束 S_B = S_A; in.get(ch_in); srcstr = ch_in; ch_in_Type = Ch_Type_Tablech_in; S_A = State_Trans_TableS_Bch_in_Type; Action_TableS_BS_A(); out.close(); in.close(); return 0;void f_save() / f_留 outsrcstr;void f_delete() /f_删void f_change() / f
