编译原理课程设计(共31页)

上传人:文**** 文档编号:56952273 上传时间:2022-02-22 格式:DOCX 页数:28 大小:411.98KB
收藏 版权申诉 举报 下载
编译原理课程设计(共31页)_第1页
第1页 / 共28页
编译原理课程设计(共31页)_第2页
第2页 / 共28页
编译原理课程设计(共31页)_第3页
第3页 / 共28页
资源描述:

《编译原理课程设计(共31页)》由会员分享,可在线阅读,更多相关《编译原理课程设计(共31页)(28页珍藏版)》请在装配图网上搜索。

1、精选优质文档-倾情为你奉上编译原理课程设计 实验名称:C-语言词法分析器的手工构造 C-语言词法分析器的lex生成 C-语言语法分析器的手工构造 学生姓名: 刘 恺 丽 学生学号: 指导教师姓名: 于中华 实验一:C-语言词法分析器的手工构造一、 实验目的及意义1. 理解C-语言的词法特点,并能构造各种token的正则表达式;2. 掌握将正则表达式转换为DFA的方法;3. 学会设计C-语言手动生成词法分析器的数据类型和数据结构。二、 实验环境1. 操作系统:Window XP/Windows 7;2. 开发环境:Microsoft Visual C+ 6.0。三、 算法分析与设计 1.C-语言

