pl0扩展编译器_设计文档.docx

11061061 袁雅辉 北京航空航天大学

《编译技术》课程设计文 档

学号：
姓名：

2013年 11月 15日

目录
一．需求说明 2
1．文法说明 2
2．目标代码说明 11
二．详细设计 12
1．程序结构 12
2．类/方法/函数功能 13
3．调用依赖关系 14
4．符号表管理方案 15
5．存储分配方案 17
6. 解释执行程序* 17
7. 出错处理 22
三．操作说明 23
1．运行环境 23
2．操作步骤 23
四．测试报告 24
1．测试程序1 24
2．测试程序2 24
3. 测试程序3 25
4. 测试程序4 25
5. 测试程序5（以上为正确程序） 25
6. 测试程序6（以下是错误程序） 25
7. 测试程序7 26
8. 测试程序8 26
9. 测试程序9 26
10. 测试程序10 26
五．总结感想 27

图目录picture 1 4
picture 2 5
picture 3 6
picture 4 7
picture 5 8
picture 6 14
picture 7 16

一．需求说明
1．文法说明
1）获取的原文法：
<程序> ::= <分程序>.
<分程序> ::= [<常量说明部分>][<变量说明部分>]{[<过程说明部分>]| [<函数说明部分>]}<复合语句>
<常量说明部分> ::= const<常量定义>{,<常量定义>};
<常量定义> ::= <标识符>＝ <常量>
<常量> ::= [+| -] (<无符号整数>| <无符号实数>)|<字符>
<字符> ::= '<字母>' | '<数字>'
<字符串> ::= "{十进制编码为32,33,35-126的ASCII字符}"
<无符号整数> ::= <数字>{<数字>}
<无符号实数> ::= <无符号整数>.<无符号整数>
<标识符> ::= <字母>{<字母>|<数字>}
<变量说明部分> ::= var <变量说明> ; {<变量说明>;}
<变量说明> ::= <标识符>{, <标识符>} : <类型>
<类型> ::= <基本类型> | array '['<无符号整数>']' of <基本类型>
<基本类型> ::= integer | char | real
<过程说明部分> ::= <过程首部><分程序>{;<过程首部><分程序>};
<函数说明部分> ::= <函数首部><分程序>{;<函数首部><分程序>};
<过程首部> ::= procedure<标识符>'('[<形式参数表>]')';
<函数首部> ::= function <标识符>'('[<形式参数表>]')': <基本类型>;
<形式参数表> ::= <形式参数段>{; <形式参数段>}
<形式参数段> ::= [var]<标识符>{, <标识符>}: <基本类型>
<语句> ::= <赋值语句>|<条件语句>|<情况语句>|<过程调用语句>|<复合语句>|<读语句>|<写语句>|<for循环语句>|<空>
<赋值语句> ::= <标识符> := <表达式>| <函数标识符> := <表达式>|<标识符>'['<表达式>']':= <表达式>
<函数标识符> ::= <标识符>
<表达式> ::= [+|-]<项>{<加法运算符><项>}
<项> ::= <因子>{<乘法运算符><因子>}
<因子> ::= <标识符>|<无符号整数>| <无符号实数>|'('<表达式>')' | <函数调用语句>|<标识符>'['<表达式>']'
<函数调用语句> ::= <标识符>'('[<实在参数表>]')'
<实在参数表> ::= <实在参数> {, <实在参数>}
<实在参数> ::= <表达式>
<加法运算符> ::= +|-
<乘法运算符> ::= *|/
<条件> ::= <表达式><关系运算符><表达式>
<关系运算符> ::= <|<=|>|>= |=|<>
<条件语句> ::= if<条件>then<语句> | if<条件>then<语句>else<语句>
<情况语句> ::= case <表达式> of <情况表元素>{; <情况表元素>}end
<情况表元素> ::= <情况常量表> : <语句>
<情况常量表> ::= <常量>{, <常量>}
<for循环语句> ::= for <标识符> := <表达式> （downto | to） <表达式> do <语句>
<过程调用语句> ::= <标识符>'('[<实在参数表>]')'
<复合语句> ::= begin<语句>{; <语句>}end
<读语句> ::= read'('<标识符>{,<标识符>}')'
<写语句> ::= write'(' <字符串>,<表达式> ')'|write'(' <字符串>')'|write'('<表达式>')'
<字母> := a|b|c|d…x|y|z |A|B…|Z
<数字> ::= 0|1|2|3…8|9
2）由于原文法不存在左递归，因此不对文法进行改写。
3）文法解读

