编译原理上机实习指导书201511修改.doc

编译原理上机实习指导书(2015-11修改)
《编译原理上机实习》指导书
一、上机实习目的
理解编译程序的构造原理，掌握编译程序的构造方法及技术。通过实习，使学生既加深对编译原理基础理论的理解，又提高动手能力，特别是提高软件设计能力。
二、上机实习要求
在理解编译原理基本思想的基础上，选择一个自己熟悉的程序设计语言，完成编译程序的设计和实现过程。
编译程序的设计可以采用自顶向下和自底向上两种不同的方法。由于许多高级语言（如PASCAL，C）中的语法成分都是递归定义的，所以本实验要求学生采用递归下降分析技术，这是一种自顶向下的的编译方法，其基本思想是对语言的每个（或若干个）语法成分编制一个处理子程序，从处理<程序>这个语法成分的子程序开始，在分析过程中调用一系列过程或函数，对源程序进行语法和语义分析，直到整个源程序处理完毕为止。
本上机实习是为C语言(子集)设计一个编译程序，完成词法分析、语法分析、语义分析等功能，并生成某种机器上的目标代码(汇编语言)或中间代码(四元式)。
三、上机实习步骤
1．阅读《上机实习指导书》。
2．根据设计要求写算法，画程序框图
3．根据框图编写编译程序
4．输入编译程序并上机调试
5．撰写上机实习报告
四、上机实习内容
1、题目：C语言小子集编译程序的实现
2、C语言小子集的文法规则：

<程序>::＝main（）{<分程序>}
<分程序>::=<变量说明部分>；<语句部分>
<变量说明部分>::=<变量说明><标识符表>
<变量说明>::=int
<标识符表>::=<标识符表>，<标识符>
<标识符表>::=<标识符>
<标识符>::=<字母>
<标识符>::=<标识符><字母>
<标识符>::=<标识符><数字>
<语句部分>::=<语句部分>；<语句>|<语句>
<语句>::＝<赋值语句>|<条件语句>|<循环语句>|
<赋值语句>::=<标识符>=<表达式>
<条件>::=<表达式><关系运算符><表达式>
<表达式>::=<项>|<表达式><加法运算符><项>
<项>::=<因子>|<项><乘法运算符><因子>
<因子>::＝<标识符>|<常量>|(<表达式>)
<常量>::＝<无符号整数>
<无符号整数>::=<数字序列>
<数字序列>::=<数字序列><数字>
<数字序列>::=<数字>
<加法运算符>::＝+|-
<乘法运算符>::=*|／
<关系运算符>::＝<|>|!=|>=|<=|==
<复合语句>::={<语句部分>}
<语句1>::＝<语句>|<复合语句>
<条件语句>::=if（<条件>）<语句1>else<语句1>
<循环语句>::=while（<条件>）do<语句1>
<字母>::=a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
<数字>::=0|1|2|3|4|5|6|7|8|9

3、实现功能：
(1)词法分析
扫描源程序，根据词法规则，识别单词，填写相应的表。
(2)语法分析
对源程序作语法分析，确定是否属于C语言小子集，同时揭示出程序的内在结构。
(3)语法错误检查
根据C语言小子集的文法规则设置检测手段，通过查错子程序或一些查错语句，报告源程序出错位置、性质等，直至整个程序结束为止。
(4)语义分析及目标代码生成
在语法分析的基础上，进行语义分析，生成输入源程序的目标代码。输入源程序的目标代码可以建立在一个假想的处理机（虚拟机）上，或者以所学的汇编语言为基础，也可以生成四元式序列。

输入源程序样本：
main ()
{ int a,b,y,max;
a=10; b= ;
while (a>0)
{ b=a+b*a;
a=a-1
};
x=a+b; y=b+b;
if (x>y) max=x
else max=y
}

五、附录：PL0编译程序的实现

