编译原理实验精选文档.ppt

编译原理实验本讲稿第一页，共四十四页一.概述 1.源语言：求n！的极小语言 （文法见后）本讲稿第二页，共四十四页begin；end；integer 本讲稿第三页，共四十四页 abcdefghijklmno pq rstuvwxyz0123456789integer function（）；本讲稿第四页，共四十四页begin；end；read()write()本讲稿第五页，共四十四页:=-*本讲稿第六页，共四十四页ifthenelse =本讲稿第七页，共四十四页 2.工具语言:Pascal、C或其它 3.语法分析采用递归下降分析法 4.目标代码:P码 5.编译程序的结构本讲稿第八页，共四十四页源程序字符串.pas词法分析器语法分析器语义分析、中间代码生成器代码优化器目标代码生成器二元式序列.dyd二元式序列.dys中间代码序列.qud中间代码序列.qdo符 号 表 管 理 程 序出 错 处 理 程 序编译程序的结构编译程序的结构P码本讲稿第九页，共四十四页二.各阶段的输入输出 1.词法分析词法分析器源程序.pas二元式(文本文件.dyd)本讲稿第十页，共四十四页 2.语法分析语法分析器.dyd.dys同时,产生文本文件.var、.pro本讲稿第十一页，共四十四页 3.语义分析语义分析器.dys.qud(文本文件)同时,产生二进制文件.ooj、varfil、profil本讲稿第十二页，共四十四页 4.优化优化段.qud.ooj.qdo(文本文件)同时,产生二进制文件.coj本讲稿第十三页，共四十四页 5.目标代码生成目标代码生成器.qdo.coj.obj(P码)同时,产生二进制文件pf(目标指令)本讲稿第十四页，共四十四页三.数据结构 1.二元式文件.dyd (1)二元式形式:单词符号种别长度为16长度为2一个空格本讲稿第十五页，共四十四页单词符号单词符号种别种别单词符号单词符号种别种别单词符号单词符号种别种别1234567891011121314151617181920212223integerbeginendelsefunctionreadwrite标识符常数=-*:=();单词符号与种别对照表单词符号与种别对照表ifthen本讲稿第十六页，共四十四页 (2)每行后加一 “.EOLN24”(3)文件结尾加 “.EOF25”本讲稿第十七页，共四十四页 2.错误信息文件.err (1)错误信息格式 *LINE:行号错误性质 (2)注意:进入每一阶段,首先打开.err,如果无错误,则.err为空。3.dys 同.dyd本讲稿第十八页，共四十四页 4.变量名表u变量名vname:char(16)u所属过程vproc:char(16)u分类vkind:0.1(0变量、1形参)u变量类型vtype:typesu变量层次vlev:intu变量在变量表中的位置vadr:int(相对第一个变量而言)types=(ints)本讲稿第十九页，共四十四页 5.过程名表u过程名pname:char(16)u过程类型ptype:typesu过程层次plev:intu第一个变量在变量表中的位置fadr:intu最后一个变量在变量表中的位置ladr:int本讲稿第二十页，共四十四页 6.四元式表 (oprd,op1,op2,result)uoprd整数码uop1第一操作数uop2第二操作数uresult结果op1、op2、result可用“值/地址”表示本讲稿第二十一页，共四十四页 7.目标代码P码 参见目标代码(P码)指令表本讲稿第二十二页，共四十四页四.实现提示 1.多数文件均和源文件同名,仅扩展名不同。2.词法分析时,注意行尾和文件尾。3.词法分析的实现方法利用状态转换图 本讲稿第二十三页，共四十四页04123567开始空白字母/数字字母非字母数字数字非数字=-*数字89()本讲稿第二十四页，共四十四页101112=13141516其它=171819：其它=其它2021；其它*本讲稿第二十五页，共四十四页 4.（有过程说明时）设一个总的变量名表，查、填表时注意嵌套。5.语法错分类:(1)缺少符号错;(2)符号匹配错;(3)符号无定义或重复定义。6.递归下降分析时,必须先消除左递归。本讲稿第二十六页，共四十四页 7.递归下降分析时,跟踪符号的位置 当进入某过程时,其第一个符号必须已经读出;退出该过程时,必须读出该语法成分的右界符。本讲稿第二十七页，共四十四页例:G(E)EE+TT TT*FF F(E)iu消除左递归:ETE E+TE TFT T*FT F(E)i本讲稿第二十八页，共四十四页u过程match:匹配单词符号,并读入下一符号u变量lookahead:即将处理但尚未处理的符号procedure match(t:token);begin if lookahead=t then lookahead=nexttoken else errorend;本讲稿第二十九页，共四十四页procedure E;begin T;Eend;procedure T;begin F;Tend;本讲稿第三十页，共四十四页procedure E;if lookahead=+then begin match(+);T;E end;procedure T;if lookahead=*then begin match(*);F;T end;本讲稿第三十一页，共四十四页 8.进行自上而下语法制导翻译时,各过程返回的是指针。本讲稿第三十二页，共四十四页五.实验要求 1.至少完成词法、语法。2.提交:实验报告 (1)源程序、测试程序、运行结果 (2)设计思想、总控算法、主要服务子程序算法、总结(心得、收获、建议等)。本讲稿第三十三页，共四十四页测试程序begin integer k;integer function F(n);begin integer n;if n=赋值无条件转移JNZ(真转移)过程调用参数个数程序结束JZ(假转移)参数传递本讲稿第三十五页，共四十四页算符与整数码对照表算符与整数码对照表2算府算府整数码整数码算符算符整数码整数码算符算符整数码整数码参数返回242526272829303132参数过程返回READREADLNWRITEWRITELN变址存数变址取数其中：其中：22,26无操作数；无操作数；0,9,17,20,21,23,27,28,29只有一个操作数；只有一个操作数；16,18,19有两个操作数；有两个操作数；1,2,3,4,5,6,7,8,10,11,12,13,14,15,24,25,31,32有三个操作数。有三个操作数。本讲稿第三十六页，共四十四页目标代码（目标代码（P码）指令表码）指令表1编码助记符操 作 码参 数TPQ功 能 说 明T类型，类型，P层次号，层次号，Q栈内位移栈内位移根据根据P,Q形成栈地址，将其栈内单元的形成栈地址，将其栈内单元的值装载到栈顶单元值装载到栈顶单元0LODT栈单元类型栈单元类型,P层次号层次号,Q栈内位移栈内位移以以P,Q形成的栈地址单元的内容作为地址，形成的栈地址单元的内容作为地址，间接取栈单元的值装载到栈顶间接取栈单元的值装载到栈顶T类型，类型，P层次号，层次号，Q栈内位移栈内位移直接存取栈顶单元内容到直接存取栈顶单元内容到P,Q指定的栈单元中指定的栈单元中间接存取栈顶单元的内容，以间接存取栈顶单元的内容，以P,Q形成的栈形成的栈地址单元为间址单元地址单元为间址单元1LDO2STRSTO3本讲稿第三十七页，共四十四页目标代码（目标代码（P码）指令表码）指令表2编码助记符操 作 码参 数TP Q功 能 说 明将类型为将类型为T，值为，值为Q的常数装载到栈顶单元的常数装载到栈顶单元4LDC对栈顶单元中的整型数取负对栈顶单元中的整型数取负对栈顶单元中的实型数取负对栈顶单元中的实型数取负栈顶两单元整型数加操作栈顶两单元整型数加操作5NGI6NGRADI78ADR栈顶两单元实型数加操作栈顶两单元实型数加操作9SBI栈顶两单元整型数减操作栈顶两单元整型数减操作本讲稿第三十八页，共四十四页目标代码（目标代码（P码）指令表码）指令表3编码助记符操 作 码参 数TPQ功 能 说 明栈顶两单元实型数减操作栈顶两单元实型数减操作10SBR栈顶两单元整型数乘操作栈顶两单元整型数乘操作栈顶两单元实型数乘操作栈顶两单元实型数乘操作栈顶两单元整型数除操作栈顶两单元整型数除操作11MPI12MPRDVR1314DVI栈顶两单元实型数除操作栈顶两单元实型数除操作15MOD栈顶两单元整型数取余操作栈顶两单元整型数取余操作本讲稿第三十九页，共四十四页目标代码（目标代码（P码）指令表码）指令表4编码助记符操 作 码参 数TPQ功 能 说 明与操作与操作16AND或操作或操作非操作非操作大于比较大于比较17OR18NOTGRT1920GEQ大于等于比较大于等于比较21LES小于比较小于比较本讲稿第四十页，共四十四页目标代码（目标代码（P码）指令表码）指令表5编码助记符操 作 码参 数TPQ功 能 说 明小于等于比较小于等于比较22LEQ不等于比较不等于比较等于比较等于比较条件成立转移。若栈顶单元的布尔值为真，条件成立转移。若栈顶单元的布尔值为真，则转移至则转移至Q表示的目标指令序号执行表示的目标指令序号执行23NEQ24EQTJP2526FJP假转移。若栈顶单元的布尔值为假，则转移假转移。若栈顶单元的布尔值为假，则转移至至Q表示的目标指令序号执行表示的目标指令序号执行27UJP无条件转移无条件转移本讲稿第四十一页，共四十四页目标代码（目标代码（P码）指令表码）指令表6编码助记符操 作 码参 数TPQ功 能 说 明转移至过程的起始目标指令处转移至过程的起始目标指令处28PROC过程调用指令，生成过程的内务管理数据区过程调用指令，生成过程的内务管理数据区过程返回，释放栈成分过程返回，释放栈成分分配一个栈单元分配一个栈单元29CALL30RETLD3132LDA取数组元素内容，装入栈顶单元取数组元素内容，装入栈顶单元33STA将数组元素值存入栈单元将数组元素值存入栈单元本讲稿第四十二页，共四十四页目标代码（目标代码（P码）指令表码）指令表7编码助记符操 作 码参 数TPQ功 能 说 明非换行读入数据，装入栈顶非换行读入数据，装入栈顶34RAD换行读入数据，装入栈顶换行读入数据，装入栈顶非换行输出栈顶单元内容非换行输出栈顶单元内容换行输出栈顶单元内容换行输出栈顶单元内容35RDN36WRIWRN37本讲稿第四十三页，共四十四页上机安排u时间第13周开始，周一晚7:3010:00u地点清水河校区实验大楼本讲稿第四十四页，共四十四页