编译原理课设报告_第1页
编译原理课设报告_第2页
编译原理课设报告_第3页
编译原理课设报告_第4页
编译原理课设报告_第5页
已阅读5页，还剩11页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、编译原理课程设计报告编译原理课程设计报告班级：1612103学号：姓 名：2014-12一、设计任务通过编写一个PL/0语言编译器的源代码， 加深对编译阶段（包括词法分析、语法分析、语义分析、中间代码生成等）和编译系统软件结构的理解，巩固和加深对编译原理的理解，提高综合运用本课程所学知识的能力。 PL/0语言可以看成PASCAL语言的子集，它的编译程序是一个编译解释执行系统。PL/0的目标程序为假想栈式计算机的汇编语言，与具体计算机无关。PL/0的编译程序和目标程序的解释执行程序都是用PASCAL语言书写的，因此PL/0语言可在配备PASCAL语言的任何机器上实现。使用语法图和扩充的巴克斯范式

2、表示法对 PL/0语言的形式描述。 其编译过程采用一趟扫描方式，以语法分析程序为核心，词法分析和代码生成程序都作为一个独立的过程，当语法分析需要读单词时就调用词法分析程序，而当语法分析正确需要生成相应的目标代码时，则调用代码生成程序。用表格管理程序建立变量、常量和过程标示符的说明与引用之间的信息联系。掌握PL/0语言编译程序的目标程序在运行时数据空间的组织管理。用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错位性质。当源程序编译正确时，PL/0编译程序自动调用解释执行程序，对目标代码进行解释执行，并按用户程序的要求输入数据和输出运行结果。总体来说，就是以PL/0语言编译程序

3、为实例,学习编译程序实现的基本步骤和相关技术，对编译程序的构造和实现得到一些感性认识和建立起整体概念，更加深入了解编译原理的学习。如下图所示。其中，课程设计要求的相关内容如下：PL/0语言的BNF描述（扩充的巴克斯范式表示法）<prog> program <id>；<block><block> <condecl><vardecl><proc><body><condecl> const <const>,<const><const> <id>:

4、=<integer><vardecl> var <id>,<id><proc> procedure <id>（<id>,<id>）;<block><proc><body> begin <statement><statement>end<statement> <id> := <exp> |if <lexp> then <statement>else <statement>

5、 |while <lexp> do <statement> |call <id>（<exp>,<exp>） |<body> |read (<id>，<id>) |write (<exp>,<exp>)<lexp> <exp> <lop> <exp>|odd <exp><exp> +|-<term><aop><term><term> <factor>

6、;<mop><factor><factor><id>|<integer>|(<exp>)<lop> =|<>|<|<=|>|>=<aop> +|-<mop> *|/<id> ll|d （注：l表示字母）<integer> dd注释：<prog>：程序 ；<block>：块、程序体 ；<condecl>：常量说明 ；<const>：常量；<vardecl>：变量说明 ；&

7、lt;proc>：分程序 ； <body>：复合语句 ；<statement>：语句；<exp>：表达式 ；<lexp>：条件 ；<term>：项 ； <factor>：因子 ；<aop>：加法运算符；<mop>：乘法运算符； <lop>：关系运算符。假想目标机的代码LIT 0 ，a 取常量a放入数据栈栈顶OPR 0 ，a 执行运算，a表示执行某种运算LOD L ，a 取变量（相对地址为a，层差为L）放到数据栈的栈顶STO L ，a 将数据栈栈顶的内容存入变量（相对地址为a，层次差

8、为L）CAL L ，a 调用过程（转子指令）（入口地址为a，层次差为L）INT 0 ，a 数据栈栈顶指针增加aJMP 0 ，a无条件转移到地址为a的指令JPC 0 ，a 条件转移指令，转移到地址为a的指令RED L ，a 读数据并存入变量（相对地址为a，层次差为L）WRT 0 ，0 将栈顶内容输出代码的具体形式：F L A其中：F段代表伪操作码 L段代表调用层与说明层的层差值 A段代表位移量（相对地址）进一步说明：INT：为被调用的过程（包括主过程）在运行栈S中开辟数据区，这时A段为所需数据单元个数（包括三个连接数据）；L段恒为0。CAL：调用过程，这时A段为被调用过程的过程体（过程体之前一条

