编译原理词法分析器语法分析课程设计

1、编译原理课程设计院 系 信息科学与技术学院专 业年 级2011 级学 号姓 名西南交通大学信息科学与技术学院2013年12月目录课程设计 1词法分析器 2.1.1 设计题目 2.1.2 设计内容 2.1.3 设计目的 2.1.4 设计环境 2.1.5 需求分析 2.1.6 概要设计 2.1.7 详细设计 4.1.8 编程调试 5.1.9 测试 0 结束语 1.3.课程设计 2赋值语句的解释程序设计 1.42.1 设计题目 设计内容 设计目的 设计环境 需求分析 概要设计 详细设计 1.

2、6.2.8 编程调试 测试 0 结束语 2.5.课程设计一 词法分析器设计一、设计题目手工设计c语言的词法分析器（可以是 c语言的子集）。二、设计内容处理 c 语言源程序，过滤掉无用符号，判断源程序中单词的合法性，并分解出正确 的单词，以二元组形式存放在文件中。三、设计目的了解高级语言单词的分类， 了解状态图以及如何表示并识别单词规则， 掌握状态图到 识别程序的编程。四、设计环境该课程设计包括的硬件和软件条件如下：4.1. 硬件（ 1 ） Intel Core Duo CPU P8700（ 2 ）内存 4G4.2. 软件（ 1 ） Window 7 32 位操作系

3、统（ 2 ） Microsoft Visual Studio c# 开发平台4.3. 编程语言C#语言五、需求分析5.1. 源程序的预处理 ：源程序中，存在许多编辑用的符号，他们对程序逻辑功能无任何 影响。例如：回车，换行，多余空白符，注释行等。在词法分析之前，首先要先剔除掉这些 符号，使得词法分析更为简单。5.2. 单词符号的识别并判断单词的合法性 ：将每个单词符号进行不同类别的划分。单词 符号可以划分成 5 中。（1）标识符：用户自己定义的名字，常量名，变量名和过程名。（2）常数：各种类型的常数。（3）保留字（关键字） ：如 if 、 else、 while 、 int 、 float 等

4、。（4）运算符：如 +、-、*、 、=等。（5）界符：如逗号、分号、括号等。5.3. 将所有合法的单词符号转化为便于计算机处理的二元组形式：（单词分类号， 单词自身值）；以图形化界面显示出来。5.4. 可选择性地将结果保存到文件中 。六、概要设计6.1数据类型6.1.1. 单词的分类：本词法分析器演示的是C 语言的一个子集，故字符集如下：(1) 标识符：以字母开头的字母数字串。(2) 整数或浮点型(3) 保留字： auto, break, case, char, con st, continue, default, do, double, else, enum, extern, float,

5、for, goto, if, int, long, register, return, short, signed, sizeof, static, struct, switch, typedef, union, un sig ned, void, volatile, while运算符：+、-、*、/、=、!=、=、=、=、+、-、!、&、&&、I； (5)界符: ( ) : ;“# ,6.1.2. 单词二元组：(单词分类号，单词自身值)表6.1单词分类表单词分类号标识符1常数2保留字3界符4运算符56.2. 词法分析器的结构图6.1词法分析器的结构6.3. 部分单词的

6、正规式与状态转换图字母数字其它非*其它图6.2部分单词的状态转换图6.4. 功能模块表6.2 词法分析器的C#程序过程或函数功能表过程或函数名简要功能说明GetToke ns()分析源程序得到单个单词并大致区分其 类型，并生成二元组Getlnput( string get )输入源程序NoWs( stri ng aCopy, int cp )去除源程序中的空格符GetToke nType最终确定标识符和保留字OutPut输出二元组到指定的.txt文件中GetResult输出二元组七、详细设计7.1. 总体流程图图7.1程序总体流程图7.2 .主要分支选择算法介绍情况算法开始八、编程调试8.1主

7、要源代码 /逻辑操作类与函数 using System;using System.Collect ion s.Ge neric; using System.Text;using Syste m.IO;n amespace Toke nAn alysis struct Toke nN ode public stri ng type; public stri ng toke n;class Toke nAn alysis int cPositi on = 0; int lPositi on = 0; int ignorWs = 0; int recordWs = 1;output;stri ng

