当前位置：文档之家› 编译原理课设报告

编译原理课设报告

编译原理

课程设计报告

班级：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描述（扩充的巴克斯范式表示法）

→ program ；

→ [][][]

→ const {,};

→ :=

→ var {,};

→ procedure （[{,}]）;{;}

→ begin {;}end

→ :=

|if then [else ]

|while do

|call （[{,}]）

|read ({，})

|write ({,})

→ |odd

→ [+|-]{}

→ {}

→||()

→ =|<>|<|<=|>|>=

→ +|-

→ *|/

→ l{l|d} （注：l表示字母）

→ d{d}

注释：

：程序；：块、程序体；：常量说明；：常量；：变量说明；：分程序；：复合语句；：语句；：表达式；：条件；：项；：因子；：加法运算符；：乘法运算符；：关系运算符。

假想目标机的代码

LIT 0 ，a 取常量a放入数据栈栈顶

OPR 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的指令

RED L ，a 读数据并存入变量（相对地址为a，层次差为L）

WRT 0 ，0 将栈顶内容输出

其中：F段代表伪操作码

L段代表调用层与说明层的层差值

A段代表位移量（相对地址）

进一步说明：

INT：为被调用的过程（包括主过程）在运行栈S中开辟数据区，这时A段为所需数据单元个数（包括三个连接数据）；L段恒为0。

CAL：调用过程，这时A段为被调用过程的过程体（过程体之前一条指令）在目标程序区的入口地址。

LIT：将常量送到运行栈S的栈顶，这时A段为常量值。

LOD：将变量送到运行栈S的栈顶，这时A段为变量所在说明层中的相对位置。

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的词法分析程序GetSym()是一个独立的过程，其功能是为语法分析提供单词用的，是语法分析的基础，它把输入的字符串形式的源程序分割成一个个单词符号。为此PL/0编译程序设置了三个变量如下：

SYM ：存放每个单词的类别，用内部编码形式表示。

ID ：存放用户所定义的标识符的值。即标识符字符串的机内表示。

NUM ：存放用户定义的数。

单词的种类有五种。

基本字：也可称为保留字或关键字，如BEGIN ，END ，IF ，THEN 等。运算符：如：+、-、*、／、∶=、#、＞=、＜=等。

标识符：用户定义的变量名、常数名、过程名。

常数：如：10，25，100等整数。

界符：如：'，'、'.'、'；'、'('、')'等。

如果我们把基本字、运算符、界符称为语言固有的单词，而对标识符、常数称为用户定义的单词。那么经词法分析程序分出的单词，对语言固有的单词只给出类别存放在SYM 中，而对用户定义的单词(标识符或常数)既给类别又给值，其类别放在SYM 中，值放在ID 或NUM 中，全部单词种类由编译程序定义的纯量类型SYMBOL 给出，也可称为语法的词汇表。

词法分析程序GETSYM 将完成下列任务：

(1) 滤空格：空格在词法分析时是一种不可缺少的界符，而在语法分析时则是无用的，所以必须滤掉。