1． PL0概述
PL0语言是一种类PASCAL语言，是教学用程序设计语言，它比PASCAL语言简单，作了一些限制。PL0的程序结构比较完全，赋值语句作为基本结构，构造概念有顺序执行、条件执行和重复执行，分别由BEGIN/END、IF和WHILE语句表示。此外，PL0还具有子程序概念，包括过程说明和过程调用语句。在数据类型方面，PL0只包含唯一的整型，可以说明这种类型的常量和变量。运算符有+，-，*，/，=，<>，<，>，<=，>=，(，)。说明部分包括常量说明、变量说明和过程说明。

2． PL0语言的文法规则

<程序>::＝<分程序>．
<分程序>::=[<常量说明部分)；][<变量说明部分>；]{<过程说明部分>；}<语句部分>
<常量说明部分>::=const<常量定义>{，<常量定义>}
<常量定义>::＝<标识符>＝<无符号整数>
<无符号整数>::=<数字>{<数字>}
<变量说明部分>::=var<标识符>{<标识符>}
<标识符>::=<字母>{<字母>|<数字>}
<过程说明部分>::=<过程首部><分程序>
<过程首部>::=procedure<标识符>
<语句部分>::=<语句>|<复合语句>
<复合语句>::=begin<语句>{；<语句>}end
<语句>::＝<赋值语句>|<条件语句>|<当型循环语句>|<过程调用语句>|
<读语句>|<写语句>|<复合语句>|<空语句>
<赋值语句>::=<标识符>:=<表达式>
<条件>::=<表达式><关系运算符><表达式>|odd<表达式>
<表达式>::=[+|-]<项>|<表达式><加法运算符><项>
<项>::=<因子>|<项><乘法运算符><因子>
<因子>::＝<标识符>|<常量>|(<表达式>)
<常量>::＝<无符号整数>
<加法运算符>::＝+|-
<乘法运算符>::=*|／
<关系运算符>::＝<|>|<>|>=|<=|=
<条件语句>::=if<条件>then<语句>
<过程调用语句>::=call<标识符>
<当型循环语句>::=while<条件>do<语句>
<读语句>::=read(<标识符>{，<标识符>})
<写语句>::=write(<表达式>{，<表达式>})
<字母>::=a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
<数字>::=0|1|2|3|4|5|6|7|8|9

3． PL0编译程序的设计思想

编译程序的设计可以采用自顶向下和自底向上两种不同的方法。由于许多高级语言（如PASCAL，C）中的语法成分都是递归定义的，PL0也是如此，所以本实验采用递归子程序法，这是一种自顶向下的的编译方法，其基本思想是对源程序的每个（或若干个）语法成分编制一个处理子程序，从处理<程序>这个语法成分的子程序开始，在分析过程中调用一系列过程或函数，对源程序进行语法和语义分析，直到整个源程序处理完毕为止。

4．PL0编译程序的功能

(1)语法分析
对由PL／0语言编制的程序作语法分析，确定是否属于PL／0语言，同时揭示出程序的内在结构。
(2)语法错误检查
根据PL／0语言的文法规则设置检测手段，通过查错子程序和一些查错语句，报告源程序出错位置、性质等，直至整个程序结束为止。
(3)生成目标代码
PL／0语言的目标代码是建立在一个假想的处理机上，此处理机称为PL／0处理机。
(4)执行目标代码
PL／0处理机是一种假想的处理机，其目标代码不能在实际的机器上执行，故此编译程序设置了一个子程序，它对PL／0语言的目标代码逐条解释执行，最后得出所需结果。

5．PL／0编译程序的有关过程及函数

