实验一词法分析

1、实验一词法分析一、实验目的通过设计、编写和调试词法分析程序， 了解词法分析程序的作用，组成结构，不同种类单词的识别方法，掌握由单词的词法规则出发，画出识别单词的状态转换图，然后在用程序实现词法分析程序设计方法。二、词法规则1、注释用 和 括起来。注释体中不能有 。注释可以出现在任何记号的后面。2、记号间的空格可有可无， 但关键字前后必须有空格、 换行、程序的开头或者结尾的原点。3、标识符的记号 id 与以字母开头的字母数字串相匹配：Letter->a-zA-ZDigit->0-9Id->letter (letter | digit)*4、记号 num 与无符号整数相匹配：Di

2、gits->digit digit*Optional_fraction -> . Digits | ?Optional_exponent->(E(+ | - | ? ) digits) | ?Num ->digitsoptional_fractionoptional_exponent5、关键字要被保留且在文法中以黑体出现6、关系运算符（ relop）指： =、<、<>、<=、>=、>7、Addop: + 、 - 、or8、Mulop ：* 、/ 、div、mod、and9、Assignop： :=三、词法分析程序详细设计及判别状态图1

3、、无符号数（可带小数和指数）的状态转换图：E/e数字数字数字数字.数字E/e+/-数字其他04612357数字其他其他2、3、标识符 /关键字的状态转换图：字母或数字其他12字母0程序详细设计：初始化打开源文件Y源程序结束？N关闭源文件读入一行到StrLine中Fgets()词法分析结束Y缓冲区空？N读取单词的第一个字符ch根据第一个字符进行分类JudgeFirstLetter(ch)数字字母识别数值常数识别标识符/ 关键字RecogDigit()RecogIdentifier()其他符号识别标点/ 操作符RecogPunc()是关键字？IsKey()NY报错NError()是否合法？Y插入队

4、列四、开发环境本程序在 Microsoft Visual C+ 6.0环境中编写，无特殊编译要求。五、函数清单void LexcialAnalysis(FILE *fp);/词法分析主函数int JudgeFirstLetter(char ch);/判断单词的第一个字符int IsDigit(char ch);/判断是否为数字int IsLetter(char ch);/判断是否为字母int IsSpecialPunc(char ch);/判断是否为特殊标点void RecogDigit(char StrLine);/用状态图识别无符号数字void RecogIdentifier(charst

5、rLine);/用状态图识别标识符void RecogPunc(char strLine);/识别特殊标点int IsKeyWord(string str);/判断标识符是否为关键字void error();/出错处理六、测试程序program example(input, output);comments goes here!var x, y: integer;function gcd(a, b: integer): integer;beginif b =1.2e3 then gcd := aelse gcd := gcd(b, a mod b)end;beginread(x, y);wri

