广工编译原理课程设计及实验报告.docx

编译原理课程设计

课程名称 编 译 原 理
题目名称 课 程 设 计
学生学院 计 算 机 学 院
专业班级
学 号
学生姓名
指导教师 蒋 艳 荣

2015 年 12 月 27 日
一、 实验要求
课内实验
对PL/0作以下修改扩充：
（1）增加单词：保留字 ELSE，FOR，TO，DOWNTO，RETURN
运算符 *=，/=，++，--，&，||，！
（2修改单词：不等号# 改为 <>
（3）增加条件语句的ELSE子句，要求：写出相关文法，语法图，语义规则。
将原本 条件语句 -> if条件 then 语句
改为 条件语句 -> if条件 then 语句 [else 语句]

1． 课程设计
基本内容（成绩范围：“中”、“及格”或“不及格”）
（1）扩充赋值运算：*= 和 /=
语句 -> ident *= 表达式
语句 -> ident /= 表达式

扩充语句（Pascal的FOR语句）:
①FOR <变量>:=<表达式> TO <表达式> DO <语句>
②FOR <变量>:=<表达式> DOWNTO <表达式> DO <语句>
其中，语句①的循环变量的步长为2，
语句②的循环变量的步长为-2。
（3）增加运算：++ 和 --。

选做内容（成绩评定范围扩大到：“优”和“良”）
（1）增加类型：① 字符类型； ② 实数类型。
（2）扩充函数：① 有返回值和返回语句；② 有参数函数。
（3）增加一维数组类型（可增加指令）。
（4）其他典型语言设施。
二、 实验环境及工具
源语言 ：PL0
目标语言：假想栈式计算机的汇编语言（C语言实现）
实现工具：codeblock
运行平台：Windows 10
三、 结构设计说明
（1）PL/0 语言编译程序结构
PL/0语言可看成是PASCAL语言的子集，它的编译程序是一个编译解释执行系统。PL/0的目标程序为假想栈式计算机的汇编语言，与具体计算机无关。
PL/0源程序
词法分析程序
语法语义分析程序
代码生成程序
表格管理程序
出错处理程序
目标程序
PL/0编译程序的结构图

（2）PL/0 语言编译程序总体流程
以下是编译程序的总体流程图，其中，PL/0编译程序的语法分析过程BLOCK是整个编译过程的核心，我们通过该流程图来弄清BLOCK过程在整个编译程序中的作用。

PL/0 的编译程序采用一趟扫描方式，以语法分析程序为核心，词法分析程序和代码生成程序都作为一个独立的过程，当语法分析需要读单词时就用词法分析程序，而当语法分析正确需生成相应的目标代码时，则调用代码生成程序。
此外，用表格管理程序建立变量，常量和过程标识符的说明与引用之间的信息联系。用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错误性质。
（3）各功能模块描述
过程或函数名
简要功能说明
pl0
主程序
error
出错处理，打印出错位置和错误编码
getsym
词法分析，读取一个单词
getch
漏掉空格，读取一个字符
gen
生成目标代码，并送入目标程序区
test
测试当前单词符号是否合法
block
分程序分析处理过程
enter
登录名字表
position(函数)
查找标识符在名字表中的位置
constdeclaration
常量定义处理
vardeclaration
变量说明处理
listode
列出目标代码清单
statement
语句处理
expression
表达式处理
term
项处理
factor
因子处理
condition
条件处理
interpret
对目标代码的解释执行程序
base(函数)
通过静态链求出数据区的基地址
四、 主要成分描述
① 符号表
在PL0中，使用以下数据结构存储符号表：
struct tablestruct
{
char name[al]; /*名字*/
enum object kind; /*类型：const，var，array or procedure*/
int val; /*数值，仅const使用*/
int level; /*所处层，仅const不使用*/
int adr; /*地址，仅const不使用*/
int size; /*需要分配的数据区空间，仅procedure使用*/
};
struct tablestruct table[txmax]; /*名字表*/