9、指令）在目标程序区的入口地址。LIT：将常量送到运行栈S的栈顶，这时A段为常量值。LOD：将变量送到运行栈S的栈顶，这时A段为变量所在说明层中的相对位置。STO：将运行栈S的栈顶内容送入某个变量单元中，A段为变量所在说明层中的相对位置。JMP：无条件转移，这时A段为转向地址（目标程序）。JPC：条件转移，当运行栈S的栈顶的布尔值为假（0）时，则转向A段所指目标程序地址；否则顺序执行。OPR：关系或算术运算，A段指明具体运算，例如A=2代表算术运算“”；A12代表关系运算“>”；A16代表“读入”操作等等。运算对象取自运行栈S的栈顶及次栈顶。假想机的结构两个存储器：存储器CODE，用来存放

10、P的代码 数据存储器STACK（栈）用来动态分配数据空间四个寄存器：一个指令寄存器I:存放当前要执行的代码一个栈顶指示器寄存器T：指向数据栈STACK的栈顶一个基地址寄存器B：存放当前运行过程的数据区在STACK中的起始地址一个程序地址寄存器P：存放下一条要执行的指令地址该假想机没有供运算用的寄存器。所有运算都要在数据栈STACK的栈顶两个单元之间进行，并用运算结果取代原来的两个运算对象而保留在栈顶。二、功能结构设计1、总体结构PL/0的解释执行结构PL/0编译程序结构词法分析程序语法语义分析程序代码生成程序表格管理程序出错处理程序PL/0源程序目标程序编译程序总体流程图2、词法分析程序的设计

11、使用状态转换图实现：表示状态，对应每个状态编一段程序，每个状态调用取字符程序，根据当前字符转到不同的状态，并做相应操作。表示终态，已识别出一个单词。PL/0的词法分析程序GetSym()是一个独立的过程，其功能是为语法分析提供单词用的，是语法分析的基础，它把输入的字符串形式的源程序分割成一个个单词符号。为此PL/0编译程序设置了三个变量如下：SYM：存放每个单词的类别，用内部编码形式表示。ID：存放用户所定义的标识符的值。即标识符字符串的机内表示。NUM：存放用户定义的数。单词的种类有五种。基本字：也可称为保留字或关键字，如BEGIN，END，IF，THEN等。运算符：如：+、-、*、=、#、

12、=、=等。标识符：用户定义的变量名、常数名、过程名。常数：如：10，25，100等整数。界符：如：'，'、'.'、'；'、'('、')'等。如果我们把基本字、运算符、界符称为语言固有的单词，而对标识符、常数称为用户定义的单词。那么经词法分析程序分出的单词，对语言固有的单词只给出类别存放在SYM中，而对用户定义的单词(标识符或常数)既给类别又给值，其类别放在SYM中，值放在ID或NUM中，全部单词种类由编译程序定义的纯量类型SYMBOL给出，也可称为语法的词汇表。词法分析程序GETSYM将完成下列任务：(1) 滤空格

13、：空格在词法分析时是一种不可缺少的界符，而在语法分析时则是无用的，所以必须滤掉。(2) 识别保留字：设有一张保留字表。对每个字母打头的字母、数字字符串要查此表。若查着则为保留字，将对应的类别放在SYM中。如IF对应值IFSYM，THEN对应值为THENSYM。若查不着，则认为是用户定义的标识符。(3) 识别标识符：对用户定义的标识符将IDENT放在SYM中，标识符本身的值放在ID中。(4) 拼数：当所取单词是数字时，将数的类别NUMBER放在SYM中，数值本身的值存放在NUM中。(5) 拼复合词：对两个字符组成的算符 如：=、=、= 等单词，识别后将类别送SYM中。(6) 输出源程序：为边读入

