PL0编译程序设计说明书.doc

PL/0编译程序设计说明书小组组长：李文（00000000）小组成员：*（00000000）*（00000000）*（00000000）*（00000000）2006年1月16日1引言31.1编写目的31.2背景31.3定义31.4参考资料52总体设计52.1需求规定52.2运行环境62.3模块流程62.4模块机理说明72.5模块设计与实现102.6人工处理过程122.7程序的亮点132.8尚未问决的问题133程序介绍和使用说明134程序测试结果分析16概要设计说明书1引言1.1编写目的此文档为VK 1.0版PL/0编译器详细设计说明书，旨在说明该编译器的设计思想和实现。此说明书可以在阅读本编译器代码时有效地帮助您理解本编译器的设计方法和实现过程，希望能提供给您所需的帮助。1.2背景名称：VK1.0版PL/0编译器说明：此编译器为北京师范大学信息科学学院计算机科学与技术系2003级2005-2006学年度第一学期编译原理课程实验作业。本软件由李文小组合作开发，组长李文，同组人员有吕叶、刘晟忻、肖纯、曲文星。本软件主要用于PL/0程序的编译，软件提供生成中间代码，并执行检测。本软件为开源软件，故除了用于编译以外还可给编译器开发者提供开发参考。本软件开发运行在Windows 32位平台上，尚未开发其他平台版本。 1.3定义本软件开发中，用到了一些PL/0语言和PCODE的定义以及编译原理术语，下面给予说明。l PL/0语言： BNF范式：程序=分程序分程序=常量说明部分变量说明部分过程说明部分语句常量说明部分=CONST常量定义 ，常量定义；常量定义=标识符=无符号整数无符号整数=数字数字变量说明部分=VAR标识符，标识符；标识符=字母字母|数字过程说明部分=过程首部分程序；过程说明部分；过程首部=PROCEDURE标识符；语句=赋值语句|条件语句|当型循环语句|过程调用语句|读语句|写语句|复合语句|空；赋值语句=标识符=表达式复合语句=BEGIN语句；语句END条件=表达式关系运算符表达式|ODD表达式表达式=+|-项加法运算符项 项=因子乘法运算符因子因子=标识符|无符号整数|(表达式)加法运算符=+|-乘法运算符=*|/关系运算符=#|=|=|=条件语句=IF条件THEN语句过程调用语句=CALL标识符当型循环语句=WHILE条件DO语句读语句=READ(标识符，标识符)写语句=WRITE(表达式，表达式)字母=a|b|X|Y|Z数字=0|1|2|8|9 PL/0语言允许过程嵌套定义，函数及变量作用于本层。即外层变量和程序对内层可见，内层变量和函数对外层不可见。其中内层函数或变量将使外层的函数或变量不可见。 PL/0允许递归调用，以函数可见为调用原则。l PCODE语言：Pcode语言是PL/0语言的中间代码，其形式如下：指令格式：flaf 功能码l 层次差 （标识符引用层减去定义层）a 根据不同的指令有所区别其代码有8条，如下：LIT 0 a将常数值取到栈顶，a为常数值LOD l a将变量值取到栈顶，a为偏移量，l为层差STO l a将栈顶内容送入某变量单元中，a为偏移量，l为层差CAL l a调用过程，a为过程地址，l为层差INT 0 a在运行栈中为被调用的过程开辟a个单元的数据区JMP 0 a无条件跳转至a地址JPC 0 a条件跳转，当栈顶布尔值非真则跳转至a地址，否则顺序执行OPR 0 0过程调用结束后,返回调用点并退栈OPR 0 1栈顶元素取反OPR 0 2次栈顶与栈顶相加，退两个栈元素，结果值进栈OPR 0 3次栈顶减去栈顶，退两个栈元素，结果值进栈OPR 0 4次栈顶乘以栈顶，退两个栈元素，结果值进栈OPR 0 5次栈顶除以栈顶，退两个栈元素，结果值进栈OPR 0 6栈顶元素的奇偶判断，结果值在栈顶OPR 0 7无操作OPR 0 8次栈顶与栈顶是否相等，退两个栈元素，结果值进栈OPR 0 9次栈顶与栈顶是否不等，退两个栈元素，结果值进栈OPR 0 10次栈顶是否小于栈顶，退两个栈元素，结果值进栈OPR 0 11次栈顶是否大于等于栈顶，退两个栈元素，结果值进栈OPR 0 12次栈顶是否大于栈顶，退两个栈元素，结果值进栈OPR 0 13次栈顶是否小于等于栈顶，退两个栈元素，结果值进栈OPR 0 14栈顶值输出至屏幕OPR 0 15 屏幕输出换行OPR 0 16从命令行读入一个输入置于栈顶l 编译术语： 开始符号集：设G=(VT，VN，S，P)是上下文无关文法FIRST()=a|a,aVT，,V*若,则规定FIRST() 后跟符号集：设 G=(VT，VN，S，P)是上下文无关 文法，AVN，S是开始符号FOLLOW(A)=a|S A,且aVT，aFIRST(),VT* ,V+若S A,且 , 则#FOLLOW(A)。1.4参考资料本软件为课程作业，故开发时主要参考了课程相关的书籍： 编译原理电子课件 北京师范大学信息科学学院计算机科学与技术系 孙波教授 提供 编译原理（第二版）清华大学出版社 张素云、吕映芝等编写。 编译原理及编译程序构造 北京航空航天大学出版社 高仲仪 金茂忠 编 Advanced Compiler Dsign and Implementation USA Stenven S.Muchnick 高级编译器设计与实现 赵克佳 沈志宇 译 机械工业出版社2总体设计2.1需求规定说明对本系统的主要的输入输出项目、处理的功能性能要求，详细的说明可参见附录C。本编译软件的设计目标是为PL/0提供编译和检错以及供开发参考。l 输入项目：1输入PL/0源程序文档名。如果路径正确继续，否则退出2选择是否进行并输出词法分析结果（Y/N）。3选择是否输出中间代码到屏幕（Y/N）。程序会在分析完毕输出中间代码到文件4运行时根据程序结构l 输出项目：1如果有错误输出错误2根据用户选择输出相应结果3PL/0程序运行的结果l 处理性能：由于PL/0程序较为简单，一般的机器平台均能很快地运行，故进行PL/0程序的编译程序设计时并未考虑性能方面的要求。2.2运行环境本编译软件要求运行在支持Windows32位系统的Intel8086以上机型中。从理论上讲，如果源代码使用GCC编译器编译，应该可以在Linux等系统上运行，但尚未做过测试。2.3模块流程 本系统各模块处理数据流程如下图所示：2.4模块机理说明本软件系统采用模块化架构，主要模块有：l 词法分析模块词法分析模块的主要功能是从PL/0源文件读入字符流的代码，然后根据各个单词类型的定义采用自动机的模式，将单词识别出来，并将标识符存储到指定位置，供其他模块取用，同时提供给其他模块以接口，来调用本模块函数，以获得单词的类型。其核心在于自动机的构建，本程序中使用自动机模型如下：同时，为了便于阶段性理解编译过程，程序提供了只查看词法分析结果的功能，因为词法分析中采用提前读判断功能，故程序为了打印出各个单词及词型，把提前读和移动读指针分开，采用preread函数和move函数来实现这一功能。l 语法语义分析模块本程序在处理语法分析时采用LL分析法，并使用递归子程序法来实现。对应各个语法单元定义了相应的处理模块。程序在进行语法语义分析时调用词法分析模块来获取当前单词的词型，并根据词型判断转向德语义分析模块，调用其处理函数执行。在处理各语法单元时，程序根据各单元语义生成中间代码。各语法单元调用关系如下图：l 代码生成模块代码生成模块包括根据语义生成代码和管理代码列表两个部分。其中错误表的管理较为简单，此处不再详细介绍。根据语义生成代码这一部分已嵌入到语法语义分析模块内，一般而言随着语法单元可以顺序翻译，但有少部分单元需要迟后翻译，即在生成代码时无法获得出口或者跳转的目标地址（因为目标在下面，尚未翻译），因此需要采用回填的手段。在本程序中，由于语法分析采用了递归子程序的方法，所考虑的回填问题仅局限在某个语法单元内，因此不用考虑层次回填的问题。故程序中不必采用复杂的拉链技术，而是记下尚未回填的某几条语句位置，等到出口确定时，直接修改代码表中该代码的跳转值即可。采用了回填技术的两个重要控制语句的原理图如下：l 错误处理模块错误处理模块主要包括错误表的管理、错误补救和致命错误的处理三个方面。 错误表的管理对外提供错误报告函数，由调用程序报告错误类型，管理模块将其记录到表中并记录出错行号。程序中主要的错误类型如下：错误类型错误信息致命错误UNEXPECTED_FILE_END不可预期的文件结尾UNEXPECTED_EXTERN_CODE程序结束还有多余代码CODELIST_OVERFLOW中间代码表溢出TABLE_OVERFLOW符号表溢出词法错误IDENT_TOO_LONG标识符过长NUM_TOO_BIG数字过长UNKNOWN_SYMBOL不可识别的符号语法错误MISSING_PERIOD程序末尾丢掉了.结束符号IDENT_REDECLARED标识符重复声明IDENT_IN_CONST_EXPECTING常量声明必须以标识符开始EQL_IN_CONST_EXPECTING常量声明中间应该为=符号NUM_IN_CONST_EXPECTING常量声明的值必须是数字常量MISSING_SEMICOLON_IN_CONST常量声明末尾丢掉了;IDENT_IN_VAR_EXPECTING变量必须为标识符MISSING_SEMICOLON_IN_VAR变量声明末尾丢掉了;PROC_LEV_TOO_DEEP过程层次定义太深IDENT_IN_PROC_EXPECTING过程名必须为标识符MISSING_SEMICOLON_IN_PROC过程声明末尾丢掉了;MISSING_SEMICOLON_END_PROC过程定义末尾丢掉了;UNEXPECTED_STATEMENT_BEGIN无效的语句开始VAR_UNDECLARED未声明的变量PROC_UNDECLARED未声明的过程IDENT_CONST_IN_ASSIGN不可为常量赋值IDENT_PROC_IN_ASSIGN赋值语句左边不可为过程名BECOMES_EXPECTING_IN_ASSIGN赋值语句中间应该为:=MISSING_SEMICOLON_IN_STATEMENT语句末尾丢掉了;THEN_EXPECTING_IN_IFif语句条件后面应该为thenDO_EXPECTING_IN_WHILEwhile语句条件后面应该为doPROC_EXPECTING_IN_CALLcall 后面必须是 过程名IDENT_CONST_IN_READread 语句中不应有常量IDENT_PROC_IN_READread 语句中不应有过程名KEYWORD_APPEAR_IN_READread 语句中不应该出现关键字IDENT_EXPECTING_IN_READread 语句中(或者IDENT_PROC_IN_EXP表达式中不因该出现过程名RELATIONOPR_EXPECTING_IN_CDT条件中的不应出现非关系运算符MISSING_LPAREN丢掉了左括号MISSING_RPAREN丢掉了右括号MISSING_END缺少ENDUNEXPECTED_STATEMENT_FOLLOW语句follow集不符UNEXPECTED_PROCDECL_FOLLOW过程声明follow集不符UNEXPECTED_CONST_FOLLOW常量声明follow集不符UNEXPECTED_VAR_FOLLOW变量声明follow集不符UNEXPECTED_PROCBODY_FOLLOW过程定义follow集不符UNEXPECTED_CDT_FOLLOW条件follow集不符UNEXPECTED_FACTOR_FOLLOW表达式follow集不符表2 错误类型表在错误处理时，可以发现，FOLLOW集不正确的错误大都是由于其他错误在先而引起的，故为了有效准确的报告错误，在处理错误报告时采取如果已有错误报告，则对FOLLOW集不予报告，否则，则报告的方式，有效减少无效错误的发生。 致命错误的处理，采用函数返回terminate标志TMNT，如果在子程序调用时返回了TMNT，则当前程序也应该立即返回TMNT，直到main函数为止来报告该错误。为了调用子程序方便，程序中把所有子程序调用使用宏定义来实现TMNT返回，将子程序调用保护起来。 错误补救采用了判断开始符号集和后跟符号集的方式。即将所有错误均认为是丢掉了语法模块，然后根据后跟符号集来读取本语法单元的内容，将错误缩小在本语法单元内。l 符号表管理模块符号表管理采用栈式存储管理，以解决符号可见性的问题。即每次进入语法块时记录此时位置，等退出时出栈该层符号。l 中间代码解释模块中间代码解释实际上是做了一个简单的虚拟机，用bx，cx，sp等模拟寄存器来解释执行指令。根据指令含义执行相应的动作。2.5模块设计与实现此部分主要介绍各个模块的程序实现及其处理数据的流程示意各模块的主要设计如下：l 词法分析模块l 语法语义分析模块l 代码生成模块l 错误处理模块l 中间代码解释模块2.6人工处理过程本软件在开发时尽量避免使用人工处理，所需要人工处理的地方主要包括对非终结符的开始符号集和后跟符号集的求解。这些求解将在语法语义分析中用于宏定义，以方便程序设计。开始符号和后跟符号及求解结果如下：非终结符名开始符号集合后继符号集合分程序const var procedure ident if call begin while read write.语句ident call begin if while read write. ; end条件odd + - ( ident numberthen do表达式+ - ( ident number. ; ) rop end then do项ident number (. ; ) rop + - end then do因子ident number (. ; + - * end then do2.7程序的亮点 为了便于观察和理解编译过程，程序专门实现了词法分析的结果显示。可以在程序运行时选择是否显示词法分析结果。 程序在错误处理上很注重错误提示的有效性，实现错误提示了定位到出错行，定位到出错标识符的功能。 程序在符号表管理上采用栈式管理，很适合于解决PL/0的嵌套定义中符号的作用域及可见性问题。2.8尚未问决的问题 程序在错误处理上下了很大功夫，实现了定位到标识符的提示。由于实现时时根据错误类型以及错误点的上一标识符和当前标识符来判断，可能在某些极特殊的错误（错误的标识符既不是上一个也不是当前的）中，会出现提示失误的情况。 本程序在设计之初已经实现了一个Win32的窗口界面，后来由于加入了解释执行程序，不得不忍痛割爱，将其拆掉。目前亟待解决的问题是，如何能在窗口界面中调用解释执行程序来模拟运行。3程序介绍和使用说明 本程序为DOS界面，程序运行时，会弹出如下窗口输入PL/0源文件名会给出两个选项，输入y/n即可：选中选项后将看到词法分析结果以及中间代码中间代码位于下面，滚动即可看到并且给出中间代码运行结果：4程序测试结果分析为了检验程序是否达到预期目标，结果是否正确，程序使用了大量的PL/0源文件来进行测试，在此以一个正确的源文件和一个错误的源文件为例来测试程序功能：l 正确的源文件：PL/0源文件：standard.plCONST a=10;var b,c;procedure p; begin c:=b+a end; begin read(b); while b#0 do begin call p; write(2*c); read(b) end end.运行结果：请输入PL/0源程序文件名:standard.pl是否显示词法分析结果？y是否显示中间代码列表？yCompiling.词法分析结果如下：CONST Type:constsyma Type:ident= Type:eql10 Type:number; Type:semicolonvar Type:varsymb Type:ident, Type:commac Type:ident; Type:semicolonprocedure Type:procsymp Type:ident; Type:semicolonbegin Type:beginsymc Type:ident:= Type:becomesb Type:ident+ Type:plusa Type:identend Type:endsym; Type:semicolonbegin Type:beginsymread Type:readsym( Type:lparenb Type:ident) Type:rparen; Type:semicolonwhile Type:whilesymb Type:ident# Type:neq0 Type:numberdo Type:dosymbegin Type:beginsymcall Type:callsymp Type:ident; Type:semicolonwrite Type:writesym( Type:lparen2 Type:number* Type:timesc Type:ident) Type:rparen; Type:semicolonread Type:readsym( Type:lparenb Type:ident) Type:rparenend Type:endsymend Type:endsym. Type:periodSyntaxing.中间代码如下： 0: JMP 0 8 1: JMP 0 2 2: INT 0 3 3: LOD 1 3 4: LIT 0 10 5: OPR 0 2 6: STO 1 4 7: OPR 0 0 8: INT 0 5 9: OPR 0 1610: STO 0 311: LOD 0 312: LIT 0 013: OPR 0 9