在PL／0语言的编译文本中，除了常量和变量说明外，共有18个相互嵌套或并列的过程(或函数)。现对这些过程和函数作扼要说明。
(1)error(n)：其功能是报告PL／0源程序的出错信息。n为错误类型号，共可查出36种错误。
(2)getsym：词法分析子程序。其功能为读单词。
getch：读字符子程序。它嵌套于读单词子程序中。
(3)gen(x，y，z)，伪代码生成子程序。其功能是根据不同的x、y、z生成不同的伪代码。x表示指令码，y表示层差，z表示位移量或数。
(4)test(sl，s2，n)：查错子程序。其功能是检测源程序中的语法错误。
(5)block(1ev，tx，fsys)：分程序处理模块。其功能为对分程序进行处理。lev表示层差，tx表示标识符表的下标，fsys是符号集，表示可能出现的符号。
分程序处理模块是整个编译程序的核心，它包含以下的过程和函数。
①enter(k)：其功能是造符号表table。k表示符号的类型，其取值范围是(constant， variable，proceable)，即此子程序对常量、变量和过程造符号表table，以备检查标识符是否说明过。
②position(id)：其功能是查符号表，它是一个函数。 id是所检查的标识符，若查到则给出标识符id在标识符表中的位置，否则给0。
③constdeclaration：常量造表子程序。其功能是为常量造一张常量表，内填常量名、常量值。它通过调用子程序enter(k)完成，此时k＝constant。
④vardeclaration：变量造表子程序。其功能是为变量造一张变量表，内填变量名、所处层号。它也是通过调用子程序enter(k)来完成的，此时k=variable。
⑤listcode，打印(伪)代码子程序。其功能是输出生成的目标代码。
⑥statement(fsys)：语句处理子程序。其功能是处理语句，它是递归调用的核心部分。其递归调用顺序如下：
expression(fsys)：处理算术表达式子程序；
term(fsys)：处理项子程序；
condition(fsys)：处理因子子程序。
(6)interpret，执行目标代码子程序。其功能是对编译过程中生成的目标代码(伪代码)逐条解释执行。
base(l)：提供计算静态链信息子程序。它为过程调用提供调用所需的基地址。
整个PL／0编译程序通过主程序调用分程序处理模块block，再通过block递归调用上述的子程序，达到对PL／0语言的程序进行编译的目的。

6．编译步骤

程序中用数组word存贮PL／0语言的所有保留字。保留字有begin、call、const、do、end、if、odd、procedure、read、then、var、while、write；
用数组swym存贮保留字所对应的符号表symbol中的符号；
用数组ssym存贮关系运算符及特殊符号+、-、*、/、(、)、=、，、<、>及；所对应的符号表symbol中的符号；
用数组mnemonic存贮目标代码的指令码部分。
其具体步骤如下：
①在主程序中给出编译程序所需的初始值。置字符字数cc、行长ll、代码分配下标cx、错误个数err等为0。调getsym读单词；
②调block模块，进入分程序处理；
③判断所读单词是否为常量说明符号constsym，是则转4），否则转5）。
④读单词并作常量说明处理；查所读单词是否为“，”，是则重复本步；否则判断此单词是否为“；”，是则读单词，否则给出出错信息。进行下一步；
⑤所读单词是否为变量说明符号variable，是则读单词并作变量说明处理，再读单词并判断是否为“，”，是则重复本步；否则判断此单词是否为“；”，是则读单词，否则给出出错信息。进行下一步；
⑥cxl:=cx，并生成jmp 0，0指令，判断所读单词是否为过程说明符号proceduresym，是则读单词转7），否则转11）；
⑦判断所读单词是否为标识符，是则转8），否则给出出错信息再进行下一步；
⑧标识符填表，再读单词。判断所读单词是否为“；”，是则读单词，否则给出出错信息。进行下一步；
⑨递归调用分程序处理子程序block；
⑩最近所读单词是否为“；”，是则继续读一单词，否则给出出错信息。转6）；
⑾code[cxl].a:=cx，生成分配局部变量指令，语句处理，生成opr 0，0指令；
⑿返回主程序，err是否为0，是则调子程序interpret，转13），否则给出出错信息，结束编译；
⒀解释执行生成的目标代码，列出结果。

