《编译原理课程设计报告》由会员分享，可在线阅读，更多相关《编译原理课程设计报告（17页珍藏版）》请在金锄头文库上搜索。
1、1 实验要求 基本内容1) 增加单词：保留字 ELSE，REPEAT，DOWHILE，RETURN运算符 +=，-=，+，-2) 修改单词：不等号# 改为 := TO DO FOR := DOWNTO DO 其中，语句的循环变量的步长为 2，语句的循环变量的步长为-2。 选做内容1) 增加运算：+ 和 -。2) 增加类型： 字符类型； 实数类型。3) 扩充函数： 有返回值和返回语句； 有参数函数。4) 增加一维数组类型（可增加指令） 。5) 其他典型语言设施。 设计方案1. 概述：源、目标语言：编译程序编绎的源程序是 PL0，程序产生的目标代码是一个假想栈式计算机的汇编语言.称为类 PCODE
2、 指令代码 ,指令格式格式如下:其中 F 代表功能码,L 表示层次差,A 表示位移量,不同指令其含义有所区别。PL/0 语言是 Pascal 语言的一个子集，这里分析的 PL/0 的编译程序包括了对 PL/0 语言源程序进行分析处理、编译生成类 PCODE 代码，并在虚拟机上解释运行生成的类 PCODE 代码的功能。PL/0 语言编译程序采用以语法分析为核心、一遍扫描的编译方法。词法分析和代码生成作为独立的子程序供语法分析程序调用。语法分析的同时，提供了出错报告和出错恢复的功能。在源程序没有错误编译通过的情况下，调用类 PCODE 解释程序解释执行生成的类 PCODE 代码。实现工具(平台)
3、，运行平台：编译器实现工具和运行平台程序用 C+语言编写,在 C+ Builder 平台下运行。F L A22. 结构设计说明： PL/0 的编译过程采用一趟扫描方式，以语法分析为核心，词法分析程序和代码生成程序都作为一个独立的过程，当语法分析需要读入单词时就调用词法分析程序，而当语法分析正确需生成相应的目标代码时，则调用代码生成程序。此外，用表格管理程序建立变量、常量和过程标识符的说明与引用之间的信息联系。用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错误性质。当源程序编译正确时，PL/0 编译程序自动调用解释执行程序，对目标代码进行解释执行，并按用户程序的要求输入数据和
4、输出运行结果。本程序编译和解释执行的结构图如下所示： 主要成分描述1. 符号表在编译过程中常用到的表格包括常量表、变量表(标识符表)、保留字表、数组表和过程信息表等。统称为符号表，又称为单词属性字表；符号表可以用来收集符号属性、是上下文语义的合法性检查的依据、也作为目标代码生成阶段地址分配的依据。从编译系统的造表过程来区分，符号表可分为静态表（是事先构造好表，编译程序需要使用时直接查找。如：保留字、标准函数名表等）和动态表（编译程序在编译过程中根据需要构造的表。如：标识符表、符号表、循环表、数组信息表和过程表等） 。符号表在编译过程的重要作用主要表现在两个方面：辅助语义的正确性和检查辅助目标代
5、码的生成。符号表有若干个表项组成，每个表项有单词的名字域和属性域两部分。符号表应包括符号的所有属性，这样可以有助于编译程序的语义检查和生成可运行的目标代码，其主要内容包括：符号的名字、符号的类型、地址码、符号的类型、地址码、数组的维数、下标的类型或过程参数等等。符号表的组织可分为符号表的总统组织、符号表项的排列、关键字域的组织、其它域的组织和下推链组织；符号表的管理包括符号表的初始化、符号的登录、符号的查找、符号表中分程序结构层次分管理。2. 运行时存储组织和管理程序运行时的存储区常常划分成：目标区、静态数据区、栈区和堆区。数据空间的使用和管理方法分成三种：静态存储分配、栈式动态存储分配和堆式
6、动态存储分配。在简单栈式存储分配的实现中常常使用两个指针指示栈最顶端的数据区，一个是 SP（总是指向现行过程活动记录的起点） ，另一个是 TOP(始终指向已占用的栈顶单元) ，嵌套过程语言的栈式实现只是增加了非局部变量的存取，其方法有在过程活动记录中增设存取链和在每进入一个过程后，在建立它的活动记录的同时建立一张嵌套层次显示表 display。在分程序结构的存储管理中要注意分清楚各过程体的活动记录和 SP 及 TOP 指针的始末位置。在过程调用过程中有可3能有参数的传递，其路径有：传值，传地址，传名及宏扩展等。3. 语法分析方法语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出的
7、单词符号序列是否是给的文法的正确句子（程序） ，目前语法分析常用的方法由自顶向下分析和自底向上分析两大类。自顶向下分析包括确定分析和不确定分析，自底向上分析包括算符优先分析和 LR 分析。自顶向下的不确定分析方法是带回溯的分析方法，实际上是一种穷举的试探方法，因此效率低。代价高。确定的自顶向下分析方法，是从文法的开始符号出发，考虑如何根据当前的输入符号（单词符号）惟一地确定选用哪个产生式替换相应非终结符以往下推导，或如何构造一棵相应的语法树。确定的自顶向下分析方法只适合于 LL(1)文法，一个文法需经过计算它的 FIRST、FOLLOW、SELECT 集合来判断其是否为 LL(1)文法，有些文
8、法也可以通过踢去左公因子和消除左递归来转换成 LL(1)文法。确定的自顶向下分析方法有递归子程序法（对应文法中每个非终结符编写一个递归过程）和预测分析方法（由预测分析程序、先进后出栈和预测分析表组成） 。简单优先分析法的基本思想是对一个文法按一定原则求出该文法所有符号即包括终结符和非终结符之间的优先关系，按照这种关系确定归约过程中的句柄，它的归约过程实际上是一种规范归约；其关键是构造优先关系表的构造。自底向上分析法的关键问题是在分析过程中如何确定句柄，LR 分析法正是给出一种能根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的 k 个（k=0）符号就可惟一确定分析器的动作是移进还
9、是归约和用哪个产生式归约，因而也就能惟一地确定句柄。LR 分析法的归约过程是规范推导的逆过程，所以 LR 分析过程是一种规范归约过程。一个 LR 分析器是由总控程序、分析表或分析函数和分析栈三部分组成的，LR 分析过程主要是对文法的产生式进行排序、计算各非终结符的 FIRST 和 FOLLOW 集、构造文法关于 LR（k）的项目集族（若有冲突的话要用相关的办法解决） 、根据项目集族构造相应的 LR(k) 分析表、对输入的字符串进行分析，看是属于接受态还是出错。4. 中间代码表示中间代码长见的形式有逆波兰记号（后缀式） 、三元式、四元式和树形表示。逆波兰记号式最简单的一种中间代码表示形式，这种表
10、示法将运算对象写在前面，把运算符号写在后面，其最大的优点是易于计算机处理表达式。利用一个栈，自左至右扫描算术表达式（后缀表示） 。每碰到运算对象，就把它推进栈；碰到运算符，若该运算符是二目的，则对栈顶部的两个运算对象实施该运算，并将运算结构代替这两个运算对象而进栈。若是一目运算符，则对栈顶元素执行该运算，并以运算结果代替该元素进栈。最后的结果留在栈顶。每个三元式 3 个组成部分式：算符 op，第 1 运算对象 ARG1，和第 2 运算对象 ARG2。对于一目算符 op，只需算用一个算符对象，多目算符可用若干个相继的三元式表示。树形表示是三元式表示的翻版。四元式的四个组成成分式：算符 op，第一
11、和第二运算对象 ARG1 和 ARG2 及运算结果 RESULT。运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的临时变量。四元式之间的联系式铜鼓临时变量实现的。 开发过程和完成情况1) 总述设计过程中添加保留字、运算符号都要对全局变量进行相关的修改。 （修改部分用粗体字标识出来）设计增加了的 9 个保留字，因而 const NORW = 23; 接下来添加修改语法词汇表：Typedef enumNULBECOMES, PLUSEQL,MINUSEQL,DOUBLEPLUS,DOUBLEMINUS,BEGINSYM, PROGSYM,4ELSESYM,REPEATSYM,DOW
12、HILESYM,RETURNSYM, FORSYM,TOSYM,DOWNTOSYM,LBRACKETSYM,RBRACKETSYM SYMBOL;char*SYMOUT=NUL.BECOMES,PLUSEQL,MINUSEEQL,DOUBLEPLUS,DOUBLEMINUS, BEGINSYM, PROGSYMELSESYM,REPEATSYM,DOWHILESYM,RETURESYM,FORSYM,TOSYM,DOWNTOSYM,LBRACKETSYM,RBRACKETSYM;相应的与字符表个数有关的所有程序都要修改，一共加了 13 个单词，例如：SYMSET SymSetNULL() SY
13、MSET S; int i,n,k;S=(SYMSET)malloc(sizeof(int)* 46);for (i=0; i”首先将“#”的内码表示 SSYM#=NEQ 删除,然后在 GetSym 添加识别的“) SYM=NEQ; GetCh(); /不等于由改为DOWHILE语法分析图如下：1 添加 REPEAT，DOWHILE 到词汇表作为保留字2 STATBEGSYSREPEATSYM=1;3 在 void STATEMENT(SYMSET FSYS,int LEV,int &TX) /*STATEMENT*/ .case REPEATSYM:CX1=CX; GetSym();STAT
14、EMENT(SymSetUnion(SymSetNew(SEMICOLON,DOWHILESYM),FSYS),LEV,TX);while (SymIn(SYM, SymSetAdd(SEMICOLON,STATBEGSYS) if (SYM=SEMICOLON) GetSym();else Error(10);STATEMENT(SymSetUnion(SymSetNew(SEMICOLON,DOWHILESYM),FSYS),LEV,TX);if (SYM=DOWHILESYM) GetSym();else Error(33); /*repeat 中少了 dowhile*/CONDITIO
15、N(FSYS,LEV,TX);CX2=CX; GEN(JPC,0,0);GEN(JMP,0,CX1);CODECX2.A=CX;break;d) 增加赋值运算符+=，-=以及+,-首先给这四个运算符命名，分别命为 PLUSEQL,MINUSEQL，和 DOUBLEPLUS, DOUBLEMINUS以便读单词时填写符号表。分析+=、-=、+、-，当遇到+= 时，根据 TABLE 表中的 C 的地址把 C 的值放在栈顶，再把栈顶元素和次栈顶元素相加，然后保 C 的值。 -=的原理与+=相同。当遇到+ 时，先取常数 1 的值到栈顶，然后第二步根据 TABLE 表中的 C 地址把 C 的值放在7栈顶，再把栈顶元素和次栈顶元素相加，然后保存 C 的值。-的原理与+相同。在 PL/0 程序中的修改如下： 词法分析 GetSym 中添加：void GetSym() else if(CH=+)/处理以+开头的GetCh( );if (CH=) SYM=PLUSBECOMES; GetCh(); else if(CH=+) SYM=DOUBLEPLUS; GetCh(); else SYM=PLUS; else if(CH=-)/处理以-开头的GetCh();if (CH=) SYM=MINUSBECOMES; GetCh(); el