14、字符边输出(可输出在文件中)。由于一个单词往往是由一个或几个字符组成的，所以在词法分析过程GETSYM中又定义了一个取字符过程GETCH(见图2.6)，由词法分析需要取字符时调用。3、语法分析的设计与实现考虑到PL/0的语法性质，语法分析的方法采用自顶向下的语法分析具体使用递归子程序法来实现PL/0的语法分析，具体方法为：对应每个非终结符语法单元，编一个独立的处理过程（或子程序）。语法分析从读入第一个单词开始，由非终结符<程序>（即开始符）出发，沿语法描述图箭头所指出的方向进行分析。当遇到非终结符时，则调用相应的处理过程，从语法描述图看，也就进入了一个语法单元，再沿当前所进入的语法

15、单元所指箭头方向继续进行分析。当遇到描述图中是终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，再读取下一个单词继续分析。遇到分支点时，将当前的单词与分支点上多个终结符逐个相比较，若都不匹配时可能是进入下一个非终结符语法单位或是出错。若检测到当前输入的词素不满足语法定义时，提示错误并推出编译程序。PL/0编译程序的语法分析采用了自顶向下的递归子程序法。什么是自顶向下的语法分析？可形象地对该程序自顶向下构造一棵倒挂着的语法分析树，其构造方法是：（1） 由开始符号非终结符'程序'作为分析树的根结点，由非终结符'程序'规则的右部为子结点。（2） 对分析树

16、中的每个非终结符结点，选择它规则的一个右部为子结点构造分析树的下一层。（3） 重复（2）直到分析树中的末端结点只有终结符。（4） 若分析树中的末端结点从左到右连接的终结符号串刚好是输入的程序终结符号串，则说明所给程序在语法上是正确的。可用下面简单的PL/0程序为例构造其语法分析树 语法调用关系图如下：具体语法结构如图所示：由于语义分析是嵌套在相关语法分析的处理函数中的具体语句，因此不在此一一列举，以if <lexp> then <statement>else <statement>为例，当语法语义正确时，就生成相应语句功能的目标代码。并在code数组中存储相

17、关的目标机代码。当正常执行完上述代码后，按顺序生成相关的目标机代码，并存储到相应的code数组单元中。如果一个PL/0语言的单词序列在整个语法分析中，都能逐个得到匹配，直到程序结束符，这时就说所输入的程序是正确的。对于正确的语法分析做相应的语义翻译，最终得出目标程序。语法分析过程中，使用递归子程序法构造语法分析程序时，对文法有一定的要求和限制。此外，从PL/0的语法描述图中可以清楚地看到，当对PL/0语言进行语法分析时，各个非终结符语法单元所对应的分析过程之间必须存在相互调用的关系。这种调用关系可称为PL/0语法的依赖图，在图中箭头所指向的程序单元表示存在调用关系，从图中不难看出这些子程序在语

18、法分析时被直接或间接递归调用。由 PL/0语法调用关系图可以看出对分程序和语句为直接递归调用，对表达式为间接递归调用。注： PL/0编译程序语法、语义分析的的核心程序是BLOCK过程，在BLOCK过程内又定义了许多嵌套及并列的过程。在过程BLOCK内对说明部分及程序体部分的分析说明如下：(1) 说明部分的分析说明部分的处理任务就是对每个过程的说明对象造名字表，填写所在层次、标识符的属性和分配的相对位置等。标识符的属性不同时，所需要填写的信息也有所不同。登录信息是调用ENTER过程完成的。(2) 过程体的分析程序的主体是由语句构成的。处理完过程的说明后就处理由语句组成的过程体，从语法上要对语句逐

19、句分析。当语法正确时就生成相应语句功能的目标代码。当遇到标识符的引用时就调用POSITION函数查TABLE表，看是否有过正确的定义，若已有，则从表中取相应的有关信息，供代码的生成用。若无定义则出错。4、错误处理 PL/0编译程序对语法错误的处理采用两种办法：(1) 对于一些易于校正的错误，如丢了逗号、分号等，则指出出错位置，并加以校正。校正的方式就是补上逗号或分号。(2) 对某些错误编译程序难于确定校正的措施，为了使当前的错误不致影响整个程序的崩溃，把错误尽量局限在一个局部的语法单位中。这样就需跳过一些后面输入的单词符号，直到读入一个能使编译程序恢复正常语法分析工作的单词为止。在本次实验课程