8、source;string kwList = "auto", "break", "case", "char", "const", "continue", "default","do", "double", "else","enum", "extern", "float", "for", "goto"

9、, "if", "int", "Iong", "register","return", "short", "signed", "sizeof", "static", "struct", "switch", "typedef", "union", "unsigned", "void", "v

10、olatile", "while","printf","scanf","end","main"int Error = -2;int Normal = -1;int statue = -1;bool isComme nt = false;List<Toke nN ode> resultToke nN odes = new List<Toke nN ode>(); public List<Toke nN ode> GetToke ns() Toke nN

11、 ode no de2Add = new Toke nN ode();int cp = 0;/curre nt positi onint lp = 0;/lastpositi onstri ng aCopy = source;int len gth = aCopy.Le ngth;aCopy = aCopy.Trim();while( cp < aCopy.Le ngth ) /ID or Keywordsno de2Add = this.GetToke n( ignorWs, aCopy, ref cp, ref lp );if( n ode2Add.type = "cmtL

12、eft" ) isComme nt = true;if( n ode2Add.type = "cmtRight" ) isComme nt = false;if( !isComment && node2Add.type != "cmtRight" ) resultToke nN odes.Add( node2Add );retur n resultToke nN odes;public Toke nN ode GetToke n() if( cPositi on < source.Le ngth ) Toke nN ode

13、 toke n = this.GetToke n( ignorWs, source, ref cPositi on, ref lPosition );return toke n;else Toke nN ode toke n = new Toke nN ode();toke n.toke n = "Error" return toke n;一private Toke nN ode GetToke n( int type, stri ng aCopy, ref int cp, ref int lp ) Toke nN ode toke n = new Toke nN ode(

14、);stri ng tempToke n;stri ng tempType;if( type = ignorWs ) if( Char.IsLetter( aCopy cp ) ) cp+;while( cp < aCopy.Le ngth &&(Char.lsLetterOrDigit( aCopy cp ) |aCopy cp = '_' ) ) cp+;tempToke n = aCopy.Substri ng( lp, cp - lp );tempType = "1 or 3"tempType = GetToke nType(

15、tempToke n, tempType );toke n.toke n = tempToke n;toke n. type = tempType;Ip = cp = NoWs( aCopy, cp );/Numelse if( Char.lsDigit( aCopy cp ) ) cp+;while( cp < aCopy.Length && ( Char.IsDigit( aCopy cp ) ) | (aCopy cp = '.' && Char.IsDigit( aCopy cp + 1 ) ) ) ) cp+; I tempTok