程序设计图1

picture 1

分程序设计图2

picture 2

语句设计图3

picture 3

因子、项、表达式设计图4

picture 4
其他语法设计图5

picture 5

<程序>::= <分程序>.
分析：程序的主体是分程序，“.”相当于结束符号，告诉编译器需要编译的程序到此为止；
范例：
const variable=4; .

<分程序> ::= [<常量说明部分>][<变量说明部分>]{[<过程说明部分>]| [<函数说明部分>]}<复合语句>
<常量说明部分> ::= const<常量定义>{,<常量定义>};
<常量定义> ::= <标识符>＝ <常量>
<常量> ::= [+| -] (<无符号整数>| <无符号实数>)|<字符>
<变量说明部分> ::= var <变量说明> ; {<变量说明>;}
<变量说明> ::= <标识符>{, <标识符>} : <类型>
<过程说明部分> ::= <过程首部><分程序>{;<过程首部><分程序>};
<过程首部> ::= procedure<标识符>'('[<形式参数表>]')';
<函数说明部分> ::= <函数首部><分程序>{;<函数首部><分程序>};
<函数首部> ::= function <标识符>'('[<形式参数表>]')': <基本类型>;
<复合语句> ::= begin<语句>{; <语句>}end

分析：分程序的组成成分以及对每个成分的语法构成。分程序可以有选择的由常量说明部分，变量说明部分，过程说明部分，函数说明部分构成，但必须包含复合语句。同时，各种成分的顺序不能调换，否则会产生错误。
范例：
Const a=1,b=2,c=3;
Var d,e,f:integer;
Procedure test;
Test 分程序;
Function mul(x,y:integer):integer;
Mul 分程序;
Begin
语句
End

<形式参数表> ::= <形式参数段>{; <形式参数段>}
<形式参数段> ::= [var]<标识符>{, <标识符>}: <基本类型>
分析：形式参数的语法形式规定，过程和函数都可以含有参数，形式参数表由一个或多个形式参数段组成，形式参数段就是对参数的描述。
范例：
Procedure test (var x,y:integer;a,b:char);

<类型> ::= <基本类型> | array '['<无符号整数>']' of <基本类型>
<基本类型> ::= integer | char | real
<字符> ::= '<字母>' | '<数字>'
<无符号整数> ::= <数字>{<数字>}
<无符号实数> ::= <无符号整数>.<无符号整数>
<标识符> ::= <字母>{<字母>|<数字>}
<字母> ::= a|b|c|d…x|y|z |A|B…|Z
<数字> ::= 0|1|2|3…8|9

分析：各种标识符和常量的产生过程。例如无符号整数，无符号实数，常量，变量，等等。
范例：
Const a = 123, b=’a’,c=12.45;
Var lab1,lab2:integer;cat1,cat2:char;
Var arr :array[5] of integer;

<语句>::= <赋值语句>|<条件语句>|<情况语句>|<过程调用语句>|<复合语句>|<读语句>|<写语句>|<for循环语句>|<空>

分析：语句的各种组成成分，且语句可以是空语句。
范例：请见如下的各种语句范例。

<赋值语句>::= <标识符> := <表达式>| <函数标识符> := <表达式>|<标识符>'['<表达式>']':= <表达式>

