《编译原理上机实习》指导书
一、上机实习目的
理解编译程序的构造原理,掌握编译程序的构造方法与技术。通过实习,使学生既加深对编译原理基础理论的理解,又提高动手能力,特别是提高软件设计能力。
二、上机实习要求
在理解编译原理基本思想的基础上,选择一个自己熟悉的程序设计语言,完成编译程序的设计和实现过程。
编译程序的设计可以采用自顶向下和自底向上两种不同的方法。由于许多高级语言(如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,x,y,max;
a=10; b=1;
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 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 eql:gen(opr,0,8); neq:gen(opr,0,9); lss:gen(opr,0,10); geq: gen(opr,0,11) ; gtr:gen(opr,0,12) ; 1eq:gen(opr,0,13) ; end end end end; {condition} begin {语句处理子程序开始} if sym=ident then {赋值语句处理} begin i:=position(id) ; if i=0 then error(11) else if table[i].kind<>variable then begin error(12) ; {对非变量赋值} i:=0; end; getsym; if sym=becomes then getsym else error(13) ; expression(fsys) ; if i<>0 then with table[i] do gen(sto,1ev-1evel,dr) end else if sym=readsym then {读语句处理} begin getsym; if sym<>lparen then error(34) e1se repeat getsym; if sym=ident then i:=position(id) else i:=0; if i=0 then error(35) else with table[i] do begin gen(opr,0,16) ; gen(sto,1ev-1evel,dr) ; end; getsym; until sym<>comma; if sym<>rparen then begin error(33): while not(sym in fsys) do getsym; end else getsym end else if sym=writesym then {写语句处理} begin getsym; if sym=1paren then begin repeat getsym; if sym=upcomma then begin getsym; if sym=ident then i:=position(id) else i:=0; if i=0 then error(11) else chwr[wx]:=id; wx:=wx+1; getsym; if sym=upcomma then getsym else error(36); getsym; expression([rparen,comma]+fsys) ; gen(opr,0,14) ; end else begin getsym; expression([rparen,comma]+fsys); gen(opr,0,14) ; end until sym<>comma; if sym<>rparen then error(33) e1se getsym end; gen(opr,0,15) ; end else if sym=callsym then {过程语句处理} begin getsym; if sym<>ident then error(14) else begin i:=position(id); if i=0 then error(11) else with table[i] do if kind=proceable then gen(cal,1ev-level,dr) else error(15) ; getsym; end end e1se if sym=ifsym then {条件语句处理} begin getsym; condition([thensym,dosym]+fsys); if sym=thensym then getsym else error(16); cxl:=cx;gen(jpc,0,0) ; statement(fsys) ; code[cxl].a:=cx; end e1se if sym=beginsym then {复合语句处理) begin getsym; statement([semicolon,endsym]+fsys) ; while sym in [semicolon]+statbegsys do begin if sym=semicolon then getsym else error(10); statement([semicolon,endsym]+fsys) end; if sym=endsym then getsym else error(17) end e1se if sym=whilesym then {循环语句处理} begin cxl:=cx;getsym; condition([dosym]+fsys); cx2:=cx;gen(jpc,0,0) ; if sym=dosym then getsym else error(18) ; statement(fsys) ; gen(jmp,0,cxl) ; code[cx2].a:=cx; test(fsys,[],19) ; end; end;{语句处理子程序结束} begin {分程序处理子程序开始} dx:=3; txO:=tx; table[tx].dr:=cx; gen(jmp,0,0) ; if 1ev>levmax then error(32); repeat if sym=constsym then {常量说明部分处理} begin getsym; repeat constdeclaration; While sym=comma do While sym=comma do begin getsym; constdeclaration;end; begin getsym; constdeclaration;end; if sym=semicolon then getsym else error(5); until sym<>ident until sym<>ident end; {常量说明部分处理结束} end; {常量说明部分处理结束} if sym=varsym then {变量说明部分处理} begin getsym; repeat vardeclaration; if sym=varsym then {变量说明部分处理} begin getsym; repeat vardeclaration; while sym=comma do begin getsym;vardeclaration; end; if sym=semicolon then getsym else begin error(5) ;getsym;end; until sym<>ident; end; {变量说明部分处理结束) while sym=procsym do {过程说明部分处理} begin getsym; if sym=ident then begin enter(proceable) ;getsym;end else error(4) ; if sym=semicolon then getsym else begin error(5) ;getsym;end; block(lev+1,tx,[semicolon]+fsys) ; if sym=semicolon then begin getsym; test(statbegsys+[ident,procsym],fsys,6) end else error(5) end; {过程说明部分处理结束} test(statbegsys+[ident],declbegsys,7); until not(sym in declbegsys) ; code[table[tx0].dr].a:=cx; with table[tx0] do dr:=cx; {代码开始地址} cxO:=cx;gen(int,0,dx); statement([semicolon,endsym]+fsys); gen(opr,0,0); {返回} test(fsys,[],8) ; listcode; end; {分程序处理结束} procedure interpret; {执行目录代码子程序} const stacksize=500; var p,b,t:integer;{p:程序地址寄存器, b:基地址寄存器, t:栈顶地址寄存器} i:instruction; {指令寄存器} s:array[1..stacksize] of integer;{数据存储} function base(l:integer):integer; var b1:integer: begin b1:=b; {顺静态链求层差为1的基地址} while l>0 do begin b1:=s[bl] ;l:=l-1;end; base:=b1 end; {base} begin writeln(’start PL/0’) ; t:=0;b:=1;p:=0;wx:=1; s[1]:=0;s[2]:=0;s[3]:=0; repeat i:=code[p] ;p:=p+1; with i do case f of lit:begin t:=t+1;s[t]:=a;end; opr:case a of {运算} 0:begin t:=b-1;p:=s[t+3] ;b:=s[t+2] end;{返回} 1: s[t]:=-s[t] ; 2:begin t:=t-1;s[t]:=s[t]+s[t+1] end; 3:begin t:=t-1;s[t]:=s[t]-s[t+1] end; 4:begin t:=t-1;s[t]:=s[t]*s[t+1] end; 5:begin t:=t-1;s[t]:=s[t] div s[t+1] end; 6: s[t]:=ord(odd(s[t])); 8:begin t:=t-1;s[t]:=ord(s[t]=s[t+1]) end; 9:begin t:=t-1;s[t]:=ord(s[t]<>s[t+1]) end; 10:begin t:=t-1;s[t]:=ord(s[t] 11:begin t:=t-1;s[t]:=ord(s[t]>=s[t+1]) end; 12:begin t:=t-1;s[t]:=ord(s[t]>s[t+1]) end; 13:begin t:=t-1;s[t]:=ord(s[t]<=s[t+1]) end; 14:begin writeln(fw2);write(fw2,chwr[wx]) ; write(fwZ,s[t]) ;t:=t-1;wx:=wx+1; end; 15:writeln(fw2) ; 16:begin t:=t+1; read(fi,s[t]) ;end; end; lod: begin t:=t+1;s[t]:=s[base(l)+a] end; sto:begin s[base(l)+a]:=s[t] ; t:=t-1; end; cal: begin {generte new block mark} s[t+1]:=base(l) ;s[t+2]:=b; s[t+3]:=p;b:=t+l;p:=a; end; int:t:=t+a; jmp:p:=a; jpc:begin if s[t]=0 then p:=a; t:=t - 1; end end {with,case } until p=0; write(’ end PL/0’); end; {interpret} begin {主程序开始} reset(ff);reset(fi);rewrite(fW2) ; for ch:=’a’ to ’;’ do ssym[ch]:=nul; word[1]:=’begin ’; word[2]:=’call ’; word[3]:=’const ’; word[4]:=’do ’; word[5]:=’end ’; word[6]:=’if ’; word[7]:=’odd ’; word[8]:=’procedure ’; word[9]:=’read ’; word[10]:=’then ’; word[11]:=’var ’; word[12]:=’while ’; word[13]:=’write ’; wsym[1]:=beginsym; wsym[2]:=callsym; wsym[3]:=constsym; wsym[4]:=dosym; wsym[5]:=endsym; wsym[6]:=ifsym; wsym[7]:=oddsym; wsym[8]:=procsym; wsym[9]:=readsym; wsym[10]:=thensym; wsym[11]:=varsym; wsym[12]:=whilesym; wsym[13]:=writesym; ssym[’+’]:=plus; ssym[’-’]:=minus; ssym['*’]:=times; ssym[’/’]:=slash; ssym[’(’]:=lparen; ssym[’)’]:=rparen; ssym[’=’]:=eql; ssym[’,’]:=comma; ssym[’.’]:=period; ssym[’;’]:=semicolon; ssym[’’’’]:=upcomma; mnemonic[lit]:=’1it’; mnemonic[opr]:=’opr’; mnemonic[lod]:=’lod’; mnemonic[sto]:=’sto’; mnemonic[cal]:=’cal’; mnemonic[int]:=’int’; mnemonic[jmp]:=’jmp’; mnemonic[jpc]:=’jpc’; declbegsys:=[constsym,varsym,procsym]; statbegsys:=[beginsym,callsym,ifsym,whilesym]; facbegsys:=[ident,number,lparen]; err:=0;cw:=1;wx:=1; cc:=0;cx:=0;ll:=0;ch:=’’;kk:=al;getsym; block(O,0,[period]+declbegsys+statbegsys); if sym<>period then error(9); if err=0 then interpret else write(fw2,’error in PL/0 program’) ;99:writeln end. {主程序结束} 出错编号出错信息 1:应为’=’而不是’:=’ 2:’=’后应为数 3:标识符后应为”=” 4: const,var,procedure后应为标识符 5:漏掉逗号或分号 6:过程说明后的符号不正确 7:应为语句 8:程序体内语句部分后的符号不正确 9:应为句号 10: 语句之间漏分号 11: 标识符未说明 12:不可向常量名或过程名赋值 13: 应为赋值运算符’:=’ 14: call后应为标识符 15: 不可调用常量或变量 16:应为’then’ 17:应为’end’ 18: 应为’do’ 19:语句后的符号不正确 20: 应为关系运算符 21:表达式内不可有过程标识符 22:漏右括号 23: 因子后不可为此符号 24:表达式不能以此符号开始 30: 这个数太大 31: 表达式内常数越界 32: 嵌套深度超过允许值 33: read或write语句中缺”)” 34: read或write语句中缺”(” 35: read语句中标识符未说明 36: write语句中需打印的标识符未加单引号 2)主要参数说明 ff: PL/O语言源程序文件名; fi: ff文件所需的数据文件; fw2: 运行后存放结果的文件; ch: 最近读到的字符; sym: 最近读到的单词; id: 最近读到的标识符; num: 最近读到的数; cc: 字符计数; ll: 行长; cw: PL/0语言源程序输出的行号; cx: 代码分配下标; kk: 读单词时的字符计数; err: 出错次数; wx: 写语句write计数; line: 读入字符的行缓冲区; a: 读词时存放所读单词; chwr:存放输出的变量名; code: 存放目标代码的数组; word: 保留字存贮区; wsym: 存放保留字所对应的符号; ssym: 存放关系运算符及特殊符; mnemoric: 存放目标代码中的指令码; table: 符号表,存放符号的类型、名字和值。 例如,用该编译程序对如下PL/0语言程序: var a,b,c; begin read(a) ;write(’a=’,a) ; read(b) ;write(’b=’,b) ; if a>b then begin c:=a+b; write(’c=’,c) ; end end. 进行编译运行,有运行结果(输出文件中包括有源程序、生成的目标指令及执行PL/0语言程序的计算结果等)如下: 1 var a,b,c; 2 begin read(a);write(’a=’,a) ; 3read(b);write(’b=’,b) ; 4if a>b then 5 begin c:=a+b; 6 write(’c=’,c) ; 7 end 8 end. 1 int 0 6 2 opr 0 16 3 sto 0 3 4 lod 0 3 5 opr 0 14 6 opr 0 15 7 opr 0 16 8 sto 0 4 9 lod 0 4 10 opr 0 14 11 opr 0 15 12 lod 0 3 13 lod 0 4 14 opr 0 12 15 jpc 0 23 16 lod 0 3 17 lod 0 4 18 opr 0 2 19 sto 0 5 20 lod 0 5 21 opr 0 14 22 opr 0 15 23 opr 0 0 a= 50 b= 40 c= 90 预先建立PL/0语言源程序文件ff和其所需要的数据文件fi(文件名预先确定)。 运行时在键盘上根据提示信息键入输出文件fw2的文件名(自行随时确定)。 编译原理实验报告实验名称:实验一编写词法分析程序 实验类型:验证型实验 指导教师:何中胜 专业班级:13软件四 姓名:丁越 学号: 电子邮箱: 实验地点:秋白楼B720 实验成绩: 日期:2016年3 月18 日 一、实验目的 通过设计、调试词法分析程序,实现从源程序中分出各种单词的方法;熟悉词法分析 程序所用的工具自动机,进一步理解自动机理论。掌握文法转换成自动机的技术及有穷自动机实现的方法。确定词法分析器的输出形式及标识符与关键字的区分方法。加深对课堂教学的理解;提高词法分析方法的实践能力。通过本实验,应达到以下目标: 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、实验过程 以编写PASCAL子集的词法分析程序为例 1.理论部分 (1)主程序设计考虑 主程序的说明部分为各种表格和变量安排空间。 数组 k为关键字表,每个数组元素存放一个关键字。采用定长的方式,较短的关键字 后面补空格。 P数组存放分界符。为了简单起见,分界符、算术运算符和关系运算符都放在 p表中 (编程时,还应建立算术运算符表和关系运算符表,并且各有类号),合并成一类。 id和ci数组分别存放标识符和常数。 instring数组为输入源程序的单词缓存。 outtoken记录为输出内部表示缓存。 还有一些为造表填表设置的变量。 主程序开始后,先以人工方式输入关键字,造 k表;再输入分界符等造p表。 主程序的工作部分设计成便于调试的循环结构。每个循环处理一个单词;接收键盘上 送来的一个单词;调用词法分析过程;输出每个单词的内部码。 ⑵词法分析过程考虑 将词法分析程序设计成独立一遍扫描源程序的结构。其流程图见图1-1。 图1-1 该过程取名为 lexical,它根据输入单词的第一个字符(有时还需读第二个字符),判断单词类,产生类号:以字符 k表示关键字;i表示标识符;c表示常数;p表示分界符;s表示运算符(编程时类号分别为 1,2,3,4,5)。 对于标识符和常数,需分别与标识符表和常数表中已登记的元素相比较,如表中已有 该元素,则记录其在表中的位置,如未出现过,将标识符按顺序填入数组id中,将常数 变为二进制形式存入数组中 ci中,并记录其在表中的位置。 lexical过程中嵌有两个小过程:一个名为getchar,其功能为从instring中按顺序取出一个字符,并将其指针pint加1;另一个名为error,当出现错误时,调用这个过程, 输出错误编号。 2.实践部分 编译原理实验指导 实验安排: 上机实践按小组完成实验任务。每小组三人,分别完成TEST语言的词法分析、语法分析、语义分析和中间代码生成三个题目,语法分析部分可任意选择一种语法分析方法。先各自调试运行,然后每小组将程序连接在一起调试,构成一个相对完整的编译器。 实验报告: 上机结束后提交实验报告,报告内容: 1.小组成员; 2.个人完成的任务; 3.分析及设计的过程; 4.程序的连接; 5.设计中遇到的问题及解决方案; 6.总结。 实验一词法分析 一、实验目的 通过设计编制调试TEST语言的词法分析程序,加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程,从输入的源程序中,识别出各个具有独立意义的单词,即基本字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 二、实验预习提示 1.词法分析器的功能和输出格式 词法分析器的功能是输入源程序,输出单词符号。词法分析器的单词符号常常表示 成以下的二元式(单词种别码,单词符号的属性值)。 2.TEST语言的词法规则 编译原理实验报告 班级 姓名: 学号: 自我评定: 实验一词法分析程序实现 一、实验目的与要求 通过编写和调试一个词法分析程序,掌握在对程序设计语言的源程序进行扫描的过程中,将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。 二、实验内容 根据教学要求并结合学生自己的兴趣和具体情况,从具有代表性的高级程序设计语言的各类典型单词中,选取一个适当大小的子集。例如,可以完成无符号常数这一类典型单词的识别后,再完成一个尽可能兼顾到各种常数、关键字、标识符和各种运算符的扫描器的设计和实现。 输入:由符合或不符合所规定的单词类别结构的各类单词组成的源程序。 输出:把单词的字符形式的表示翻译成编译器的内部表示,即确定单词串的输出形式。例如,所输出的每一单词均按形如(CLASS,VALUE)的二元式编码。对于变量和常数,CLASS字段为相应的类别码;VALUE字段则是该标识符、常数的具体值或在其符号表中登记项的序号(要求在变量名表登记项中存放该标识符的字符串;常数表登记项中则存放该常数的二进制形式)。对于关键字和运算符,采用一词一类的编码形式;由于采用一词一类的编码方式,所以仅需在二元式的CLASS字段上放置相应的单词的类别码,VALUE字段则为“空”。另外,为便于查看由词法分析程序所输出的单词串,要求在CLASS字段上放置单词类别的助记符。 三、实现方法与环境 词法分析是编译程序的第一个处理阶段,可以通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义(如BNF),用手工的方式(例如可用C语言)构造词法分析程序。一般地,可以根据文法或状态转换图构造相应的状态矩阵,该状态矩阵同控制程序便组成了编译器的词法分析程序;也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序的另外一种途径是所谓的词法分析程序的自动生成,即首先用正规式对语言中的各类单词符号进行词型描述,并分别指出在识别单词时,词法分析程序所应进行的语义处理工作,然后由一个所谓词法分析程序的构造程序对上述信息进行加工。如美国BELL实验室研制的LEX就是一个被广泛使用的词法分析程序的自动生成工具。 总的来说,开发一种新语言时,由于它的单词符号在不停地修改,采用LEX等工具生成的词法分析程序比较易于修改和维护。一旦一种语言确定了,则采用手工编写词法分析程序效率更高。 四、实验设计 1)题目1:试用手工编码方式构造识别以下给定单词的某一语言的词法分析程序。 语言中具有的单词包括五个有代表性的关键字begin、end、if、then、else;标识符;整型常数;六种关系运算符;一个赋值符和四个算术运算符。参考实现方法简述如下。 单词的分类:构造上述语言中的各类单词符号及其分类码表。 表I 语言中的各类单词符号及其分类码表 单词符号类别编码类别码的助记符单词值 实验1-3 《编译原理》S语言词法分析程序设计方案 一、实验目的 了解词法分析程序的两种设计方法之一:根据状态转换图直接编程的方式; 二、实验内容 1.根据状态转换图直接编程 编写一个词法分析程序,它从左到右逐个字符的对源程序进行扫描,产生一个个的单词的二元式,形成二元式(记号)流文件输出。在此,词法分析程序作为单独的一遍,如下图所示。 具体任务有: (1)组织源程序的输入 (2)拼出单词并查找其类别编号,形成二元式输出,得到单词流文件 (3)删除注释、空格和无用符号 (4)发现并定位词法错误,需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。 (5)对于普通标识符和常量,分别建立标识符表和常量表(使用线性表存储),当遇到一个标识符或常量时,查找标识符表或常量表,若存在,则返回位置,否则返回0并且填写符号表或常量表。 标识符表结构:变量名,类型(整型、实型、字符型),分配的数据区地址 注:词法分析阶段只填写变量名,其它部分在语法分析、语义分析、代码生成等阶段逐步填入。 常量表结构:常量名,常量值 三、实验要求 1.能对任何S语言源程序进行分析 在运行词法分析程序时,应该用问答形式输入要被分析的S源语言程序的文件名,然后对该程序完成词法分析任务。 2.能检查并处理某些词法分析错误 词法分析程序能给出的错误信息包括:总的出错个数,每个错误所在的行号,错误的编号及错误信息。 本实验要求处理以下两种错误(编号分别为1,2): 1:非法字符:单词表中不存在的字符处理为非法字符,处理方式是删除该字符,给出错误信息,“某某字符非法”。 2:源程序文件结束而注释未结束。注释格式为:/* …… */ 四、保留字和特殊符号表 学生学号0120810680316 实验课成绩 武汉理工大学 学生实验报告书 实验课程名称《编译原理》 开课学院计算机科学与技术学院 指导老师姓名何九周 学生姓名刘洋 学生专业班级软件工程0803 2010 —2011 学年第二学期 实验课程名称:编译原理 实验项目名称单词的词法分析程序设计实验成绩实验者刘洋专业班级软件0803 组别 同组者实验日期 2011 年 5 月 17日 第一部分:实验分析与设计(可加页) 一、实验内容描述(问题域描述) 实验目的: 设计,编制并调试一个词法分析程序,加深对词法分析原理的理解。 实验要求: 在上机前应认真做好各种准备工作,熟悉机器的操作系统和语言的集成环境,独立完成算法编制和程序代码的编写;上机时应随带有关的高级语言教材或参考书;要学会程序调试与纠错;每次实验后要交实验报告。 实验题目: 对于给定的源程序(如C语言或Pascal等),要求从组成源程序的字符行中寻找出单词,并给出它们的种别和属性——输出二元组序列。以便提供给语法分析的时候使用。要求能识别所有的关键字,标志符等,并且能够对出先的一些词法规则的错误进行必要的处理。 二、实验基本原理与设计(包括实验方案设计,实验手段的确定,试验步骤等,用硬件逻辑或 者算法描述) 实验原理: 由于这是一个用高级语言编写一个词法分析器,使之能识别输入串,并把分析结果(单词符号,标识符,关键字等等)输出.输入源程序,输入单词符号,本词法分析器可以辨别关键字,标识符,常数,运算符号和某些界符,运用了文件读入来获取源程序代码,再对该源程序代码进行词法分析,这就是词法分析器的基本功能.当词法分析器调用预处理子程序处理出一串输入字符放进扫描缓冲区之后,分析器就从此缓冲区中逐一识别单词符号.当缓冲区里的字符串被处理完之后,它又调用预处理子程序来处理新串. 编写的时候,使用了文件的输入和输出,以便于词法分析的通用型,同时在文件输出时,并保存在输出文件output文件中。 从左到右扫描程序,通过初始化:1为关键字;2为标志符; 3为常数;4为运算符或界符。 三、主要仪器设备及耗材 计算机 《编译原理》课程实验指导书 课程编号: 课程名称:编译原理/Compiler Principles 实验总学时数: 8 适用专业:计算机科学与技术、软件工程 承担实验室:计算机学院计算机科学系中心实验室、计算机技术系中心实验室 一、实验教学的目的与要求 上机实习是对学生的一种全面综合训练,是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常,实习题中的问题比平时的练习题要复杂,也更接近实际。编译原理这门课程安排的2次上机实验都属于一种设计类型的实验,每个实验的训练重点在于基本的编译技术和方法,而不强调面面俱到;实验的目的是旨在使学生进一步巩固课堂上所学的理论知识,深化理解和灵活掌握教学内容;培养学生编制算法的能力和编程解决实际问题的动手能力。 要求学生在上机前应认真做好各种准备工作,熟悉机器的操作系统和语言的集成环境,独立完成算法设计和程序代码的编写;上机时应随带有关的编译原理教材或参考书;要学会程序调试与纠错。 每次实验后要交实验报告,实验报告的内容应包括: (1)实验题目、班级、学号、姓名、完成日期; (2)简要的需求分析与概要设计; (3)详细的算法描述; (4)源程序清单; (5)给出软件的测试方法和测试结果; (6)实验的评价、收获与体会。 开发工具: (1)DOS环境下使用Turbo C; (2)Windows环境下使用Visual C++ 。 考核: 实验成绩占编译原理课程结业成绩的10%。 三、单项实验的内容和要求: 要求每个实验保证每个学生一台微机。 实验一(4学时):单词的词法分析程序设计。 (一)目的与要求 1.目的 通过设计、编制、调试一个具体的词法分析程序,加深对词法分析原理的理解,并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 实验一词法分析程序实现 一、实验目得与要求 通过编写与调试一个词法分析程序,掌握在对程序设计语言得源程序进行扫描得过程中,将字符流形式得源程序转化为一个由各类单词符号组成得流得词法分析方法 二、实验内容 基本实验题目:若某一程序设计语言中得单词包括五个关键字begin、end、if、then、else;标识符;无符号常数;六种关系运算符;一个赋值符与四个算术运算符,试构造能识别这些单词得词法分析程序(各类单词得分类码参见表I)。 表I语言中得各类单词符号及其分类码表 输入:由符合与不符合所规定得单词类别结构得各类单词组成得源程序文件。 输出:把所识别出得每一单词均按形如(CLASS,VALUE)得二元式形式输出,并将结果放到某个文件中。对于标识符与无符号常数,CLASS字段为相应得类别码得助记符;V AL UE字段则就是该标识符、常数得具体值;对于关键字与运算符,采用一词一类得编码形式,仅需在二元式得CLASS字段上放置相应单词得类别码得助记符,V ALUE字段则为“空". 三、实现方法与环境 词法分析就是编译程序得第一个处理阶段,可以通过两种途径来构造词法分析程序.其一就是根据对语言中各类单词得某种描述或定义(如BNF),用手工得方式(例如可用C语言)构造词法分析程序。一般地,可以根据文法或状态转换图构造相应得状态矩阵,该状态矩阵连同控制程序一起便组成了编译器得词法分析程序;也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序得另外一种途径就是所谓得词法分析程序得自动生成,即首先用正规式对语言中得各类单词符号进行词型描述,并分别指出在识别单词时,词法分析程 武汉科技大学计算机科学与技术学院 编译原理实验指导书 实验一词法分析器设计 【实验目的】 1.熟悉词法分析的基本原理,词法分析的过程以及词法分析中要注意的问题。 2.复习高级语言,进一步加强用高级语言来解决实际问题的能力。 3.通过完成词法分析程序,了解词法分析的过程。 【实验内容】 用C语言编写一个PL/0词法分析器,为语法语义分析提供单词,使之能把输入的字符串形式的源程序分割成一个个单词符号传递给语法语义分析,并把分析结果(基本字,运算符,标识符,常数以及界符)输出。 【实验要求】 1.要求绘出词法分析过程的流程图。 2.根据词法分析的目的以及内容,确定完成分析过程所需模块。 3.写出每个模块的源代码,并给出注释。 4.整理程序清单及所得结果。 【说明】 运行成功以后,检查程序,并将运行结果截图打印粘贴到实验报告上。 辅助库函数scanerLib设计以及使用说明: 下面内容给出了一个辅助库函数的接口说明以及具体实现。 接口设计 //字符类 class Token { TokenType type; String str; Int line; } //词法分析结果输出操作类 class TokenWriter { ArrayList tokens; //用来记录所识别出来的token TokenWriter(); //构造函数指定输入文件名,创建文件输出流 V oid Add(Token); //将词法分析器中分析得到的Token添加到tokens中 WriteXML(); //将tokens写出到目标文件.xml中 } //词法分析操作词法分析生成文件接口<暂时不需要对该类的操作;下一步做语法分析的时候使用> class TokenReader 《编译原理》(实验部分) 实验1_程序预处理 一、实验目的 明确预处理子程序的任务,构造一个简单的预处理子程序,对源程序进行相应的预处理。 二、实验设备 1、PC 兼容机一台;操作系统为WindowsWindowsXP。 2、Visual C++ 6.0 或以上版本, Windows 2000 或以上版本,汇编工具(在Software 子目录下)。 三、实验原理 定义模拟的简单语言的词法构成,编制读入源程序和进行预处理的程序,要求将源程序读入到文件或存入数组中,再从文件或数组中逐个读取字符进行预处理,包括去掉注释、Tab、Enter和续行符等操作,并显示预处理后的程序。 四、实验步骤 1、从键盘读入源程序存放到输入缓冲区中。 2、对源程序进行预处理,预处理后的程序存放到扫描缓冲区中。 3、显示预处理后的程序。 参考源程序(C++语言编写) //源程序的输入及预处理 #include { //定义扫描缓冲区 char buf[4048]={'\0'}; //缓冲区清0 //调用预处理程序 pro_process(buf); //在屏幕上显示扫描缓冲区的内容cout< 《编译原理》实验指导书 实验目的和内容 编译原理实验的目的是使学生将编译理论运用到实际当中,实现一个简单语言集的词法、语法和语义分析程序,验证实际编译系统的实现方法,并加深对编译技术的认识。 实验内容共需实现编译器的词法、语法和语义分析程序三个组成部分。要求学生必须完成每个实验的基本题目要求,有余力的同学可尝试实验的扩展要求部分。 实验报告 要求每人针对所完成的实验内容上交一份实验报告,其中主要包括三方面内容:1、实验设计:实验采用的实现方法和依据(如描述语言的文法及其机内表示,词分析 的单词分类码表、状态转换图或状态矩阵等,语法分析中用到的分析表或优先矩阵等,语法制导翻译中文法的拆分和语义动作的设计编写等);具体的设计结果(应包括整体设计思想和实现算法,程序结构的描述,各部分主要功能的说明,法以及所用数据结构的介绍等)。 2、程序代码:实验实现的源程序清单,要求符合一般的程序书写风格,有详细的注释。 3、实验结果分析:自行编写若干源程序作为测试用例,对所生成的编译程序进行测试 (编译程序的输入与输出以文件的形式给出);运行结果分析(至少包括一个正确和一个错误单词或语句的运行结果);以及改进设想等。 注意事项 1、电子版实验报告和源程序在最后一次机时后的一周内上交。(每个同学上交一个压 缩文件,其命名格式为“学号_姓名.rar”,内含实验报告和一个命名为“源程序” 的文件夹。注意提交的源程序应是经过调试、测试成功的较为通用的程序,并应有相应的注释、运行环境和使用方法简介。) 2、不接受不完整的实验报告和没有说明注释的源程序,或者说明与程序、运行结果不 符合的作业。 特别鼓励:扩展题目 1、为亲身经历一个小型编译器的开发全过程,触摸一下与实际编译器开发相关的工作, 大家可以自由组成3人左右的小组,推举组长,模拟一个团队分工协作开发大型软件的实战环境,融入软件工程的思想规范和一般理论方法,初步体验从系统分析设计、编码测试到交付维护的一个完整编译器软件的开发过程。要求组长为每个小组成员分配主要负责的任务,完成相应的分析设计员、程序员和测试员等角色的工作,并以小组为单位提交一份实验报告和源程序,在报告封面上写明每个同学主要完成和负责的部分。 2、以组为单位完成的实验内容至少必须整合词法、语法和语义三个部分的实验,对于 选定的适当规模的文法(如C语言的一个大小适宜的子集),进行系统的总体设计、功能分析、编码测试等工作。完成一个从对源程序的词法分析开始,到中间代码生成的完整的编译器前端的开发,使所涉及到的编译系统的各个组成模块有机地衔接在一起,提交一份完整的实验报告和源程序,并将以下几个方面描述清楚: [实验任务] 完成以下正则文法所描述的Pascal语言子集单词符号的词法分析程序。 <标识符>→字母︱<标识符>字母︱<标识符>数字 <无符号整数>→数字︱<无符号整数>数字 <单字符分界符> →+ ︱-︱* ︱; ︱(︱) <双字符分界符>→<大于>=︱<小于>=︱<小于>>︱<冒号>=︱<斜竖>* <小于>→< <等于>→= <大于>→> <冒号> →: <斜竖> →/ 该语言的保留字:begin end if then else for do while and or not 说明:1 该语言大小写不敏感。 2 字母为a-z A-Z,数字为0-9。 3可以对上述文法进行扩充和改造。 4 ‘/*……*/’为程序的注释部分。 [设计要求] 1、给出各单词符号的类别编码。 2、词法分析程序应能发现输入串中的错误。 3、词法分析作为单独一遍编写,词法分析结果为二元式序列组成的中间文件。 4、设计两个测试用例(尽可能完备),并给出测试结果。 demo.cpp #include 电子科技大学 实验报告 学生姓名:学号:指导教师: 实验地点:实验时间: 一、实验室名称:计算机学院软件工程实验室 二、实验项目名称:词法分析器的设计与实现 三、实验学时:4学时 四、实验原理 1.编译程序要求对高级语言编写的源程序进行分析和合成,生成目标程序。词法分析是对源程序进行的首次分析,实现词法分析的程序为词法分析程序。 2.词法分析的功能是从左到右逐个地扫描源程序字符串,按照词法规则识别出单词符号作为输出,对识别过程中发现的词法错误,输出相关信息。 3.状态转换图是有限有向图,是设计词法分析器的有效工具。 五、实验目的 通过设计词法分析器的实验,使同学们了解和掌握词法分析程序设计的原理及相应的程序设计方法,同时提高编程能力。 六、实验内容 实现求n!的极小语言的词法分析程序,返回二元式作为输出。 七、实验器材(设备、元器件) 1.操作系统:Windows XP 2.开发工具:VC6.0 3.普通PC即可 八、实验步骤 (1)启动VC6.0,创建空白工程项目。选择菜单中的“文件”->“新建”->“项目”,在弹出的对话框中,左边的“项目类型”框中,选择“Visual C++ 项目”,在右边框中,选择“空项目(.Net)”,在对话框下边,选择工程文件存放目录及输入名称,如Example1,单击“确定”。 (2)建立相应的单词符号与种别对照表; (3)根据状态转换图编写相应的处理函数; (4)完成词法分析器; (5)编译与调试以上程序; (6)生成相应的*.dyd文件,作为后面语法分析的输入文件。 九、实验数据及结果分析 可以对源程序进行词法分析,如果有错给出出错信息和所在行数,如果无错则生成二元式文件。 十、实验结论 本实验程序较好地完成了词法分析程序的设计与实现,能够对所给文法的程序进行词法分析,在没有词法错误的时候生成相应的二元式文件。该实验程序可一次性给出源程序中的词法错误。 十一、总结及心得体会 通过该实验,对词法分析程序的设计,以及运用C语言进行编程有了更深刻的理解,同时加深了自己对词法分析程序的原理的理解与掌握,提高了自己的动手能力。 十二、对本实验过程及方法、手段的改进建议 程序设计合理,代码可进一步优化。 报告评分: 指导教师签字: 编译原理 实 验 指 导 书 作者:莫礼平 2011年3月 实验一简单词法分析程序设计 一、实验目的 了解词法分析程序的基本构造原理,掌握词法分析程序的手工构造方法。 二、实验内容 1、了解编译程序的词法分析过程。 2、根据PASCAL语言的说明语句形式,用手工方法构造一个对说明语句进行词法分析的程序。该程序能对从键盘输入或从文件读入的形如: “const count=10,sum=81.5,char1=’f’,string1=”hj”, max=169;” 的常量说明串进行处理,分析常量说明串中各常量名、常量类型及常量值,并统计各种类型常量个数。 三、实验要求 1、输入的常量说明串,要求最后以分号作结束标志; 2、根据输入串或读入的文本文件中第一个单词是否为“const”判断输入串或文本文件是否为常量说明内容; 3、识别输入串或打开的文本文件中的常量名。常量名必须是标识符,定义为字母开头,后跟若干个字母,数字或下划线; 4、根据各常量名紧跟等号“=”后面的内容判断常量的类型。其中:字符型常量定 义为放在单引号内的一个字符;字符串常量定义为放在双引号内所有内容;整型常量定 义为带或不带+、- 号,不以0开头的若干数字的组合;实型常量定义为带或不带+、- 号, 不以0开头的若干数字加上小数点再后跟若干数字的组合; 5、统计并输出串或文件中包含的各种类型的常量个数; 6、以二元组(类型,值)的形式输出各常量的类型和值; 7、根据常量说明串置于高级语言源程序中时可能出现的错误情况,模仿高级语言编 译器对不同错误情况做出相应处理。 四、运行结果 1、输入如下正确的常量说明串: const count=10,sum=81.5,char1=‘f’,max=169,str1=“h*54 2..4S!AAsj”, char2=‘@’,str2=“aa!+h”; 输出: count(integer,10) sum(float,81.5) char1(char, ‘f’) max(integer,169) str1(string,“h*54 2..4S!AAsj”) char2(char, ‘@’) str2(string,“aa!+h”) int_num=2; char_num=2; string_num=2; float_num=1. 2、输入类似如下的保留字const错误的常量说明串: Aconstt count=10,sum=81.5,char1=‘f’; 输出类似下面的错误提示信息: 实验四中间代码生成 一.实验目的: 掌握中间代码的四种形式(逆波兰式、语法树、三元式、四元式)。 二.实验内容: 1、逆波兰式定义:将运算对象写在前面,而把运算符号写在后面。用这种表示法表示的表 达式也称做后缀式。 2、抽象(语法)树:运算对象作为叶子结点,运算符作为内部结点。 3、三元式:形式序号:(op,arg1,arg2) 4、四元式:形式(op,arg1,arg2,result) 三、以逆波兰式为例的实验设计思想及算法 (1)首先构造一个运算符栈,此运算符在栈内遵循越往栈顶优先级越高的原则。 (2)读入一个用中缀表示的简单算术表达式,为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。 (3)从左至右扫描该算术表达式,从第一个字符开始判断,如果该字符是数字,则分析到该数字串的结束并将该数字串直接输出。 (4)如果不是数字,该字符则是运算符,此时需比较优先关系。 做法如下:将该字符与运算符栈顶的运算符的优先关系相比较。如果,该字符优先关系高于此运算符栈顶的运算符,则将该运算符入栈。倘若不是的话,则将此运算符栈顶的运算符从栈中弹出,将该字符入栈。 (5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式,确定所有字符都得到正确处理,我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。 四、程序代码: //这是一个由中缀式生成后缀式的程序 #include<> #include<> #include<> #include<> #define maxbuffer 64 void main() { char display_out(char out_ch[maxbuffer], char ch[32]); //int caculate_array(char out_ch[32]); static int i=0; static int j=0; char ch[maxbuffer],s[maxbuffer],out[maxbuffer]; cout<<"请输入中缀表达式: "; 集美大学计算机工程学院实验报告 课程名称:编译原理班级: 指导教师:: 实验项目编号:实验一学号: 实验项目名称:词法分析器的设计实验成绩: 一、实验目的 通过设计编制调试一个具体的词法分析程序,加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 二、实验容 编写一个词法分析器,从输入的源程序(编写的语言为C语言的一个子集)中,识别出各个具有独立意义的单词,即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的部编码及单词符号自身值。(遇到错误时可显示“Error”,然后跳过错误部分继续显示) 三、实验要求 1、词法分析器的功能和输出格式 词法分析器的功能是输入源程序,输出单词符号。词法分析器的单词符 2 别单词的类型,将标识符和常量分别插入到相应的符号表中,增加错误处理等。 3、编程语言不限。 四、实验设计方案 1、数据字典 本实验用到的数据字典如下表所示: 3、实验程序 #include 实验一词法分析程序实现 一、实验目的与要求 通过编写和调试一个词法分析程序,掌握在对程序设计语言的源程序进行扫描的过程中,将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。 二、实验内容 选取无符号数的算术四则运算中的各类单词为识别对象,要求将其中的各个单词识别出来。 输入:由无符号数和+,-,*,/, ( , ) 构成的算术表达式,如1.5E+2-100。 输出:对识别出的每一单词均单行输出其类别码(无符号数的值暂不要求计算)。 三、实现方法与环境 1、首先设计识别各类单词的状态转换图。 描述无符号常数的确定、最小化状态转换图如图1所示。其中编号0,1,2, (6) 表非终结符号<无符号数>、<余留无符号数>、<十进小数>、<小数部分>、<指数部分>、<整指数>及<余留整指数>,1,2和6为终态,分别代表整数、小数和科学计数的识别结束状态。 图1 文法G[<无符号数>]的状态转换图 其中编号0,1,2,…,6代表非终结符号<无符号数>、<余留无符号数>、<十进小数>、<小数部分>、<指数部分>、<整指数>及<余留整指数>,1,2和6为终态,分别代表整数、小数和科学计数的识别结束状态。 在一个程序设计语言中,一般都含有若干类单词符号,为此可首先为每类单词建立一张状态转换图,然后将这些状态转换图合并成一张统一的状态图,即得到了一个有限自动机,再进行必要的确定化和状态数最小化处理,最后据此构造词法分析程序。 四则运算算术符号的识别很简单,直接在状态图的0状态分别引出相应标记的矢线至一个新的终态即可。根据自己的习惯,也可以将其转换为状态矩阵形式。 2、词法分析程序编写 根据描述语言中各类单词的文法状态转换图或状态矩阵,利用某种语言(C语言或JA V A 语言)直接编写词法分析程序。 3、词法分析程序测试 用于测试扫描器的实例源文件中应有词法正确的,也应有错误的字符串,对于输入的测试用例的源程序文件,以对照的形式将扫描器的分析结果信息在输出文件中表示出来。四、参考资料 实现无符号数识别的参考方法:将设计的状态转换图直接转化为一张程序流程图,并在外层再增加一个以EOF为循环终止条件的while循环,即形成能连续识别各类单词的词法分析程序。 各类单词的编码建议如表1。 表1 单词的内部编码 编译原理实验指导书 实验2 语法分析 实验目的 1.巩固对语法分析的基本功能和原理的认识。 2.通过对语法分析表的自动生成加深语法分析表的认识。 3.理解并处理语法分析中的异常和错误。 实验要求 一、对学生要求: 1.掌握语法分析程序的总体框架,并将其实现。 2.掌握语法分析表的构造方法 3.掌握语法分析的异常和错误处理。 二、对实验指导教师要求: 1.明确语法分析的基本功能和原理。 2.语法分析程序的总体结构及其关键之处。 3.语法分析表的生成程序。 4.语法分析的异常和错误处理。 5.编写并运行该题目程序代码,具有该题目的参考答案。 6.深刻理解题目内涵,能够清晰描述问题,掌握该题目涉及的知识点,指导学生实验时需要注意的问题。 实验内容 采用至少一种语法分析技术(LL(1)、SLR(1)、LR(1)或LALR(1))分析类高级语言中的基本语句(至少包括函数定义、变量说明、赋值、循环、分支等语句)。 对如下工作进行展开描述 (1)给出如下语言成分的文法描述 ?函数定义(或过程定义) ?变量说明 ?赋值 ?表达式 ?循环 ?分支 (2) 语法分析程序的总体结构及物理实现(程序框图) (3) 核心数据结构和功能函数的设计 (4) 错误处理 错误的位置及类型等 实验评分标准 一、课堂表现(10分) 1.出勤情况(按时,迟到,早退,缺席) 2.是否遵守课堂纪律 二、实验结果(50分) 1.当堂按时完成(10分) 2.独立完成(10分),(和同学协商完成,在老师帮助下完成)3.结果正确无误(15分)其中分析表的输出占5分 4.功能齐全,界面美观,具有较好演示效果(10分) 5.在源程序中有必要的注释和说明,程序文档齐全(5分)三、实验报告(40分) 1.语言的文法描述(10分) 2.语法分析程序的模块结构图(10分) 3.核心数据结构的设计(10分) 4.错误处理(5分) 5.实验过程中遇到的问题的总结及实验的体会(5分) 编译原理实验指导书 主编:徐静李娜 信息与电气工程学院 2010年3月 概述 一、本课程实验的目的和任务 编译原理是一门实践性很强的课程,只有通过实践,才能真正掌握。实际的编译程序是十分复杂的,有时由多达十几万条指令组成。为此,编译原理的实践教学,采用简化编译过程的办法,选择最关键的3个环节──词法分析、语法分析(包括语义处理、产生无优化的目标指令)、连接调试,进行编程和调试训练。每个环节作为一个实践课题。先分别编程调试,再连接在一起总调。 二、实验方法 任何一个实用的高级语言,其语法都比较复杂,如选其作为源语言,很难实践全过程。故本实验将定义一个简化的语言── C语言的一个子集作为源语言,设计调试出它的编译程序。前后贯穿这一条主线进行实践。每次都可利用课余时间编程,利用上机时间进行输入和调试。 三、实验报告的规范和要求 每个实验完成后写出实验报告。实验报告的内容包括如下内容: 一、实验目的 二、程序设计时采用的算法和方法 三、输入的源程序 四、词法分析程序清单和输出结果。 五、心得体会 实验一词法分析 一、实验目的: (1)通过设计编制调试一个具体的词法分析程序,理解词法分析在编译程序中的作用。 (2)加深对有穷自动机模型的理解。 (3)掌握词法分析程序的实现方法和技术。 (4)用C语言对一个简单语言的子集编制一个一遍扫描的程序,以加深对编译原理的理解,掌握编译程序的实现方法和技术。 编制一个读单词过程,从输入的源程序中,识别出各个具有独立意义的单词,即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。(遇到错误时可显示“Error”,然后跳过错误部分继续显示)。 二、实验预习提示 1. 词法分析器的功能和输出格式 词法分析器的功能是输入源程序,输出单词符号。词法分析器的单词符号常常表示成以下的二元式(单词种别码,单词符号的属性值)。本实验中,采用的是一类符号一种别码的方式。 2. 单词的BNF表示 <标识符>→ <字母><字母数字串> <字母数字串>→<字母><字母数字串>|<数字> <字母数字串>| <下划线><字母数字串>|ε <无符号整数>→<数字> <数字串> <数字串>→<数字><数字串>|ε <加法运算符>→+ <减法运算符>→- <大于关系运算符>→> <大于等于关系运算符>→>= 3. “超前搜索”方法 编译原理实验指导 书 《编译原理》实验指导书 太原科技大学计算机学院 -3-1 序 《编译原理》是国内外各高等院校计算机科学技术类专业,特别是计算机软件专业的一门重要专业课程。该课程系统地向学生介绍编译程序的结构、工作流程及编译程序各组成部分的设计原理和实现技术。由于该课程理论性和实践性都比较强,内容较为抽象复杂,涉及到大量的软件设计和算法,因此,一直是一门比较难学的课程。为了使学生更好地理解和掌握编译原理和技术的基本概念、基本原理和实现方法,实践环节非常重要,只有经过上机进行程序设计,才能使学生对比较抽象的教学内容产生具体的感性认识,增强学生综合分析问题、解决问题的能力,并对提高学生软件设计水平大有益处。 为了配合《编译原理》课程的教学,考虑到本课程的内容和特点,本指导书设置了七个综合性实验,分别侧重于词法分析、NFA的确定化、非递归预测分析、算符优先分析器的构造、LR分析、语义分析和中间代码的生成、基于DAG的基本块优化,以支持编译程序的各个阶段,基本涵盖了《编译原理》课程的主要内容。 本指导书可作为《编译原理》课程的实验或课程设计内容,在课程教学的同时,安排学生进行相关的实验。实验平台可选择在MS-DOS或Windows操作系统环境,使用C/C++的任何版本作为开发工具。学生在做完试验后,应认真撰写实验报告,内容应 包括实验名称、实验目的、实验要求、实验内容、测试或运行结果等。 目录 实验一词法分析 ........................................................... 错误!未定义书签。实验二 NFA的确定化.................................................... 错误!未定义书签。实验三非递归预测分析 ............................................... 错误!未定义书签。实验四算符优先分析器的构造................................... 错误!未定义书签。实验五 LR分析 .............................................................. 错误!未定义书签。实验六语义分析和中间代码生成................................ 错误!未定义书签。实验七基于DAG的基本块优化................................... 错误!未定义书签。 《编译原理上机实验指导》 实验一词法分析 1 实验目的 设计编制并调试一个词法分析程序,加深对构造词法分析器的原理和技术理解与应用。 2 实验要求 选择一种计算机高级程序语言子语言,运用恰当的词法分析技术线路,设计和实现其子语言的词法分析器。语言选择,建议为《计算机程序设计》课程所采用的语言。技术线路建议如下两种之一:正则式→NFA→DFA→min DFA→程序设计和正则文法→NFA →DFA→min DFA→程序设计。分析器输出结果存入到磁盘文件中。具有出错处理功能。 选择子语言方法举例。以教材选取的PASCAL语言为例,确定其子语言涉及的单词类如下: (1)关键字 begin end if then while do (2)运算符和界符 := +-* /< <= <> > >= = ; ( ) :# (3)标识符 正则式:ID=letter(letter|digit)* (4)整型常数 正则式:NUM= digit(digit)* 3 算法设计 (1)单词种别码设计 (2)输出形式设计 词法分析器的输入是源程序字符串,输出是对应的单词串。每个单词按照二元组(种别码,单词符号本身)格式输出。 例如:假设源程序为begin x:=9; if x>0 then x:=2*x+1/3;end #,则词法分析器对应输出的结果是: (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)(10,x)(23,>)(11,0)(3,then)(10,x)(18,:=)(11,2)(15, *) (10,x)(13, +)(11,1)(16,/)(11,3)(26,;)(6,end)(0,#) (3)算法思想 依据建立的识别单词的DFA,设计算法,其框架如下。其中,①syn存放单词的种别码;②token存放符合标识符规则的单词;③sum存放整型常量的单词。 实现技术细节注意的几个要点:A)标识符和关键字,属于同一构词规则,识别方法是建立一个关键字表,在识别出标识符单词时,查关键字表,以确认或区别是否是关键字,还是标识符。B)对前导空格符、制表符和换行,均须过滤。详细处理技术请参见陈火旺等编写《程序设计语言编译原理》(第三版);C)约定标识符单词8位有效。 主算法流程图编译原理实验报告实验一编写词法分析程序
编译原理实验指导
编译原理实验报告
实验1-3-《编译原理》词法分析程序设计方案
编译原理实验报告
编译原理实验指导书2010
编译原理实验报告一
《编译原理》实验指导书-2015
《编译原理(实验部分)》实验1_程序预处理
《编译原理》实验指导书
编译原理实验代码
编译原理标准实验报告
编译原理实验指导书
编译原理实验 中间代码生成
编译原理实验-词法分析器的设计说明
编译原理实验报告
编译原理实验指导书-语法分析
编译原理实验指导
编译原理实验指导书
《编译原理上机实验指导》