PL／0编译程序及主要参数
1)PL／0编译程序
program plO(input，output，ff，fi，fw2)；{带有代码生成的PL／0编译程序}
label 99；
const norw＝13； {保留字个数}
txmax=100， {标识符表的长度}
nmax=14， {数中数字的最大个数}
a1=10； {标识符的长度}
amax＝20471；{最大地址}
levmax＝3； {程序体嵌套的最大深度}
cxmax＝200； {代码数组的大小}
writex=20；
type symbol=(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，dosym，callsym，constsym，varsym，procsym，readsym，writesym，upcomma) ；
alfa＝packed array[1..a1] of char；
object＝(constant，variable，proceable) ；
symset＝set Of symbol；
fct=(1it，opr，lod，sto，cal，int，jmp，jpc)；{functions}
instruction=packed record
f：fct ； {功能码}
l: 0..1evmax；{层}
a：0..amax； {相对地址}
end；
{lit 0，a ：取常数a
opr 0，a：执行运算a
lod l，a：取层差为l，相对地址为a的常量
sto l，a：存到层差为l，相对地址为a的变量
cal l，a：调用层差为l的过程
int 0，a：t寄存器增加a
jmp 0，a: 转移到指令地址a处
jpc 0，a：条件转移到指令地址a处}
var ff,fi：text； {输入文件名ff和fi}
fw2：text； {输出文件名fw2}
ch：char； {最近读到的字符}
sym：symbol； {最近读到的符号}
id：alfa； {最近读到的标识符}
num：integer； {最近读到的数}
cc：integer； {字符计数}
ll：integer； {行长}
wx：integer；
kk，err，cw：integer；
cx：integer； {代码分配下标}
line：array[1..81]of char；
a：alfa；
chwr：array[1..writex] of alfa；
code：array[0..cxmax] of instruction；
word：array[1..norw] of alfa；
wsym：array[1..norw] of symbol；
ssym：array[char] of symbol；
mnemonic：array[fct] of packed array[1..3] of char；
declbegsys，statbegsys，facbegsys：symset；
table：array[0..txmax] of record
name：alfa；
case kind：object of
constant：(val：integer)；
variable，proceable：(1evel，dr：integer)；
end；
procedure error(n:integer)； {出错显示子程序}
begin writeln(fw2，’****’,’’：cc，n：2)：
err:=err+1；
end；
procedure getsym； {读单词子程序}
var i，j，k：integer；
procedure getch; {读字符子程序}
begin if cc=ll then
begin if eof(ff) then
begin write(fw2，’program incompletet’)； goto 99；end；
ll:=O；cc:=0；write(fw2，cw：5，’ ’)；cw:=cw+1；
while not(eoln(ff)) do
begin ll:=ll+1 ；read(ff，ch) ；write(fw2，ch) ； line[ll]:=ch；
end；
writeln(fw2)；ll:=ll+1；read(ff，1ine[ll]) ；
end；
cc:=cc+l；ch:=line[cc] ；
end； {读字符子程序结束}
begin {读单词子程序开始}
while ch＝’ ’ do getch；
if ch in [’a’..’z’] then
begin kc:=0；
repeat if k<a1 then
begin k:=k+1；a[k]:=ch； end；
getch；
until not(ch in[’a’..’z’，’0’..’9’])；
if k>=kk then kk:=k
else repeat a[kk]:=’ ’ ；kk:=kk-1；
untll kk=k；
id:=a；i:=1；j:=norw；
repeat k=(i+j) div 2；
if id<=word[k] then j:=k-1；
if id>=word[k] then i:=k+1；
untll i>j；
if i-1>j then sym:=wsym[k]
e1se sym:=ident；
end {标识符或保留字处理结束}
else if ch in [’0’..’9’] then
begin {数处理}
k:=0；num:=0；sym:=number；
repeat num:=10*num+(Ord(ch)一Ord(’0’))； k:=k+1；getch；
until not(ch in[’0’..’9’]) ；
if k>nmax then error(30)
end {数处理结束}
e1se if ch＝’:’ then
begin getch；
if ch=’=’ then
begin sym:=becomes；getch； end
else sym:=nul；
end
else case ch of
’+’，’-’，’*’，’／’,’(’，’)’，’=’,’,’,’ ；’,’.’：begin sym:=ssym[ch] ；
getch；
end；
’>’：begin getch；
if ch=’=’ then begin sym:=geq；getch；end
else sym:=gtr；
end；
’<’：begin getch；
if ch=’=’ then begin sym:=leq；getch；end
else if ch=’>’ then
begin sym:=neq；getch；end
else sym:=lss；
end
end ； {case }
end； {读单词子程序结束}

