编译原理大作业

1、2017届课程设计   扫描器设计 姓 名: 库尔班江.阿瓦克日学  号:  5011212524   学 院:  信息工程学院  专  业: 计算机科学与技术 班  级:  计算机17-1班    塔里木大学教务处制实验一 词法扫描器设计一 实验目的通过设计调试词法分析程序，实现从源程序中分出各种单词的方法；加深对课堂教学的理解；提高词法分析方法的实践能力。二 实验内容设计一

2、个简单的类C语言的词法扫描器。三 实验要求（一） 程序设计要求（1） 根据附录给定的文法，从输入的类C语言源程序中，识别出各个具有独立意义的单词，即关键字、标识符、常数、运算符、分隔符五大类；文法见最后附录。（2） 提供源程序输入界面；（3） 词法分析后可查看符号表和TOKEN串表；（4） 保存符号表和TOKEN串表（如：文本文件）； （5） 遇到错误时可显示提示信息，然后跳过错误部分继续进行分析。（二）实验报告撰写要求（1） 系统功能（包括各个子功能模块的功能说明）；（2） 开发平台（操作系统、设计语言）；（3） 设计方案；1） 主数据流图；2） 主要子程序的流程框图（若有必要）；3） 模块

3、结构图；4） 主要数据结构：符号表、TOKEN串表等。（4） 具体设计过程（包括主控程序、各个功能模块的具体实现）。四 实验总结附录：类C语言的词法文法id® Letter <temp> int10® Num int10 | Num OP® +| - |* |/ |>| < | = | ( | ) | ; | | = | >= |<= | !=Keyword®if | then | else | while | do Letter®a|b|c|d|e|f|g|i|j|k|l|m|n|o|p|q|r|s|t|u

4、|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|ZNum®0|1|2|3|4|5|6|7|8|9 |<temp>® Letter <temp> | Num <temp> | 一.设计内容1.根据附录给定的文法，从输入的类C语言源程序中，识别出各个具有独立意义的单词，即关键字、标识符、常数、运算符、分隔符五大类；文法见最后附录。2.源程序保存在文件中。3.词法分析后可查看符号表和TOKEN串表；4.保存符号表和TOKEN串表（如：文本文件）； 二.详细设计1.首先根据

5、题目要求对要进行词法分析的单词符号进行编码。单词符号种别编码单词符号种别编码main117int218char319if420else5,21for6:22while7；23ID824NUM925=1026+1127-1228*13！29/14(15)162.在本实验中，将需要出来的文法符号分为几类：（1）关键字：在本实验中对关键字分别进行存储，在判断是否为标识符前首先对关键字进行识别。（2）标识符：标识符处理函数识别标识符。正则定义为：（3）运算符：运算符包括= + - * / ( ) , ; > < >= <= = != 等，需单独写函数进行识别。 关系运算符需根据

6、下图进行识别： （4）数字：在本例中仅识别整数。digit = 1|2|3|4|5|6|7|8|9Digit = 0|1|2|3|4|5|6|7|8|9Digit = digit Digit*3.扫描器 扫描器作为独立的子程序，首先进行扫描剔除无用的换行和连续的空格，对处理后的代码进行分析。三.模块划分和实现1.数据结构（1）ModulClass存储划分好的词法单元的分类，存储有单元的名称和单元的标号，与上面的表格中的信息一致。在程序开始时需要首先将分类信息读取然后填充表格class ModulClass /存储词法单元的分类public:string strID; /单元名字int numb

7、er; /单元编号;ModulClass modulclassModulClass_size;（2）Codeclass存储在程序识别过程中识别到的词法单元class CodeClass /存储识别过程中识别的词法单元public:string code; /名字int number; /编号;CodeClass codeclassCodeClasss_size;2.预处理模块 readcode()函数（1）代码存储在code.txt中，用C+流读取文件内容，相关代码如下。ifstream infile("code.txt",ios:in);if (!infile)cout&

