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

《编译原理课程设计(共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等方法。在努力完成本次试验的过程中，巩固了平时课上所学内容，我更加清楚了递归下降原理及实现过程。将理论与实际应用结合起来，锻炼了动手能力，也为以后的学习和实践打下了基础。 由于每一个细节都需要自己去仔细钻研，所以提高了自己编程序的能力。同时，虚心学习也是非常重要的，很多不会不理解的地方和同学探讨之后，听了别人的观点，就有了新的认识。 另外选取合适的数据结构是程序设计中非常重要的一项工作。正确合理的数据结构不仅能够简化程序设计的复杂度，还能适应程序需求变化。 总之，本课程设计不仅锻炼了我编程能力，增加了我对程序设计的兴趣.专心-专注-专业