2、的词法规则(1)关键字else if int return void while(2)特殊符号+ - * / = = != = ; , ( ) /* */(3)其它token(区分大小写)ID = letter letter*NUM = digit digit*letter = a|z|A|.|ZDigit = 0|9 (4)空白符号 空白 n t (5)注释 由标记符号/*/标记起来的部分。 2.C-语言的词法正则表达式digit 0-9number digit+letter a-zA-Zidentifier letter+newline nwhitespace t+3.C-语言的DFA4.

3、重要数据类型设计(1)token类型用枚举量分为以下几个typedef enumENDFILE,ERROR,ELSE,IF,INT,RETURN,VOID,WHILE,ID,NUM,PLUS,MINUS,TIMES,OVER,LT,LTE,RT,RTE,EQ,NE,ASSIGN,SEMI,COMMA,LPAREN,RPAREN,LZ,RZ,LD,RD,LC,RCTokenType;(2)DFA9个状态typedef enumSTART,INNE,INEQ,INLT,INRT,INID,INNUM,INOVER,INCOMMENT1,INCOMMENT2,DONEStateType;四、代码实现

4、1. 查找保留字函数TokenTypeS FindResvd (char * s)须注意:对Keyword先将keyWord归为ID类。getToken时再匹配。 保留字数据结构如下:static struct char* str;TokenType tok;reservedWordsMAXRESERVED=else,ELSE,if,IF,int,INT,return,RETURN,void,VOID,while,WHILE;static TokenType reservedLookup (char * s)int i;for (i=0;i)state = INRT;else if (c =

5、)state = INLT;else if (c = /)state = INOVER;else if (c = )|(c = t)|(c =n)save=false;/state = START;elsestate = DONE;switch(c)case EOF:save = false;currentToken = ENDFILE;break;case +:currentToken = PLUS;break;case -:currentToken = MINUS;break;case *:currentToken = TIMES;break;case ;:currentToken = S

6、EMI;break;case ,:currentToken = COMMA;break;case (:currentToken = LPAREN;break;case ):currentToken = RPAREN;break;case :currentToken = LZ;break;case :currentToken = RZ;break;case :currentToken = LD;break;case :currentToken = RD;break;default:currentToken = ERROR;break;break;case INNE:state = DONE;if

7、(c=)currentToken=NE;elseungetNextChar();save=false;currentToken=ERROR;break;case INEQ:state = DONE;if(c=)currentToken=EQ;elseungetNextChar();currentToken=ASSIGN;break;case INRT:state = DONE;if(c=)currentToken=RTE;elseungetNextChar();currentToken=RT;break;case INLT:state = DONE;if(c=)currentToken=LTE

8、;elseungetNextChar();currentToken=LT;break;case INNUM:if(!isdigit(c)ungetNextChar();save = false;state = DONE;currentToken =NUM;break;case INID:if(!isalpha(c)ungetNextChar();save = false;state = DONE;currentToken =ID;break;case INOVER:if(c = *)save=false;state = INCOMMENT1;tokenStringIndex=0;/curren

9、tToken =LC;elseungetNextChar();save = false;state = DONE;currentToken =OVER;break;case INCOMMENT1:if(c = *)save=false;state = INCOMMENT2;else if(c=EOF)save=false;state=DONE;currentToken=ERROR; else save = false;state = INCOMMENT1;/currentToken =ENDFILE;break;case INCOMMENT2:save = false;if(c = /)sta

10、te = START;else if(c=EOF)state=DONE;currentToken=ERROR;else if(c = *)state =INCOMMENT2;elsestate = INCOMMENT1;break;case DONE:default:fprintf(listing,Scanner Bug: state= %dn,state); state = DONE;currentToken = ERROR;break;五、 测试结果测试小程序: 输出结果:程序运行结果分析:如上图所示:通过观察分析,发现程序已经能够成功识别关键字,如 第一行的“1”,能成功识别出NUM,如

11、 第六行的“int”,成功识别出reserved word等。 另外,第三行为注释部分,已经被识别出并跳过。同时,第四行为空,跳过。 通过以上实例运行结果可以得知,源文件中的各种token无论正确与否,都能够被本扫描程序准确的扫描出来。当能够获取正确的token时,就输出token;当遇到不能识别的token时,就输出一个ERROR:token;当遇到注释的时候,就说明是注释,并绕过。程序运行成功,词法分析正确。六、小结通过g本次实验,我学会了根据目标语言的词法规则构造正则表达式,并通过正则表达式构造出对应的DFA,并用代码实现DFA,能够用DFA来对C-语言进行词法分析。更深入的理解了DFA

12、的精髓,了解了用代码实现DFA的各种方法以及它们各自的特点。同时,也深入理解并实践了编译原理词法分析的相关理论。实验二:C-语言词法分析器的lex生成一、 实验目的及意义1. 实现基于Lex的C-语言的词法分析器2. 学会安装Parser Generator 2并且熟悉其环境3. 熟练配置Microsoft Visual C+ 6.0,并实现与Parser Generator 2 相应库的连接4. 学习基于Lex构造词法分析器的方法,以及实验过程5. 熟悉C-语言的各种Token6. 构造各种Token的正则表达式7. 设计词法分析器所需要的各种数据结构及Token识别成功后的 动作8. 用P

13、arser Generator 2实现所设计的C-词法分析器二、 实验环境1. Windows XP操作系统2. 编译环境Parser Generator3. VC6.0开发环境三、 分析与设计 1.C-语言的词法规则(1)关键字else if int return void while(2)特殊符号+ - * / = = != = ; , ( ) /* */(3)其它token(区分大小写)ID = letter letter*NUM = digit digit*letter = a|z|A|.|ZDigit = 0|9 (4)空白符号 空白 n t (5)注释 由标记符号/*/标记起来的部

14、分。 2.C-语言的词法正则表达式设计keyWord, SpecialChar, ID, ErrorID, Num, Annotation, Whitespace ,Enter, End, Other相关正则表达式如下所示:KeyWord else|if|int|return|void|whileSpecialChar +|-|*|/|=|=|!=|=|;|,|(|)|letter A-Za-zdigit 0-9ID letterletter*ErrorID digit+letter+(digit|letter)*|letter+digit+(digit|letter)*Num digit+A

15、nnotation /*Whitespace t+Enter n+ End Other .3.Erro的处理四、 测试结果输出测试小程序输出结果:实验结果分析: 如上图黄色部分所示,程序已经能够成功识别keyWord,ID,NUM,SpecialCh等常规token类型,同时能识别出ErrorID。 并能处理嵌套注释 和 文件末注释。程序分析正确,运行成功。五、 小结通过lex词法分析,学会了pargen的环境配置与使用。并对C-的正则表达式和lex的运行原理有一定的了解。实验四:C-语言语法分析器的手工构造一、实验目的及意义1.熟悉C-语言的语法规则;2.使用上下文无关文法描述C-语言的语法

16、规则 ;3.设计语法分析器所需要的各种数据结构 ; 4.基于递归下降法实现C-语言的语法分析器,能够输入源程序,输出整个程序的语法树。二、实验环境1.Windows XP2.Microsoft Visual C+ 6.0三、算法分析与设计(1)C-的BNF语法描述如下: 1.program - declaration-list2.declaration-list - declaration-list declaration | declaration3.declaration - var-declaration | func-declaration4.var-declaration - typ

17、e-specifier ID; |type-specifier ID NUM ;5.type-specifier - int | void6.fun-declaration - type-specifier ID ( params ) compound-stmt7.params - param-list | void8.param-list - param-list , param | param9.param - type-specifier ID | type-specifier ID pound-stmt - local-declarations statement-list | emp

18、ty11.local-declarations - local-declarations var-declaration | empty12.statement-list - statement-list statement | empty13.statement - expression-stmt | compound-stmt | selection-stmt | iteration-stmt | return-stmt14.expression-stmt - expression ; | ; 15.selection-stmt - if ( expression ) statement

19、| if ( expression ) statement else statement16.iteration-stmt - while ( expression ) statement 17.return-stmt - return ; | return expression ; 18.expression - var = expression | simple-expression19.var - ID | ID expression 20.simple-expression - additvie-expression relop addtive-expression | additiv

20、e-expression21.relop - = | | = | = | != 22.additive-expression - additive-expression addop term | term23.addop - + | - 24.term -term mulop factor | factor25.mulop - * | / 26.factor - ( expression ) | var | call | NUM 27.call - ID ( args ) 28.args - arg-list | empty29.arglist - arglist , expression |

21、 expression(2)节点类型:共有三种:表达式,语句,声明,参数四种 typedef enumStmtK,ExpK,DeclarK, ParamK NodeKind; 语句类型:分为if,while,return三种 typedef enumIfK,WhileK,ReturnK StmtKind; 表达式类型:Call类型,操作符类型,常数类型及变量类型,其中变量又 分数组和简单变量 typedef enumCallK,OpK,ConstK,IdK,ArryK ExpKind; 声明类型:分函数声明和变量声明,其中变量又分普通变量和数组变量 typedef enumFunDeclarK

22、,ArryDeclarK,VarDeclarK DeclarKind; 参数类型:数组参数,简单参数,函数参数 typedef enumArryParamK,IdParamK,VoidK ParamKind; typedef enumVoid,Int TypeKind;(3)节点的声明:typedef struct treeNodestruct treeNode*childMAXCHILDREN;struct treeNode*sibling;int lineno;NodeKind nodekind;union StmtKind stmt;ExpKind exp;DeclarKind decl

23、ar;ParamKind param;kind;struct TokenType op;int val;char *name;int index;attr;TypeKind type;TreeNode;四、代码实现 节点类型代码typedef enumStmtK,ExpK,DeclarK,ParamK NodeKind;typedef enumIfK,WhileK,ReturnK StmtKind;typedef enumCallK,OpK,ConstK,IdK,ArryK ExpKind;typedef enumFunDeclarK,ArryDeclarK,VarDeclarK Declar

24、Kind;typedef enumArryParamK,IdParamK,VoidK ParamKind;typedef enumVoid,Int TypeKind;typedef struct treeNodestruct treeNode*childMAXCHILDREN;struct treeNode*sibling;int lineno;NodeKind nodekind;union StmtKind stmt;ExpKind exp;DeclarKind declar;ParamKind param;kind;struct TokenType op;int val;char *nam

25、e;int index;attr;TypeKind type; 新建节点TreeNode *newDeclarNode(DeclarKind kind)TreeNode*t=(TreeNode *)malloc(sizeof(TreeNode);int i;if(t=NULL)printf(Out of memory error at line %dn,lineno);elsefor(i=0;ichildi=NULL;t-sibling=NULL;t-nodekind=DeclarK;t-kind.declar=kind;t-lineno=lineno;t-type=Void;t-attr.i

26、ndex=0;return t; 最重要的parse.cpp部分的关键代码static TokenType token;static TreeNode *declaration_list();static TreeNode *declaration();static TreeNode *params();static TreeNode *param_list();static TreeNode *param();static TreeNode *compound_stmt();static TreeNode *local_declarations();static TreeNode *stat

27、ement_list();static TreeNode *statement();static TreeNode *expression_stmt();static TreeNode *selection_stmt();static TreeNode *iteration_stmt();static TreeNode *return_stmt();static TreeNode *expression();static TreeNode *simple_expression(TreeNode* p);static TreeNode *additive_expression(TreeNode*

28、 p);static TreeNode *term(TreeNode* p);static TreeNode *factor();static TreeNode *args();static TreeNode *arg_list();static void syntaxError(char* message)printf( Syntax error at line %d: %s,lineno,message);static void match(TokenType expected)if(token=expected) token=getToken();elsesyntaxError(unex

29、pected token- );printToken(token,tokenString);TreeNode *declaration_list()TreeNode *t=declaration();TreeNode *p=t;while(token!=ENDFILE)TreeNode *q;q=declaration();if(q!=NULL)if(t=NULL)t=p=q;elsep-sibling=q;p=q;return t;TreeNode *declaration()TreeNode*t=NULL;char*s=NULL;if(token=INT)match(INT);char*s

30、=copyString(tokenString);match(ID);if(token=LZ)match(LZ);t=newDeclarNode(ArryDeclarK);t-type=Int;t-attr.name=copyString(s);t-attr.index=atoi(tokenString);match(NUM);match(RZ);match(SEMI);else if(token=LPAREN)t=newDeclarNode(FunDeclarK);t-attr.name=copyString(s);match(LPAREN);t-child0=params();match(

31、RPAREN); t-child1=compound_stmt();elset=newDeclarNode(VarDeclarK);t-type=Int;t-attr.name=copyString(s);match(SEMI);elset=newDeclarNode(FunDeclarK);match(VOID);t-type=Void;t-attr.name=copyString(tokenString);match(ID);match(LPAREN);t-child0=params();match(RPAREN);t-child1=compound_stmt();return t;Tre

32、eNode *params()TreeNode *t=NULL;if(token!=VOID)t=param_list();elset=newParamNode(VoidK);match(VOID);return t;TreeNode *param_list()TreeNode*t=NULL;t=param();TreeNode*p=t;while(token!=RPAREN) match(COMMA);/token=getToken();TreeNode*q=param();p-sibling=q;p=q;return t;TreeNode *param()TreeNode*t=NULL;m

33、atch(INT);char*s=copyString(tokenString);match(ID);if(token=LZ)match(LZ);t=newParamNode(ArryParamK);t-attr.name=copyString(s);t-attr.index=atoi(tokenString);match(token);match(RZ);elset=newParamNode(IdParamK);t-attr.name=copyString(s);return t;TreeNode *compound_stmt()match(LD);TreeNode*t=NULL;TreeN

34、ode*p=NULL;p=t=local_declarations();if(p!=NULL)while(p-sibling!=NULL) p=p-sibling;p-sibling=statement_list();elset=statement_list();match(RD);return t;TreeNode *local_declarations()TreeNode*t=NULL;TreeNode*p=NULL;TreeNode*q=NULL;while(token=INT)match(INT);char*s=copyString(tokenString);match(ID);if(

35、token=LZ)match(LZ);q=newDeclarNode(ArryDeclarK);q-attr.index=atoi(tokenString);q-type=Int;q-attr.name=copyString(s);match(NUM);match(RZ);match(SEMI);elseq=newDeclarNode(VarDeclarK);q-type=Int;q-attr.name=copyString(s);match(SEMI);if(q!=NULL)if(t=NULL) t=p=q;elsep-sibling=q;p=q;return t;TreeNode *sta

36、tement_list()TreeNode*t=NULL;if(token!=RD)t=statement();TreeNode*p=t;while(token!=RD)TreeNode*q=statement();p-sibling=q;p=q;return t;TreeNode *statement()TreeNode*t=NULL;switch(token)case IF:t=selection_stmt();break;case WHILE:t=iteration_stmt();break;case RETURN:t=return_stmt();break;case LD:t=comp

37、ound_stmt();break;default:t=expression_stmt();break;return t;TreeNode *expression_stmt()TreeNode*t=NULL;if(token!=SEMI)t=expression();match(SEMI);return t;TreeNode *selection_stmt()TreeNode*t=newStmtNode(IfK);match(IF);match(LPAREN);t-child0=expression();match(RPAREN);t-child1=statement();if(token=E

38、LSE)match(ELSE);t-child2=statement();return t;TreeNode *iteration_stmt()TreeNode*t=newStmtNode(WhileK);match(WHILE);match(LPAREN);t-child0=expression();match(RPAREN);t-child1=statement();return t;TreeNode *return_stmt()TreeNode*t=newStmtNode(ReturnK);match(RETURN);if(token!=SEMI)t-child0=expression(

39、);match(SEMI);return t;TreeNode *expression()TreeNode* t=NULL;if(token = ID)t=newExpNode(IdK);t-attr.name=copyString(tokenString);match(ID);if(token = LPAREN)t-kind.exp=CallK;match(LPAREN);t-child0=args();match(RPAREN);t=simple_expression(t);else if(token = LZ)match(LZ);t-kind.exp=ArryK;t-child0=exp

40、ression();match(RZ);if(token = ASSIGN)TreeNode* p=newExpNode(OpK);p-attr.op=token;match(ASSIGN);p-child0=t;p-child1=expression();t=p;elset=simple_expression(t);else if(token = ASSIGN)TreeNode* p=newExpNode(OpK);t-kind.exp=IdK;p-attr.op=token;match(ASSIGN);p-child0=t;p-child1=expression();t=p;else t=

41、simple_expression(t);else t=simple_expression(NULL);return t;TreeNode *simple_expression(TreeNode* p)TreeNode* t=additive_expression(p);if(token=LT|token=LTE|token=RT|token=RTE|token=ASSIGN|token=NE|token=EQ)/token”TreeNode*p=newExpNode(OpK);if(p!=NULL)p-child0=t;p-attr.op=token;t=p;match(token);t-c

42、hild1=additive_expression(NULL);return t;TreeNode *additive_expression(TreeNode* p)TreeNode*t=term(p);while(token=PLUS)|(token=MINUS)TreeNode*p=newExpNode(OpK);if(p!=NULL)p-child0=t;p-attr.op=token;t=p;match(token);p-child1=term(NULL);return t;TreeNode *term(TreeNode* p) TreeNode*t=NULL;if(p = NULL)

43、 t=factor();else t=p;while(token=TIMES)|(token=OVER)TreeNode*p=newExpNode(OpK);if(p!=NULL)p-child0=t;p-attr.op=token;t=p;match(token);p-child1=factor();return t;TreeNode *factor()TreeNode*t=NULL;char*s=NULL;switch(token)case(LPAREN):match(LPAREN);t=expression();match(RPAREN);break;case(ID):s=copyStr

44、ing(tokenString);match(ID);if(token=LZ)t=newExpNode(ArryK);match(LZ);TreeNode*p=expression();t-child0=p;t-attr.name=copyString(s);match(RZ);else if(token=LPAREN)t=newExpNode(CallK);match(LPAREN);t-attr.name=copyString(s);t-child0=expression();match(RPAREN);elset=newExpNode(IdK);t-attr.name=copyStrin

45、g(s);break;case(NUM):t=newExpNode(ConstK);if(token!=NULL)t-attr.val=atoi(tokenString);match(NUM);break;default:break;return t;TreeNode *args()TreeNode*t=NULL;if(token=RPAREN)t=NULL;elset=arg_list();return t;TreeNode *arg_list() treeNode*t=NULL;t=expression();TreeNode*p=t;while(token!=RPAREN)match(CO

46、MMA);TreeNode*q=expression();p-sibling=q;p=q;return t;TreeNode *parse()TreeNode*t=NULL;token=getToken();t=declaration_list();if(token!=ENDFILE)syntaxError(Code ends before filen);return t;五、测试结果 测试小程序:输出结果:实验结果分析:程序成功地打印出了测试文件内容的分析树。程序分析正确,运行成功.五、小结 通过此次实验,我掌握了用递归下降的方法实现c-语言的语法分析,其主要思想是:遇到终结符token进行

47、匹配,否则调用相对应的函数。仔细分析文法,构造出文法的结构,这是编码的基础也是关键。课程设计总结 本次编译原理课程设计,运用C/C+语言,分别从lex构造词法分析,手工构造词法分析,手工构造语法分析三个部分实现了一个C语言语法分析器。主要涉及到类和结构体的运用。通过本次实验,更加熟悉了VC编程,掌握了构造编译程序中使用的递归下降、LEX等方法。在努力完成本次试验的过程中,巩固了平时课上所学内容,我更加清楚了递归下降原理及实现过程。将理论与实际应用结合起来,锻炼了动手能力,也为以后的学习和实践打下了基础。 由于每一个细节都需要自己去仔细钻研,所以提高了自己编程序的能力。同时,虚心学习也是非常重要的,很多不会不理解的地方和同学探讨之后,听了别人的观点,就有了新的认识。 另外选取合适的数据结构是程序设计中非常重要的一项工作。正确合理的数据结构不仅能够简化程序设计的复杂度,还能适应程序需求变化。 总之,本课程设计不仅锻炼了我编程能力,增加了我对程序设计的兴趣.专心-专注-专业

展开阅读全文
温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

copyright@ 2023-2025  zhuangpeitu.com 装配图网版权所有   联系电话:18123376007

备案号:ICP2024067431-1 川公网安备51140202000466号


本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!