编译原理上机实习指导书08.doc

编译原理上机实习指导书一、上机实习目的理解编译程序的构造原理，掌握编译程序的构造方法与技术。通过实习，使学生既加深对编译原理基础理论的理解，又提高动手能力，特别是提高软件设计能力。二、上机实习要求在理解编译原理基本思想的基础上，选择一个自己熟悉的程序设计语言，完成编译程序的设计和实现过程。本上机实习是为某个计算机语言设计一个编译程序，完成词法分析、语法分析、语义分析等功能，并生成某种机器上的目标代码。在上机实习指导书中给出了上机实习的基本思路，学生可以按照这个去做，能力强的学生还可以按照所学知识，自行设计方案。三、上机实习步骤1阅读上机实习任务书及上机实习指导书。2根据设计要求写算法，画程序框图3根据框图编写源程序4输入源程序并上机调试5撰写上机实习报告四、上机实习内容1、题目：C语言小子集编译程序的实现2、C语言小子集的文法规则： :main（） :=常量说明部分)； :=const:=，:= : :=:=int:=，:= :=:=:= :=；|:|:=:= := :=|:=|:|():=:=:=:+|-:=*|:|!=|=|=|=:=if（）else:=while（）do:=scanf(，) :=printf(，) :=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|93、实现功能：(1)词法分析扫描源程序，根据词法规则，识别单词，填写相应的符号表。(2)语法分析对由源程序作语法分析，确定是否属于C语言小子集，同时揭示出程序的内在结构。 (3)语法错误检查根据C语言小子集的文法规则设置检测手段，通过查错子程序或一些查错语句，报告源程序出错位置、性质等，直至整个程序结束为止。(4)语义分析与目标代码生成在语法分析的基础上，进行语义分析，生成源程序的目标代码。源程序的目标代码可以建立在一个假想的处理机（虚拟机）上，也可以以所学的汇编语言为基础。源程序样本：main () int a,b,x,y,max;a=10; while (a0) b=a*a;a=a-1;x=a+b; y=b+b;if (xy) 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 :=+|-|:=|:|():+|-:=*|:|=|=|=:=ifthen:=call:=whiledo:=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|93 PL0编译程序的设计思想编译程序的设计可以采用自顶向下和自底向上两种不同的方法。由于许多高级语言（如PASCAL，C）中的语法成分都是递归定义的，PL0也是如此，所以本实验采用递归子程序法，这是一种自顶向下的的编译方法，其基本思想是对源程序的每个（或若干个）语法成分编制一个处理子程序，从处理这个语法成分的子程序开始，在分析过程中调用一系列过程或函数，对源程序进行语法和语义分析，直到整个源程序处理完毕为止。在本上机实习中，我们给出用PASCAL语言编写的PL0的编译程序，要求学生先读懂它，然后再用自己熟悉的高级语言改写它，能力强的同学可以按照所学知识，自行设计实现方案。 4PL0编译程序的功能(1)语法分析 对由PL0语言编制的程序作语法分析，确定是否属于PL0语言，同时揭示出程序的内在结构。 (2)语法错误检查 根据PL0语言的文法规则设置检测手段，通过查错子程序和一些查错语句，报告源程序出错位置、性质等，直至整个程序结束为止。 (3)生成目标代码 PL0语言的目标代码是建立在一个假想的处理机上，此处理机称为PL0处理机。 (4)执行目标代码 PL0处理机是一种假想的处理机，其目标代码不能在实际的机器上执行，故此编译程序设置了一个子程序，它对PL0语言的目标代码逐条解释执行，最后得出所需结果。5PL0编译程序的有关过程及函数在PL0语言的编译文本中，除了常量和变量说明外，共有18个相互嵌套或并列的过程(或函数)。现对这些过程和函数作扼要说明。(1)error(n)：其功能是报告PL0源程序的出错信息。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)完成，此时kconstant。vardeclaration：变量造表子程序。其功能是为变量造一张变量表，内填变量名、所处层号。它也是通过调用子程序enter(k)来完成的，此时k=variable。listcode，打印(伪)代码子程序。其功能是输出生成的目标代码。statement(fsys)：语句处理子程序。其功能是处理语句，它是递归调用的核心部分。其递归调用顺序如下：expression(fsys)：处理算术表达式子程序；term(fsys)：处理项子程序；condition(fsys)：处理因子子程序。(6)interpret，执行目标代码子程序。其功能是对编译过程中生成的目标代码(伪代码)逐条解释执行。 base(l)：提供计算静态链信息子程序。它为过程调用提供调用所需的基地址。整个PL0编译程序通过主程序调用分程序处理模块block，再通过block递归调用上述的子程序，达到对PL0语言的程序进行编译的目的。6编译步骤程序中用数组word存贮PL0语言的所有保留字。保留字有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）；codecxl.a:=cx，生成分配局部变量指令，语句处理，生成opr 0，0指令；返回主程序，err是否为0，是则调子程序interpret，转13），否则给出出错信息，结束编译；解释执行生成的目标代码，列出结果。 PL0编译程序及主要参数1)PL0编译程序program plO(input，output，ff，fi，fw2)；带有代码生成的PL0编译程序 label 99； const norw13； 保留字个数 txmax=100， 标识符表的长度nmax=14， 数中数字的最大个数a1=10； 标识符的长度amax20471；最大地址 levmax3； 程序体嵌套的最大深度cxmax200； 代码数组的大小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) ；alfapacked array1.a1 of char；object(constant，variable，proceable) ；symsetset Of symbol；fct=(1it，opr，lod，sto，cal，int，jmp，jpc)；functionsinstruction=packed recordf：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和fifw2：text； 输出文件名fw2ch：char； 最近读到的字符sym：symbol； 最近读到的符号id：alfa； 最近读到的标识符num：integer； 最近读到的数cc：integer； 字符计数ll：integer； 行长wx：integer；kk，err，cw：integer；cx：integer； 代码分配下标line：array1.81of char；a：alfa；chwr：array1.writex of alfa；code：array0.cxmax of instruction；word：array1.norw of alfa；wsym：array1.norw of symbol；ssym：arraychar of symbol；mnemonic：arrayfct of packed array1.3 of char；declbegsys，statbegsys，facbegsys：symset；table：array0.txmax of recordname：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) ； linell:=ch； end； writeln(fw2)；ll:=ll+1；read(ff，1inell) ； end； cc:=cc+l；ch:=linecc ； end； 读字符子程序结束 begin 读单词子程序开始 while ch do getch； if ch in a.z then begin kc:=0； repeat if k=kk then kk:=k else repeat akk:= ；kk:=kk-1； untll kk=k； id:=a；i:=1；j:=norw； repeat k=(i+j) div 2； if id=wordk then i:=k+1； untll ij； if i-1j then sym:=wsymk 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 in0.9) ； if knmax 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:=ssymch ； getch； end；：begin getch； if ch= then begin sym:=geq；getch；end else sym:=gtr； end； then begin sym:=neq；getch；end else sym:=lss；end end ； case end； 读单词子程序结束procedure gen(x：fct；y，z：integer) ； 代码生成子程序 begin if cxcxmax then begin write(program too long) ； goto 99 end； with codecx do begin f:=x；l:=y；a:=z end； cx:=cx+1end； 代码生成子程序结束 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 tabletx do begin name:=id；kind:=k； case kind of constant：begin if numamax 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 :=id；i:=tx； while tableI.nameid 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 symbecomes 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 codei do writeln(fw2，i，mnemonici：5，l:3，a：5) end； listcode procedure statement(fsys：symset)；语句处理子程序 var i，cxl，cx2integer； 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 tablei 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 numamax 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 intimes，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 addp:=sym；getsym； term(fsys+plus，minus)； if addop=plus then gen(opr，0，2) else gen(opr，0，3) endend；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 ineql，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； conditionbegin 语句处理子程序开始 if sym=ident then 赋值语句处理 begin i:=position(id) ； if i0 then error(11) else if tablei.kindvariable then begin error(12) ； 对非变量赋值 i:=0； end； getsym； if sym=becomes then getsym else error(13) ； expression(fsys) ； if i0 then with tablei do gen(sto，1ev-1evel，dr) end else if symreadsym then 读语句处理 begin getsym； if symlparen then error(34) e1se repeat getsym； if sym=ident then i:=position(id) else i:=0； if