他是一个全程量一维数组TABLE。表中每个元素为记录型数据。
如果标识符被说明为常数，其属性值为常数值；如果标识符被说明成变量，其属性就是由层次和修正量（偏移量）组成的地址；如果标识符被说明为过程，其属性就是过程的入口地址及层次。
常数的值由程序正文提供，编译的任务就是确定存放该值的地址。我们选择顺序分配变量和代码的方法；每遇到一个变量说明，就将数据单元的下标加一（PL/0 机中，每个变量占一个存贮单元）。
开始编译一个过程时，要对数据单元的下标dx 赋初值，表示新开辟一个数据区。dx 的初值为3，因为每个数据区包含三个内部变量RA，DL 和SL。
② 运行时存储组织和管理
当源程序经过语法分析，如果没有发现错误，由编译程序调用解释程序，对存放在CODE中的目标代码从CODE[0]开始解释执行。
存放目标代码的数据结构：
struct instruction
{
enum fct f; /*虚拟机代码指令*/
int l; /*引用层与声明层层次差*/
int a; /*根据f的不同而不同*/
};
struct instruction code[cxmax];/*存放虚拟机代码的数组*/
当编译结束之后，记录源程序中标识符的TABLE表已经没用了，因此存储区只需要以数组CODE存放的只读目标程序和运行时的数据区S。S是由解释程序定义的一维整型数组。代码如下:
int p, b, t; /*指令指针，指令基址，栈顶指针*/
struct instruction i; /*存放当前指令*/
int s[stacksize]; /*栈*/
其中，有四个寄存器。分别为I指令寄存器，P程序地址寄存器，T栈顶寄存器，B基址寄存器。
对于源程序的每一个过程（包括主程序），在被调用时，首先在数据段中开辟三个空间，存放静态链SL、动态链DL和返回地址RA。
1. 静态链记录了定义该过程的直接外过程（或主程序）运行时最新数据段的基地址。
2. 动态链记录调用该过程前正在运行的过程的数据段基址。
3. 返回地址记录了调用该过程时程序运行的断点位置。对于主程序来说，SL、DL和RA的值均置为0。
静态链的功能是在一个子过程要引用它的直接或间接父过程（这里的父过程是按定义过程时的嵌套情况来定的，而不是按执行时的调用顺序定的）的变量时，可以通过静态链，跳过个数为层差的数据段，找到包含要引用的变量所在的数据段基址，然后通过偏移地址访问它。
③ 语法分析方法
PL/0编译程序的语法分析采用了自顶向下的递归子程序法。语法分析从读入第一个单词开始由开始符『程序』出发，沿语法描述图箭头所指方向进行分析。当遇到非终结符时，则调用相对应的处理过程，从语法描述图也就进入了一个语法单元，再沿当前所进入的语法描述图的箭头方向进行分析，当遇到描述图中是终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，则执行对应的语义程序（翻译程序）。再读入下一个单词继续分析。遇到分支点时将当前的单词与分支点上的多个终结符逐个比较，若都不匹配时可能是进入下一非终结符语法单位或是出错。
如果一个PL0语言程序的单词序列在整个语法分析中，都能逐个得到匹配，直到程序结束符『·』，这时说明所输入的程序是正确的。对于正确的语法分析进行对应的语义翻译，生成目标代码。
语法分析主要由分程序分析过程（BLOCK）常量定义分析过程（ConstDeclaration）、变量定义分析过程（Vardeclaration）、字符变量定义分析过程（Chardeclaration）、语句分析过程（Statement）、表达式处理过程（Expression）、项处理过程（Term）、因子处理过程（Factor）和条件处理过程（Condition）构成。这些过程在结构上构成一个嵌套的层次结构。