20、设计中，不准备在错误处理方面做非常详细的功能实现，只做了简单的错误位置说明和错误实现。5、目标代码解释执行时的存储分配 解释程序定义了4个寄存器：(1) I：指令寄存器。存放着当前正在解释的一条目标指令。(2) P：程序地址寄存器。指向下一条要执行的目标程序的地址(相当目标程序CODE数组的下标)。(3) T：栈顶寄存器。由于每个过程当它被运行时，给它分配的数据空间(下边称数据段)可分成两部分。静态部分：包括变量存放区和三个联系单元(联系单元的作用见后)。动态部分：作为临时工作单元和累加器用。需要时随时分配，用完后立即释放。栈顶寄存器T指出了当前栈中最新分配的单元(T也是数组S的下标)。(4)

21、 B：基址寄存器。指向每个过程被调用时，在数据区S中给它分配的数据段起始地址，也称基地址。 为了实现对每个过程调用时给它分配数据段，也就是对即将运行的过程所需数据段进栈；过程运行结束后释放数据段，即该数据段退栈；以及嵌套过程之间对标识符引用的寻址问题。每个过程被调用时，在栈顶分配三个联系单元，这三个单元存放的内容分别为：(1) SL：静态链：它是指向定义该过程的直接外过程(或主程序)运行时最新数据段的基地址。(2) DL：动态链：它是指向调用该过程时正在运行过程的数据段基地址。(3) RA：返回地址：记录调用该过程时目标程序的断点，即当时的程序地址寄存器P的值。也就是调用过程指令的下一条指令的

22、地址。数据空间只需以数组CODE存放的只读目标程序和运行时的数据栈S。S是由解释程序定义的一维整型数组。由于PL/0语言的目标程序是一种假想的栈式计算机的汇编语言，仍用PASCAL语言解释执行。解释执行时的数据空间S为栈式计算机的存储空间。遵循后进先出规则，对每个过程(包括主程序)当被调用时，才分配数据空间，退出过程时，则所分配的数据空间被释放。解释程序根据待翻译的目标机代码（三地址语句代码）中相关的F段中的操作码，L段中调用层与说明层的层差值以及A段中位移量（相对地址），对数据栈stack以及相关寄存器进行操作，当P寄存器（存放下一条要执行的指令地址）为0时结束解释程序，至此编译完成。三、函

23、数说明/子程序过程，将下一输入字符读到ch中，搜索指示器前移一个字符位置。void GetChar(char &ch, FILE *fp, int & end)/子程序过程，检查ch中的字符是否为空白。若是，则调用GetChar直至ch中加入一个非空白字符。void GetBC(char &ch, FILE *fp, int & end)/子程序过程，将ch中的字符连接到strToken之后。例如，假定strToken原来的值为“AB”，而ch中存放着'C',经调用Concat后，strToken的值就变味“ABC”void Concat(cha

24、r* &str, char ch, int &length)/判断ch中的字符是否为字母bool IsLetter(char ch)/判断ch中的字符是否为数字bool IsDigit(char ch)/整形函数过程，对strToken中的字符串查找保留字表，若它是一个保留字则返回它的编码，否则0值;int Reserve(char *strToken)/子程序过程，将搜索指示器回调一个字符位置，将ch置为空白字符。void Retract(char &ch, int & end)/词法分析从文件指针fp所指向文件中start位置处开始，得到一个非空白的词素，并

25、将返回信息token lexical_analysis(FILE *fp, int &start, int &end)/调用词法分析子程序，得到下一个词素，并改变搜索指示器的值void GetSym(FILE *fp, int &start, int &end, token & sym)bool ProgDo(FILE *fp, int &start, int &end, token &sym);/对照文法定义中产生式<prog> program <id>；<block>对从文件指针fp所指 向

26、的文件中start位置处开始进行语法分析bool BlockDo(FILE *fp, int &start, int &end, token & sym);/对照文法定义中产生式<condecl><vardecl><proc><body>对从文件指针fp所指向的文件中start位置处开始进行语法分析并产生相关的目标机代码bool CondeclDo(FILE *fp, int &start, int &end, token & sym);/对照文法定义中产生式<condecl> cons