分析：赋值语句的作用是给变量或者函数或者数组元素赋值。
范例：
Var a: integer ; arr : array[10] of integer;
Function func;
a=12+3;
arr[0]=13*9;
func = 2+a;

<函数标识符> ::= <标识符>
分析：函数标识符除去意义与标识符不同以外，形成方式相同。

<表达式> ::= [+|-]<项>{<加法运算符><项>}
<项> ::= <因子>{<乘法运算符><因子>}
<因子> ::= <标识符>|<无符号整数>| <无符号实数>|'('<表达式>')' | <函数调用语句>|<标识符>'['<表达式>']'
<加法运算符> ::= +|-
<乘法运算符> ::= *|/
分析：表达式是一组由标识符和运算符组成的字符串。项是一个只含有乘法运算符合因子的表达式。因子是只含有无法分解的变量常量或由括号括起来的量。
范例：
a=2+3*2*b+(3-1);

<函数调用语句> ::= <标识符>'('[<实在参数表>]')'
<实在参数表> ::= <实在参数> {, <实在参数>}
<实在参数> ::= <表达式>

分析：函数调用语句是调用已经声明的函数，调用时要附上实在参数表。实在参数由表达式构成。
范例：前面声明了函数mul，那么我们调用这个函数
Mul(a, b);

<条件> ::= <表达式><关系运算符><表达式>
<关系运算符> ::= <|<=|>|>= |=|<>
<条件语句> ::= if<条件>then<语句> | if<条件>then<语句>else<语句>

分析：说明了条件语句的解析方法，但是只支持两种格式的条件语句，即if then 和if then else，且条件只能使用二元关系运算符连接成的表达式。关系运算符包括小于，小于等于，大于，大于等于，等于，不等于。
范例：
If a>10 then b++;
If b>3 then b=b+20 ; else b=b+10;
<情况语句> ::= case <表达式> of <情况表元素>{; <情况表元素>}end
<情况表元素> ::= <情况常量表> : <语句>
<情况常量表> ::= <常量>{, <常量>}
<常量> ::= [+| -] (<无符号整数>| <无符号实数>)|<字符>
<字符> ::= '<字母>' | '<数字>'
分析：case语句的构成。与c语言大致相同。
范例：
Case name of //name是变量
‘a’: write(‘a’);//常量可以是任意常量，例如 1，-2，1.234，等等。
‘b’: write(‘b’);
‘c’: write(‘c’);
‘d’: write(‘d’);
End

<for循环语句> ::= for <标识符> := <表达式>（downto | to） <表达式> do <语句>
分析：for循环语句，能顾递增或者递减，但是步长只能为1.
范例：
For i=1 to 5 do a=a+10;

<过程调用语句> ::= <标识符>'('[<实在参数表>]')'
<实在参数表> ::= <实在参数> {, <实在参数>}
<实在参数> ::= <表达式>
分析：过程的调用方法，需要提供实在参数表。
范例：
假设已经定义过程test
test ( x,y,a,b);//其中x，y是整型，a，b是字符型

<复合语句> ::= begin<语句>{; <语句>}end
分析：复合语句的格式，即begin end之间有若干语句。
范例：
Begin
a=110;
b=120;
c=a+b;
End

<读语句> ::= read'('<标识符>{,<标识符>}')'
分析：从标准输入读取字符串。
范例 ：
Read(a,b,c);//a,b,c都是整型的变量。

<写语句> ::= write'(' <字符串>,<表达式> ')'|write'(' <字符串>')'|write'('<表达式>')'
<字符串> ::= "{十进制编码为32,33,35-126的ASCII字符}"
分析：将字符串或值写到标准输出。
范例：
Write(”abc=”,a,b,c);

4）保留字表
单词名称
类别码
单词名称
类别码
单词名称
类别码
const
CONSTTK
end
ENDTK
to
TOTK
integer
INTTK
if
IFTK
downto
DOWNTOTK
Real
REALTK
then
THENTK
procedure
PROCETK
char
CHARTK
else
ELSETK
function
FUNCTK
Var
VARTK
do
DOTK
read
READTK
array
ARRAYTK
case
CASETK
write
WRITETK
of
OFTK
for
FORTK
begin
BEGINTK