(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程序为例构造其语法分析树

语法调用关系图如下：

具体语法结构如图所示：

由于语义分析是嵌套在相关语法分析的处理函数中的具体语句，因此不在此一一列举，以if then [else ]为例，当语法语义正确时，就生成相应语句功能的目标代码。并在code数组中存储相关的目标机代码。当正常执行完上述代码后，按顺序生成相关的目标机代码，并存储到相应的code 数组单元中。

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

注：

PL/0编译程序语法、语义分析的的核心程序是BLOCK过程，在BLOCK过程内又定义了许多嵌套及并列的过程。

在过程BLOCK内对说明部分及程序体部分的分析说明如下：

(1) 说明部分的分析

说明部分的处理任务就是对每个过程的说明对象造名字表，填写所在层次、标识

符的属性和分配的相对位置等。标识符的属性不同时，所需要填写的信息也有所不同。登录信息是调用ENTER过程完成的。

(2) 过程体的分析

程序的主体是由语句构成的。处理完过程的说明后就处理由语句组成的过程体，从语法上要对语句逐句分析。当语法正确时就生成相应语句功能的目标代码。当遇到标识符的引用时就调用POSITION函数查TABLE表，看是否有过正确的定义，若已有，则从表中取相应的有关信息，供代码的生成用。若无定义则出错。

4、错误处理

PL/0编译程序对语法错误的处理采用两种办法：

(1) 对于一些易于校正的错误，如丢了逗号、分号等，则指出出错位置，并加以校正。校正的方式就是补上逗号或分号。

(2) 对某些错误编译程序难于确定校正的措施，为了使当前的错误不致影响整个程序的崩溃，把错误尽量局限在一个局部的语法单位中。这样就需跳过一些后面输入的单词符号，直到读入一个能使编译程序恢复正常语法分析工作的单词为止。

在本次实验课程设计中，不准备在错误处理方面做非常详细的功能实现，只做了简单的错误位置说明和错误实现。

5、目标代码解释执行时的存储分配

解释程序定义了4个寄存器：

(1) I：指令寄存器。存放着当前正在解释的一条目标指令。

(2) P：程序地址寄存器。指向下一条要执行的目标程序的地址(相当目标程序CODE数组的下标)。

(3) T：栈顶寄存器。由于每个过程当它被运行时，给它分配的数据空间(下边称数据段)可分成两部分。

静态部分：包括变量存放区和三个联系单元(联系单元的作用见后)。

动态部分：作为临时工作单元和累加器用。需要时随时分配，用完后立即释放。栈顶寄存器T指出了当前栈中最新分配的单元(T也是数组S的下标)。

(4)B：基址寄存器。指向每个过程被调用时，在数据区S中给它分配的数据段起始地址，也称基地址。

为了实现对每个过程调用时给它分配数据段，也就是对即将运行的过程所需数据段进栈；过程运行结束后释放数据段，即该数据段退栈；以及嵌套过程之间对标识符引用的寻址问题。每个过程被调用时，在栈顶分配三个联系单元，这三个单元存放的内容分别为：

(1) SL：静态链：它是指向定义该过程的直接外过程(或主程序)运行时最新数据段的基地址。

(2) DL：动态链：它是指向调用该过程时正在运行过程的数据段基地址。

(3) RA：返回地址：记录调用该过程时目标程序的断点，即当时的程序地址寄存器P的值。也就是调用过程指令的下一条指令的地址。

数据空间只需以数组CODE存放的只读目标程序和运行时的数据栈S。S是由解释程序定义的一维整型数组。由于PL/0语言的目标程序是一种假想的栈式计算机的汇编语言，仍用PASCAL语言解释执行。解释执行时的数据空间S为栈式计算机的存储空间。遵循后进先出规则，对每个过程(包括主程序)当被调用时，才分配数据空间，退出过程时，则所分配的数据空间被释放。

解释程序根据待翻译的目标机代码（三地址语句代码）中相关的F段中的操作码，L段中调用层与说明层的层差值以及A段中位移量（相对地址），对数据栈stack以及相关寄存器进行操作，当P寄存器（存放下一条要执行的指令地址）为0时结束解释程序，至此编译完成。

三、函数说明

//子程序过程，将下一输入字符读到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(char* &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位置处开始，得到一个非空白的词素，并将返回信息

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);

//对照文法定义中产生式 →program ；对从文件指针fp所指向的文件中start位置处开始进行语法分析

bool BlockDo(FILE *fp, int &start, int &end, token & sym);

//对照文法定义中产生式[][][]对从文件指针fp 所指向的文件中start位置处开始进行语法分析并产生相关的目标机代码

bool CondeclDo(FILE *fp, int &start, int &end, token & sym);

//对照文法定义中产生式 →const {,};对从文件指针fp 所指向的文件中start位置处开始进行语法分析并产生相关的目标机代码

bool ConstDo(FILE *fp, int &start, int &end, token & sym);

//对照文法定义中产生式 → :=

对从文件指针fp所指向的文件中start位置处开始进行语法分析

bool VardeclDo(FILE *fp, int &start, int &end, token & sym);

//对照文法定义中产生式 → var {,};

对从文件指针fp所指向的文件中start位置处开始进行语法分析

bool ProcDo(FILE *fp, int &start, int &end, token & sym);

//对照文法定义中产生式 → procedure

（[{,}]）;{;}

对从文件指针fp所指向的文件中start位置处开始进行语法分析

bool BodyDo(FILE *fp, int &start, int &end, token & sym);

//对照文法定义中产生式 → begin {;}end

对从文件指针fp所指向的文件中start位置处开始进行语法分析

bool StatementDo(FILE *fp, int &start, int &end, token & sym);

//对照文法定义中的产生式