59编译原理

第2章PL/0编译程序2.1PL/0语言和pcode的描述2.2PL/0编译程序的结构2.3PL/0编译程序的语法语义分析2.4PL/0编译程序的错误处理2.5pcode代码解释器本章目的：以PL/0为实例,学习编译程序实现的基本步骤和相关技术PL/0编译程序PL/0编译程序PL/0语言程序pcode代吗源语言(PL/0)目标语言(pcode)实现语言（pascal)PL/0pcodepascalPL/0编译程序pcode解释程序pcode代码PL/0源程序输入输出PL/0编译系统的结构框架PL/0语言PL/0程序示例PL/0的语法描述图PL/0语言文法的EBNF表示PL/0语言：PASCAL语言的子集PL/0程序示例CONSTA=10;（*常量说明部分*）VARB,C;（*变量说明部分*）PROCEDUREP;（*过程说明部分*）VARD;PROCEDUREQ;VARX;BEGINREAD(X);D:=X;WHILEX#0DOCALLP;END;BEGINWRITE(D);CALLQ;END;BEGINCALLP;END.Q的过程体p的过程体主程序体程序分程序.内的文字表示非终结符或内的文字或符号表示终结符constidentnumber=,;varident,;;procedureident;分程序语句分程序PL/0语言文法的EBNF表示EBNF引入的符号(元符号)：用左右尖括号括起来的语法成分为非终结符∷=(→)‘定义为’∷=(→)的左部由右部定义|‘或’{}表示花括号内的语法成分可重复任意次或限定次数[]表示方括号内的语法成分为任选项()表示圆括号内的成分优先例：用EBNF描述整数的定义：整数∷=[+|-]数字{数字}数字∷=0|1|2|3|4|5|6|7|8|9或更好的写法整数∷=[+|-]非零数字{数字}|0非零数字∷=1|2|3|4|5|6|7|8|9数字∷=0|非零数字PL/0语言是PASCAL语言的子集同PASCAL作用域规则（内层可引用包围它的外层定义的标识符），上下文约束，过程可嵌套定义，可递归调用子集数据类型,只有整型数据结构,只有简变和常数数字最多为14位标识符的有效长度是10语句种类过程最多可嵌套三层目标代码类pcode目标代码类pcode是一种假想栈式计算机的汇编语言。指令格式：flaf功能码l层次差（标识符引用层减去定义层）a根据不同的指令有所区别LIT0a将常数值取到栈顶，a为常数值LODla将变量值取到栈顶，a为偏移量，l为层差STOla将栈顶内容送入某变量单元中，a为偏移量，l为层差CALla调用过程，a为过程地址，l为层差INT0a在运行栈中为被调用的过程开辟a个单元的数据区JMP0a无条件跳转至a地址JPC0a条件跳转，当栈顶布尔值非真则跳转至a地址，否则顺序执行OPR00过程调用结束后,返回调用点并退栈OPR01栈顶元素取反OPR02次栈顶与栈顶相加，退两个栈元素，结果值进栈OPR03次栈顶减去栈顶，退两个栈元素，结果值进栈OPR04次栈顶乘以栈顶，退两个栈元素，结果值进栈OPR05次栈顶除以栈顶，退两个栈元素，结果值进栈OPR06栈顶元素的奇偶判断，结果值在栈顶OPR07OPR08次栈顶与栈顶是否相等，退两个栈元素，结果值进栈OPR09次栈顶与栈顶是否不等，退两个栈元素，结果值进栈OPR010次栈顶是否小于栈顶，退两个栈元素，结果值进栈OPR011次栈顶是否大于等于栈顶，退两个栈元素，结果值进栈OPR012次栈顶是否大于栈顶，退两个栈元素，结果值进栈OPR013次栈顶是否小于等于栈顶，退两个栈元素，结果值进栈OPR014栈顶值输出至屏幕OPR015屏幕输出换行OPR016从命令行读入一个输入置于栈顶指令功能表consta=10;varb,c;procedurep;beginc:=b+a;end;beginread(b);whileb#0dobegincallp;write(2*c);read(b);endend.(0)jmp08转向主程序入口(1)jmp02转向过程p入口(2)int03过程p入口,为过程p开辟空间(3)lod13取变量b的值到栈顶(4)lit010取常数10到栈顶(5)opr02次栈顶与栈顶相加(6)sto14栈顶值送变量c中(7)opr00退栈并返回调用点(16)(8)int05主程序入口开辟5个栈空间(9)opr016从命令行读入值置于栈顶(10)sto03将栈顶值存入变量b中(11)lod03将变量b的值取至栈顶(12)lit00将常数值0进栈(13)opr09次栈顶与栈顶是否不等(14)jpc024等时转(24)（条件不满足转）(15)cal02调用过程p(16)lit02常数值2进栈(17)lod04将变量c的值取至栈顶(18)opr04次栈顶与栈顶相乘(2*c)(19)opr014栈顶值输出至屏幕(20)opr015换行(21)opr016从命令行读取值到栈顶(22)sto03栈顶值送变量b中(23)jmp011无条件转到循环入口(11)(24)opr00结束退栈PL/0编译程序的结构词法分析程序语法语义分析程序代码生成程序表格管理程序出错处理程序PL/0源程序目标程序PL/0编译程序的总体设计其编译过程采用一趟扫描方式以语法、语义分析程序为核心词法分析程序和代码生成程序都作为一个过程，当语法分析需要读单词时就调用词法分析程序，而当语法、语义分析正确，需要生成相应的目标代码时，则调用代码生成程序。表格管理程序实现变量，常量和过程标识符的信息的登录与查找。出错处理程序，对词法和语法、语义分析遇到的错误给出在源程序中出错的位置和与错误性质有关的编号，并进行错误恢复。PL/0编译程序词法分析的设计与实现识别的单词：保留字或关键字：如：BEGIN、END、IF、THEN等运算符：如：+、-、*、/、：=、#、=、=等标识符：用户定义的变量名、常数名、过程名常数：如：10、25、100等整数界符：如：‘,’、‘.’、‘;’、‘(’、‘)’等词法分析过程GETSYM所要完成的任务：读源程序（getch)滤空格识别保留字识别标识符拼数识别单字符单词拼双字符单词词法分析过程程序（proceduregetsym）当识别到标识符时先查保留字表保留字表：（begin(*main*)）word[1]:=‘begin‘；word[2]:=‘call‘；...word[13]:=‘write‘；查到时找到相应的内部表示Wsym[1]:=beginsym;wsym[2]:=callsym；…wsym[13]:=writesym；字符对应的单词表：ssym[‘+’]:=plus;ssym[‘-’]:=minus;…ssym[‘;’]:=semicolon;词法分析如何把单词传递给语法分析typesymbol=(nul,ident,number,plus,…,varsym,procsym)；3个全程量sym:symbol;id:alfa;num:integer;通过三个全程量SYM、ID和NUM将识别出的单词信息传递给语法分析程序。SYM：存放单词的类别如：有程序段落为：begininitial:=60；end对应单词翻译后变为：beginbeginsym,initialident,‘:=‘becomes,60number,‘；’semicolon，endendsym。ID：存放用户所定义的标识符的值如：initial（在SYM中放ident，在ID中放initial）NUM：存放用户定义的数如：60（在SYM中放在number在NUM中放60）使用状态转换图实现词法分析程序的设计方法词法分析程序的设计---使用状态转换图实现表示状态，对应每个状态编一段程序，每个状态调用取字符程序，根据当前字符转到不同的状态，并做相应操作。表示终态，已识别出一个单词。1235141312109786411空格字母字母数字非字母数字数字数字非数字：==非==非=,+-(……PL/0编译程序语法语义分析PL/0编译程序语法分析的设计与实现自顶向下的语法分析递归子程序法程序分程序.constidentnumber=,;varident,;;procedureident;分程序语句分程序identreadend;语句表达式：=begin语句语句)(ident,自顶向下的语法分析VARA;BEGINREAD(A)END.程序分程序.变量说明部分语句VAR标识符；复合语句ABEGIN语句END读语句READ（标识符）A程序为文法的开始符号，以开始符号作为根结点构造一棵倒挂着的语法树。递归子程序法递归子程序法：对应每个非终结符语法单元，，编一个独立的处理过程（或子程序）。语法分析从读入第一个单词开始，由非终结符程序（即开始符）出发，沿语法描述图箭头所指出的方向进行分析。当遇到非终结符时，则调用相应的处理过程，从语法描述图看，也就进入了一个语法单元，再沿当前所进入的语法单元所指箭头方向继续进行分析。当遇到描述图中是终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，再读取下一个单词继续分析。遇到分支点时，将当前的单词与分支点上多个终结符逐个相比较，若都不匹配时可能是进入下一个非终结符语法单位或是出错。例：如何用递归子程序法实现表达式的语法分析项表达式+-项+-项因子因子*/语法图因子的语法图因子identnumber(表达式)表达式的EBNF〈表达式〉∷=[+|-]〈项〉{（+|-）〈项〉}〈项〉∷=〈因子〉{（*|/）〈因子〉}〈因子〉∷=〈标识符〉|〈无符号整数〉|‘（’〈表达式〉‘）’〈表达式〉的递归子程序实现procedureexpr;beginifsymin[plus,minus]thenbegingetsym;term;endelseterm;whilesymin[plus,minus]dobegingetsym;term;endend;〈表达式〉∷=[+|-]〈项〉{（+|-）〈项〉}〈项〉的递归子程序实现procedureterm;beginfactor;whilesymin[times,slash]dobegingetsym;factor;endend;〈项〉∷=〈因子〉{（*|/）〈因子〉}〈因子〉的递归子程序实现procedurefactor;beginifsym=identthengetsymelseifsym=numberthengetsymelseifsym=‘(‘thenbegingetsym;expr;ifsym=‘)’thengetsymelseerrorendelseerrorend;〈因子〉∷=〈标识符〉|〈无符号整数〉|‘（’〈表达式〉‘）’程序∷=分程序begin（*main*)…(*initialize*)…(*r/wfileset*)getsym;block();…ifsymperiodthenerror...end.。程序pl0分程序block语句statement条件condition表达式expression项term因子factor语法调用关系图编译程序总体流程图启动置初值调用GETSYM取单词调用BLOCK过程当前单词是否为源程序结束符'.'？出错源程序中是否有错误？调用解释过程INTERPRET解释执行目标程序打印错误结束NYYNPL/0编译程序语义分析的设计与实现PL/0编译程序语法、语义分析的的核心程序是BLOCK过程，说明部分的分析与处理表格管理过程体(语句）的分析与处理说明部分的分析与处理对每个过程（含主程序）说明的对象（变量，常量和过程）造符号表登录标识符的属性。标识符的属性:种类，所在层次,值和分配的相对位置。登录信息由ENTER过程完成。说明部分的分析与处理（程序）说明种类的定义：object=(constant,