16、e n = aCopy.Substri ng( Ip, cp - Ip ); tempType = "2"toke n.toke n = tempToke n;toke n. type = tempType;Ip = cp = NoWs( aCopy, cp );/Borderelse if( aCopy cp ='('II aCopy cp =')'II aCopy cp ='' IIaCopy cp ='' | aCopy cp =''| aCopy cp =''IIaCop

17、y cp =','II aCopy cp =''II aCopy cp ='"'II aCop)/ cp =''' | aCopy cp =' ) cp+;tempToke n = aCopy.Substri ng( Ip, cp - Ip ); tempType = "4"toke n.toke n = tempToke n;toke n. type = tempType;Ip = cp = NoWs( aCopy, cp );/Operati on and otherelse if

18、( cp < aCopy.Le ngth ) cp+;switch( aCopy cp - 1 ) case '+':cp = NoWs( aCopy, cp );if( aCopy cp = '=' | aCopy cp = '+' ) 一cp+;break;case '-':cp = NoWs( aCopy, cp );if( aCopy cp = '=' | aCopy cp = '-' | aCopy cp = '>' ) cp+;break;cp = NoWs(

19、 aCopy, cp ); if( aCopy cp = '=' | aCopy cp = '/' ) cp+;break;case '/':cp = NoWs( aCopy, cp );if( aCopy cp = '=' | aCopy cp = '*' ) cp+;break;case '=':cp = NoWs( aCopy, cp );if( aCopy cp = '=' ) cp+;break;case '>':cp = NoWs( aCopy, c

20、p );if( aCopy cp = '=' ) cp+;break;case '<':cp = NoWs( aCopy, cp );if( aCopy cp = '=' ) cp+;break;case '!':cp = NoWs( aCopy, cp );if( aCopy cp = '=' ) cp+;else statue = Error;break;case T：cp = NoWs( aCopy, cp );if( aCopy cp = '|' ) 一cp+;else statue

21、= Error;break;case '&':cp = NoWs( aCopy, cp );if( aCopy cp = & ) break;default:statue = Error;break;tempToke n = aCopy.Substri ng( lp, cp - lp ); tempToke n = tempToke n.Replace(” ",""); tempType = "5"tempType = GetToke nType( tempToke n, tempType ); toke n.t

22、oke n = tempToke n;toke n. type = tempType;Ip = cp = NoWs( aCopy, cp ); return toke n;public void Get In put( stri ng get ) /source = "for( int i = 0; i < array -> len gth; i+ ) /* cmt */" source = get;private int NoWs( string aCopy, int cp ) if( cp < aCopy.Le ngth ) while( Char.l

23、sWhiteSpace( aCopy cp ) ) cp+;return cp;private stri ng GetToke nType( stri ng tk2a nls, stri ng ini Type ) if( ini Type = "1 or 3" ) foreach( stri ng kw in kwList ) if( tk2a nls = kw ) return "3" return "1"if( ini Type = "5") if( tk2a nls = "/*" ) r

24、eturn "cmtLeft"if( tk2a nls = "*/" ) return "cmtRight" -retur n ini Type;retur n "Unknown Tpye"public void OutPut( stri ng) outFile = new ();StreamWriter fw = out();foreach( Toke nN ode tkNode in resultToke nN odes ) stri ng show = stri ng.Format( "0,-251

25、,-40", tkNode.toke n, tkNode.type );System.C on sole.WriteLi ne( show ); fw.WriteL ine( show ); fw.Close(); Ipublic void OutPut() outFile = new ( "result.txt");StreamWriter fw = out();foreach( Toke nN ode tkNode in resultToke nN odes ) stri ng show = stri ng.Format( "0,-251,-40&q

26、uot;, tkNode.toke n, tkNode.type );System.C on sole.WriteLi ne( show );fw.WriteL ine( show );fw.Close();public List<string> GetResult() List<string> res = new List<string>();foreach( Toke nN ode tkNode in resultToke nN odes ) stri ng show = stri ng.Format( "0,-251,-40", t

27、kNode.toke n, tkNode.type );res.Add( show );return res;/前台控制类与函数n amespace Toke nAn alysis_FormApp -public partial class Form1 : Formpublic Form1()In itializeComp onen t(); private void btnAn alysis_Click(object sen der, Even tArgs e) -Toke nAn alysis.Toke nAn alysis ta = new Toke nAn alysis.Toke nA

28、n alysis(); ta.GetI nput(rtxtI nput.Text);ta.GetToke ns();List< string > res = ta.GetResult();lstResult.Items.Clear();IstResult.ltems.AddRa nge(res.ToArray();private void btn Exit_Click(object sen der, Eve ntArgs e) -Applicatio n.Exit();private void 保存 SToolStripButton_Click(object sender, Eve

29、ntArgs e) -save ="保存分析结果"save ="文本文件 |*.txt"if( ( save() ) = DialogResult.OK ) if( save. != n ull ) outFile = new ( save );StreamWriter fw = out();foreach( string tkString in lstResult.Items ) fw.WriteLi ne( tkStri ng );fw.Close();private void btn save_Click(object sen der, Even

30、tArgs e) -save ="保存分析结果" save ="文本文件 |*.txt"if (save() = DialogResult.OK)if (save != n ull)outFile = new (save); StreamWriter fw = out(); foreach (string tkString in IstResult.ltems) fw.WriteLi ne(tkStri ng); fw.Close();8.2调试调试过程中存在保存不了输出结果的问题。最后调试发现是由于绝对路径与相对路径 的区分。最后上网搜索解决方法，通过

31、调用C#中提供的文件保存接口来解决保存的问题九、测试1.运行的主界面图9.1运行的主界面2.输入想要分析的c语言源程序-*轴入c语右程序：词法術|分析后的二扌vcm fnaino inta-10(.b-2(Q;iwa*t»a 1sta=a"t>printfCt.ci%(raPbJ;|图9.2输入源程序3点击分析的按钮，显示分析后的结果，以二元组形式展示图9.3分析结果4.点击保存按钮，弹出选择保存文件的路径和名称图9.4保存过程5.保存后的.txt文档科 £ 论 0 BAMVjLtMl -图9.5保存后的文档f-if b 一 a斗 b十、结束语通过这次的课程

32、设计， 我学会了很多。让我学会了如何设计、 编制并调试词法分析程序， 加深对词法分析原理的理解；熟悉了构造词法分析器的手工方式的相关原理，也对状态图以及如何表示并识别单词规则有了更进一步的了解。并且在掌握状态图对识别程序的编程上有了更深层次的进步。除此之外，还复习了高级语言单词的分类，总之，通过这次的实验，从 各方面提高了我的编程能力以及解决问题和bug的能力。但此次的课程设计还存在一定的缺陷，如只实现了 c语言子集的词法分析器以及，对于错误的单词无法识别出其错误原因。因此，我在今后的学习中还需要再接再厉，争取编出更完美的程序。课程设计二赋值语句的解释程序设计一、设计题目手工设计c语言的赋值语

33、句解释程序（可以是c语言的子集）二、设计内容2.1. 要求用算符优先分析方法设计一个分析程序，对输入的赋值语句，输出语句，清除语句进行词法分析、语法分析、表达求值并存储于指定变量中；若存在错误，提示错误相关信息。2.2. 给定文法S->V=E|E?|clearE->E+T|E-T|TT->T*F|T/F|FF->（E）|V|cV->i2.3. 给定单词种别码表1单词种别码表单词种别码单词种别码=1?2+3-4*5/6(7)8v9c10clear11#12N132.4. 测试数据a=5b=a+10b?b+a*a?a=a+10三、设计目的1.了解掌握算符优先分析的基本

34、方法；2理解并处理语法分析中的异常和错误3学会科学思考并解决问题，提高程序设计能力四、设计环境该课程设计包括的硬件和软件条件如下：4.1.硬件（1）In tel Core Duo CPU P8700（2）内存4G42软件(1) Window 7 32位操作系统(2) Microsoft Visual Studio c# 开发平台4.3.编程语言C#语言五、需求分析5.1数据分析数据输入(1)文法，即定义的语法单位，在进行语法分析时语句的规约必须遵循该文法定义。算数表达式，如 a=5、b=a+10、b ？数据输出(1) 四元式语法分析器所输出的分析结果用如下的四元式表示：(操作符，操作数 1,操

35、作数2，结果)其中，操作符为文法定义中的=，？， +，-，*，/，(,)中的一个。(2) 算符优先关系表。表2算符优先关系表=?+-*/()v#=?+>><<<><>->><<<><>*>>><><>/ 1>>><><>(1<<<<=<)>>>>>i>>>>>#<<<<<=(3) 变量表，包括变量的

36、名称以及属性值。(4) 赋值表达式的结果输出。(5 )错误提示若语法分析失败，则提示相应的错误信息。包括：输入错误；变量不存在或已清除；输入非法字符等。5.2功能分析本课程设计的赋值语句解释器能实现的功能如下(1) 从外部输入或导入文法规则和测试的赋值语句、输出语句，清除语句(2) 对文法规则、赋值语句、输出语句以及清除语句进行词法分析(3) 计算每个非终结符的 FIRSTVT和LASTVT，以及他们的算符优先关系表。(4) 在内存中申请一段空间，称为变量表，用于存放变量及其赋值，并按照声明次序 给变量添加索引。(5) 把输入的符号一个一个地移进栈里，当栈顶形成某个产生式的一个候选式时，把栈顶

37、的这一部分归约为该产生式的左部符号，重复这一过程直到归约栈中只剩下 文法开始的符号。其中，可归约串包括变量归约、常量归约、运算归约、括号归 约、赋值语句、输出语句、清除语句六、概要设计本程序主要分为四个模块，由主函数模块来调用输入串模块，归约栈模块，变量表模块。其中，各模块的功能说明如下表所示表3语法分析器的C#1序过程和函数功能表模块名简要功能说明输入控制模块判断输入是否合法，并返回相应结果的功能归约过程控制模块判断是否形成一个产生式，并将表达式归约变量表存储模块r存储已声明的关键字和变量，定义了查找变量，清除变 量等一系列函数主函数模块调用各个子模块，完成整体的语句解释程序流程七、详细设计

38、7.1输入控制模块static int in_in dex;inuct *temp_ip;char instr40;void in_ini t(char *in)-in_in dex = 0;strcpy(i nstr, i n);inu ct* i n_get_uct()-int in_le ngth = 0;char *in put = (char *)malloc(sizeof(char);while(is_space() in_in dex+;-if(is_e nd() return NULL;if(is_error_char() temp_ip = (inuct *)malloc(s

39、izeof( inu ct);temp_ip->type = INPUT_ERROR;temp_ip->value.strv = (char *)malloc(sizeof(char) * 11); memcpy(temp_ip->value.strv, &in stri n_in dex, sizeof(char); return temp_ip; -if(is_char() while(is_char() | is_num() inputin_length+ = instrin_index; in_index +;input = (char *)realloc(i

40、nput, sizeof(char) * (in_length + 1); inputin_length = '0'if(in_length) temp_ip = (inuct *)malloc(sizeof(inuct); if(strcmp(input, "clear0") = 0) temp_ip->type = CLEAR; return temp_ip;else if(strcmp(input, "quit") = 0) temp_ip->type = QUIT; return temp_ip; else temp_

41、ip->type = V AR; temp_ip->value.strv = (char *)malloc(sizeof(char) * (in_length + 1); strcpy(temp_ip->value.strv, input); return temp_ip; while(is_num() inputin_length+ = instrin_index; in_index +;input = (char *)realloc(input, sizeof(char) * (in_length + 1); inputin_length = '0'if(

42、in_length) temp_ip = (inuct *)malloc(sizeof(inuct); temp_ip->type = CONST; temp_ip->v = atoi(input);return temp_ip; if(is_leftbra() temp_ip = (inuct *)malloc(sizeof(inuct); temp_ip->type = LEFTBRA; temp_ip->value.strv = (char *)malloc(sizeof(char); strcpy(temp_ip->value.strv,

43、 "("); in_index+;return temp_ip;if(is_rightbra() temp_ip = (inuct *)malloc(sizeof(inuct); temp_ip->type = RIGHTBRA;temp_ip->value.strv = (char *)malloc(sizeof(char); strcpy(temp_ip->value.strv, ")");in_index+;return temp_ip;if(is_oper() | is_printsign() temp_ip = (inuct

44、*)malloc(sizeof(inuct); if(instrin_index = '+') temp_ip->type = ADD_OPER; else if(instrin_index = '-') temp_ip->type = SUB_OPER; else if(instrin_index = '*') temp_ip->type = MULT_OPER; else if(instrin_index = '/') temp_ip->type = DIV_OPER; else if(instrin_

45、index = '=') temp_ip->type = ASSIGN_OPER; else temp_ip->type = PRINTSIGN;temp_ip->value.strv = (char *)malloc(sizeof(char); temp_ip->value.strv0 = instrin_index+;return temp_ip;status is_error_char()return !(is_num() | is_char() | is_oper() | is_end() | is_leftbra() | is_rightbra

46、() | is_printsign();status is_num()if(instrin_index >= '0' && instrin_index <= '9') return YES;return NO;status is_char()if(instrin_index >= 65 && instrin_index <= 90 | instrin_index >= 97 && instrin_index <= 122 | instrin_index = '_'

47、)return YES;return NO;/ is_'+-*/%='status is_oper()if(instrin_index = '+' | instrin_index = '-' | instrin_index = '*' | instrin_index = '/' | instrin_index = '%' | instrin_index = '=') return YES;return NO;/ is_'('status is_leftbra() re

48、turn instrin_index= '(' ?YES:NO;/ is_')'status is_rightbra() return instrin_index= ')' ?YES:NO; / is_0 status is_end()return instrin_index = 0 ?YES: NO;/ is_?status is_printsign()return instrin_index = '?'?YES:NO;/is_spacestatus is_space()return instrin_index = 32?YES

49、:NO;7.2 归约过程控制模块 #define STACK_LENGTH 40 static int operlevel14; static inuct inuctstack1STACK_LENGTH; static inuct inuctstack2STACK_LENGTH; int now_oper_level ;int pop_index_1;int pop_index_2;int shift_index;void instack_init()operlevelLEFTBRA = 0; operlevelMULT_OPER = 1; operlevelDIV_OPER = 1; ope

50、rlevelADD_OPER = 2; operlevelSUB_OPER = 2; operlevelRIGHTBRA = 3; operlevelPRINTSIGN = 4; operlevelASSIGN_OPER = 5; operlevelEND_OPER = 6; pop_index_1 = 0; pop_index_2 = 0; shift_index = 0;now_oper_level = 6;void push(inuct *ip, int which)if(which = 1) memcpy(&inuctstack1pop_index_1+, ip, sizeof

51、(*ip);else memcpy(&inuctstack2pop_index_2+, ip, sizeof(*ip);void error_print(char *lang)printf("syntax wrong:%5sn", lang);/ 1 means ok , 0 means something wrongint valid(inuct *ip)int index ;inuct *bip;index = pop_index_1; if(index != 0) bip = &inuctstack1pop_index_1 -1;switch(ip-&

52、gt;type)case ASSIGN_OPER:if(index = 0 | bip->type != V AR) error_print(ip->value.strv);return 0;break;case ADD_OPER:case SUB_OPER: case MULT_OPER: case DIV_OPER: case RIGHTBRA:!=if(index = 0 | (bip->type != VAR && bip->type != CONST && bip->type RIGHTBRA) error_print(i

53、p->value.strv);return 0;break;case LEFTBRA:if(index != 0 && (bip->type = VAR | bip->type = CONST | bip->type RIGHTBRA) error_print(ip->value.strv);return 0;break;case VAR:case CONST:if(index != 0 && bip->type = RIGHTBRA) error_print(ip->value.strv);return 0;break

54、;case END_OPER:if(index != 0 && (bip->type = ADD_OPER | bip->type = SUB_OPER | bip->type = MULT_OPER | bip->type = DIV_OPER | bip->type = ASSIGN_OPER | bip->type = LEFTBRA) | index = 0) printf("illegal endn");return 0;break;case PRINTSIGN:if(index != 0 &&

55、(bip->type = ADD_OPER | bip->type = SUB_OPER | bip->type = MULT_OPER | bip->type = DIV_OPER | bip->type = ASSIGN_OPER | bip->type = LEFTBRA) | index = 0) error_print(ip->value.strv);return 0;break;default:break;return 1; int input_stack_push(inuct *ip) if(valid(ip) = 0)return 0;

56、push(ip, 1);return 1;int add_endoper()inuct *ip = (inuct *)malloc(sizeof(inuct); ip->type = END_OPER;ip->value.strv = (char *)malloc(sizeof(char); strcpy(ip->value.strv, "#");return input_stack_push(ip);void res_stack_push(inuct *ip)push(ip, 2);void add_beginoper()inuct *ip = (inuct *)malloc(sizeof(inuct); ip->type = END_OPER;ip->value.strv = (char *)malloc(sizeof(char); strcpy(ip->value.strv, "#");res_stack_push(ip); inuct* pop(int which) inuct *i