④ 中间代码表示
中间代码是是源程序的一种内部表示，复杂性介于源语言和目标机语言之间。
中间代码的表示方法有逆波兰式、三元式、树形、四元式等。
(1) 逆波兰记号是最简单的一种中间代码表示形式，早在编译程序出现之前，它就用于表示算术表达式。
后缀表示法表示表达式，其最大的优点是易于栈式计算机处理表达式。
(2) 每个三元式由三个部分组成：
算符op
第一运算对象ARG1
第二运算对象ARG2
运算对象可能是源程序中的变量，也可能是某个三元式的结果，用三元式的编号表示。
(3) 树形表示是三元式表示的翻版。
(4) 四元式是一种比较普遍采用的中间代码形式：
算符op
运算对象ARG1
运算对象ARG2
运算结果RESULT
五、 开发过程和完成情况
（1）增加单词：保留字 ELSE，FOR，TO，DOWNTO，RETURN
运算符 *=，/=，++，--，&，||，！
1.1修改symbol枚举
enum symbo
l{
nul, ident, number, plus, minus,
times, slash, oddsym, eql, neq,
lss, leq, gtr, geq, lparen,

rparen, comma, semicolon,period, becomes,
beginsym, endsym, ifsym, thensym, whilesym,
writesym, readsym, dosym, callsym, constsym,
varsym, procsym,elsesym,forsym,tosym,downtosym,returnsym,
muleqsym,deviesym,pplus,mminus,andsym,logical_or,logical_not,charsym,charvalue,
writecharsym,readcharsym
};
1.2 修改getSym(),增加以下语句
int getsym()
{
//乘等识别
else if(ch=='*')
{
getchdo;
if (ch=='=')
{
sym= muleqsym;
getchdo;
}
else
{
sym = nul;
}
}
.....
//除等识别
else if(ch=='/')
{
getchdo;
if (ch=='=')
{
sym= deviesym;
getchdo;
}
else
{
sym = nul;
}
}
//++、--识别
if (ch=='+')
{
getchdo;
if (ch=='+') // 自增检测
{
sym=pplus;
getchdo;
}
else
{
sym = plus;
}
}
else if (ch=='-')
{
getchdo;
if (ch=='-') // 自减检测
{
sym=mminus;
getchdo;
}
else
{
sym = minus;
}
}
1.3 修改init()，增加以下语句
void init()
{
...
ssym['&']=andsym;
ssym['!']=neq;
...
}
1.4 修改init()增加保留字识别
strcpy(&(word[i++][0]),"do");
strcpy(&(word[i++][0]),"downto");
strcpy(&(word[i++][0]),"else");
strcpy(&(word[i++][0]),"for");
strcpy(&(word[i++][0]),"return");
strcpy(&(word[i++][0]),"then");
strcpy(&(word[i++][0]),"to");
i = 0;
/*设置保留字符号*/
wsym[i++]=dosym;
wsym[i++]=downtosym;
wsym[i++] =elsesym;
wsym[i++]=forsym;
wsym[i++]=returnsym;
wsym[i++]=thensym;
wsym[i++]=tosym;
1.5 修改单词总数symnum，加2
#define NumOfKeywork 21 //21是完成时的状态
（2）修改单词：不等号# 改为 <>
2.1 修改getsym(),识别<>
getsym()
{
...
else if(ch=='<')
{
getchdo;
if(ch=='=') //小于等于
{
sym=leq;
getchdo;
}
else if(ch=='>') //不等于
{
sym=neq;
getchdo;
}
else
{
sym = lss;
}
}
...
}
(3)增加条件语句的ELSE子句，要求：写出相关文法，语法图，语义规则
3.1 文法
将原本 条件语句 -> if条件 then 语句
改为 条件语句 -> if条件 then 语句 [else 语句]

<条件语句> ::== if <条件> then <语句> [else <语句>]

3.2修改statement
else if(sym==ifsym) /*准备按照if语句处理*/
{
getsymdo;
memcpy(nxtlev,fsys,sizeof(bool)*symnum);
nxtlev[thensym]=true;
nxtlev[dosym]=true; /*后跟符号为then或do*/
conditiondo(nxtlev,ptx,lev); /*调用条件处理（逻辑运算）函数*/
if(sym==thensym)
{
getsymdo;
}
else
{
error(16); /*缺少then*/
}
cx1=codePointer; /*保存当前指令地址*/
gendo(jpc,0,0); /*生成条件跳转指令，暂写0*/
statementdo(fsys,ptx,lev); /*处理then后的语句*/

/*经statement处理后，cx为then后语句执行
完的位置，它正是前面未定的跳转地址*/
getsymdo;
if (sym==elsesym)
{
code[cx1].a=codePointer+1;
int jmpdx = codePointer;//记下jmp指令位置
gendo(jmp,0,0);
getsymdo;
statementdo(fsys,ptx,lev);
code[jmpdx].a = codePointer;
}
else
{
code[cx1].a=codePointer;
}
}
（4）扩充赋值运算：*= 和 /=
4.1 文法
语句 -> ident *= 表达式
语句 -> ident /= 表达式
4.2 符号识别（上面已经完成）
4.3 修改statement函数
if(sym==ident)
{
i=position(id,*ptx);
if(i==0)
{
error(11);
}
else
{
if(table[i].kind!=variable&&table[i].kind!=character)
{
error(12);
i=0;
}
else if (table[i].kind==variable)
{
getsymdo;
//如果是 := *= /=
if(sym==becomes||sym==muleqsym||sym==deviesym)
{
tempsym = sym;
//如果是 /=
if (sym==deviesym)
{
//将变量放到顶
gendo(lod,lev-table[i].level,table[i].adr);
}
getsymdo;

memcpy(nxtlev,fsys,sizeof(bool)* symnum);
expressiondo(nxtlev,ptx,lev);

if (tempsym==becomes)//如果是赋值
{
gendo(sto,lev-table[i].level,table[i].adr);
}
else if (tempsym==muleqsym)//如果是 *=
{
//将变量放到顶
gendo(lod,lev-table[i].level,table[i].adr);
//乘法运算
gendo(opr,0,4);
//将结果送到变量
gendo(sto,lev-table[i].level,table[i].adr);
}
else if (tempsym==deviesym)//如果是 /=
{
//除法法运算
gendo(opr,0,5);
//将结果送到变量
gendo(sto,lev-table[i].level,table[i].adr);
}
}
...
}
（5）扩充语句（Pascal的FOR语句）:
①FOR <变量>:=<表达式> TO <表达式> DO <语句>
②FOR <变量>:=<表达式> DOWNTO <表达式> DO <语句>
其中，语句①的循环变量的步长为2，
语句②的循环变量的步长为-2。

5.1 文法
for语句 ::== FOR <变量>:=<表达式> TO <表达式> DO <语句> |
FOR <变量>:=<表达式> DOWNTO <表达式> DO <语句>
5.2关键字识别
修改init()
void init()
{
...
strcpy(&(word[i++][0]),"for");
strcpy(&(word[i++][0]),"to");
strcpy(&(word[i+][0]),"do");
strcpy(&(word[i++][0]),"downto");
...
wsym[i++]=forsym;
wsym[i++]=dosym;
wsym[i++]=downtosym;
wsym[i++]=tosym;
...
}
5.3 语法语义解析
修改statement 增加for分支
int statement()
{
.....
else if (sym==forsym)
{
getsymdo;
if (sym==ident)
{
i=position(id,*ptx);
ifi==0)
{
error(11);//找不到标识符
}
else
{
if(table[i].kind!=variable) //如果不是变量
{
error(12);
i=0;
}
else
{
getsymdo;
if(sym==becomes)//如果是赋值
{
getsymdo;
expressiondo(nxtlev,ptx,lev);
//将栈顶表达式内容送到变量中
gendo(sto,lev-table[i].level,table[i].adr);

if (sym==tosym||sym==downtosym)
{
int jmp1,jmp2,jpc1;
tempsym = sym;

jmp1 = codePointer;
gendo(jmp,0,0);//jmp1,跳到判断处

//开始自增
jmp2 = codePointer
gendo(lod,lev-table[i].level,table[i].adr);
if (tempsym==tosym)
{
gendo(lit,0,tostep);
}
else
gendo(lit,0,downtostep);

gendo(opr,0,2);
gendo(sto,lev-table[i].level,table[i].adr);

code[jmp1].a = codePointer;
getsymdo;
expressiondo(nxtlev,ptx,lev);

//开始判断
gendo(lod,lev-table[i].level,table[i].adr);
if (tempsym==tosym)
{
gendo(opr,0,11);
}
else
{
gendo(opr,0,13);
}

jpc1 = codePointer;
gendo(jpc,0,0);//如果为假，跳到循环后面,否则执行后面语句

if (sym==dosym)
{
getsymdo;
statementdo(fsys,ptx,lev);
gendo(jmp,0,jmp2);//跳到自增指令
code[jpc1].a = codePointer;
}
else
error(27);
}
else
{
error(26);//to expected
}
}
}
}
}
}
.......
}
（6）增加运算：++ 和 --。
6.1 文法
<语句> ::== ++|-- ident
<语句> ::== ident ++|--
<因子>::== [ ++|-- ] ident
<因子>::== ident [ ++|-- ]
6.2 增加自增自减处理函数
int selfopr(int lev,int addr,int opration)
{
gendo(lod,lev,addr);
gendo(lit,0,1);
if (opration==pplus)
{
gendo(opr,0,2);
}
else{
gendo(opr,0,3);
}
gendo(sto,lev,addr);
return 0;
}
6.3 修改statement语句，增加i++ i--句式识别
int statement()
{
...
if(sym==ident)
{
....
else if (sym==pplus) // ident 后面跟 ++ 处理
{
selfopr(lev-table[i].level,table[i].adr,pplus);
getsymdo;
}
else if (sym==mminus) // -- 处理
{
selfopr(lev-table[i].level,table[i].adr,mminus);
getsymdo;
}
...
}
6.4 修改statement语句，增加、++ -- 前缀句式识别
int statement()
{
...
else if (sym==mminus||sym==pplus) //如果是 ++ 或 --
{
tempsym= sym;
getsymdo;
if(sym==ident)
{
i=position(id,*ptx);
if(i==0)
{
error(11);
}
else
{
if(table[i].kind!=variable)
{
error(12);
i=0;
}
else
{
selfopr(lev-table[i].level,table[i].adr,tempsym);
getsymdo;
}
}
}
else
{
error(12);
}

}
6.4 修改因子 ++ -- 前缀识别
int factor(bool*fsys,int *ptx,int lev)
{
int sopr = -1;
int i;
bool nxtlev[symnum];
testdo(facbegsys,fsys,24); /*检测因子的开始符好号*/
while(inset(sym,facbegsys)) /*循环直到不是因子开始符号*/
{
if (sym==mminus||sym==pplus)
{
sopr = sym;
getsymdo;
if(sym==ident) /*因子为常量或者变量*/
{
i=position(id,*ptx); /*查找名字*/
if(i==0)
{
error(11); /*标识符未声明*/
}
else
{
switch(table[i].kind)
{
case constant:/*名字为常量*/
error(28);
break;
case variable:
selfopr(lev-table[i].level,table[i].adr,sopr);//++ --处理
gendo(lod,lev-table[i].level,table[i].adr); /*找到变量地址并将其值入栈*/
break;
case procedur:
error(21);
break;
case character:
error(31);
break; }
}
getsymdo;
}
else
{error(29);
}
}
6.5 增加因子 ++ -- 后缀识别
6.5.1 增加新的数据结构，记录要自增或自减的变量
struct backpath
{int o; //++ 或 --
int lev; // 层次
int addr; //地址
}Info[50];
6.5.2 增加语句完成后的自增处理函数
//在statemtent之后调用
int backpath()
{
int i = 0;
for(;i
selfopr(Info[i].lev,Info[i].addr,Info[i].o);
}
infoindex = 0;
return 0;
}
6.5.3 修改statement函数
else if(sym==beginsym) /*准备按照复合语句处理*/
{
getsymdo;
memcpy(nxtlev,fsys,sizeof(bool)*symnum);
nxtlev[semicolon]=true;
nxtlev[endsym]=true;/*后跟符号为分号或end*/
/*循环调用语句处理函数，直到下一个符号不是语句开始符号或收到end*/
statementdo(nxtlev,ptx,lev);
backpath();
while(inset(sym,statbegsys)||sym==semicolon)
{
if(sym==semicolon)
{
getsymdo;
}
else
{
error(10);/*缺少分号*/
}
statementdo(nxtlev,ptx,lev);
backpath();
}
6.5.4 因子处理
修改factor函数
int factor()
{
if(sym==ident)
{
...
getsymdo;
if (sym==mminus||sym==pplus)
{
Info[infoindex].o = sym;
Info[infoindex].lev = lev-table[i].level;
Info[infoindex].addr =table[i].adr;
infoindex++;
getsymdo;
}
...
}
增加因子前缀集
facbegsys[pplus]=true;
facbegsys[mminus]=true;

(7) 增加字符类型
7.1 增加枚举变量
enum symbol{ ... charsym、charvalue ...}
enum object{
constant,
variable,
procedur,
character
};
7.2增加 关键字识别
strcpy(&(word[i++][0]),"char");
wsym[i++]=charsym;
7.3增加到声明符集
declbegsys[charsym]=true;
7.4增加字符识别
修改getsym()
...
else if (ch=='\'')

{
getchdo;
Tchar = ch;
getchdo;
if (ch!='\'')
{
error(30);
}
else
{
sym = charvalue;
getchdo;
}
}
7.5 增加字符声明函数
int chardeclaration(int * ptx,int lev,int * pdx)
{
if(sym==ident)
{ enter(character,ptx,lev,pdx);//填写名字表