procedure gen(x：fct；y，z：integer) ； {代码生成子程序}
begin if cx>cxmax then
begin write(’program too long’) ； goto 99 end；
with code[cx] do
begin f:=x；l:=y；a:=z end；
cx:=cx+1
end； {代码生成子程序结束}
procedure test(s1，s2：symset；n：integer) ；
begin if not(sym in s1) then
begin error(n)；s1:=s1+s2；
while not(sym in s1)do getsym
end；
end；
procedure block(1ev，tx：integer；fsys：symset)； {分程序处理模块}
var dx ：integer； {数据分配下标}
txO：integer； {起始标识符的下标}
cxO：integer； {起始代码的下标}
procedure enter(k：object)；{把object填入标识符表中}
begin tx：＝tx+1；
with table[tx] do
begin name:=id；kind:=k；
case kind of
constant：begin if num>amax then
begin error(30)；num:=0 ； end；
val:=num；
end；
variable：begin level:=levl；dr:=dx；dx:=dx+l；end；
proceable：level:=lev
end { case }
end
end； {填标识符表子程序结束}
function position(id：alfa)：integer； { 在标识符表中查标识符id }
var i：integer；
begin table[0].name:=id；i:=tx；
while table[I].name<>id do i:=i-1；
position:=i；
end； {position}
procedure constdeclaration； {常量说明处理子程序}
begin if sym=ident then
begin getsym；
if sym in [eql，becomes] then
begin if sym＝becomes then error(1)；
getsym；
if sym=number then
begin enter(constant) ；
getsym；
end
else error(2)
end
else error(3)
end else error(4)
end； {constdeclaration}
procedure vardeclaration； {变量说明处理子程序}
begin if sym=ident then
begin enter(variable) ；getsym； end
else error(4)
end；{ vardeclaration }
procedure listcode； {列出本程序体生成的代码子程序}
var i：integer；
begin for i:=cxO to cx-1 do
with code[i] do
writeln(fw2，i，mnemonic[i]：5，l:3，a：5)
end； {listcode }
procedure statement(fsys：symset)；{语句处理子程序}
var i，cxl，cx2．integer；
procedure expression(fsys:symset)； {表达式处理子程序}
var addop：symbol；
procedure term(fsys:symset) ； {项处理子程序}
var mulop：symbol；
procedure factor(fsys：symset)； {因子处理子程序}
var i：integer；
begin test(facbegsys，fsys，24) ；
while sym in facbegsys do
begin if sym=ident then
begin i:=position(id)；
if i=0 then error(11)
else with table[i] do
case kind of
constant：gen(1it，0，val)；
variable：gen(lod，lev-level，dr)；
proceable：error(21)
end；
getsym；
end
else
if sym=number then
begin if num>amax then
begin error(30) ；num:=O；end；
gen(lit，0，num)；getsym；
end else
if sym=lparen then
begin getsym；
expression([rparen]+fsys)；
if sym=rparen then getsym
else error(22)
end；
test(fsys，[1paren]，23)
end
end； {factor}
begin {项处理子程序开始}
factor(fsys+[times，slash]) ；
while sym in[times，slash] do
begin mulop:=sym；getsym；
factor(fsys+[times，slash]) ；
if mulop=times then
gen(opr，0，4)
else gen(opr，0，5)
end
end； {项处理子程序结束}
begin {表达式处理子程序开始)
if sym in [plus，minus] then
begin addop:=sym；getsym；
term(fsys+[plus，minus]) ；
if addop=minus then gen(opr，0，1)
end else term(fsys+[plus，minus])；
while sym in [plus，minus] do
begin add／p:=sym；getsym；
term(fsys+[plus，minus])；
if addop=plus then
gen(opr，0，2)
else gen(opr，0，3)
end
end；{exprssion}
procedure condition(fsys:symset)； {条件表达式处理子程序开始}
var relop:symbol；
begin if sym=oddsym then
begin getsym；expression(fsys) ；gen(opr，0，6)；
end else
begin expression([eql，neq，1ss，gtr，leq，geq]+fsys) ；
if not(sym in[eql，neq，1ss，leq，gtr，geq]) then error(20)
else begin relop:=sym；getsym； expression(fsys)；
case relop of