2．目标代码说明
文法生成的目标码是p-code码，由interpret（）函数解释执行。
目标代码指令集
Lit
取语句中的整数、实数、字符或者常量放到栈顶
Opr
运算操作
Lod
找到变量的地址，并存入栈顶
Sto
将数据栈顶内容保存入变量
Cal
过程函数调用
Jmp
无条件跳转
Int
分配空间
Jpc
有条件跳转
LodArray
载入数组的第几个元素
RedI
读入integer型数据
RedR
读入real型数据
RedC
读入char型数据
StoPara
将函数的实参存入paraStack栈，用于以后保存到活动记录的形参的位置上
AssignPara
将paraStack栈中的实参值一一赋给活动记录的形参位置
WrtI
写入int型数据
WrtR
写入real型数据
WrtC
写入char型数据
LodRet
将函数的返回值保存到中间变量FuncReturn中
StoRet
把存在FuncReturn中的值放到栈顶，用于下一步的操作
LodAdd
把实参的地址放到栈顶
StoA
间接存
LDA
间接寻址
Template
载入数组模板，进行动态检查
StoArray
将数据栈顶内容保存至数组的某个元素
StoPara
将函数的实参存入paraStack栈，用于以后保存到活动记录的形参的位置上
Swi
处理case函数的跳转
Swr
处理case函数的跳转

二．详细设计
1．程序结构
扩充PL/0文法编译器工程可分为前端和后端两部分。
前端，包括词法分析，语法分析，符号表建立，语义分析和目标代码生成。根据前端功能，对应PL0类中几个主要函数，包括getsym（）、block（）、tableEnter（）、generate（）、和error（），分别负责词法分析，语法分析，符号表管理，代码生成及管理，错误处理等功能。
后端，包括目标代码的解释与执行。对应PL0中的interpret（）函数。
扩充PL0编译程序的组成如图1所示：

picture 6

2．类/方法/函数功能
关键函数：
///////////////////符号表的操作/////////////////////////////////////
int enterTable(char *name,varKind type,identKind kind,int level,int address,int arrayFlag,int AddFlag);
void backEnter(int tx,varKind type,identKind kind,int arrayFlag);//返填类型
void enterConst(varKind type,int Inum,double Fnum,char Cnum);
void enterArray(int tx,varKind type,int len);
void enterFunc(int tx,int Num,varKind ReturnVal);
void enterPro(int tx,int Num);
int DeclarePosition(char *name,int lev);//声明时查表
int StatementPosition(char *name,int lev);//语句部分查表
void printTableInfo();//打印符号表信息到tableInfo.txt

////////////////////词法分析////////////////////////////////////////////
int getSym();
int getch();
void error(int index);

/////////////////////语法分析///////////////////////////////////
void block(int level,int *address);//分程序
void ConstDeclaration(int level,int *address);//常量声明
void ConstDefine(int level);//常量定义
void VarDeclaration(int level,int *address);//变量声明
void VarDefine(int level,int *address);//变量定义
int FuncProDeclare(int level,int *address);//过程函数声明
int parameter(int level,int *address);//参数处理
void Sentence(int level);//语句处理
void IfSentence(int level);//if语句处理
void Condition(int level);//条件语句处理
void AssignSentence(int level);//赋值语句处理
void ReadSentence(int level);//读语句处理
void WriteSentence(int leve);//写语句处理
void MultiSentence(int level);//乘语句处理
void CaseSentence(int level);//情况语句处理
void ForSentence(int level);//for语句处理
void PopTable(int begin,int end);//弹出无效的符号表项
void CallFunc(int level);//函数调用
void CallPro(int level);//过程调用
void caselabel(int level);//case常量项处理
void onecase(int level);//case每一类的常量处理
void CaseSentence(int level);//case语句处理

