基于SNL语言编译器的面向对象开发.doc

“基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2010 基于 SNL 语言编译器的面向对象开发 文件标识：文件标识：基于 SNL 语言编译器的面向对象开发 当前版本：当前版本： 1.0.0.0 作作 者：者： 文件状态： 草稿 正式发布 正在修改 完成日期：完成日期： 2010.6.20 “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2010 庄琨、戴雨达、冉启 蕾 开发流程 参与者参与者起止日期起止日期备注备注 2010.03 - 2010.04 词法分析阶段 2010.04 - 2010.05 语法分析阶段 2010.05 - 2010.06 语义分析阶段 2010.06 - 2010.06 编译器测试 “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008i 目目目 录录录 一一. . 文档介绍文档介绍 .1 1 1.1 文档目的.1 1.2 文档范围.1 1.3 读者对象.1 1.4 参考文献.1 二二. . 开发环境及运行环境说明开发环境及运行环境说明 .2 2 三三. . 需求分析需求分析 .2 2 3.1 总体需求.2 3.1.1 编译器界面要求.2 3.1.2 编译器功能要求.2 3.2 系统总体功能设计.3 3.2.1 编译程序的组成 .3 3.2.2 对源语言 SNL 的分析 .3 3.2.3 基于 SNL 语言编译器的实现 .4 3.2.4 各模块的概要设计 .4 四四. . 详细设计详细设计 .5 5 4.1 词法分析模块.5 4.2 语法分析模块.8 4.3语义分析模块.10 五五. . 面向对象面向对象 UMLUML 设计设计 .1414 5.15.1 SNLSNL 编译器用例图编译器用例图.1414 5.25.2 SNLSNL 编译器类图编译器类图.1414 5.35.3 SNLSNL 编译器状态图编译器状态图.1616 5.45.4 SNLSNL 编译器时序图编译器时序图.1616 5.55.5 SNLSNL 编译器活动图编译器活动图.1717 5.65.6 SNLSNL 编译器协作图编译器协作图.1919 5.75.7 SNLSNL 编译器包图编译器包图.1919 六六. . SNLSNL 编译器测试编译器测试.1919 6.16.1 单元测试单元测试 .1919 6.1.1 模块间调用测试.19 6.1.2 主要类调用测试.19 “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008ii 6.1.3 接口函数测试.20 6.1.4 界面测试.20 6.26.2 功能测试功能测试 .2121 6.2.1 等价类表.21 6.2.2 测试用例.21 7.7. 小组开发心得小组开发心得 .2222 “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008Page 1 of 25 一. 文档介绍 1.1 文档目的 本文档主要对基于 SNL 语言的面向对象开发过程中词法分析、语法分析、语义分析中的 类设计、接口设计、界面设计、编码等做出了统一的规定，同时给出了面向对象设计的完整 过程。它是开发人员，测试人员编码及测试的重要参考依据。 1.2 文档范围 本文档包含以下几个部分： 1. 文档介绍 2. 开发环境及运行环境说明 3. 需求分析 4. 详细设计 5. 面向对象 UML 设计 6SNL 编译器测试 7小组开发心得 1.3 读者对象 本文档的主要读者包括： 1. SNL 编译器的设计人员：包括模块设计人员 2. SNL 编译器的系统开发人员：包括编码人员 3. SNL 编译器的测试人员 1.4 参考文献 1 刘磊，金英，张晶，张荷花.编译程序的设计与实现M.北京：高等教育出版 社，2004 2 金成植.编译原理与实现M.北京：高等教育出版社，2004 “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008Page 2 of 25 二. 开发环境及运行环境说明 开发语言：C+ 界面制作：MFC 开发平台：VS 2008 面向对象 UML 设计工具：PowerDesigner12.5 版本控制：SVN 文件生成工具：JartoExe 单元测试工具：Junit3.8 三. 需求分析 3.1 总体需求 经过调研及小组讨论“SNL 编译器”的用户需求有两方面，分别为界面要求及功能要求。 3.1.1 编译器界面要求 “SNl 编译器”的窗口界面分为三部分；最上部分为菜单栏，包括文件、单步执行、小 组信息等三个按钮，其中文件按钮细分为打开、保存、关闭；单步执行按钮细分为词法分析， 语法分析。中间部分为程序显示，最下面为进行词法和语法分析后的结果显示。 3.1.2 编译器功能要求 从菜单栏中点击单步执行中的词法分析时显示词法分析结果，点击语法分析时显示语法 树，如果程序有错则可以显示错误信息，点击语义分析，显示语义分析结果。 “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008Page 3 of 25 3.2 系统总体功能设计 3.2.1 编译程序的组成 编译程序通常包括：词法分析、语法分析、语义分析、中间代码生成、中间代码优化、 目标代码生成。如图 1 所示。由于时间有限，本编译器只做前三部分。 SNL 源程序 词 法 分 析 程序 语 法 分 析 程序 语 义 分 析 程序 出 错 处 理 目 标 代 码 生 成 SNL 目 标程序 表 格 处 理 中 间 代 码 生 成 中 间 代 码 优 化 图 3.2 带优化的 SNL 编译程序功能结构图 图 1 3.2.2 对源语言 SNL 的分析 词法： 1 SNL 语言的字符表:=a-z|A-Z|0-9|+|-|*|/|=|(| )| |.|;|EOF|空白字符| | 2. 单词的巴克斯范式 :=字母 字母 | 数字 :=数字 数字 := + | - | *| / | ( | ) | | | ; | . | | = | EOF | 空白字符 :=: = := := “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008Page 4 of 25 := :=. := a-z|A-Z := 0-9 语法： 1. 程序头的形式是：关键字 program 后面跟着程序名标识符； 2. 类型定义的形式是：类型名称标识符=类型定义 3. 变量声明形式是：类型名后面跟着能够逗号隔开的变量标识符序列 4. 过程声明的形式是：关键字 procedure 跟着过程名标识符以及参数声明、类型定义、 变量说明、内层 5. 程序体的形式是：以关键字 begin 开始，关键字 end 结尾，中间是用分号隔开的语 句序列。如果是主程序，则在 end 后用“. ”标志整个程序体结束 语义： 1、 构造符号表和信息表 2、 进行语义错误检查 3.2.3 基于 SNL 语言编译器的实现 词法分析，以源程序为输入，生成单词的内部表示 TOKEN 序列 语法分析，以 TOKEN 序列为输入进行语法分析，采用了 LL1 方法生成整个源程序的语法 分析树。 语义分析，输入为一棵语法正确的语法分析树，遍历这棵语法分析树，构造符号表和信 息表，并进行语义错误检查，生成一棵语义正确的语法树。 3.2.4 各模块的概要设计 词法分析模块： “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008Page 5 of 25 根据源语言的词法规则，扫描源程序的字母（ASCII 码）序列，并识别出一个一个具有 独立意义的最小语法单位，即“单词” ，同时确定该单词的种类（如标识符，或界限符，或 常数，等等） ，并把每个单词的 ASCII 码序列替换为统一的标准形式所谓的机内表示 TOKEN 形式，同时词法分析还要完成词法错误的检查以及去掉注释、空格、制表符等。词法 分析阶段不依赖于语言的语法定义。 语法分析模块： 根据源语言的语法规则，逐一地扫描词法分析后的 TOKEN 序列，以确定源程序的具体组 成结构（语法结构） 。分析时如发现有不符合语法规则的地方，则打印出错位置，以便程序 员进行修改；如果未发现语法错误，则将源程序转换成能够表示程序结构的语法树的形式。 语义分析模块： 遍历语法分析的结果语法分析树的各个结点，对于声明部分的各个结点，构造符号表和 信息表，利用局部符号表栈的存储原理，进行判定是否重复声明错误。对于程序体部分的各 个节点，判定是否语义错误，如果错误，则输出错误，如果没有错误，则输出符号表。 四四. . 详细设计详细设计 4.1 词法分析模块 1. 任务目标：以源程序输入，生成单词的内部表示 TOKEN 序列 2. 词法分析程序的输入处理 缓冲区：使用 1 个字符串作为缓冲区。 3. SNL 语言词法的形式化描述 DFA 如图 2 所示。 “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008Page 6 of 25 Start End L 标识符 状态 数字状 态 Other D 完成状 态 Other + +| |- -| |* *| |/ /| | | |= =| |( (| |) )| | | | | |; ;| |E EO OF F| |空空格格 L|D D 赋值状态 = = ： 注释开 始 Other Other数组下标 . . 字符状态 . . Other Other 程序结束状态 其他符号 出错 L|D 字符状态 Other 其他出错 其他字符 出错 L|D 注释结 束 其他字符 其他字符 图 2 “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008Page 7 of 25 4. DFA 的实现 运用直接转向法，又称程序中心法，把状态转换图看成一个流程图，从状态转换图的初 态开始，对它的每一个状态节点都编一段相应的程序。 5. Token 的数据结构定义如下 class Token int t_LineNum; TokenType t_TokenType; string t_TokenSeman; 6. Token 链表 class TokenList list m_tokens; list:iterator m_tokensIterator; 7 词法分析程序的输出（要求在显示器上输出 token） 词法分析程序读入字符串形式的源程序，识别出具有独立意义的最小语法单位单词， 并将单词序列变换成表明单词性质的 TOKEN 序列。 SNL 词法分析对于每类单词的分析结果的 TOKEN 结构为三元组（词法信息，语义信息以 及该单词在源程序中的行号） 。SNL 词法分析程序的输出是 TOKEN 序列。数据表示为链表形式。 8. 程序实现： 输入：字符串形式的 SNL 源程序 输出：表明单词性质的 TOKEN 序列 实现过程的主要函数如下： void Initial(string filename);/初始化函数 void LexAnalyze();/词法分析的主要分析函数 bool isLetter (char ch);/标识符 bool isDigit (char ch);/数字 bool isSymbol (char ch);/分界符 Status GotoStatus(char ch);/转向状态 int reservedLookup(const char *ch);/查找是否在保留字表中 TokenList getTokenList();/返回tokenlist void PrintResult();/返回最后结果，包括 tokenlist 和 errorlist 状态对照 START:开始状态 DONE:完成状态，输出其内部的单词标志码 INASSIGN:赋值状态，如果读入下一个不是“=” ，则识别为冒号 INCOMMENT:注释状态，不生成单词 ungetNextChar()reservedLookup()Copy() “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008Page 8 of 25 INNUM:数字状态，识别并组合数字 INID:标识符状态，确定是保留字还是自定义的标识符 INCHAR:字符标志状态 INRANGE:数组下标界限状态，如果下一个字符不是“. .” ，则为程序结束标志；否则为数组下 标界限标志 9. 分析错误类型： 赋值语句少输入了“=” ； 没有注释结尾符错误； 无法识别的字符错误； 4.2 语法分析模块 1. 任务目标：根据语言的的语法规则，对原程序进行语法检查，并识别出相应的语法成分。 2. 程序实现： 输入：从词法分析器输出的源程序的 TOKEN 序列形式 输出：无语法错误的语法成分，表示成语法树的形式 语法分析部分说明如图 3 所示。 . TypeKPheadKStmLK K Prock ProK DecK . DecKDecK VarK DecKs 图 3 3. 语法分析部分采用 LL1 分析方法 构造 LL1 分析表举例如下： tableNProgramPROGRAM=1; tableProgramHeadPROGRAM=2; tableProgramNameIDENTIFIER=3; tableDeclarePartTYPE=4; tableDeclarePartVAR=4; tableDeclarePartPROCEDURE=4; tableDeclarePartBEGIN=4; “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008Page 9 of 25 tableTypeDecpartVAR=5; tableTypeDecpartPROCEDURE=5; tableTypeDecpartBEGIN=5; 4语法树节点的数据结构定义如下： class ParseNode string name; /节点名称 int value; /节点值对应的enum值 int linenum; ParseNode* child10; /节点孩子 int length; 5语法分析的主要处理类及函数实现： class parse private: stack parseStack; int table110110; int linenum; TokenList tokenlist; Token nowToken; ParseNode* chushiNode; ParseNode* nowNode; ErrorLog parseErrorlist; int parseErrorNum; public: void CreatLL1Table(); void parseInitial(string filename); void LL1parse(); void predict(int num); void process(int n, ParseNode *node); void process1();void process104(); void printParseTree(); void printTree(ParseNode *print_nownode); ParseNode* getParsetreeChushinode(); void printErrorList(); ErrorLog getparseErrorlist(); ; “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008Page 10 of 25 4.3语义分析模块 1任务目标：根据语义规则，对语法分析树进行语义检查，输出构建的符号表以及信息表， 若有语义错误，则输出语义错误。 2程序实现： 输入：从语法分析器输出的语法正确的语法分析树 输出：符号表和信息表以及语义错误 3符号表结构： 名字项名字项信息项信息项 NAME NAME_INFO 4信息项内部表示： 类型标识符： TypePtr kind typeKind 变量标识符 TypePtr kind Access Level Off varKind 过程标识符 TypePtr kind Level Parm Code Size 类型内部表示 Size kind MORM ArrayAttr indexTyelemTy boby 记录域表 idnameunitTypeoffsetnext 形参信息表 entrynext 5主要数据结构定义如下 class SymbTable list SymbList; list:iterator it; class SymbNode string idname; AttributeIR* attrIR; “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008Page 11 of 25 class AttributeIR TypeIR* idtype; / 指向标识符的类型的内部表示 IdKind kind; / 标识符的类型 union / 其中所有标识符都有公共部分,其他信息部分随标识符的不同而不 同 struct AccessKind access; int level;/表示该变量声名所在的主程序/过程的层数 int off;/表示该变量相对它所在主程序/过程的偏移量 VarAttr; struct int level;/表示过程层数 list* param;/参数列表 int code;/表示过程的目标代码地址(此部分在代码生成阶段 填写) int size;/表示过程所需的空间大小 ProcAttr; More; class TypeIR int size; / 类型所占空间大小 TypeKind kind; / 内部表示的类型 union struct TypeIR* indexTy;/指向数组下标的内部表示 TypeIR* elemTy;/指向数组元素的内部表示,即指向整数或字 符 TypeKind elemtypekind; ArrayAttr; list* body;/记录类型中的域链 More; “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008Page 12 of 25 6语义分析的主要实现类及函数 class Semantic private: ParseNode *chushi; ParseNode *nowparsenode; Scope semanticScope; SymbTable *nowsymbtable; SemanticErrorList semanticErrorlist; public: Semantic() SemanticErrorList geterrorlist() bool FindEntry(string id, SymbNode* Entry); bool SearchOneTable(string id, SymbTable* curSymbTable, SymbNode* Entry); void semanticInitial(string filename); void SemanticScanner(); void _Program(ParseNode *chushi); /处理声明 void _DeclarePart(ParseNode *ptr); void _TypeDecpart(ParseNode *ptr); void _TypeDecList(ParseNode *ptr); void _VarDecpart(ParseNode *ptr); void _VarDecList(ParseNode *ptr); void _VarIdList(ParseNode *ptr,TypeIR *typeir); void _ProcDecpart(ParseNode *ptr); void _ProcDec(ParseNode *ptr); / 处理参数列表，如果有参数则返回参数列表否则返回NULL list* _ParamDecList(ParseNode* paramDecList); / 返回基本类型内部表示 TypeIR* _BuildBaseTypeIR(TokenType tokenType); / 处理类型返回类型的内部表示 TypeIR* _TypeDef(ParseNode* typeDef); / 处理FormList节点 void _FormList(ParseNode* formList, list* formlist); bool _Param(ParseNode* param, list* paramtable); void _ParamMore(ParseNode* paramMore, list* paramtable); /处理函数体 void _ProgramBody(ParseNode *ptr); “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008Page 13 of 25 void _StmList(ParseNode *ptr); void _Stm(ParseNode *ptr); void _InputStm(ParseNode *ptr); void _OutputStm(ParseNode *ptr); void _ReturnStm(ParseNode *ptr); void _LoopStm(ParseNode *ptr); void _ConditionalStm(ParseNode *ptr); void _AssCall(ParseNode *ptr); TypeKind _Exp(ParseNode *ptr); TypeKind _Term(ParseNode *ptr); TypeKind _OtherTerm(ParseNode *ptr); TypeKind _Factor(ParseNode *ptr); TypeKind _OtherFactor(ParseNode *ptr); list _CallStmRest(ParseNode *ptr); list _ActParamList(ParseNode *ptr,list procparamkindlist); TypeKind _AssignmentRest(ParseNode *ptr); void _RelExp(ParseNode* relExp); TypeKind _OtherRelE(ParseNode* otherRelE, TokenType* cmpOp); ; 7语义分析阶段的错误类型： 重复变量声明 无声明的标识符 过程调用中形实参类型不匹配 过程调用中形实参个数不相同 表达式中运算符的分量的类型不相同 赋值语句的左右两边类型不相容 “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008Page 14 of 25 五. 面向对象 UML 设计 5.1 SNL 编译器用例图 5.2 SNL 编译器类图 词法分析： “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008Page 15 of 25 语义分析： “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008Page 16 of 25 5.3 SNL 编译器状态图 5.4 SNL 编译器时序图 “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008Page 17 of 25 5.5 SNL 编译器活动图 总活动图： “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008Page 18 of 25 词法分析活动图： “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008Page 19 of 25 5.6 SNL 编译器协作图 5.7 SNL 编译器包图 六. SNL 编译器测试 6.1 单元测试 6.1.1 模块间调用测试 类名类名功能描述功能描述是否正确调用是否正确调用缺陷描述缺陷描述测试员测试员测试日期测试日期 scanner 词法分析模块调用正确无戴雨达 2010.6.20 parse 语法分析模块调用正确无庄琨 2010.6.20 semantic 语义分析模块调用正确无冉启蕾 2010.6.20 6.1.2 主要类调用测试 类名类名功能描述功能描述是否正确调是否正确调 用用 缺陷描述缺陷描述测试员测试员测试日期测试日期 CFile 文件类调用正确无戴雨达 2010.6.20 Token 单词类调用正确无戴雨达 2010.6.20 TokenList 单词链表类调用正确无戴雨达 2010.6.20 “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008Page 20 of 25 Error 错误类调用正确无戴雨达 2010.6.20 ErrorLog 错误链表类调用正确无戴雨达 2010.6.20 LexScanner 词法分析主程序类调用正确无戴雨达 2010.6.20 ParseNode 语法树节点类调用正确无庄琨 2010.6.20 parse 数组属性定义调用正确无庄琨 2010.6.20 SymbNode 符号表节点类调用正确无冉启蕾 2010.6.20 SymbTable 符号表类调用正确无冉启蕾 2010.6.20 AttributeIR 信息表类调用正确无冉启蕾 2010.6.20 TypeIR 类型内部表示类调用正确无冉启蕾 2010.6.20 Scope 局部符号表栈调用正确无冉启蕾 2010.6.20 Semantic 语义分析主程序类调用正确无冉启蕾 2010.6.20 6.1.3 接口函数测试 函数名函数名功能描述功能描述是否正确是否正确 调用调用 缺陷缺陷 描述描述 测试员测试员测试日期测试日期 getTokenlist 取得 Token 序列函数调用正确无戴雨达 2010.6.20 PrintResult() Token 序列输出函数 以及输出错误序列 调用正确无戴雨达 2010.6.20 printParseTree() 语法树输出调用正确无庄琨 2010.6.20 printErrorList() 输出语法分析错误序列调用正确无庄琨 2010.6.20 getParsetree Chushinode() 获取语法分析树的头结 点 调用正确无庄琨 2010.6.20 printSymbtable() 输出符号表调用正确无庄琨 2010.6.20 printErrorlist() 输出语义分析错误序列调用正确无庄琨 2010.6.20 6.1.4 界面测试 界面元素名界面元素名功能描述功能描述是否正确调用是否正确调用缺陷描述缺陷描述测试员测试员测试日期测试日期 文件按钮文件操作相关运行正确无冉启蕾 2010.6.20 单步执行按钮执行操作相关运行正确无冉启蕾 2010.6.20 第 22 组按钮开发小组相关运行正确无冉启蕾 2010.6.20 打开命令按钮文件操作相关运行正确无冉启蕾 2010.6.20 保存命令按钮文件操作相关运行正确无冉启蕾 2010.6.20 关闭命令按钮文件操作相关运行正确无冉启蕾 2010.6.20 词法分析按钮词法分析命令运行正确无冉启蕾 2010.6.20 语法分析按钮语法分析命令运行正确无冉启蕾 2010.6.20 “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008Page 21 of 25 小组成员按钮开发小组相关运行正确无冉启蕾 2010.6.20 程序显示栏显示源程序运行正确无冉启蕾 2010.6.20 执行结果输出栏显示执行结果运行正确无冉启蕾 2010.6.20 6.2 功能测试 6.2.1 等价类表 输入条件输入条件有效等价类有效等价类 输入源程序没有错误没有词法错误 没有语法错误 没有语义错误 输入源程序有词法错误赋值语句少输入了“=” ； 没有注释结尾符错误； 无法识别的字符错误； 输入源程序有语法错误括号匹配错 后继单词错 关键字错 标示符错 开始单词错 输入源程序有语义错误重复变量声明 无声明的标识符 过程调用中形实参类型不匹配 过程调用中形实参个数不相同 表达式中运算符的分量的类型不相同 赋值语句的左右两边类型不相容 6.2.2 测试用例 用例编号用例编号输入输入所属等价类所属等价类 01 详见附件里的输入例子没有词法错误 02 详见附件里的输入例子没有语法错误 03 详见附件里的输入例子没有语义错误 04 详见附件里的输入例子存在词法错误 05 详见附件里的输入例子存在语法错误 06 详见附件里的输入例子存在语义错误 “基于 SNL 语言编译器的面向对象开发”设计报告 Software College of NENU, 2008Page 22 of 25 7. 小组开发心得 我们知道， “编译原理”这一课程是计算机科学与技术专业最重要的专业课之一，掌握 编译方法和技术是每一个优秀的计算机软件专业人员的必备素质。同时一直听老师和学长跟 我们讲编译器开发的重要性，所以从新学期接触到编译程序的设计与实现这门课开始， 我们小组就进入了认真地学习、讨论和开发的过程。 在编译器的开发过程中我们也遇到了很多的困难，由于我们采用的方法是一部分一部分 学习、开发，即先学习词法分析部分，然后开发词法分析部分，再学习语法分析部分，然后 开发语法分析部分 这样的方法导致我们对全局思想的把握不好，对编译程序的总体 理解不好，各部分之间衔接处理得不好。加之由于急于求成，过早地编写代码，导致对编译 原理的思想理解不透彻，所以编写代码时又遇到好多困难，不得不重新回过头来看原理，反 反复复浪费了很长时间，效果也不好。由于对面向对象的思想接触比较晚，也没有很透彻的 学习，导致好多地方理解不好，思路不清晰。 我们先是用了一周的时间系统地对上学期编译原理的课程进行了复习