词法分析的设计与实现(共16页).doc

《词法分析的设计与实现(共16页).doc》由会员分享，可在线阅读，更多相关《词法分析的设计与实现(共16页).doc（16页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上题 目 词法分析的设计与实现 学 院 专业名称 计算机科学与技术 姓 名 导师姓名 2010年 12 月目录1课程设计的目的12课程设计的内容13、 课程设计的要求 14课程设计报告内容1 4.1设计功能分析1 4.2 设计思路1 4.3 正规文法24.4 状态图 3 4.5设计词法分析算法代码 5 4.6基本测试数据 12 4.7结果截图 125设计体会 126参考文献137思考题13专心-专注-专业词法分析的设计与实现一、课程设计的目的1、基本掌握计算机语言的词法分析程序的开发方法。2、实现一个词法分析程序，将字符串流分解成终结符流供语法分析使用。3、通过设计编制

2、调试一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。4、了解当前常用的软件开发工具Visual C+，熟练掌握基于MFC的程序设计，培养解决实际问题的能力。5、对C语言和数据结构的进一步巩固加深。二课程设计的内容编制一个能够分析三种数、标识符、主要运算符、分隔符和主要关键字的词法分析程序。三、课程设计的要求1根据以下的正规式，编制正规文法，画出状态图；标识符 (|)*十进制数 (0 | 1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* (|.)(0|1|2|3|4|5|6|7|8|9)

3、(0|1|2|3|4|5|6|7|8|9)*八进制数0(1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*（|.)(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*十六进制 0x(0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f)(0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f)* (|.)(0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f)(0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f)*运算符和分隔符 + - * / B1C1 B1D1B1| C1E1B1 E1 |. D10|1|2|3|4|5

4、|6|7|8|9 对于八进制数： A20B2 B2C2D2 C2E2F2 E21|2|3|4|5|6|7 F2GF| D2H2F2 H2 |. D21|2|3|4|5|6|7 G20|1|2|3|4|5|6|7对于十六进制： A30xB3 B3C3D3 C3E3C3| E3 0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f D3F3C3 F3 |.对于运算符和分隔符： A4+|-|*|/|B5C5 B5D5E5 D5a|b|y|z E5F5E5| F5a|b|y|z|0|1|2|3|4|5|6|7|8|9 C5G5E5 G5 |.综上正规文法为： SA1|A2|A3|A4|A5

5、A1B1C1 B1D1B1| C1E1B1 E1 |. D10|1|2|3|4|5|6|7|8|9 A20B2 B2C2D2 C2E2F2 E21|2|3|4|5|6|7 F2GF| D2H2F2 H2 |. D21|2|3|4|5|6|7 G20|1|2|3|4|5|6|7 A30xB3 B3C3D3 C3E3C3| E3 0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f D3F3C3 F3 |. A4+|-|*|/|B5C5 B5D5E5 D5a|b|y|z E5F5E5| F5a|b|y|z|0|1|2|3|4|5|6|7|8|9 C5G5E5 G5 |.4.4、状态图07

6、0*0.9/az/AZ1909其他开始空白a.z/ AZ023469其他。09非数字。07非o.7且非。110007非o.7。75812111319/a.f/ AF14非1.9且非a.f且非A.F150.9/a.f/A.F16非0.9且非a.f且非A.F。17。018190+/-/ /;If/while/then/dox/X4.4设计词法分析算法代码：#include#include#include stdafx.hunion chars /联合，可存储字符串，整型和浮点型char pro_char15;int pro_number;float real;struct data /将每个单元用

7、一个结构来存储，其内容包括：类型，所属的具体类型，以及属性值char kind7;int id;union chars pro;int scan(char *a); /对每个用空格打断的单元进行进一步的分析，对其进行进一步的分类void Prints(char a15,int id,int a_long); /将分析后的每个token输出void save(char *a,int id,int x); /将分析后的结果保存到一个结构数组中char nowChar15; /临时的存储单元，用来存储被空格打断以后单元char kinds118= ,INT10,INT8,INT16,IDN, , ,

8、 ,REAL10,REAL8,REAL16;/单词的不同种别struct data link100; /用来存放词法分析以后的结果的结构数组int link_long=0; /全局变量int scan(char *a)int id;int a_long=0;int doc=0;while(*a!=NULL)nowChar0=0;a_long=0;doc=0;/对数值的判断及处理if(0=*a&*a=9) /如果第一个字符为数值nowChara_long=*a;*a+;a_long+;/对十六进制的判断及处理if(nowChar0=0&(*a=x|*a=X) /如果第一个字符为0且第二个字符为x

9、,则为十六进制数nowChara_long=*a;*a+;a_long+;while(*a!=NULL&(0=*a&*a=9)|(a=*a&*a=f)|(A=*a&*a=F)|*a=.)nowChara_long=*a; /一直将此十六进制数完全读入，若为浮点型的，则加以标记if(*a=.)doc=1;*a+;a_long+;nowChara_long=0; /判断输入的十六进制数是否合法if(a_long=2) /输入的只有0x，则输入错误Prints(nowChar,7,a_long);return 0;if(doc) /输入的十六进制数是浮点型的Prints(nowChar,10,a_l

10、ong); /则将其具体的类型属性定为10else /输入的十六进制数是整型的Prints(nowChar,3,a_long); /则将其具体的类型属性定义为3continue;/对八进制的判断及处理if(nowChar0=0&0=*a&*a=7) /如果第一个字符为0且第二个字符为07,则为八进制数nowChara_long=*a;*a+;a_long+;while(*a!=NULL&(0=*a&*a=7)|*a=.)nowChara_long=*a; /一直将此八进制数完全读入，若为浮点型的，则加以标记if(*a=.)doc=1;*a+;a_long+;nowChara_long=0;if

11、(doc) /输入的八进制数是浮点型的Prints(nowChar,9,a_long); /则将其具体的类型属性定为9else /输入的十六进制数是整型的Prints(nowChar,2,a_long); /则将其具体的类型属性定义为2continue;/对十进制数的判断及处理elsewhile(*a!=NULL&(0=*a&*a=9)|*a=.)nowChara_long=*a; /一直将此十进制数完全读入，若为浮点型的，则加以标记if(*a=.)doc=1;*a+;a_long+;nowChara_long=0;if(doc) /输入的十进制数是浮点型的Prints(nowChar,8,a

12、_long); /则将其具体的类型属性定为8else /输入的十进制数是整型的Prints(nowChar,1,a_long); /则将其具体的类型属性定义为1continue; /完成了对数值的判断及处理/对字符的判断及处理elsenowChara_long=*a;*a+;a_long+;/判断输入的字符是否为运算符或其他的分隔符switch(nowChar0)case+:case-:case*:case/:case:case(:case):case=:case;:nowChara_long=0;Prints(nowChar,5,a_long); /将其具体的类型属性定义为5continue

13、;default:break;/判断输入的第一个字符是否为字母if(a=nowChar0&nowChar0=z)|(A=nowChar0&nowChar0=Z)while(*a!=NULL&(a=*a&*a=z)|(A=*a&*a=Z)|(0=*a&*a=9)|(*a=.)|(*a=_) /一直将此字符串完全读入nowChara_long=*a;*a+;a_long+;nowChara_long=0;/判断输入的字符串是否为特殊的标识符，若是，则将其具体类型值定义为6/判断输入的字符串是否为特殊的字符串ifif(a_long=2&strcmp(nowChar,if)=0)Prints(nowC

14、har,6,a_long);continue;/判断输入的字符串是否为特殊的字符串thenif(a_long=4&strcmp(nowChar,then)=0)Prints(nowChar,6,a_long);continue;/判断输入的字符串是否为特殊的字符串elseif(a_long=4&strcmp(nowChar,else)=0)Prints(nowChar,6,a_long);continue;/判断输入的字符串是否为特殊的字符串whileif(a_long=5&strcmp(nowChar,while)=0)Prints(nowChar,6,a_long);continue;/判

15、断输入的字符串是否为特殊的字符串doif(a_long=2&strcmp(nowChar,do)=0)Prints(nowChar,6,a_long);continue;/若输入的字符串不符合以上几种情况，则输入的为变量/若输入的字符串为变量，则将其具体属性值定义为4Prints(nowChar,4,a_long);continue;/如果输入的既不是数值也不是字符串，则输入错误，将其具体类型之定义为7elsePrints(nowChar,7,a_long);return 0;return 1;main() char buf100; /用来存储从键盘上输入一串字符 char *tokenPtr

16、; /用来存储用空格打断后的单元int id=1; /用来存储具体的类型号link_long=0;while(id)link_long=0;gets(buf); /从键盘上输入一串字符tokenPtr=strtok(buf, ); /用空格将字符串打断while(id&*tokenPtr!=NULL) /分割出来的单元不为空 id=scan(tokenPtr); /将此单元进行继续分析，并返回其具体的类型值 tokenPtr=strtok(NULL, ); /将字符串继续用空格进行分割printf(nn);getchar();return 0;/将所分解后的单元存入结构数组中void save

17、(char *a,int id,int x,float y)int i;if(link_long=5)if(id=8)/id=8,9,10/若为浮点型的数值，则将浮点型的y值（转换后的）存入其属性当中且存入单词的种别for(i=0;i9&kindsidi!=0;i+)linklink_long.kindi=kindsidi;linklink_long.pro.real=y;/id=5,6,7else/若为标识符，则将单词种别定为自身，属性值定为空for(i=0;i15&ai!=0;i+)linklink_long.kindi=ai;linklink_long.pro.pro_char0=-;l

18、inklink_long.pro.pro_char1=0;link_long+;/id=1,2,3,4elsefor(i=0;i8&kindsidi!=0;i+)linklink_long.kindi=kindsidi; /若分解后的token为变量或者整型数值，则将其单词种别直接输出if(id=4) /若token为变量，则将其属性值设为自身for(i=0;i15&ai!=0;i+)linklink_long.pro.pro_chari=ai;linklink_long.pro.pro_chari=0;else /若token为整型数值，则将其相应的十进制数值赋给其属性值linklink_l

19、ong.pro.pro_number=x;link_long+; /继续存入下一个tokenelseprintf(Full 100n); /结构数组已经存满return;/将词法分析器分解后的结果输出出来void Prints(char a15,int id,int a_long)int i;int x=0;float y=0;/int float1;/char *c;if(id=1) /若为十进制整数for(i=1;ia_long&ai!=0;i+)x=x*10+(ai-48);printf(INT10t%sn,a);save(a,id,x,y); /存入结构数组return;if(id=2

20、) /若为八进制整数for(i=1;ia_long&ai!=0;i+)x=x*8+(ai-48); /换算为十进制数printf(INT8t%dn,x);save(a,id,x,y); /存入结构数组return;if(id=3) /若为十六进制整数for(i=2;ia_long&ai!=0;i+)if(0=ai&ai9)x=x*16+(ai-48); /换算为十进制数elseif(a=ai&ai=f)x=x*16+(ai-87);elsex=x*16+(ai-55);printf(INT16t%dn,x);save(a,id,x,y); /存入结构数组return;if(id=4) /若为变

21、量printf(IDNt%sn,a);save(a,id,x,y); /存入结构数组return;if(id=5|id=6) /若为标识符（+,-,*,/,+以及if,else,while,then,do）printf(%st-n,a);save(a,id,x,y); /存入结构数组return;if(id=8) /若为十进制浮点型for(i=0;i=0&ai!=.;i-)y=(y+(ai-48)/10;y=y+x; /整数部分与小数部分换算后相加printf(REAL10t%fn,y);save(a,id,x,y); /存入结构数组return;if(id=9) /若为八进制浮点型for(i

22、=1;i=0&ai!=.;i-)y=(y+(ai-48)/8;y=y+x; /整数部分与小数部分换算后相加printf(REAL8t%fn,y);save(a,id,x,y); /存入结构数组return;if(id=10) /若为十六进制浮点型for(i=2;i=0&ai!=.;i-)y=(y+(ai-48)/16;y=y+x; /整数部分与小数部分换算后相加printf(REAL16t%fn,y); /存入结构数组save(a,id,x,y);return;printf(Wrong Enter); /所得的具体类型值为7，则输入有错误return ;4.5基本测试数据:输入数据例：00 9

23、6*name 25 0x8d while 5;4.6结果截图：五、设计体会本次的课程设计使团队成员对词法分析的过程有了全新的了解，同时也明白了词法分析何时可以采用空格来区分单词，明白了程序设计中影响词法分析的效率的环节。比如，关键字的识别过程。因为当词法分析器识别出一个标识符时，就去和保留字表中的关键字进行比较，以确定它是否是关键字。如果关键字和标识符比较少，标识符在表中采取顺序比较的时间还可以接受，但如果关键字和标识符都比较多，那么查询比较的平均时间就会比较长，就会影响到词法分析的效率。且每一次比较都是字符串之间的比较，也很耽误时间。因此，我们讨论出了采取比较好的预选方式，如对标识符先进行筛

24、选，有些不可能是关键字的标识符就可以不再与保留字表中的关键字进行比较了。如某种语言的关键字最长为8个字符，那么对于长度大过8的标识符被“筛下”了。当然进行“筛选” ，也要付出一定的代价。本次的课程设计培养了团队成员团结合作的精神，通过大家分工合作，提高了综合运用本课程所学知识的能力，培养成员独立思考、深入研究和认真分析问题的工作作风，体会到在遇到不懂时，认真查资料的重要性。对于这次的课程设计，从中积累了很多的经验，同时也总结了一些编程出现的问题。1、在调试的过程中添加语句时经常忘记加分号。2、在编写时对于多层括号的，时常少一边的括号，这个可以采用在编写时直接将完整的括号编写上去，不要只先写一边

25、的括号。3、经常未经定义便使用该变量。4、注意前后的函数名的大小写，保持前后一致，避免出现原本前后是同一个函数，但由于字母的大小写，而导致是表示两个不同的函数 。5、要判断好某个函数是否需要返回其函数值。6、判断好该代码需要在什么环境先实现的，是C还是C+。 六、参考文献 陈火旺、刘春林、谭庆平、赵克佳、刘越. 程序设计语言编译原理 .北京：国防工业出版社，2000高仲仪、金茂忠. 编译原理及编译程序构造. 北京：航空航天大学出版，1990刘春林.编译原理学习指导与典型题解析. 北京：国防工业出版社，2004Louden, K.C.编译原理及实践 . 机械工业出版社，2000（荷）格伦.现代编

26、译程序设计. 人民邮电出版社，2003七、思考题1词法分析能否采用空格来区分单词？答：不能这么绝对。因为有些单词之间一定要用空格等空白符分开，如关键字、标识符和常数之间没有确定的运算符或界符做间隔时，就一定要用空格等空白符分开。但是，因为存在加减乘除等运算符和分隔符，使用空格来区分可能造成错误的分解。2程序设计中哪些环节影响词法分析的效率？如何提高效率？答: 在程序设计中，影响词法分析的效率主要因素是各个状态的分支如何规划。比如关键字的识别过程。因为当词法分析器识别出一个标识符时，就去和保留字表中的关键字进行比较，以确定它是否是关键字。如果每个进来的单词都能在最短的时间和最少的匹配次数内找到其入口，则效率将得到很大程度上的提高。 在我看来，对分支的入口设计的优化的具体方法如下： 由于程序中大部分都是标识符和关键字，因此先对其进行判断：若不是，则判断是否是运算符或分隔符；若不是，则最后进行各类进制数的判断。由于我们平时在编写程序时很少使用进制数，因此将其放在最后来进行判断，这样可以提高整体的执行效率。