/*对于需要运算的函数返回表达式结果类型*/
varKind factor();//因子处理
varKind expression();//表达式处理
varKind term();//项处理

//////////////////////////P-code指令处理部分////////////////////////////////////
void generate(fct funcName,int lev,double add);//指令生成
void interpret();//解释执行程序
void listcode();//列出代码
int base(int l);//找层次
3．调用依赖关系
扩充PL0编译器模块间调用依赖关系图如图2所示：

picture 7
4．符号表管理方案
符号表table定义如下
/*定义符号表的类型*/
typedef struct
{
char name[MAXLENGTH_NAME];//标识符的名字
varKind type;//标识符的基本类型:integer,char,real
identKind kind;//标识符的种类：变量，常量，函数，过程，函数和过程的参数
int arrayFlag;//数组标记,如果是1则表示是数组
int AddUse;//引用调用的标记，0表示传值调用，1表示传地址调用
int index; /* 如果是函数，则index用来检索这个函数在函数记录表中的位置
* 如果是数组，则index用来检索这个数组在数组记录表中的位置
* 如果是常量，则index用来检索这个常量在常量记录表中的位置
* 如果是过程，则index用来检索这个过程在过程记录表中的位置
*/
int level;//层次
int address;//偏移

}tabStruct;
static tabStruct Table [200];//符号表

/*定义函数类型结构*/
typedef struct
{
int paraNum;//定义函数的参数个数
varKind ReturnVal;//定义函数的返回值类型
}funcStruct;
funcStruct funcTable[50];//定义函数的记录表

/*定义过程的类型结构*/
typedef struct
{
int paraNum;//定义过程的参数个数
}proStruct;
proStruct proTable[50];//定义过程的记录表
/*数组对应的记录表类型*/

typedef struct
{
varKind type;//数组的基本类型
int len;//数组的长度
}arrStruct;
static arrStruct arrayTable[100];//定义数组的记录表

/*定义常量记录表类型*/
typedef struct
{
varKind type;//定义常量的类型:integer,char,real
/*分别定义几种类型常量的值*/
int valueI;
char valueC;
double valueF;
}constStruct;
constStruct constTable[100];//定义常量的记录表
符号表管理算法如下
///////////////////符号表的操作/////////////////////////////////////
int enterTable(char *name,varKind type,identKind kind,int level,int address,int arrayFlag,int AddFlag);//登记符号表
void backEnter(int tx,varKind type,identKind kind,int arrayFlag);//返填类型
void enterConst(varKind type,int Inum,double Fnum,char Cnum);//登记常量
void enterArray(int tx,varKind type,int len);//登入数组
void enterFunc(int tx,int Num,varKind ReturnVal);//登入函数名
void enterPro(int tx,int Num);//登入过程名
int DeclarePosition(char *name,int lev);//声明时查表
int StatementPosition(char *name,int lev);//语句部分查表
void printTableInfo();//打印符号表信息到tableInfo.txt
5．存储分配方案
运行栈以数组的形式运行。
通过栈顶指针的移动，栈顶数据的加载和保存来运行程序。
double s[10000];//运行栈
double paraStack[20];//保存实参的栈
int paraT=0;//控制实参栈的栈顶指针

