词法分析程序+语法语义分析四元式生成+实验报告

《词法分析程序+语法语义分析四元式生成+实验报告》由会员分享，可在线阅读，更多相关《词法分析程序+语法语义分析四元式生成+实验报告（34页珍藏版）》请在装配图网上搜索。

1、编译原理实验报告本文档集合了编译原理大作业的实验报告加代码实验主要内容为用C+实现了词法分析程序；语法语义以及四元式生成程序 代码见附录，复制进VS后程序绝对可编译执行。文档代码为原创，谨慎使用（姚砺的大作业）实验设计一、实验名称词法分析程序二、实验目的(1) 设计一个词法分析程序，每调用一次就从源程序文件中顺序识别出一个单词符号，并返回 该单词符号的内部编码、单词符号自身、行列位置信息。(2) 要能处理单行注释。三、实验内容及要求单词种类与识别规则(1) 标识符：首字符为字母或下划线，其后由字母、数字或下划线组成、长度不超过255个字符；(2) 整数：由1到8个数字组成。(3) 小数：数字串

2、1数字串2，其中：数字串1由1-8个数字符组成;数字串2由0-8个数字符组成，即：数字串2可以为空。(4) 字符串：由一对“”括起来的符号串，长度不超过255个字符；(5) 保留字：if、else、while、do、integer float、string、input、output、and、or、function end、def、as、begin(6)数学运算符：+、一、*、/、=比较运算符：、=、=、=(8) 逻辑运算符：and、or(9) 分隔符： 、(、)、；、四、实验环境操作系统：Win7/其他编译工具：VC+6.0 / CFree /VS2012五、设计1设计大体思路将读取的文件采用

3、一遍扫描的方法，即从左到右只扫描一次源程序，将读取的数据存放在一个二维 数组里。然后通过扫描函数scan，再从数组中一行一行的读取数据，每调用其依次返回一个单词的 类型，同时单词本身以及行列号存放在全局变量中。而说词法分析作为语法分析的一个子程序，故 在编写词法分析程序时，将会反复调用scan函数来获取一个个单词信息。3设计流程图GETSYM七/. In出中i ri&trn: = Ehnc =n+ lstr a : = chIIgetEh |港 ETCHVai -vhIM tH-ch-OGETCM5足 取宁IGETCHGETCH成双字符1a n I J =ch-一邸商将母风字知Hl1E-i-G

