第2章--PL0编译程序的实现解析.ppt

第2章PL 0编译程序的实现 本章目的 以PL 0编译程序为实例 学习编译程序实现的基本步骤和相关技术1PL 0编译程序的结构2PL 0编译程序的分析工作 词法 语法和语义 实现3PL 0编译程序的错误处理方法4目标代码生成和类pcode代码解释器 1 PL 0编译程序的结构 PL 0编译程序 PL 0语言程序 类p code代码 源语言 PL 0 目标语言 类p code 实现语言 pascal C PL 0 类p code pascal C PL 0编译程序 类p code解释程序 类p code代码 PL 0源程序 输入数据 输出数据 PL 0编译系统的结构框架 PL 0语言 PL 0语言 PASCAL语言的子集PL 0程序示例PL 0的语法描述图PL 0语言的EBNF表示 PL 0程序示例 CONSTA 10 常量说明部分 VARB C 变量说明部分 PROCEDUREP 过程说明部分 VARD P的局部变量说明部分 PROCEDUREQ P的局部过程说明部分 VARX BEGINREAD X D X WHILEX 0DOCALLP END BEGINWRITE D CALLQ END BEGINCALLP END Q过程体 p过程体 主程序体 输入圆柱的半径和高 计算一些面积 体积等 varr h len a1 a2 volumn beginread r read h len 2 3 r a1 3 r r a2 a1 a1 len h volumn a1 h write len write a1 write a2 write volumn end 计算最大公约数 varm n r q 计算m和n的最大公约数 proceduregcd beginwhiler 0dobeginq m n r m q n m n n r endend beginread m read n 为了方便 规定m n ifm nthenbeginr m m n n r end beginr 1 callgcd write m end end pl 0程序 递规调用 varn procedurerec beginifn 0thenbeginwrite n n n 1 callrec end end beginread n callrec end 计算sum 1 2 n n从控制台读入 varn m fact sum 递规计算fact m procedurefactorial beginifm 0thenbeginfact fact m m m 1 callfactorial end end begin 读入n read n sum 0 whilen 0dobeginm n fact 1 callfactorial sum sum fact n n 1 end 输出n write sum end 程序 分程序 内的文字表示语法成分 短语 或 内的文字表示单词符号 程序 内的文字表示语法成分 短语 语法图 const ident number var ident procedure ident 分程序 语句 分程序 PL 0语言的EBNF表示 构成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语句种类过程无参 最多可嵌套三层 目标代码类p code 目标代码类p code是一种栈式机的汇编语言 栈式机系统结构 没有累加器和寄存器 只有存储栈指针所有运算都在栈顶 零地址机 指令格式 fla f功能码l层次差 标识符引用层减去定义层 a根据不同的指令有所区别 指令功能表 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编译程序的总体设计 以语法 语义分析程序为核心词法分析程序和代码生成程序都作为一个过程 当语法分析需要读单词时就调用词法分析程序 而当语法 语义分析正确 需要生成相应的目标代码时 则调用代码生成程序 表格管理程序实现变量 常量和过程标识符的信息的登录与查找 出错处理程序 对词法和语法 语义分析遇到的错误给出在源程序中出错的位置和与错误性质有关的编号 并进行错误恢复 第2章PL 0编译程序 本章目的 以PL 0编译程序为实例 学习编译程序实现的基本步骤和相关技术1PL 0编译程序的结构2PL 0编译程序的分析工作 词法 语法和语义 实现3PL 0编译程序的错误处理方法4目标代码生成和类pcode代码解释器 2PL 0编译程序的分析工作 词法 语法和语义 2 1PL 0编译程序词法分析的实现 识别的单词 保留字或关键字 如 BEGIN END IF THEN等运算符 如 等标识符 用户定义的变量名 常数名 过程名常数 如 10 25 100等整数界符 如 等 词法分析过程GETSYM所要完成的任务 从源程序读字符 getch 滤空格识别保留字识别标识符拼数识别单字符单词拼双字符单词 词法分析过程 GETSYM框图 见教材图2 5 程序 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 使用状态转换图实现词法分析程序的设计方法 词法分析程序的设计 使用状态转换图实现 表示状态 对应每个状态编一段程序 每个状态调用取字符程序 根据当前字符转到不同的状态 并做相应操作 表示终态 已识别出一个单词 2 2PL 0编译程序语法分析 自顶向下的语法分析递归子程序法 上下文无关文法 句型的分析 句型分析就是识别一个符号串是否为某文法的句型的过程 或者说是某个推导的构造过程 对于一个给定的文法 要想判定一个符号串是否为该文法的句子 需要考察是否可以从该文法的开始符号派生出 推导出 此符号串 编译程序的语法分析工作 分析算法分类 分析算法可分为 自上而下分析法 从文法的开始符号出发 寻找与输入符号串匹配的推导 或者说 为输入串寻找一个最左推导 自下而上分析法 从输入符号串开始 逐步进行归约 直至归约到文法的开始符号 语法分析 从概念上讲 建立一棵与输入串相匹配的语法树 语法树 推导的几何表示 句型aabbaa的可能推导序列和语法树 例 G S S aASA SbAA SSS aA ba SaASSbAaaba S aAS aAa aSbAa aSbbaa aabbaaS aAS aSbAS aabAS aabbaS aabbaaS aAS aSbAS aSbAa aabAa aabbaa 两种方法反映了语法树的两种构造过程 自上而下方法是从文法符号开始 将它做为语法树的根 向下逐步建立语法树 使语法树的结果正好是输入符号串自下而上方法则是从输入符号串开始 以它做为语法树的结果 自底向上的构造语法树 自上而下的语法分析的一般过程 例 文法G S cAdA abA a识别输入串w cabd是否为该文法的句子 SSScAdcAdab推导过程 S cAdcAd cabd 程序 分程序 const ident number var ident procedure ident 分程序 语句 分程序 ident read end 语句 表达式 begin 语句 语句 ident 自顶向下的语法分析 VARA BEGINREAD A END VAR ABEGINENDREAD A 为文法的开始符号 以开始符号作为根结点构造一棵倒挂着的语法树 递归子程序法 语法分析程序由一组递归过程组成 对应每个非终结符 语法单元 编一个独立的处理过程 或函数 子程序 由 即开始符 开始 沿语法描述图箭头所指出的方向进行分析 规则右部 遇到非终结符 进入了又一个语法单元 则调用相应的处理过程遇到终结符 则判断当前读入的单词是否与该终结符相匹配 若匹配 再读取下一个单词继续分析 也称为递归下降分析器 recursive descentparser 例 表达式的语法分析程序 递归子程序 项 表达式 项 项 因子 因子 语法图 因子的语法图 因子 ident number 表达式 表达式的EBNF 表达式 项 项 项 因子 因子 因子 标识符 无符号整数 表达式 表达式 项 项 pascal 表达式 的分析程序 递归子程序 procedureexpr beginifsymin plus minus thenbegingetsym term endelseterm whilesymin plus minus dobegingetsym term endend 项 因子 因子 pascal 项 的分析程序 递归子程序 procedureterm beginfactor whilesymin times slash dobegingetsym factor endend 因子 标识符 无符号整数 表达式 因子 的分析程序 递归子程序 procedurefactor beginifsymidentthenbeginifsymnumberthenbeginifsym thenbegingetsym expr ifsym thengetsymelseerrorendelseerrorendelsegetsymendelsegetsymend 表达式 项 项 inC intexpression bool fsys int ptx intlev if sym plus sym minus 开头的正负号 当前表达式被看作一个正的或负的项 getsymdo termdo nxtlev ptx lev 处理项 else 此时表达式被看作项的加减 termdo nxtlev ptx lev 处理项 while sym plus sym minus getsymdo termdo nxtlev ptx lev 处理项 return0 项 因子 因子 intterm bool fsys int ptx intlev factordo nxtlev ptx lev 处理因子 while sym times sym slash getsymdo factordo nxtlev ptx lev return0 因子 标识符 无符号整数 表达式 intfactor bool fsys int ptx intlev if sym ident 因子为常量或变量 getsymdo else if sym number 因子为 getsymdo elseif sym lparen 因子为表达式 expressiondo nxtlev ptx lev if sym rparen getsymdo elseerror 22 缺少右括号 return0 begin main initialize r wfileset getsym block ifsymperiodthenerror end 程序pl0 分程序block 语句statement 条件condition 表达式expression 项term 因子factor 语法调用关系图 编译系统总体流程图 2 3PL 0编译程序语义分析的设计与实现 PL 0编译程序语法 语义分析的的核心程序是BLOCK过程哪些语义分析工作 如何实现 语义分析环境 符号表 说明部分的分析与处理表格管理过程体 语句 的分析与处理 因子 标识符 无符号整数 表达式 语义分析intfactor bool fsys int ptx intlev if sym ident 因子为常量或变量 i position id ptx 查找名字 if i 0 error 11 标识符未声明 else switch table i kind caseconstant 名字为常量 break casevariable 名字为变量 break caseprocedur 名字为过程 error 21 不能为过程名 登录符号表说明部分的分析与处理 对每个过程 含主程序 说明的对象 变量 常量和过程 造符号表登录标识符的属性 标识符的属性 种类 所在层次 值和分配的相对位置 登录信息由ENTER过程完成 符号表结构 Enumobject constant variable procedur Structtablestruct charname al enumobjectkind intval intlevel intadr intsize Structtablestructtable txmax 符号表结构 说明种类的定义 object constant variable procedur 定义纯量 枚举类型 符号表的定义table array 0 txmax ofrecordname alfa casekind objectofconstant val integer variable procedur level adr size integer 例程序说明部分为 CONSTA 35 B 49 VARC D E PROCEDUREP VARG 符号表 名字种类层次 值地址存储空间 对应名字表 tx table表的下标指针 是以值参数形式使用的 dx 计算每个变量在运行栈中相对本过程基地址的偏移量 放在table表中的adr域 生成目标代码时再放在code中的a域 变量定义语句的处理 C 语法 var 程序 if sym varsym 收到变量声明符号 开始处理变量声明 getsymdo do vardeclarationdo 注意 tx 变量说明处理 C intvardeclaration int ptx intlev int pdx if sym ident enter variable ptx lev pdx 填写名字表getsymdo else error 4 var后应是标识符 return0 变量定义语句的处理 语法 var 程序 ifsym varsymthenbegingetsym repeatvardeclaration 变量说明处理 whilesym commadobegingetsym vardeclarationend ifsym semicolonthengetsymelseerror 5 untilsymident end 变量说明处理 procedurevardeclaration beginifsym identthenbeginenter variable getsymendelseerror 4 end vardeclaration 过程ENTER的实现 C 在名字表中加入一项 k 名字种类const varorprocedure ptx 名字表尾指针的指针 lev 名字所在的层次 以后所有的lev都是这样 pdx 当前应分配变量的相对地址 分配后增加1 voidenter enumobjectk int ptx intlev int pdx 过程ENTER的实现 C ptx strcpy table ptx name id 全局变量id中已存有当前名字的名字 table ptx kind k switch k caseconstant 常量名字 if num amax error 31 数越界 num 0 table ptx val num break 过程ENTER的实现 C casevariable 变量名字 table ptx level lev table ptx adr pdx pdx break caseprocedur 过程名字 table ptx level lev break 过程ENTER的实现 tx table表的指针procedureenter k object begin enterobjectintotable tx tx 1 withtable tx do 开域语句 beginname id 表示table tx name id kind k 表示table tx kind k 过程ENTER的实现 casekofconstant beginifnum amaxthenbeginerror 31 num 0 end val num table tx val num end 过程ENTER的实现 variable beginlevel lev 表示table tx level lev adr dx 表示table tx adr dx dx dx 1 end procedur level lev 表示table tx level lev end case endend enter 过程体的处理 编译程序主体 lev 当前分程序所在层 tx 名字表当前尾指针 fsys 当前模块后跟符号集合 intblock intlev inttx bool fsys 过程体的处理 main 函数if 1 block 0 0 nxtlev if sym period error 9 interpret 调用解释执行程序 过程体的处理 while sym procsym block 函数 getsymdo if sym ident enter procedur if 1 block lev 1 tx nxtlev 过程体的处理 变量引用的处理 对语句进行语法分析语义分析当遇到标识符的引用时就调用POSITION函数查TABLE表 看是否有过正确定义 若已有 则从表中取相应的有关信息 供代码的生成使用 若无定义则错 语义分析TABLE表若已有过正确定义 检查引用与说明的属性是否一致 若不一致则错 当语法语义正确时 就生成相应语句功能的目标代码 赋值语句的处理 C if sym ident 准备按照赋值语句处理 i position id ptx if i 0 error 11 变量未找到 else if table i kind variable error 12 赋值语句格式错误 i 0 else gendo sto lev table i level table i adr 赋值语句的处理 ifsym identthenbegini position id ifi 0thenerror 11 elseiftable i kindvariablethenbeginerror 12 i 0end getsym ifsym becomesthengetsymelseerror 13 expression fsys ifi0thenwithtable i dogen sto lev level adr end 第2章PL 0编译程序 本章目的 以PL 0编译程序为实例 学习编译程序实现的基本步骤和相关技术1PL 0编译程序的结构2PL 0编译程序的分析工作 词法 语法和语义 实现3PL 0编译程序的错误处理方法4目标代码生成和类pcode代码解释器 编译程序的错误处理 错误处理的原则 尽可能准确指出出错位置 错误性质 尽可能进行校正 PL 0编译程序对语法错误的处理 1 对于易于校正的错误 如丢了逗号 分号等 指出出错位置 加以校正 继续进行分析 2 对于难于校正的错误 给出错误的位置与性质 跳过后面的一些单词 直到下一个可以进行正常语法分析的语法单位 在进入某个语法单位时 调用TEST 检查当前符号是否属于该语法单位的开始符号集合 若不属于 则滤去开始符号和后跟符号集合外的所有符号 在语法单位分析结束时 调用TEST 检查当前符号是否属于调用该语法单位时应有的后跟符号集合 若不属于 则滤去后跟符号和开始符号集合外的所有符号 TESTTEST 开始符号集合与后跟符号集合 开始符号集合symset setofsymbol declbegsys statbegsys facbegsys symset 开始符号集合 主程序 declbegsys constsym varsym procsym statbegsys beginsym callsym ifsym whilesym readsym writesym facbegsys ident number lparen 后跟符号集合fsys作为参数 proceduretest s1 s2 symset n integer procedureblock lev tx integer fsys symset procedurestatement fsys symset procedureexpression fsys symset procedureterm fsys symset procedurefactor fsys symset READ语句的分析处理 C if sym readsym 处理read语句getsymdo if sym lparen error 34 格式错误 应是左括号 else do getsymdo READ语句的语法语义分析处理 ifsym readsymthenbegingetsym ifsymlparenthenerror 34 elserepeatgetsym READ语句的语法语义分析处理 ifsym identtheni position id elsei 0 ifi 0thenerror 35 elsewithtable i dobegingen opr 0 16 gen sto lev level adr end READ语句的语法语义分析处理 getsymuntilsymcomma ifsymrparenthenbeginerror 33 whilenot syminfsys dogetsymendelsegetsymend 出错处理跳过不应出现的符号 正确出口 TEST SYM在S1中 打印出错编号n S1 S1 S2 SYM在S1中 GETSYM 返回 Y Y N N TEST测试过程流程图 因子的处理过程 例 因子的处理过程procedurefactor fsys symset vari integer begin入口 test facbegsys fsys 24 whilesyminfacbegsysdobeginif 出口 test fsys facbegsys 23 endend 因子的处理过程 Facbegsys y 处理identnumber lparen test n test 增加后跟符与调用位置有关例 调用expression fsys write语句的语法write write语句 后调用expression时后跟符expression rparen comma fsys factor的语法 factor exp 在factor 后调用expression时后跟符expression rparen fsys 第2章PL 0编译程序 本章目的 以PL 0编译程序为实例 学习编译程序实现的基本步骤和相关技术1PL 0编译程序的结构2PL 0编译程序的分析工作 词法 语法和语义 实现3PL 0编译程序的错误处理方法4目标代码生成和类pcode代码解释器 代码生成 代码生成是由过程GEN完成 GEN有3个参数 分别代表目标代码的功能码 层差和位移量 例如gen opr 0 16 gen sto lev level adr lev 当前处理的过程层次level 被引用变量或过程所在层次CX 为目标代码code数组的下标指针 代码结构变换 地址返填 Ifcthensgetsym condition ifsym thensymthengetsymelseerror 16 cx1 cx gen jpc 0 0 statement code cx1 a cx 类p code代码解释器的实现 类p code目标机结构目标代码解释执行时数据栈的布局 运行栈的存储分配 目标代码类p code 目标代码类p code是一种栈式机的汇编语言 栈式机系统结构 没有累加器和寄存器 只有存储栈指针所有运算都在栈顶 零地址机 指令格式 fla f功能码l层次差 标识符引用层减去定义层 a根据不同的指令有所区别 类p code解释器的结构 目标代码 指令 存放在数组CODE中 程序地址寄存器p 解释程序定义一个一维整型数组S作为运行栈栈顶寄存器 指针 t 基址寄存器 指针 b 指令寄存器i 当前正在解释的目标指令 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结束退栈 目标代码解释执行时数据栈的布局 运行栈的存储分配 在每个过程调用时在栈顶分配3个联系单元 SL 静态链 指向定义该过程的直接外过程 或主程序 运行时最新数据段的基地址 DL 动态链 指向调用该过程前正在运行过程的数据段基地址 RA 返回地址 记录调用该过程时目标程序的断点 即调用过程指令的下一条指令的地址 Varx y ProcedureP vara procedureQ varb begin Q b 10 end Q procedureS varc d procedureR vare f begin R callQ end R begin S callR end S begin P callS end P begin MAIN callP end MAIN 目标代码的解释执行运行栈S M调用过程PM调用过程PP调用过程S RADLSL b t t b P M P M S 目标代码的解释执行 几条特殊指令在code中的位置和功能INT0A在过程目标程序的入口处 开辟A个单元的数据段 A为局部变量的个数 3 OPR00在过程目标程序的出口处 释放数据段 退栈 恢复调用该过程前正在运行的过程的数据段基址寄存器B和栈顶寄存器T的值 并将返回地址送到指令地址寄存器P中 以使调用前的程序从断点开始继续执行 目标代码的解释执行 几条特殊指令在code中的位置和功能CALLA调用过程 还完成填写静态链 动态链 返回地址 给出被调用过程的基地址值 送入基址寄存器B中 目标程序的入口地址A的值送指令地址寄存器P中 使指令从A开始执行 CX 为目标代码code数组的下标指针 code为一维数组 数组元素为记录型数据 每一个记录就是一条目标指令 CX为整数变量 由0开始顺序增加 实际上目标代码的顺序是内层过程的在前边 主程序的目标代码在最后 tx table表的下标指针 是以值参数形式使用的 dx 计算每个变量在运行栈中相对本过程基地址的偏移量 放在table表中的adr域 生成目标代码时再放在code中的a域 下标指针cx tx和变量dx的作用 code cx table tx s t 运行栈 cxtxt 运行时栈指针 0 jmp00 1 int07 cx 0 name adr 1 b dx tx q p m b Table表的下标指针tx补充说明 主程序 BLOCK 第1次调用blockBLOCK 0 0 0 0 BLOCK BLOCK LEV 1 TX 递归进入分程序 LEV tx LEV tx 6 6 9 1 tx是BLOCK的实际值参 PL 0编译程序的实现 proceduregen x fct y z integer beginifcx cxmaxthen 指针越界 beginwrite programtoolong close fin 关闭文件 writeln exitend PL 0编译程序的实现 withcode cx dobeginf x 表示code cx f x l y 表示code cx l y a z 表示code cx a z end cx cx 1end gen PL 0编译程序的实现 对分程序的定义 见教材417 437页 procedureblock lev tx in