int j;//中间变量
int t;//栈顶指针
int p;//保存下一条指令的地址
int b=0;//当前运行的分程序的数据区的基地址
instruction i;//当前要执行的指令
6. 解释执行程序*
解释执行根据产生的p-code代码解释执行程序，用case语句确定指令并执行
/*解释执行P-code代码*/
void interpret()
{

int tempI;
double tempR;
char tempC;
int k,buf;
double FuncReturn;

t=0;
b=0;
p=0;
for(j=0;j<500;j++)
s[j]=0;

do
{
i=codeTable[p];
p++;
switch (i.f)
{
case Lit: //取语句中的整数、实数、字符或者常量放到栈顶
t++;
s[t]=i.a;
break;
case Opr://运算操作
switch((int)(i.a))
{
case 0://返回上一个调用的位置
t=b-1;
p=(int)s[t+4];
b=(int)s[t+2];
break;
case 1://栈顶单元的值取反
s[t]=-s[t];
break;
case 2://加法（栈顶加次栈顶，保存至栈顶）
t--;
s[t]=s[t]+s[t+1];
break;
case 3:// 减法（次栈顶减栈顶，保存至栈顶）
t--;
s[t]=s[t]-s[t+1];
break;
case 4://乘法（次栈顶乘以栈顶，保存至栈顶）
t--;
s[t]=s[t]*s[t+1];
break;
case 5://除法（次栈顶除以栈顶，保存至栈顶）
t--;
s[t]=s[t]/s[t+1];
break;
case 6://逻辑运算：相等比较，将结果（0或1）保存至栈顶
t--;
if(s[t]==s[t+1])
s[t]=1;
else
s[t]=0;
break;
case 7://不等
t--;
if(s[t]!=s[t+1])
s[t]=1;
else
s[t]=0;
break;
case 8://大于
t--;
if(s[t]>s[t+1])
s[t]=1;
else
s[t]=0;
break;
case 9://大于等于
t--;
if(s[t]>=s[t+1])
s[t]=1;
else
s[t]=0;
break;
case 10://小于
t--;
if(s[t]<s[t+1])
s[t]=1;
else
s[t]=0;
break;
case 11://小于等于
t--;
if(s[t]<=s[t+1])
s[t]=1;
else
s[t]=0;
break;
case 12://整数除法
t--;
s[t]=(int)((int)s[t]/(int)s[t+1]);
break;
default:
break;
}
break;
case Lod://找到变量的地址，并存入栈顶
t++;
s[t]=s[base(i.l)+(int)i.a];
break;
case LodArray://载入数组的第几个元素
t++;
s[t-1]=s[base(i.l)+(int)i.a+(int)s[t-1]];
t--;
break;
case Sto://将数据栈顶内容保存入变量
s[base(i.l)+(int)i.a]=s[t];
t--;
break;
case StoArray://将数据栈顶内容保存至数组的某个元素
s[base(i.l)+(int)i.a+(int)s[t-1]]=s[t];
t--;
break;
case StoPara://将函数的实参存入paraStack栈，用于以后保存到活动记录的形参的位置上
paraStack[paraT]=s[t];
paraT++;
t--;
break;
case AssignPara://将paraStack栈中的实参值一一赋给活动记录的形参位置上
buf=t+5;
paraT=0;
for(k=0;k<(int)i.a;k++)
{
s[buf]=paraStack[k];
buf++;
}
break;
case Cal://过程函数调用
s[t+1]=base(i.l);//动态链
s[t+2]=b;//静态链
s[t+4]=p;//下条语句地址
b=t+1;
p=(int)i.a;
break;
case Int://分配空间
t=t+(int)i.a;
break;
case Jmp://无条件跳转
p=(int)i.a;
break;
case Jpc://有条件跳转
if(((int)s[t])==0)
{
p=(int)i.a;
t--;
}
break;
case RedI://读入integer型数据
scanf("%d",&tempI);
s[base(i.l)+(int)i.a]=tempI;
break;
case RedR://读入real型数据
scanf("%f",&tempR);
s[base(i.l)+(int)i.a]=tempR;
break;
case RedC://读入char型数据
scanf("%c",&tempC);
s[base(i.l)+(int)i.a]=tempC;
break;
case WrtI:
printf("%d",(int)s[t]);
t++;
break;
case WrtR:
printf("%lf",s[t]);
t++;
break;
case WrtC:
printf("%c",(char)s[t]);
t++;
break;
case LodRet://将函数的返回值保存到中间变量FuncReturn中
t++;
s[t]=FuncReturn;
break;
case StoRet:/