6、te(gcd(x, y);end.七、运行效果八、实验总结通过这次编译器词法分析程序的编写， 我更好地了解了词法分析的作用及工作原理，讲课本中的知识融入到程序编写过程中，理论结合了实际。最先的时候觉得自己没有学过编译原理也可以写出语法分析，觉得书上的理论没有用，但是状态转换图则以一种十分规范的分析方式来分析程序 , 这样的做法应该是让词法分析从简单的程序实现上升到理论 . 而不仅仅拘泥于程序语言范畴之内 . 自己通过状态转换图识别单词和数字的过程， 我觉得这种思想是值得我们借鉴的，很美妙。当然，本次实验由于能力、时间等多方面因素只是实现了一个简单的词法分析程序，很多地方还不是很完善，如错误处理

7、等。此外，在编写词法分析程序的过程中，我遇到不少的问题，通过不断地调试才得以解决，锻炼了我调试程序的能力，这个能力是很难得的。实验二语法分析一、实验目的通过设计、编写和调试自顶向下语法分析程序，了解一般自顶向下语法分析程序的组成以及对文法的要求，掌握从给定文法出发构造相应的预测分析表的方法。二、实验设计本次语法分析实验我选用自顶向下的LL(1) 预测分析方法，该方法实现的语法分析程序最主要的一点就是能构造出其文法对应的预测分析表，只有正确的预测分析表，才能得到正确的语法分析结果。我使用了一个队列 (Queue)来存放词法分析的结果，在词法分析过程中就开始维护该队列， 然后在语法分析的时候， 从

8、队列中读取词法分析的结果。此外，我还定义了一个分析栈，供语法分析过程使用。三、文法规则终结符（ VT）1.保留关键字Program const do begin end call if else then function var while int real特殊标点：,;:.()其他assignop :=mulop * 、/、div 、mod、 and addop +、-、orrelop =、<>、<、<=、>=、>.（0 1 2 3 4 5 ）Id 变量名num 数字非终结符P(program)Ds(declarations)Subp_Ds(subpro

9、gram_declarations)C_S(compound_statement)ID_L(id_list)T(type)Subp_D(subprogram_delaclation)Subp_H(subprogram_head)A(arguments)P_L(parameter_list)OP_S(optional_statement)S_L(starement_list)S(statement)P_S(procedure_statememt)E_L(expression_list)E(expression) S_E(simple_expression)Tm(term) F(factor)消除

10、左递归后产生的新的非终结符ID_L , P_L,S_L,E_L,S_ETm ,E ,F改进后文法：1.P->program id(ID_L); Ds Subp_Ds C_S .2.ID_L->id ID_L3.ID_L ->,id ID_L 4.ID_L ->?5.Ds->var ID_L : T ;Ds6.Ds-> ?7.T-> integer8.T->real9.Subp_Ds->Subp_D ;Subp_Ds10.Subp_Ds->?11.Subp_D->Subp_H Ds C_S12.Subp_H->functio

11、n id A :T ;13.A->(P_L)14.A-> ?15.P_L ->ID_L: TP_L16.P_L -> ; ID_L: TP_L17.P_L ->?18.C_S -> begin OP_S end19.OP_S -> S_L20.OP_S -> ?21.S_L -> SS_L22.S_L-> ; S S_L23.S_L-> ?24.S > id P_S25.P_S -> assignop E26.P_S -> (E_L)27.S -> C_S28.S -> ifEthen Selse

12、S29.S -> while E do S30.E_L -> EE_L31.E_L -> , EE_L 32.E_L -> ?33.E->S_EE34.E ->relop S_E35.E -> ?36.S_E-> Tm S_E 37.S_E -> addop Tm S_E 38.S_E -> ?39. Tm -> FTm 40.Tm -> mulop F Tm 41.Tm -> ?42. F ->id F 43. F ->(E_L)44. F-> ?45.F-> ?46.F->(E)47

13、.F->not F以上文法构造出预测分析表，然后在程序中维护该预测分析表。(预测分析表见最后或源程序)四、函数清单及数据结构struct Queue/定义一个队列int front;int rear;string *str;void InitQueue(Queue &q,int QueueSize)/ 初始化队列q.front=q.rear=0;q.str=new stringQueueSize;void EnQueue(Queue &q,string str)/ 进队q.strq.rear=str;q.rear+;void DeQueue(Queue &q,st

14、ring &str)/出队str=q.strq.front;q.front+;typedef struct/ 定义分析栈int base;int top;symbol *symbol;Stack;void GetTop(Stack s,symbol &symbol)/获得栈顶元素if(s.base=s.top)cout<<" 栈为空 "return;symbol=s.symbols.top;void Push(Stack &s,symbol symbol)/ 进栈s.top+;s.symbols.top=symbol;void Pop(S

15、tack &s,symbol &symbol)/出栈if(s.base=s.top)cout<<" 栈为空 "return;symbol=s.symbols.top;s.top-;struct Production/ 定义一个产生式结构体string head;string body;void InitPaserTable(Production (*p)25) ； /维护一张预测分析表 int Hash(string str)/ 返回对应字符的行列数用于预测分析表的定位 void SyntaxAnalysis() ； / 语法分析程序void m

16、ain()/main函数中调用词法分析程序和语法分析程序FILE * fp;while(TRUE)/cin>>fNamePath;if(fp=fopen("ex.cpp","r")!=NULL)/文件可读就跳出循环break;else cout<<" 文件路径错误！请输入源文件名（包括路径和后缀名）:"LexcialAnalysis(fp);/词法分析SyntaxAnalysis();/ 语法分析五、运行效果由于结果很长这里只贴上部分截屏六、实验总结通过本次设计、 编写和调试语法分析程序的过程， 我了解了一般自顶向下语法分析程序的组成以及对文法的要求， 掌握了从给定文法出发构造相应的预测分析表的方法。 如构造 First 集、Follow 集、Select集和 LL(1) 预测分析表。了解了语法分析的具体过程。由于时间的原因，我的语法分析程序还并不完善，出错处理还不是面面俱到，待以后有时间再完善也是一次不错的锻炼。在语法分析的学习中 ,通过对自顶向下和自底向上理解, 让我领悟了一些有价值的考虑问题的方法. 在我看来编译原理从本质上来讲就是算法问题， 本次的实验大多也都是算法思想的体现，只是由于编译器的复杂性 ,