8、lt;<"无法打开代码文件!"<<endl;exit(-1);infile.getline(temp,1000,EOF);tempstrlen(temp) = '0'（2）去除换行符号for(i = 0;i < strlen(temp);i+) if(tempi = 'n') strtemp += " " else strtemp += tempi;（3）去除多余的空格符号，将多个空格连续的压缩成一个for(j = 0;j <= strtemp.length();)if(strtempj =

9、' ')while(strtemp+j = ' ')strcode += ' ' /处理空格，将多个连续的空格压缩成一个continue;elsestrcode += strtempj; j+;cout<<"消去空格和换行符处理结果"<<endl<<strcode<<endl;3.文法输入模块 init_class()该模块将表格中的文法符号通过文件读取的方式读取到实现建立好的对象数组中，方便以后进行查询操作。核心代码如下：while(!(in_class.eof()in_cla

10、ss>>modulclassi.strID;in_class>>modulclassi.number;i+;4. 判断是否为标识符int is_key_ID(int forward,int back) /判断是否是标识符该函数判断读入的是否为标识符，根据标识符判断的正则表达式进行识别，若非标识符则输出错误，若识别则将该标识符的字符串和种别码进行保存。需建立两个指针，forwawrd 指针和 back指针，首先forward指针移动，back指针则指向标识符的第一个字符的位置，直到识别完毕。关键代码如下：while(+forward) /扫描字符串，返回 idtemp，保

11、存forwardif(strcodeforward >= 65)&&(strcodeforward <= 89) | (strcodeforward >= 97)&&(strcodeforward <= 122) /下一个是字母 temp+len = strcodeforward;else if(strcodeforward >= 48)&&(strcodeforward <= 57) /下一个是数字temp+len = strcodeforward;elseforward-;break;5.判断匹配关键字判断

12、该字符串符合标识符的文法之后，需事先判断该标识符是否是系统预留的关键字。bool iskey = false; /判断是否是keycodeclassnum_class.code = idtemp; /保存词法单元code属性for(int i = 0;i < ModulClass_size;i+) /在表中查找当前词法单元的编号if(idtemp = modulclassi.strID)/完全匹配：是关键字codeclassnum_class.number = modulclassi.number;iskey = true; break;if(!iskey) /如果不是关键字，即为IDc

13、odeclassnum_class.number = 8; /ID的编号为8num_class+;6.判断是否是数字函数：is_number(int forward,int back)需建立两个指针，forwawrd 指针和 back指针，首先forward指针移动，back指针则指向标识符的第一个字符的位置，直到识别完毕。若是数字则保存，指针回退一个字符。否则宣布错误信息。while(+forward) /扫描字符串，返回 idtemp，保存forwardif(strcodeforward >= 48)&&(strcodeforward <= 57)/下一个是数字

14、temp+len = strcodeforward;elseforward-;break;7.判断是否是relop符号分为两种情况：由一个字符组成和由两个字符组成（1）仅有一个字符组成if(temp1 != '=' ) /该运算符仅有一个字符forward-; /回退指针/保存词法单元switch(temp0)case '<': codeclassnum_class.code = "L" /保存词法单元code属性 codeclassnum_class.number = 25; /ID的编号 break;case '>&#

15、39;: codeclassnum_class.code = "G" /保存词法单元code属性 codeclassnum_class.number = 24; /ID的编号 break;case '=': codeclassnum_class.code = "=" /保存词法单元code属性 codeclassnum_class.number = 10; /ID的编号 num_class+;（2）由两个字符组成else /由两个字符构成,第二个为=/保存词法单元switch(temp0)case '<': code

16、classnum_class.code = "LE" /保存词法单元code属性 codeclassnum_class.number = 27; /relop的编号 break;case '>': codeclassnum_class.code = "GE" /保存词法单元code属性 codeclassnum_class.number = 26; /relop的编号 break;case '=': codeclassnum_class.code = "EQ" /保存词法单元code属性 code

17、classnum_class.number = 28; /relop的编号 break;case '!': codeclassnum_class.code = "NE" /保存词法单元code属性 codeclassnum_class.number = 29; /relop的编号 num_class+;return forward; /返回当前扫描的位置8.词法单元扫描器扫描器维持两个指针，forward指针和back指针，同时获取扫描区域的总长度。根据back指针指向的字符的属性，判断该词法单元的种类，然后根据种类跳转到相应的识别函数中去，观察该函数能否被

18、识别，若能够被识别则保存该词法单元，跳转道下一个词法单元，否则输出错误信息。void scanner()int i;int forward = 0,back = 0; /维持两个指针int lenth = strcode.length(); /扫描区域的总长度char temp;num_class = 0; /记录识别出词法单元的个数方便存储while(forward <= strcode.length()-1) /开始扫描temp = strcodeforward;if(temp >= 65)&&(temp <= 89) | (temp >= 97)&

19、amp;&(temp <= 122)/判断是否是标识符或关键字back = forward;forward = is_key_ID(forward,back); /识别该标识符或ID，存入相应的词法单元，返回当前扫描位置forward指针forward +;back = forward; /继续扫描下一个字符continue;else if(temp >= 48)&&(temp <= 57) /判断是否是数字back = forward;forward = is_number(forward,back);forward+;back = forward;

20、continue;else if( (temp = '+') | (temp = '-') |(temp = '*') |(temp = '/') |(temp = '(') |(temp = ')') | (temp = '') | (temp = '') |(temp = '') |(temp = '') |(temp = ',') |(temp = ':') |(temp = '')

21、 )/判断是否是符号back = forward;for(i = 0;i < ModulClass_size;i+) /在表中查找当前词法单元的编号if(modulclassi.strID0 = temp)codeclassnum_class.number = modulclassi.number; codeclassnum_class.code = modulclassi.strID;break;num_class+; /增加词法单元个数forward+;back = forward;continue;else if(temp = '<') | (temp = &

22、#39;=') |(temp = '>') |(temp = '!') ) /判断是否是relop比较运算符back = forward;forward = is_relop(forward,back);forward+;back = forward;continue;else if(temp = ' ') /空格forward+;back = forward;continue;elseforward+;back = forward;/while9. 将产生的词法单元写入文件 依次将生成的对象写入文件即可。ofstream outf

23、ile;outfile.open("词法分析结果.txt");for(i = 0;i < num_class;i+)outfile<<codeclassi.code<<" " outfile<<codeclassi.number<<endl;cout<<codeclassi.code<<" " cout<<codeclassi.number<<endl;outfile.close();四.实验结果1.class文件的内容如下，存放预先

24、设定好的词法单元2.code文件代码如下，存放要识别的程序源代码3.图为程序运行结果，为识别后的词法单元五.实验总结 本次实验中词法分析相关代码均由我一人独立编写。理论联系实际的过程中比较坎坷，首先必须明白词法分析的过程，明白词法单元的识别过程，然后才能设计自己的程序。但书本知识和程序仍然有一定的差距，在设计过程中必须按照步骤一步一步进行设计，按照标准的模块进行划分。同时模块的划分必须合理，尽量减少模块间的联系，对今后调试程序有很大帮助。 同时通过这次实验我明白了正则文法的作用，在学习形式语言的时候一直疑惑文法的体系和正规文法的用处，在本次实验中我体会到了正则文法的威力，正则文法可以很好的被计

25、算机高级语言编程识别，而其他文法则没有这种优势。附录：源代码/词法分析器 BaiChenjia#include "iostream"#include "string"#include "math.h"#include "fstream"#define ModulClass_size 29#define CodeClasss_size 100using namespace std;string strcode; /存储处理过后的代码int num_class = 0; /记录识别出的词法单元的个数class Modu

26、lClass /存储词法单元的分类public:string strID; /单元名字int number; /单元编号;ModulClass modulclassModulClass_size;class CodeClass /存储识别过程中识别的词法单元public:string code; /名字int number; /编号;CodeClass codeclassCodeClasss_size;int readcode() /读取要处理的代码int i,j;char temp1000;strcode = ""string strtemp = ""

27、 /存储代码ifstream infile("code.txt",ios:in);if (!infile)cout<<"无法打开代码文件!"<<endl;exit(-1);infile.getline(temp,1000,EOF);tempstrlen(temp) = '0'infile.close();for(i = 0;i < strlen(temp);i+) if(tempi = 'n') strtemp += " " else strtemp += tempi;st

28、rtempi = '0'for(j = 0;j <= strtemp.length();)if(strtempj = ' ')while(strtemp+j = ' ')strcode += ' ' /处理空格，将多个连续的空格压缩成一个continue;elsestrcode += strtempj; j+;cout<<"消去空格和换行符处理结果"<<endl<<strcode<<endl;return 0;void init_class() /对文法规定

29、的标识符、数字、符号等进行分类，写入modulclass对象中int i;ifstream in_class;in_class.open("class.txt");if (!in_class)cout<<"无法打开代码文件!"<<endl;exit(-1);i = 0;while(!(in_class.eof()in_class>>modulclassi.strID;in_class>>modulclassi.number;i+;in_class.close();/*for(i = 0;i < Mod

30、ulClass_size;i+)cout<<modulclassi.strID<<" "<<modulclassi.number<<endl;*/int is_key_ID(int forward,int back) /判断是否是标识符string idtemp = ""char temp100;memset(temp,0,100);int len = 0; /记录该标识符或ID的长度-1temp0 = strcodeback;while(+forward) /扫描字符串，返回 idtemp，保存forwa

31、rdif(strcodeforward >= 65)&&(strcodeforward <= 89) | (strcodeforward >= 97)&&(strcodeforward <= 122) /下一个是字母 temp+len = strcodeforward;else if(strcodeforward >= 48)&&(strcodeforward <= 57) /下一个是数字temp+len = strcodeforward;elseforward-;break;idtemp = temp;/保存

32、词法单元bool iskey = false; /判断是否是keycodeclassnum_class.code = idtemp; /保存词法单元code属性for(int i = 0;i < ModulClass_size;i+) /在表中查找当前词法单元的编号if(idtemp = modulclassi.strID)/完全匹配：是关键字codeclassnum_class.number = modulclassi.number;iskey = true; break;if(!iskey) /如果不是关键字，即为IDcodeclassnum_class.number = 8; /I

33、D的编号为8num_class+;return forward; /返回当前扫描的位置int is_number(int forward,int back)char temp100;memset(temp,0,100);string numtemp;int len = 0; /记录该标识符或ID的长度-1templen = strcodeback;while(+forward) /扫描字符串，返回 idtemp，保存forwardif(strcodeforward >= 48)&&(strcodeforward <= 57) /下一个是数字temp+len = st

34、rcodeforward;elseforward-;break;numtemp = temp;/保存词法单元codeclassnum_class.code = numtemp; /保存词法单元code属性codeclassnum_class.number = 9; /ID的编号为8num_class+;return forward; /返回当前扫描的位置int is_relop(int forward,int back) /识别relop符号string relop;int len = 0; /记录该标识符或ID的长度-1char temp2;temp0 = strcodeback; /第一个

35、字符temp1 = strcode+forward; /第二个字符if(temp1 != '=' ) /该运算符仅有一个字符forward-; /回退指针/保存词法单元switch(temp0)case '<': codeclassnum_class.code = "L" /保存词法单元code属性 codeclassnum_class.number = 25; /ID的编号 break;case '>': codeclassnum_class.code = "G" /保存词法单元code属性

36、codeclassnum_class.number = 24; /ID的编号 break;case '=': codeclassnum_class.code = "=" /保存词法单元code属性 codeclassnum_class.number = 10; /ID的编号 num_class+;else /由两个字符构成,第二个为=/保存词法单元switch(temp0)case '<': codeclassnum_class.code = "LE" /保存词法单元code属性 codeclassnum_class

37、.number = 27; /relop的编号 break;case '>': codeclassnum_class.code = "GE" /保存词法单元code属性 codeclassnum_class.number = 26; /relop的编号 break;case '=': codeclassnum_class.code = "EQ" /保存词法单元code属性 codeclassnum_class.number = 28; /relop的编号 break;case '!': codecla

38、ssnum_class.code = "NE" /保存词法单元code属性 codeclassnum_class.number = 29; /relop的编号 num_class+;return forward; /返回当前扫描的位置void scanner()int i;int forward = 0,back = 0; /维持两个指针int lenth = strcode.length(); /扫描区域的总长度char temp;num_class = 0; /记录识别出词法单元的个数方便存储while(forward <= strcode.length()-1)

39、 /开始扫描temp = strcodeforward;if(temp >= 65)&&(temp <= 89) | (temp >= 97)&&(temp <= 122)/判断是否是标识符或关键字back = forward;forward = is_key_ID(forward,back); /识别该标识符或ID，存入相应的词法单元，返回当前扫描位置forward指针forward +;back = forward; /继续扫描下一个字符continue;else if(temp >= 48)&&(temp &l

40、t;= 57) /判断是否是数字back = forward;forward = is_number(forward,back);forward+;back = forward;continue;else if( (temp = '+') | (temp = '-') |(temp = '*') |(temp = '/') |(temp = '(') |(temp = ')') | (temp = '') | (temp = '') |(temp = '

41、9;) |(temp = '') |(temp = ',') |(temp = ':') |(temp = '') )/判断是否是符号back = forward;for(i = 0;i < ModulClass_size;i+) /在表中查找当前词法单元的编号if(modulclassi.strID0 = temp)codeclassnum_class.number = modulclassi.number; codeclassnum_class.code = modulclassi.strID;break;num_cla

42、ss+; /增加词法单元个数forward+;back = forward;continue;else if(temp = '<') | (temp = '=') |(temp = '>') |(temp = '!') ) /判断是否是relop比较运算符back = forward;forward = is_relop(forward,back);forward+;back = forward;continue;else if(temp = ' ') /空格forward+;back = forwar

43、d;continue;elseforward+;back = forward;/whilevoid printFile() /将产生的词法单元写入文件int i;ofstream outfile;outfile.open("词法分析结果.txt");for(i = 0;i < num_class;i+)outfile<<codeclassi.code<<" " outfile<<codeclassi.number<<endl;cout<<codeclassi.code<<&qu

44、ot; " cout<<codeclassi.number<<endl;outfile.close();int main()readcode(); /读取代码文件并进行初步处理init_class(); /读取对词法单元的分类信息scanner(); /依次扫描识别词法单元printFile(); /将识别结果存入文件中getchar();return 0;实验二 LR语法分析器设计一 实验目的通过设计调试LR语法分析程序，实现根据词法分析的输入TOKEN字，进行文法的语法分析；加深对课堂教学的理解；提高语法分析方法的实践能力。二 实验内容使用附录中的文法，可

45、以对类似下面的程序语句进行语法分析：int a;int b;int c;a=2;b=1; if （a>b）c=a+b;elsec=a-b;三 实验要求（一） 程序设计要求（1）给出主要数据结构：分析栈、符号表；（2）将扫描器作为一个子程序，每次调用返回一个TOKEN；（3）程序界面：表达式输入、语法分析的表示结果（文件或者图形方式）；（二）实验报告撰写要求（1）系统功能分析与设计（包括各个子功能模块的功能说明）；（2）开发平台（操作系统、设计语言）；（3）设计方案:包括功能模块结构图、主要函数的流程图；（4）主要数据结构：分析栈、分析表、符号表；（5）具体设计实现过程（包括主控程序、各个

46、功能模块的具体实现）。四 实验总结附录：简单类c语言文法产生式 语义规则注：P为文法的开始符号说明语句部分文法：P D SD L id ; D |L int | float程序语句部分文法：S id = E; S.code = E.code | gen(id.place:=E.place)S if （C） S1 C.true = newlabel; C.false = S.next;S1.next = S.next;S.code = C.code | gen(C.true:) | S1.codeS if （C） S1 else S2S while （C） S1 do S2C.true = ne

47、wlabel; C.false = newlabel;S1.next = S2.next =S.next;S.code = C.code | gen(C.true:) | S1.code| gen(gotoS.next)| gen(C.false:)| S2.code;S S ;SC E1 > E2C.code = E1.code | E2.code |gen(ifE1.place>E2.placegotoC.true) |gen(gotoC.false)C E1 < E2 C.code = E1.code | E2.code |gen(ifE1.place<E2.pl

48、acegotoC.true) |gen(gotoC.false)C E1 = E2 C.code = E1.code | E2.code |gen(ifE1.place=E2.placegotoC.true) |gen(gotoC.false)E E1 + T E.place = newtemp;E.code = E1.code|T.code|gen(E.place:=E1.place+T.place)E E1 T E.place = newtemp; E.code = E1.code | T.code |gen(E.place:=E1.place-T.place)E T E.place =

49、T.place; E.code = T.codeT F T.place = F.place; T.code = F.codeT T1 * F T.place = newtemp;T.code = T1.code | F.code |gen(T.place:=T1.place*F.place)T T1 / F T.place = newtemp; T.code = T1.code | F.code |gen(T.place:=T1.place/F.place)F ( E ) F.place = E.place; F.code = E.codeF id F.place = ; F.c

50、ode = F int10 F.place = int10.value; F.code = 实验报告 注：我编写的语法分析程序没有调试通，所以先实现了课本上的简单文法的例子，即 E> E E > E+T | T T > T*F | F F > (E) | id 的文法的语法分析，并未完全实现本实验的要求。一.实验要求1.对已给语言文法，构造LR(1)分析表，编制语法分析程序，要求将错误信息输出到语法错误文件中，并输出分析句子的过程（显示栈的内容）；2.给出主要数据结构：分析栈、符号表。3.将扫描器作为一个子程序，每次调用返回一个TOKEN；4.程序界面：表达式输入、语法分析的表示结果（文件或者图形方式）；二.详细设计1.此次所写程序是以词法分析器为基础编写的。2.考虑以下输入为合法： 数字 自定义变量 + * （ ） $作为句尾结束符。其它符号都判定为非法。3.首先我们构造状态转换图 状态actiongotoId+*()$ETF0S5S41231S6acc2R2R7R2R23R4R4R4R44S5S48235R6R6R6R66S5S4937S5S4108S6S119R1S7R1R110R3R3R3R311R5R5R5R54.根据状态转换图写出移入和规约关系。程序结构示意图是否否是否能否归约词法分析器