实验报告
课程名称 编译原理
题目名称 PL/0编译器的扩充
学生学院 计算机学院
专业班级计算机科学与技术12(4)
学 号 3112005901
学生姓名 柏石先
指导教师 李杨
2014 年 12 月 20日
一、 实验目的与要求
对PL/0作以下修改扩充:
(1) 增加单词:保留字 ELSE,FOR,STEP,UNTIL,DO,RETURN
运算符 *=,/=,&,||,!
(2)修改单词:不等号# 改为 <>
(3)增加条件语句的ELSE子句,要求:写出相关文法,语法描述图,语义描述图。
二、 实验环境与工具
1、源语言:PL/0语言,PL/0语言是PASCAL语言的子集,它的编译程序是一个编译解析执行系统,后缀名为.PL0;
2、目标语言:生成文件后缀为*.COD的目标代码
3、实现平台:Borland C++Builder 6
4、运行平台:Windows 8.1
三、 设计方案
1、 结构设计说明
(1)PL/0 语言编译器
PL/0语言可看成是PASCAL语言的子集,它的编译程序是一个编译解释执行系统。PL/0的目标程序为假想栈式计算机的汇编语言,与具体计算机无关。
(2)PL/0编译程序的语法分析过程BLOCK是整个编译过程的核心。这里根据编译程序的总体流程图,来弄清BLOCK过程在整个编译程序中的作用。总流程图如下图所示:
PL/0 的编译程序采用一趟扫描方式,以语法分析程序为核心,词法分析程序和代码生
成程序都作为一个独立的过程,当语法分析需要读单词时就用词法分析程序,而当语法分析
正确需生成相应的目标代码时,则调用代码生成程序。此外,用表格管理程序建立变量,常
量和过程标识符的说明与引用之间的信息联系。用出错处理程序对词法和语法分析遇到的错
误给出在源程序中出错的位置和错误性质。
(3)各功能模块描述
2、主要成分描述
1符号表
为了组成一条指令,编译程序必须知道其操作码及其参数(数或地址)。这些值是由编译程序本身联系到相应标识符上去的。这种联系是在处理常数、变量和过程说明完成的。为此,标识符表应包含每一标识符所联系的属性;如果标识符被说明为常数,其属性值为常数值;如果标识符被说明成变量,其属性就是由层次和修正量(偏移量)组成的地址;如果标识符被说明为过程,其属性就是过程的入口地址及层次。常数的值由程序正文提供,编译的任务就是确定存放该值的地址。我们选择顺序分配变量和代码的方法;每遇到一个变量说明,就将数据单元的下标加一(PL/0 机中,每个变量占一个存贮单元)。开始编译一个过程时,要对数据单元的下标dx 赋初值,表示新开辟一个数据区。dx 的初值为3,因为每个数据区包含三个内部变量RA,DL 和SL。
2运行时存储组织和管理
对于源程序的每一个过程(包括主程序),在被调用时,首先在数据段中开辟三个空间,存放静态链SL、动态链DL和返回地址RA。静态链记录了定义该过程的直接外过程(或主程序)运行时最新数据段的基地址。动态链记录调用该过程前正在运行的过程的数据段基址。返回地址记录了调用该过程时程序运行的断点位置。对于主程序来说,SL、DL和RA的值均置为0。静态链的功能是在一个子过程要引用它的直接或间接父过程(这里的父过程是按定义过程时的嵌套情况来定的,而不是按执行时的调用顺序定的)的变量时,可以通过静态链,跳过个数为层差的数据段,找到包含要引用的变量所在的数据段基址,然后通过偏移地址访问它。
在过程返回时,解释程序通过返回地址恢复指令指针的值到调用前的地址,通过当前段基址恢复数据段分配指针,通过动态链恢复局部段基址指针。实现子过程的返回。对于主程序来说,解释程序会遇到返回地址为0的情况,这时就认为程序运行结束。
解释程序过程中的base函数的功能,就是用于沿着静态链,向前查找相差指定层数的局部数据段基址。这在使用sto、lod、stoArr、lodArr等访问局部变量的指令中会经常用到。
类PCODE代码解释执行的部分通过循环和简单的case判断不同的指令,做出相应的动作。当遇到主程序中的返回指令时,指令指针会指到0位置,把这样一个条件作为终至循环的条件,保证程序运行可以正常的结束。
3语法分析方法
语法分析子程序采用了自顶向下的递归子程序法,语法分析同时也根据程序的语义生成相应三元代码,并提供了出错处理的机制。语法分析主要由分程序分析过程(BLOCK)、参数变量分析过程(ParaDeclaration)、参数变量处理过程(ParaGetSub)、数组处理过程(ParaGetSub)、常量定义分析过程(ConstDeclaration)、变量定义分析过程(Vardeclaration)、语句分析过程(Statement)、表达式处理过程(Expression)、项处理过程(Term)、因子处理过程(Factor)和条件处理过程(Condition)构成。这些过程在结构上构成一个嵌套的层次结构。除此之外,还有出错报告过程(Error)、代码生成过程(Gen)、测试单词合法性及出错恢复过程(Test)、登录名字表过程(Enter)、查询名字表函数(Position)以及列出类 PCODE代码过程(Listcode)作过语法分析的辅助过程。
4中间代码表示
中间代码是是源程序的一种内部表示,复杂性介于源语言和目标机语言之间。
中间代码的表示方法有逆波兰式、三元式、树形、四元式等。
(1) 逆波兰记号是最简单的一种中间代码表示形式,早在编译程序出现之前,它就用于表示算术表达式。
后缀表示法表示表达式,其最大的优点是易于栈式计算机处理表达式。
(2) 每个三元式由三个部分组成:
A. 算符op
B. 第一运算对象ARG1
C. 第二运算对象ARG2
运算对象可能是源程序中的变量,也可能是某个三元式的结果,用三元式的编号表示。
(3) 树形表示是三元式表示的翻版。
(4) 四元式是一种比较普遍采用的中间代码形式:
算符op,运算对象ARG1,运算对象ARG2,运算结果RESULT
四、 开发过程和完成情况
(一)增加单词:保留字 ELSE,FOR,STEP,UNTIL,DO , RETURN
运算符 *=,/=,&,||,!
新增6个保留字和5个运算符,合计11个单词。
其中保留字ELSE,FOR,STEP,UNTIL,DO, RETURN 分别对应ELSESYM,FORSYM,STEPSYM,
UNTILSYM,DOSYM,RETURNSYM;
运算符 *= ,/= ,& ,|| , ! 分别对应
TIMESBECOMES, SLASHBECOMES, ANDSYM, ORSYM, NOTSYM。
注:要求只做词法分析部分,不做语义分析处理,实验的结果只是识别新增的保留字和运算符,并且将其打印显示出来。
1.1保留字
typedef enum { 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, PROGSYM,
ELSESYM, FORSYM, STEPSYM, STEPSYM, RETURNSYM,
TIMESBECOMES, SLASHBECOMES, ANDSYM, ORSYM, NOTSYM
} SYMBOL;
char *SYMOUT[] = {"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", "PROGSYM",
"ELSESYM", "FORSYM", "STEPSYM", "STEPSYM", "RETURNSYM",
"TIMESBECOMES", "SLASHBECOMES", "ANDSYM", "ORSYM", "NOTSYM"
};
strcpy(KWORD[ 1],"BEGIN"); strcpy(KWORD[ 2],"CALL");
strcpy(KWORD[ 3],"CONST"); strcpy(KWORD[ 4],"DO");
strcpy(KWORD[ 5],"ELSE");
strcpy(KWORD[ 6],"END");
strcpy(KWORD[ 7],"FOR");
strcpy(KWORD[ 8],"IF");
strcpy(KWORD[ 9],"ODD"); strcpy(KWORD[ 10],"PROCEDURE");
strcpy(KWORD[ 11],"PROGRAM"); strcpy(KWORD[12],"READ");
strcpy(KWORD[13],"RETURN");
strcpy(KWORD[14],"STEP");
strcpy(KWORD[15],"THEN");
strcpy(KWORD[16],"UNTIL");
strcpy(KWORD[17],"VAR");
strcpy(KWORD[18],"WHILE"); strcpy(KWORD[19],"WRITE");
WSYM[ 1]=BEGINSYM; WSYM[ 2]=CALLSYM;
WSYM[ 3]=CONSTSYM; WSYM[ 4]=DOSYM;
WSYM[ 5]=ELSESYM; /*增加保留字符号elsesym*/
WSYM[ 6]=ENDSYM;
WSYM[ 7]=FORSYM;
WSYM[ 8]=IFSYM;
WSYM[ 9]=ODDSYM; WSYM[ 10]=PROCSYM;
WSYM[ 11]=PROGSYM; WSYM[12]=READSYM;
WSYM[13]=RETURNSYM;
WSYM[14]=STEPSYM;
WSYM[15]=THENSYM;
WSYM[16]=UNTILSYM;
WSYM[17]=VARSYM;
WSYM[18]=WHILESYM; WSYM[19]=WRITESYM;
SSYM['+']=PLUS; SSYM['-']=MINUS;
SSYM['*']=TIMES; SSYM['/']=SLASH;
SSYM['(']=LPAREN; SSYM[')']=RPAREN;
SSYM['=']=EQL; SSYM[',']=COMMA;
SSYM['.']=PERIOD;
SSYM[';']=SEMICOLON; SSYM['&']=ANDSYM;
SSYM['!']=NOTSYM;
在void STATEMENT(SYMSET FSYS,int LEV,int &TX){}函数中增加:
case FORSYM:
GetSym();
Form1->printfs("保留字:FORSYM~~~~");
break;
case STEPSYM:
GetSym();
Form1->printfs("保留字:STEPSYM~~~~");
break;
case UNTILSYM:
GetSym();
Form1->printfs("保留字:UNTILSYM~~~~");
break;
case RETURNSYM:
GetSym();
Form1->printfs("保留字:RETURNSYM~~~~");
break;
case DOSYM:
GetSym();
Form1->printfs("保留字:DOSYM~~~~");
break;
1.2运算符
1.2.1在GetSym()函数中在相应位置增加下面所示的语句:
else
if (CH==':') {
GetCh();
if (CH=='=') { SYM=BECOMES; GetCh(); }
else SYM=NUL;
}
else
if(CH == '*'){
GetCh();
if(CH == '='){
SYM = TIMESBECOMES;
GetCh();
}else SYM=SSYM['*'];
}
else
if(CH == '/'){
GetCh();
if(CH == '='){
SYM = SLASHBECOMES;
GetCh();
}else SYM=SSYM['/'];
}
else /* THE FOLLOWING TWO CHECK WERE ADDED
BECAUSE ASCII DOES NOT HAVE A SINGLE CHARACTER FOR <= OR >= */
if (CH=='<') {
GetCh();
if (CH=='=') { SYM=LEQ; GetCh(); }
else if(CH=='>'){ SYM=NEQ; GetCh(); } //不等号加
else SYM=LSS;
}
else
if (CH=='>') {
GetCh();
if (CH=='=') { SYM=GEQ; GetCh(); }
else SYM=GTR;
}
else
if (CH=='&') {
SYM=ANDSYM;
GetCh();
}
else
if (CH=='|') {
GetCh();
if (CH=='|') {
SYM=ORSYM;
GetCh();
}
else Error(19);
}
else
if (CH=='!') {
SYM=NOTSYM;
GetCh();
}
else { SYM=SSYM[CH]; GetCh(); }
1.2.2在void STATEMENT(SYMSET FSYS,int LEV,int &TX){}函数中增加:
case TIMESBECOMES:
GetSym();
Form1->printfs("运算符:*= ~~~~");
break;
case SLASHBECOMES:
GetSym();
Form1->printfs("运算符: /= ~~~~");
break;
case ANDSYM:
GetSym();
Form1->printfs("运算符:& ~~~~");
break;
case ORSYM:
GetSym();
Form1->printfs("运算符:|| ~~~~");
break;
case NOTSYM:
GetSym();
Form1->printfs("运算符:! ~~~~");
break;
1.3保留字的个数
原保留字个数是14,故const NORW = 14; /* # OF RESERVED WORDS */
因为新增加保留字5个,故应改为:
const NORW = 19; /* # OF RESERVED WORDS */
1.4单词总数
原单词总数是33,故所有“i<33” (i实际上是指单词总数)
因为新增加单词10个,故应改为“i<43”。
为了方便以后新增加单词,特加入了常量const WNUM = 43;然后把所有的43替换成了WNUM,以后要增加单词,就可以直接修改该值,不必再重新把所有的值找出来做替换。
2.修改单词:不等号# 改为 <>
(1)把源代码中的程序段 SSYM['#']=NEQ; 删除或注释消去。
(2)在GetSym()过程中把分析到的<>定义为不等号#,从“<”切入修改。
else /* THE FOLLOWING TWO CHECK WERE ADDED
BECAUSE ASCII DOES NOT HAVE A SINGLE CHARACTER FOR <= OR >= */
if (CH=='<') {
GetCh();
if (CH=='=') { SYM=LEQ; GetCh(); }
else if(CH=='>'){ SYM=NEQ; GetCh(); } //更改不等号为“<>”
else SYM=LSS;
}
3.增加条件语句的ELSE子句,要求:写出相关文法,语法图,语义规则。
(1)相关文法
G(S): S→if S else S | if S | a
(2)语法图
(3)语义规则
(4)代码修改
在void STATEMENT(SYMSET FSYS,int LEV,int &TX)中加入ELSE的实现语句
case IFSYM:
GetSym();
/* 条件语句*/
CONDITION(SymSetUnion(SymSetNew(THENSYM,DOSYM),FSYS),LEV,TX);
if (SYM==THENSYM) GetSym();
else Error(16);
CX1=CX; GEN(JPC,0,0);
STATEMENT(FSYS,LEV,TX);
if (SYM==ELSESYM) /* 如果THAN后面跟ELSE,ELSE可有可无,不影响IF语句 */{
GetSym();
CX2=CX;
GEN(JMP,0,0);/*无条件跳转语句*/
CODE[CX1].A=CX; /*cx即为else语句的位置,回填之前的JPC语句跳转的语句*/
STATEMENT(FSYS,LEV,TX); /*else中的语句体*/
CODE[CX2].A=CX; /*执行完ELSE中的语句体后的地址,把它回填JMP中的跳转地址*/
}
else /*如果than语句后面没有发现else*/{
CODE[CX1].A=CX; /*执行JPC语句跳转到此地址,当前地址为then后面Statement语句执行完的地址*/
}
break;
一、 实验结果
1. 测试用例说明:
实例代码:可测试实验中所有增加的内容。(使用的测试用例:E01.PL0)
PROGRAM E01;
VAR A,B,C;
BEGIN
B:=8;
C:=2;
READ(A);
IF A<>1 THEN
WRITE(B)
ELSE
WRITE(C);
FOR;
DO;
UNTIL;
RETURN;
*=;
/=;
&;
||;
!;
2. 实验结果及目标代码生成情况
0 JMP 0 1
1 INI 0 6
2 LIT 0 8
3 STO 0 4
4 LIT 0 2
5 STO 0 5
6 OPR 0 16
7 STO 0 3
8 LOD 0 3
9 LIT 0 1
10 OPR 0 9
11 JPC 0 16
12 LOD 0 4
13 OPR 0 14
14 OPR 0 15
15 JMP 0 19
16 LOD 0 5
17 OPR 0 14
18 OPR 0 15
19 OPR 0 0
结果截图:
二、 心得体会
本次实验在理解课程内容的基础上,总的来说难度不算很大。
其中增添保留字和运算符以及修改单词是学习编译程序的基本操作,易于理解,因为只涉及到词法分析,只要识别新增的保留字和运算符并打印显示出来就算完成。
实现单词对应的扩展功能则比较麻烦,需要不断的调试,直到保证语法单词检测结果正确才能够完成。头一次实验不是十分理解,经过老师的讲解和提醒总算有了清晰的基本思路。虽然在调试实验ELSE字句功能的时候遇到不少小错误,在和同学探讨和认真分析后,最终找到了解决方案。
在实验课程中,本人能够善于思考,勇于创新,例如,在单词总数的问题上,为了方便以后新增加单词,加入了常量const WNUM = 43;然后把所有的43替换成了WNUM,以后要增加单词,就可以直接修改该值,不必再重新把所有的值找出来做替换。
通过这次实验,我对编译原理这门课程有了更深刻的理解,同时也提升了自己的代码分析能力和动手编程能力。