搜索
编译原理课程设计报告班级：1612103学号：姓名：2014-12一、设计任务通过编写一个PL/0语言编译器的源代码，加深对编译阶段（包括词法分析、语法分析、语义分析、中间代码生成等）和编译系统软件结构的理解，巩固和加深对编译原理的理解，提高综合运用本课程所学知识的能力。PL/0语言可以看成PASCAL语言的子集，它的编译程序是一个编译解释执行系统。PL/0的目标程序为假想栈式计算机的汇编语言，与具体计算机无关。PL/0的编译程序和目标程序的解释执行程序都是用PASCAL语言书写的，因此PL/0语编译原理课程设计报告言可在配备PASCAL语言的任何机器上实现。使用语法图和扩充的巴克斯范式表示法对PL/0语言的形式描述。其编译过程采用一趟扫描方式，以语法分析程序为核心，词法分析和代码生成程序都作为一个独立的过程，当语法分析需要读单词时就调用词法分析程序，而当语法分析正确需要生成相应的目标代码时，则调用代码生成程序。用表格管理程序建立变量、常量和过程标示符的说明与引用之间的信息联系。掌握PL/0语言编译程序的目标程序在运行时数据空间的组织管理。用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错位性质。当源程序编译正确时，PL/0编译程序自动调用解释执行程序，对目标代码进行解释执行，并按用户程序的要求输入数据和输出运行结果。总体来说，就是以PL/0语言编译程序为实例,学习编译程序实现的基本步骤和相关技术，对编译程序的构造和实现得到一些感性认识和建立起整体概念，更加深入了解编译原理的学习。如下图所示。其中，课程设计要求的相关内容如下：PL/0语言的BNF描述（扩充的巴克斯范式表示法）prog→programid；blockblock→[condecl][vardecl][proc]bodycondecl→constconst{,const};const→id:=integervardecl→varid{,id};proc→procedureid（[id{,id}]）;block{;proc}body→beginstatement{;statement}endstatement→id:=exp|iflexpthenstatement[elsestatement]|whilelexpdostatement|callid（[exp{,exp}]）编译原理课程设计报告|body|read(id{，id})|write(exp{,exp})lexp→explopexp|oddexpexp→[+|-]term{aopterm}term→factor{mopfactor}factor→id|integer|(exp)lop→=|||=||=aop→+|-mop→*|/id→l{l|d}（注：l表示字母）integer→d{d}注释：prog：程序；block：块、程序体；condecl：常量说明；const：常量；vardecl：变量说明；proc：分程序；body：复合语句；statement：语句；exp：表达式；lexp：条件；term：项；factor：因子；aop：加法运算符；mop：乘法运算符；lop：关系运算符。假想目标机的代码LIT0，a取常量a放入数据栈栈顶OPR0，a执行运算，a表示执行某种运算LODL，a取变量（相对地址为a，层差为L）放到数据栈的栈顶STOL，a将数据栈栈顶的内容存入变量（相对地址为a，层次差为L）CALL，a调用过程（转子指令）（入口地址为a，层次差为L）INT0，a数据栈栈顶指针增加aJMP0，a无条件转移到地址为a的指令JPC0，a条件转移指令，转移到地址为a的指令REDL，a读数据并存入变量（相对地址为a，层次差为L）WRT0，0将栈顶内容输出代码的具体形式：其中：F段代表伪操作码L段代表调用层与说明层的层差值A段代表位移量（相对地址）进一步说明：INT：为被调用的过程（包括主过程）在运行栈S中开辟数据区，这时A段为所需数据单元个数（包括三个连接数据）；L段恒为0。CAL：调用过程，这时A段为被调用过程的过程体（过程体之前一条指令）在目标程序区的入口地址。LIT：将常量送到运行栈S的栈顶，这时A段为常量值。LOD：将变量送到运行栈S的栈顶，这时A段为变量所在说明层中的相对位置。FLA编译原理课程设计报告STO：将运行栈S的栈顶内容送入某个变量单元中，A段为变量所在说明层中的相对位置。JMP：无条件转移，这时A段为转向地址（目标程序）。JPC：条件转移，当运行栈S的栈顶的布尔值为假（0）时，则转向A段所指目标程序地址；否则顺序执行。OPR：关系或算术运算，A段指明具体运算，例如A=2代表算术运算“＋”；A＝12代表关系运算“”；A＝16代表“读入”操作等等。运算对象取自运行栈S的栈顶及次栈顶。假想机的结构两个存储器：存储器CODE，用来存放P的代码数据存储器STACK（栈）用来动态分配数据空间四个寄存器：一个指令寄存器I:存放当前要执行的代码一个栈顶指示器寄存器T：指向数据栈STACK的栈顶一个基地址寄存器B：存放当前运行过程的数据区在STACK中的起始地址一个程序地址寄存器P：存放下一条要执行的指令地址该假想机没有供运算用的寄存器。所有运算都要在数据栈STACK的栈顶两个单元之间进行，并用运算结果取代原来的两个运算对象而保留在栈顶。二、功能结构设计1、总体结构PL/0的解释执行结构PL/0编译程序结构编译原理课程设计报告编译程序总体流程图2、词法分析程序的设计使用状态转换图实现：表示状态，对应每个状态编一段程序，每个状态调用取字符程序，根据当前字符转到不同的状态，并做相应操作。词法分析程序语法语义分析程序代码生成程序表格管理程序出错处理程序PL/0源程序目标程序编译原理课程设计报告表示终态，已识别出一个单词。PL/0的词法分析程序GetSym()是一个独立的过程，其功能是为语法分析提供单词用的，是语法分析的基础，它把输入的字符串形式的源程序分割成一个个单词符号。为此PL/0编译程序设置了三个变量如下：SYM：存放每个单词的类别，用内部编码形式表示。ID：存放用户所定义的标识符的值。即标识符字符串的机内表示。NUM：存放用户定义的数。单词的种类有五种。基本字：也可称为保留字或关键字，如BEGIN，END，IF，THEN等。运算符：如：+、-、*、／、∶=、#、＞=、＜=等。标识符：用户定义的变量名、常数名、过程名。常数：如：10，25，100等整数。界符：如：'，'、'.'、'；'、'('、')'等。如果我们把基本字、运算符、界符称为语言固有的单词，而对标识符、常数称为用户定义的单词。那么经词法分析程序分出的单词，对语言固有的单词只给出类别存放在SYM中，而对用户定义的单词(标识符或常数)既给类别又给值，其类别放在SYM中，值放在ID或NUM中，全部单词种类由编译程序定义的纯量类型SYMBOL给出，也可称为语法的词汇表。词法分析程序GETSYM将完成下列任务：(1)滤空格：空格在词法分析时是一种不可缺少的界符，而在语法分析时则是无用的，所以必须滤掉。1235141312109786411空格字母字母数字非字母数字数字数字非数字：==非==非=,+-(……编译原理课程设计报告(2)识别保留字：设有一张保留字表。对每个字母打头的字母、数字字符串要查此表。若查着则为保留字，将对应的类别放在SYM中。如IF对应值IFSYM，THEN对应值为THENSYM。若查不着，则认为是用户定义的标识符。(3)识别标识符：对用户定义的标识符将IDENT放在SYM中，标识符本身的值放在ID中。(4)拼数：当所取单词是数字时，将数的类别NUMBER放在SYM中，数值本身的值存放在NUM中。(5)拼复合词：对两个字符组成的算符如：＞=、∶=、＜=等单词，识别后将类别送SYM中。(6)输出源程序：为边读入字符边输出(可输出在文件中)。由于一个单词往往是由一个或几个字符组成的，所以在词法分析过程GETSYM中又定义了一个取字符过程GETCH(见图2.6)，由词法分析需要取字符时调用。3、语法分析的设计与实现考虑到PL/0的语法性质，语法分析的方法采用自顶向下的语法分析具体使用递归子程序法来实现PL/0的语法分析，具体方法为：对应每个非终结符语法单元，编一个独立的处理过程（或子程序）。语法分析从读入第一个单词开始，由非终结符程序（即开始符）出发，沿语法描述图箭头所指出的方向进行分析。当遇到非终结符时，则调用相应的处理过程，从语法描述图看，也就进入了一个语法单元，再沿当前所进入的语法单元所指箭头方向继续进行分析。当遇到描述图中是终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，再读取下一个单词继续分析。遇到分支点时，将当前的单词与分支点上多个终结符逐个相比较，若都不匹配时可能是进入下一个非终结符语法单位或是出错。若检测到当前输入的词素不满足语法定义时，提示错误并推出编译程序。PL/0编译程序的语法分析采用了自顶向下的递归子程序法。什么是自顶向下的语法分析？可形象地对该程序自顶向下构造一棵倒挂着的语法分析树，其构造方法是：（1）由开始符号非终结符'程序'作为分析树的根结点，由非终结符'程序'规则的右部为子结点。（2）对分析树中的每个非终结符结点，选择它规则的一个右部为子结点构造分析树的下一层。（3）重复（2）直到分析树中的末端结点只有终结符。（4）若分析树中的末端结点从左到右连接的终结符号串刚好是输入的程序终结符号串，则说明所给程序在语法上是正确的。可用下面简单的PL/0程序为例构造其语法分析树编译原理课程设计报告语法调用关系图如下：具体语法结构如图所示：编译原理课程设计报告编译原理课程设计报告由于语义分析是嵌套在相关语法分析的处理函数中的具体语句，因此不在此一一列举，以iflexpthenstatement[elsestatement]为例，当语法语义正确时，就生成相应语句功能的目标代码。并在code数组中存储相关的目标机代码。当正常执行完上述代码后，按顺序生成相关的目标机代码，并存储到相应的code数组单元中。如果一个PL/0语言的单词序列在整个语法分析中，都能逐个得到匹配，直到程序结束符，这时就说所输入的程序是正确的。对于正确的语法分析做相应的语义翻译，最终得出目标程序。语法分析过程中，使用递归子程序法构造语法分析程序时，对文法有一定的要求和限制。此外，从PL/0的语法描述图中可以清楚地看到，当对PL/0语言进行语法分析时，各个非终结符语法单元所对应的分析过程之间必须存在相互调用的关系。这种调用关系可称为PL/0语法的依赖图，在图中箭头所指向的程序单元表示存在调用关系，从图中不难看出这些子程序在语法分析时被直接或间接递归调用。由PL/0语法调用关系图可以看出对分程序和语句为直接递归调用，对表达式为间接递归调用。注：PL/0编译程序语法、语义分析的的核心程序是BLOCK过程，在BLOCK过程内又定义了许多嵌套及并列的过程。在过程BLOCK内对说明部分及程序体部分的分析说明如下：(1)说明部分的分析说明部分的处理任务就是对每个过程的说明对象造名字表，填写所在层次、标识编译原理课程设计报告符的属性和分配的相对位置等。标识符的属性不同时，所需要填写的信息也有所不同。登录信息是调用ENTER过程完成的。(2)过程体的分析程序的主体是由语句构成的。处理完过程的说明后就处理由语句组成的过程体，从语法上要对语句逐句分析。当语法正确时就生成相应语句功能的目标代码。当遇到标识符的引用时就调用POSITION函数查TABLE表，看是否有过正确的定义，若已有，则从表