27、t <const>,<const>对从文件指针fp所指向的文件中start位置处开始进行语法分析并产生相关的目标机代码bool ConstDo(FILE *fp, int &start, int &end, token & sym);/对照文法定义中产生式<const> <id>:=<integer>对从文件指针fp所指向的文件中start位置处开始进行语法分析bool VardeclDo(FILE *fp, int &start, int &end, token & sym);/对照文

28、法定义中产生式<vardecl> var <id>,<id>对从文件指针fp所指向的文件中start位置处开始进行语法分析bool ProcDo(FILE *fp, int &start, int &end, token & sym);/对照文法定义中产生式<proc> procedure <id>（<id>,<id>）;<block><proc>对从文件指针fp所指向的文件中start位置处开始进行语法分析bool BodyDo(FILE *fp, int &a

29、mp;start, int &end, token & sym);/对照文法定义中产生式<body> begin <statement><statement>end对从文件指针fp所指向的文件中start位置处开始进行语法分析bool StatementDo(FILE *fp, int &start, int &end, token & sym);/对照文法定义中<statement>的产生式对从文件指针fp所指向的文件中start位置处开始进行语法分析并产生相关的目标机代码bool LexpDo(FILE

30、 *fp, int &start, int &end, token & sym);/对照文法定义中产生式<lexp> <exp> <lop> <exp>|odd <exp>对从文件指针fp所指向的文件中start位置处开始进行语法分析并产生相关的目标机代码bool ExpDo(FILE *fp, int &start, int &end, token & sym);/对照文法定义中产生式<exp> +|-<term><aop><term>对

31、从文件指针fp所指向的文件中start位置处开始进行语法分析并产生相关的目标机代码bool TermDo(FILE *fp, int &start, int &end, token & sym);/对照文法定义中产生式<term> <factor><mop><factor>对从文件指针fp所指向的文件中start位置处开始进行语法分析并产生相关的目标机代码bool FactorDo(FILE *fp, int &start, int &end, token & sym);/对照文法定义中产生式<

32、;factor><id>|<integer>|(<exp>)对从文件指针fp所指向的文件中start位置处开始进行语法分析并产生相关的目标机代码void Enter(int type,Token sym);/向符号表中添加一条类型为type，相关信息为结构体中sym信息的符号表记录，并改变相关参数值int Position(char * name);/在符号表中搜索名字为name的符号表记录并返回该记录在符号表中的位置void Gen(op f_tmp, int l_tmp, int a_tmp)/在code数组中存储操作码为f_tmp,层差值为l_t

33、mp,偏移地址为a_tmp的目标机代码void Interpret();/目标代码翻译程序，按顺序解释执行code数组中存储的相关目标机代码int Base(int l);/寻找数据段静态链，指向定义直接外层的最新数据段基地址四、试验体会说起这次课程设计，我简直太有体会了，觉得想要做好这次课设真是要花很大的功夫。本来最开始做词法分析器和语法分析器觉得不算难，我基本参照书本就很好地完成了，很有成就感，沾沾自喜，觉得自己也不笨嘛。可是没想到到了真正做课设的时候，才明白为什么大家普遍认为编译原理比较难，课堂的知识我都认真听了，所以课本上的习题我可以独立完成，课本知识我也很好地理解了。可是最初看到辅助

34、的PPT时，郁闷至极，因为有些地方看都看不懂。我后来思考了下，觉得问题在于，课程设计考验的是我们对编译原理的整体理解，哪一个地方出现了问题，整个实现都会有问题。而关于理论的理解就相对容易一些。所以虽然我明白了编译原理中的一些理论，但是所需要的知识远远不够。语义分析、目标代码产生以及代码的解释执行，这才是真正考验人的水准和实力的，而这些相关知识分布在第六、七、八、九章，这部分恰恰很难。另外，对于PPT上的给的提示看不懂怎么办？很简单，一个字“问”，问同学问老师问大神均可，在我想破头也想不出来的时候，我就没有一个劲的钻死胡同，而是找了能力比较强的同学一起讨论。比如有关PPT上符号表处理以及目标代码产生的有关内容，我看得思维混乱，一头雾水，不耻上问之后总算是

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论