4、ETCHGETSYMmi -2版UIPJE血初阕IM 1-3 版椅利二计. F符彳f期仲罟产林J ?-4函数设计/*词法分析函数*/int scan( string s ,int line )框架：初始化工作是空格直接跳过，知直到读取到一个字符if(是字母)查表判断是否为关键字判断是否为逻辑运算符and或orElse则为标识符else if(是否为数字)判断是整数Else是小数Else其余情况判断是否为运算符，字符串等else if( getchar=)/if( contentlinei+1=/) 向前看一个，确定是否为行注释;如果是，则游标指向行末，跳过行注释if( contentlinei

5、+1=/*)如果向前看一个发现时块注释贝。一直向前扫描直到出现“ */”停止，略过块注释 如果都不是则Else判断为除号，返回运算符类型2对其中部分实现的说明(1) 数字识别while ( contentlinei=0 & contentlinei=0 & contentlinei=65 & contentlinei=91 & contentlinei=0 & contentlinei=9 )/判断是否为数字或者字母或者下划线(text += contentlinei;i+;for( j=0; j=13 ; j+ )if( text=keyj)查表判断是否为保留字return 5;检查到读取的

6、字符为字母时，进行查表判断，找到即说明为关键字(3) 空格，注释，行号的处理if( mode=0 )if( icontentk.length() ) i+; /如果为行注释 直接跳到下一行elseif( mode=-1 )如果为块注释找回行号k=templine;六、程序源代码见源代码文件。七、实验数据、结果测试数据见文件ct ion aaabegintemp3 = 111；def tempi, temp2 as input tenpl,temp2； def tempi as float: 也变量重复定义f loat/*此处变量未定义就使用 此处少分号tempi = 123:tempi = t

7、empi + temp2；if tempi = temp2begintempi = 123；endelsebegin+ 4*2；tempi = 3 endend functionI1.H-IH-I1 在在在在在在11112333340 3 4 0 3 111142811列?|歹列列歹列列歹列 H 结4=%:另另牙另DRU 怀 P.E.nW司司.同词斛都斡词词词 a- -B-.一 .UTT .urr.llrr.八、总结之前的每周作业曾经写过一个词法分析程序，所以这次写词法分析程序没什么太多困难。在读取源文件时，最初的想法是一行一行的读取，读一次就存一行，这样可以节省空间资源，提高效 率。但是仔细

8、一想考虑到块注释分布在不同的行中，而且这样对行列的操作十分麻烦，而且许多地方 涉及到要向前看，（比如判断注释与/除号运算符时），最后只好一次全部读完，存在一个二维数组中。 再用scan函数来处理。这样一来行列的处理就自由多了。第二点，在写scan函数的时候，最初的想法是每调用一次，返回一个单词，然后在语法分析时 不断调用它。但是仅仅返回单词是不够的，于是打算返回一个结构体，把单词信息行列号什么的全部 存进去，这个在后来的语法语义分析中可以看到，这里任然采用的是返回一个单词类型。单词本身， 和行列号作为全局变量保存。然后只要按照流程图一步一步判断，慢慢写就行了，没有太多难度，唯一要注意的是单词位

9、置 行列的计算一定要细心。这个是要穿插在整个词法分析的全部地方的。所有涉及到读入一个字符的地 方都需要考虑到如何修改行列变量。尤其是本程序拓展了块注释，要注意行列变化。实验设计二注：由于语义分析和四元式生成都是在语法分析的基础上拓展得到的，这一章实验报 告囊括了语法，语义和四元式。一、实验名称语法语义以及四元式分析程序二实验目的设计一个语法语义以及生成四元式的分析程序三、实验内容及要求设计要求：构造相应文法的语法分析程序，应能指出源程序中出现的错误。为语法分析程序中添加类型检查功能，包括： 变量重复定义； 变量未定义就使用； 变量未赋值就引用；将语法正确的源程序翻译成四元式。文法见附录四、实验

10、环境操作系统：Win7/其他编译工具：VC+6.0/ CFree / VS2012五、设计1. 语法分析设计(1) 相关数据机构struct Token(string value;值intmode;/类型introw;/彳亍intcol;/歹列token;说明：这本应是词法分析时的结构，但是scan函数返回的是但单一值，于是又设计了 Token函数， 对scan函数进行扩充，每个单词的信息均保存一次在结构体中，方便错误报告函数进行处理。(2) 各个非终结符函数形式/*/*语法语义各产生式函数*/void chengxu();void hanshukuai();void hanshu();voi

11、d yujukuai();void yuju();void bianliangdingyiyuju();void shujuleixing();void shuruyuju();void shuchuyuju();void fuzhiyuju();void fenzhiyuju();void xunhuanyuju();void biaodashi();void xiang();void yinzi();void buerbiaodashi();void guanxibiaodashi();void guanxi();其他函数：void error();void warning();每个函数具

12、体作用在代码中都有注释说明(3) 语法分析整体设计思路采用递归下降的方法，为每个非终结符设计一个函数，在函数中对此处可能出现的语法错误进行处理。处理也语法错误的思路主要分两种:1. 查找关键字由于进行语法分析时检查到错误不可能就此停下，要一次性尽量找到所有的错误，而且测试数据的语法错误形式千奇百怪，这就要求发现错误之后如何找到继续进行分析的位置。这里对于一些不常见的错误采取查找关键字的方法，一旦出现错误在相应函数中查找下一个出现的关键字的位置，然后继续分析。2. 跳过错误单词，直接分析下一个单词由于查找关键字方法会跳过许多代码，从而有可能造成一些信息不必要的遗漏。尤其是对于漏分号这种错误，与是

13、这里采取，直接当前错误，默认后续单词可能就是正确单词，继续分析。但是这个方法在一些地方并不适用，可能会导致一连串的错误出现，于是在使用时要考虑好取舍。编译错误处理函数：void error( Token token, char *msg)编译错误处理函数(cout 编译错误：；printf( %s, msg); cout endl 错误位置：第 token.row 行，第 token.col token.value;cout endl;cout endl;errornum+;每出现错误时，通过传递错误信息参数以及单词信息，调用编译错误处理函数进行实时报错。(3) 测试数据和结果见后文语义分析部

14、分(4) 语法分析部分的小总结原本打算试试自底向上归约方法设计的，结果想了想发现实在麻烦，老师给的文法又 挺庞杂的，创建分析表什么的就要好久。后来一想用递归下降方法好处很多，做到之 后的语义分析和四元式生成的时候在语法分析的基础上拓展很方便，整体框架非常清晰。在错误处理方面考虑的还是挺合理的，对于一些常见错误都能有效指出。并且程 序只有一个出口，任何代码输入都会从那一个出口结束，不会引起程序崩溃。2、语义分析设计语义分析主要实现3个功能 变量重复定义； 变量未定义就使用； 变量未赋值就引用；(1) 相关数据结构struct Symtable符号表结构(string name;int type;

15、bool value;S;struct compare: binary_function /仿函数和绑定器(bool operator()( Symtable s, string str) const(if (s.name= str)return true;elsereturn false;(2) 相关函数void push_in_token( Token token ) /进表操作(S.name = token.value;S.type = -1;S.value = false;ST.push_back( S );vector : iterator find_token( Token tok

16、en ) /查表操作(it = find_if( ST.begin(), ST.end(), bind2nd( compare (), token .value );return it;（2）测试数据和结果（4）设计思路语义部分主要采用符号表结构，符号表中记录了每个非终结符的信息。（名称，类型， 是否赋值）。然后再程序中每次调用Token函数发现读取到标识符时都进行查表操作。 根据查表结果进行相关分析。在赋值函数中，如果查表找到其信息就说明重复定义。再其余函数中1.没有找到说明为声明就使用。2.找到发现未赋值说明未赋值就引用。（5）语义部分小总结 假如只实现以上3个功能语义部分并不难，关键是符

17、号表的构建以及进表查表等操作。在这一部分我使用了仿函数和绑定器进行查表。由于我把相应表结构都存在vector内， 导致查找结构内成员信息的不便，但是自己写一套查找操作代码估计效率不高，索性 使用仿函数进行查找，泛型操作一般效率较高而且代码较少也很清晰。假如时间更充 足一点其实还可以把数据类型匹配这一部分拓展一下，毕竟也是查表比较，但是时间 有限只好先完成要求的3个任务。3、四元式分析设计 （1）相关数据结构struct Quaternary四元式结构(int serial;string op;string v1;string v2;string result;Q;stack operator_

18、stack;操作数堆栈stack operand_stack;操作符堆栈(2)相关函数Quaternary Quaternary_generater( int serial , string op, string v1, string v2, string result ) 四元式生成函数 (Q.serial = serial;Q.op = op;Q.v1 = v1;Q.v2 = v2;Q.result = result; return Q; void Quaternary_maker() ( while ( !operand_stack.empty() & !operator_stack.e

19、mpty() ( op = operator_stack.top(); operator_stack.pop(); v1 = operand_stack.top(); operand_stack.pop(); v2 = operand_stack.top(); operand_stack.pop(); res = resultr;r+; Q = Quaternary_generater( serial, op, v1, v2, res );serial+; QV.push_back( Q ); / for( it2=QV.begin(); it2!=QV.end(); it2+ )找回真出口i

20、f( (*it2).result=null ) ( stringstream ss; ssQV.back().serial; string s=ss.str(); (*it2).result=s; break; / operand_stack.push( res );void Quaternary_output()(while( !QV.empty()(cout QV.front().serial ( QV.front().op , QV.front().v2 , QV.front().v1 , QV.front().result ) endl;it2 = QV.begin();QV.eras

21、e( it2 );(3) 测试数据和结果(4) 设计思路赋值运算部分整体结构流程如下:I二害场;-云扣志5r? = PriZ 艾至二直坦注菸骂.=: 了-长三且结束l说明：首先建立操作符栈和运算符栈。每次扫描遇到操作符遍进栈，遇到运算符如果当前栈 空则进栈，否则和栈顶操作符的优先级进行比较，如果小于等于其优先级，则pop栈 顶符号，进行四元式生成，再将四元式压入四元式队列，然后继续与栈顶元素比较直 至其优先级大于其优先级或栈空则进栈。If语句部分在对布尔表达式进行判断时，先让操作符和运算符进栈，转移序号先赋为null等到扫描到if then之后的部分通过对其四元式生成确定了序号，这时候再查找队

22、列进 行回填序号。函数具体结构：void biaodashi()(xiang();while ( token.value=+ | token.value=- ) ( / 四元式 while ( !operator_stack.empty() & operator_stack.top()!二= )/此处要注意用while循环，if会出错，因为需要不断判断直至栈顶的符号优先级小于需要压栈的符号 (此处生成四元式，四元式进队列 for( it2=QV.begin(); it2!=QV.end(); it2+ )找回真出口if( (*it2).result=null ) ( stringstream

23、ss; ssQV.back().serial; string s=ss.str(); (*it2).result=s; break; operator_stack.push( token.value );如果栈空或者准备进栈的符号的优先级大于栈顶的优先级则进栈 token = getToken(); xiang(); (5) 四元式的总结：这部分是我觉得此次试验最难的一部分。而且也是我花费时间最多的一部分。在写赋值运算的那部分时，把一个while循环写成了 if (我一开始以为运算符进栈只需 判断一次)导致测试数据结果出错找了好久错误才找到。If语句那部分的四元式的编 写也十分困难，尤其是找回

24、真假出口让我考虑了很久。而且测试数据整个代码有许多 这种语句，应当在每个语句结束时就输出一次四元式，不然会导致次序的混乱。(一开 始我没发现，是把所有四元式进队列到最后程序结束时一起输出的)，最后调试了许久， 才发现问题，于是在语句结果判断分号时，就调用四元式输出函数进行输出。六、整体总结这次编译原理大作业让真的我受益良多，整个近千行代码基本都是我一点一点慢慢敲 出来的，过程固然辛苦但是学到了不少。尤其是在做语法分析和四元式生成的部分， 代码量较大，一开始思路也不太清晰，但是还是一点一点硬着头皮往下写，结果在写 的过程中一些思路就出来了，看来有时候还是要多动手，光苦思冥想并不行。对于这 次作业

25、我自己是比较满意的但是还是有一些不足：语法部分本来想对文法进行拓展把 布尔表达式那部分的附加题解决掉，无奈时间有限，实在来不及写，可能留到暑假自 己再完善吧。四元式部分其实做得并不完完善，有些测试数据会出现错误结果，主要 是还是因为布尔表达式那部分文法没有拓展，在进行复杂布尔表达式判断时会出错， 而且if语句真假口如果遇到复杂的算数运算可能会出口回填错误。总体来说，这次作 业基本任务还是都完成了，通过这次大作业也对整个编译器的设计有了比以前更深的 了解和体会，看来还是实践才能出真知。附录文法如下:1. 程序一函数块2. 函数块一函数函数3. 函数一 function id ()语句块end f

26、unction4. 语句块一 begin语句语句end5. 语句一分支语句|赋值语句|循环语句|输入语句1输出语句1变量定义语句6. 变量定义语句一 def id :, id as数据类型7. 数据类型一 integer | float | string8. 输入语句一 input id , id :9. 输出语句一 output表达式,表达式；10. 赋值语句一 id =表达式11. 分支语句一 if布尔表达式语句块else语句块12. 循环语句一 while布尔表达式do语句块13. 表达式一 项 +1 - 项 14. 项一因子*|/ 因子15. 因子一 id | con | deci |

27、 (表达式)14. 布尔表达式一关系表达式and | or布尔表达式15. 关系表达式一表达式关系表达式16. 关系一 | = | | = | = | 附录：词法分析完整代码(复制可执行)/*词法分析程序 BY谢卓函 ON June 20th */#include #includealgorithm#include #include #include #define MAXLINE 30 using namespace std;/标识符1,整数2,小数3,字符串4,保留字5,数学运算符6,比较运算符7,逻辑运算符8,分隔符9string key14=if,else”,while,do,floa

28、t”,string,begin”,end”,def,integer”,input,output,as,function;保留字string border5= ; , , , ( , ) ;/分隔符 5string arithmetic9=+ , - , * , / , , , = ;运算符 6string text;记录标识符1string contentMAXLINE;保存从文件读取的内容int i=0;i为字符游标int templine = 0;int scan( string s ,int line )int j, flag =0;text =;赋空 textwhile( conten

29、tlinei=)判断空格i+;/是空格跳过if( (contentlinei=65 & contentlinei=91 & contentlinei=65 & contentlinei=91 & contentlinei=0, & contentlinei=9, )/判断是否为数字或者字母或者下划线text += contentlinei;i+; for( j=0; j=0 & contentlinei=0 & contentlinei=9)判断是否为数字 text += contentlinei;i+; return 2;/整数 return 3; 小数 if( contentlinei=

30、; II contentlinei= II contentlinei= II contentlinei=( II contentlinei=) II contentlinei=, ) /判断是否为分隔符 text = contentlinei;i+; return 9;if( contentlinei= + II contentlinei=- II contentlinei=* II contentlinei=)判断是否为运算符 text = contentlinei; i+;return 6;if( contentlinei= ) if( contentlinei+1= ) text = c

31、ontentlinei;text += contentlinei+1;i=i+2;return 7; else text = contentlinei;i+; return 7; if( contentlinei= )判断是否为字符串 text += contentlinei;i+; while( contentlinei!=”) text += contentlinei;i+; text += contentlinei;i+; return 4; if( contentlinei=/)判断是否为注释if( contentlinei+1=/) i=contentline.length();re

32、turn 0;如果为行注释那么游标指向行末else if( contentlinei+1=*) i=i+2; while( contentlinei!=* II contentlinei+1!=/) if( i=contentline.length() line+;i=0; else i+;i=i+2;templine = line;return -1;-1 代表块注释 else text = contentlinei;i+; return 0;return 0;int main()ifstream infile(ceshi1.txt,ios:in);if( infile )cout 文件读取

33、成功！ endl;elsecout 文件读取失败! endl;int hang, mode,k=1,numline; /k 用于定位行数 cout endl;cout 测试数据如下： endl;while ( getline(ink) ) cout contentk endl; k+;numline = k-; /numline 记录了文件总行数 cout endl;cout 词法分析结果： endl;for( k=1; k=numline; k+ )while( i!=contentk.length() mode = scan( contentk, k );if( mode!=0 & mod

34、e!= -1 ) cout 所在行数： k 所在列数： i-text.length()+1 单词类别： mode 单词 为： text endl ;else if( mode=0 ) if( icontentk.length() ) i+; /如果为行注释 直接跳到下一行 elseif( mode=-1 )/如果为块注释 找回行号k=templine;i = 0;/一行结束定位到下一行行头getchar();return 0;附录二 语法语义四元式生成代码(复制可执行)/*语法+语义+四元式分析程序BY谢卓函ON June 25th */#include #includealgorithm#i

35、nclude #include #include #include #include #include #include #include #include #include #include #include #define MAXLINE 30using namespace std;/标识符1，整数2,小数3,字符串4,保留字5,数学运算符6,比较运算符7,逻辑运算符8,分隔符9string key14=nif,else,Hwhilen,don,floatn,Hstringn,Hbeginn,nendn,ndef,ninteger,ninputH,outputn,asn,nfunction

36、n;保留字string border5= ; , , , ( , ) ;分隔符 5string arithmetic9=+ , - , * , / , , , = ;运算符 6string text;记录标识符1string contentMAXLINE;保存从文件读取的内容string resultMAXLINE = t1”,t2”,”t3”,”t4”,”t5”,”t6”,”t7,”t8”,”t9”,t10;*/*语法语义各产生式函数*/void chengxu();void hanshukuai();void hanshu();void yujukuai();void yuju();voi

37、d bianliangdingyiyuju();void shujuleixing();void shuruyuju();void shuchuyuju();void fuzhiyujuO;void fenzhiyuju();void xunhuanyuju();void biaodashi();void xiang();void yinzi();void buerbiaodashi();void guanxibiaodashi();void guanxi();void error();void Quaternary_output();void Quaternary_maker();int i

38、=0,k=1,numline,mode;i为字符游标,k为行号,numline记录了文件总行数int templine = 0;int errornum = 0;int warningnum = 0;int r = 0, serial = 1;string op,v1,v2,res;struct Tokenstring value;值int mode;类型int row;/行int col;列token;struct Symtable符号表结构string name;int type;bool value;S;struct Quaternary 四元式结构int serial;string o

39、p;string v1;string v2;string result;Q;Quaternary Quaternary_generater( int serial, string op, string v1, string v2, string result );函数声明vector ST;vector : iterator it;vector QV;vector : iterator it2;stack operator_stack;/操作数堆栈stack operand_stack;/操作符堆栈struct compare: binary_function 仿函数和绑定器bool oper

40、ator()( Symtable s, string str) constif (s.name= str)return true;elsereturn false; ;void push_in_token( Token token ) 进表操作S.name = token.value;S.type = -1;S.value = false;ST.push_back( S );vector : iterator find_token( Token token ) 查表操作it = find_if( ST.begin(), ST.end(), bind2nd( compare(),token.va

41、lue );return it;int scan( string s ,int line )int j, flag =0;text =;赋空 textwhile( contentlinei= )/判断空格i+;/是空格跳过if( (contentlinei=65 & contentlinei=91 & contentlinei=65 & contentlinei=91 & contentlinei=0, & contentlinei=9 )/判断是否为数字或者字母或者下划线 text += contentlinei;i+; for( j=0; j=0 & contentlinei=0 & co

42、ntentlinei=9 )/判断是否为数字 text += contentlinei;i+; return 2;/整数 return 3; 小数 if( contentlinei= ; | contentlinei= | contentlinei= | contentlinei=( | contentlinei=) | contentlinei=, ) /判断是否为分隔符 text = contentlinei;i+; return 9;if( contentlinei= + | contentlinei=- | contentlinei=* | contentlinei=)判断是否为运算符

43、 text = contentlinei; i+;return 6;if( contentlinei= ) if( contentlinei+1= ) text = contentlinei;text += contentlinei+1;i=i+2;return 7; else text = contentlinei;i+; return 7; if( contentlinei= ) 判断是否为字符串 text += contentlinei;i+;while( contentlinei!=”)text += contentlinei;i+; text += contentlinei;i+;r

44、eturn 4;if( contentlinei=/)判断是否为注释if( contentlinei+1=/) i=contentline.length();return 0;如果为行注释那么游标指向行末elseif( contentlinei+1=*) i=i+2;while( contentlinei!=* | contentlinei+1!=/) if( i=contentline.length()line+;i=0; elsei+;i=i+2;templine = line;return -1;-1 代表块注释 else text = contentlinei; i+;return 6

45、;说明是除号 text = contentlinei;i+; return 0;return 0;Token getToken() /该函数用于取字符 for( ; k=numline; k+ )while( i!=contentk.length()mode = scan( contentk, k ); if( mode!=0 & mode!= -1 )token.value = text;token.mode = mode; token.row = k;token.col = i-text.length()+1;return token;/cout 所在行数: k 所在列数: i-text.

46、length()+1 单词类别: mode 单词为： text endl ;elseif( mode=0 )if( icontentk.length() ) i+; /如果为行注释 直接跳到下一行 elseif( mode=-1 )如果为块注释 找回行号k=templine;i = 0;/一行结束定位到下一行行头token.value = EOF;return token;int main()cout *编译原理大作业 语法语义四元式分析程序by谢卓函* endl;string ;cout ”请输入测试文件名: ;ifstream infile( );此处在VC上可能编译不过可改为ifstre

47、am infile( ceshi1.txt”,ios:in);手动输入文件名if( infile )cout ”文件读取成功！ endl;elsecout ”文件读取失败!” endl;int hang, mode,k=1; /k 用于定位行数cout endl;cout ”测试数据如下： endl;while ( getline(ink)cout contentk endl;k+;numline = k-;/numline 记录了文件总行数cout endl;cout ”语法分析结果：vv endl;chengxu();if( warningnum )cout warning: warnin

48、gnum;if( errornum )cout error: errornum endl;elsecout ”编译成功！ endl;cout endl;if( !errornum )cout ”四元式如下： endl;Quaternary_maker();Quaternary_output();getchar();return 0;void error( Token token,char *msg)编译错误处理函数cout 编译错误：;printf( %s,msg); cout endl 错误位置：第 token.row 行，第 token.col token.value;cout endl;cout endl;errornum+;void warning( Token token,char *msg)警告错误处理函数cout 警告错误：”;printf( %s,msg); cout endl 警告位置.：第 token.row 行，第 token.col token.value;cout endl;cout endl;warningnum+;void chengxu()token = getToken();hanshukuai();void hanshukuai()hanshu();while( token.vaiue=Hfunction)hanshu();void