编译实验一指导.ppt

第二章编译程序的实现 1 第二章编译程序的实现 一 PL 0编译程序的词法分析二 PL 0编译程序的语法分析三 PL 0编译程序的伪代码生成 第二章编译程序的实现 2 一 PL 0编译程序的词法分析 1 基本思想2 PL 0程序设计语言的词法规则3 完成的任务4 PL 0词法分析程序的设计5 词法分析程序的输入和输出6 实验要求 第二章编译程序的实现 3 采用直接分析法 根据读入的第一个字符的种类 分别转入到相应的程序段去处理 从而最终把单词识别出来 1 基本思想 第二章编译程序的实现 4 A B X Y Z 0 1 8 9 BEGIN CALL CONST DO END IF ODD PROCEDURE PROGRAM READ THEN VAR WHILE WRITE 2 PL 0程序设计语言的词法规则 第二章编译程序的实现 5 1 滤空格 2 识别保留字 3 识别标识符 4 识别常量 5 识别界符 3 完成的任务 第二章编译程序的实现 6 CH 当前符号 ID 当前标识符的单词自身值 SYM 当前单词的类别值 NUM 当前常量的单词自身值 WORD 保留字表 WSYM 保留字的单词类别值表 SSYM 界符的类别值 4 PL 0词法分析程序的设计 第二章编译程序的实现 7 保留字表的定义 charword 14 10 BEGIN CALL CONST DO END IF ODD PROCEDURE PROGRAM READ THEN VAR WHILE WRITE 保留字的单词类别值表的定义 charwsym 14 10 BEGINSYM CALLSYM CONSTSYM DOSYM ENDSYM IFSYM ODDSYM PROCSYM PROGSYM READSYM THENSYM VARSYM WHILESYM WRITESYM 第二章编译程序的实现 8 界符表的定义 charsymble 11 界符类别值表的定义 charssym 11 10 plus minus times slash lparen rplren eql comma peried neq semicolon 第二章编译程序的实现 9 词法分析程序的程序框图 第二章编译程序的实现 10 CH fgetc CH 字母 K 0 CH 数字 K 10 K K 1 A K CH SYM NUMBER NUM 数值 SYM SSYM CH fgetc 字母 数字 ID A 保留字 SYM WSYM K SYM IDENT N Y Y N N Y Y Y N N N Y 标识符 保留字 常量 界符 滤空格 标识符长度小于10 第二章编译程序的实现 11 输入 PL 0源程序 保存在一个文本文件中 输出 单词类别值 单词自身值组成的二元组 保存在一个文本文件中 5 词法分析程序的输入和输出 第二章编译程序的实现 12 PL 0源程序 PROGRAMmain CONSTa 10 e 5 VARf g PROGRAMPROGSYM mainIDENT SEMICOLON CONSTCONSTSYM aIDENT EQL 10NUMBER COMMA eIDENT EQL 5NUMBER SEMICOLON VARVARSYM fIDENT COMMA gIDENT SEMICOLON 词法分析程序输出 第二章编译程序的实现 13 BEGINg a e f g WRITE g END BEGINBEGINSYM gIDENT BECOMES aIDENT PLUS eIDENT SEMICOLON fIDENT BECOMES gIDENT SEMICOLON WRITEWRITESYM LPAREN gIDENT RPAREN ENDENDSYM PERIOD PL 0源程序 续 词法分析程序输出 续 第二章编译程序的实现 14 6实验要求 实验名称 词法分析程序实验目的 实现功能 实验报告内容 第二章编译程序的实现 15 设计 编制 调试一个词法分析程序 加深对词法分析原理的理解 实验目的 第二章编译程序的实现 16 通过对PL 0词法分析程序的分析 编制出一个词法分析程序 此程序应具有如下功能 1 输入为PL 0源程序 输出为由 单词自身值 单词类别值 组成的二元组 2 有一定的出错处理能力 实现功能 第二章编译程序的实现 17 目的要求 算法描述 程序结构 主要变量名说明 程序清单 调试情况 设计技巧 心得体会 实验报告内容 第二章编译程序的实现 18 二 PL 0编译程序的语法分析 1 基本思想2 PL 0语法规则的BNF表示3 语法分析程序的输入和输出4 符号表的建立5 实验要求 第二章编译程序的实现 19 采用自顶向下的递归子程序法 即为每一个非终结符号编写一个独立的子程序 1 基本思想 第二章编译程序的实现 20 2 PL 0语法规则的BNF表示 PROGRAM 举例 PROGRAMtest 程序名 第二章编译程序的实现 21 2 PL 0语法规则的BNF表示 例如 PROGRAMmain CONSTa 10 b 5 VARx y PROCEDUREtest1CONSTc 20 d 30 VARx1 y1 BEGIN END BEGIN END 常量说明 变量说明 过程说明 常量说明 变量说明 第二章编译程序的实现 22 2 PL 0语法规则的BNF表示 CONST 举例 CONSTa 10 b 5 常量定义 第二章编译程序的实现 23 2 PL 0语法规则的BNF表示 VAR 举例 VARa b 第二章编译程序的实现 24 2 PL 0语法规则的BNF表示 PROCEDURE 举例 PROCEDUREtest1 过程名 第二章编译程序的实现 25 2 PL 0语法规则的BNF表示 BEGIN END 举例 BEGINa b c IFa 0THENflag 1END 第二章编译程序的实现 26 2 PL 0语法规则的BNF表示 PROCEDURESTATEMENTP297 P300 第二章编译程序的实现 27 2 PL 0语法规则的BNF表示 举例 a b c 第二章编译程序的实现 28 2 PL 0语法规则的BNF表示 READ 举例 READ a b c 第二章编译程序的实现 29 2 PL 0语法规则的BNF表示 WRITE 举例 WRITE a b b c 第二章编译程序的实现 30 2 PL 0语法规则的BNF表示 CALL 举例 CALLtest1 过程名 第二章编译程序的实现 31 2 PL 0语法规则的BNF表示 IFTHEN 举例 IFa 0THENflag 1 第二章编译程序的实现 32 2 PL 0语法规则的BNF表示 举例 BEGINa b c IFa 0THENflag 1END BEGIN END 第二章编译程序的实现 33 2 PL 0语法规则的BNF表示 WHILEDO 例 WHILEa 0DOflag 1 第二章编译程序的实现 34 2 PL 0语法规则的BNF表示 PROCEDUREFACTORP294 P295 第二章编译程序的实现 35 2 PL 0语法规则的BNF表示 PROCEDURETERMP295 P296 左递归 第二章编译程序的实现 36 2 PL 0语法规则的BNF表示 PROCEDUREEXPRESSIONP296 左递归 第二章编译程序的实现 37 2 PL 0语法规则的BNF表示 ODD PROCEDURECONDITIONP296 P297 第二章编译程序的实现 38 3 语法分析程序的输入 PROGRAMmysource CONSTa 10 VARb c PROCEDUREp VARd PROCEDUREq CONSTe 5 VARf PROCEDUREr VARg BEGINg a e f g WRITE g END BEGINCALLr WRITE f f a e f WRITE f d END BEGINd a b WRITE d CALLqEND PROCEDUREs BEGINCALLp b 10 WRITE b END 过程q的过程体 过程p的过程体 BEGINb 8 READ c WHILEc 0DOBEGINWRITE b CALLs b b c WRITE b READ c END CALLpEND 主程序的程序体 过程r的过程体 过程s的过程体 第二章编译程序的实现 39 PROGRAMPROGSYM mysourceIDENT CONSTCONSTSYM aIDENT EQL 10NUMBER SEMICOLON VARVARSYM bIDENT COMMA cIDENT SEMICOLON PROCEDUREPROCSYM gIDENT BECOMES aIDENT PLUS eIDENT SEMICOLON ThisisaassignStatement 赋值语句 fIDENT BECOMES gIDENT SEMICOLON ThisisaassignStatement 赋值语句 WRITEWRITESYM LPAREN gIDENT RPAREN SEMICOLON ThisisawriteStatement 写语句 4 语法分析程序的输出 第二章编译程序的实现 40 符号表的内容符号表的结构相关子程序的流程图实验要求 符号表 第二章编译程序的实现 41 PL 0编译文本是在处理 1 变量说明VAR 2 常量说明CONST 3 过程说明PROCEDURE建立符号表table按照标识符在源程序出现的先后顺序来建表 符号表的建立 第二章编译程序的实现 42 标识符名 NAME类型 KIND CONSTANT 常量 VARIABLE 变量 PROCEDURE 过程 值或层次 VAL或LEVEL地址 ADR大小 SIZE 符号表的内容 第二章编译程序的实现 43 地址 ADR简单变量或常量 该量在数据区所占单元的绝对地址或相对地址 过程 该过程的分程序的入口地址 需要返填 地址 ADR 第二章编译程序的实现 44 大小 SIZE过程 该过程局部变量的个数 需要返填 大小 SIZE 第二章编译程序的实现 45 值或层次 VAL或LEVEL 1 若类型为CONSTANT 存放常量的值 2 若类型为VARIABLE或PROCEDURE 存放所属分程序的层次 主程序的层次为0 值或层次 VAL或LEVEL 第二章编译程序的实现 46 PROGRAMmain 符号表的内容 PL 0源程序 TABLE a VARIABLE 0 DX 3 d VARIABLE 0 DX 4 p1 PROCEDURE 0 P1入口 返填 6 x VARIABLE 1 DX 3 y VARIABLE 1 DX 4 z VARIABLE 1 DX 5 p2 PROCEDURE 1 P2入口 返填 u VARIABLE 2 DX 3 6 v VARIABLE 2 DX 4 d VARIABLE 2 DX 5 p3 PROCEDURE 2 P3入口 返填 5 i VARIABLE 3 DX 3 j VARIABLE 3 DX 4 PROCEDUREp1 VARx y z PROCEDUREp2 VARu v d PROCEDUREp3 VARi j VARa d 第二章编译程序的实现 47 LEVEL 过程说明语句PROCEDURE的层次与该过程中的局部变量的层次相差1 ADR 在PL 0中使用一个运行栈 而运行栈的前3个单元即0 1 2单元分别为SL 静态链 DL 动态链 RA 返回地址 所以从第3个单元开始给变量分配单元 注意事项 第二章编译程序的实现 48 Structtab charname 14 enumsortkind intval intlevel intadr intsize table 100 enumsort CONSTANT VARIABLE PROCEDURE 符号表的结构 第二章编译程序的实现 49 相关子程序的流程图 主程序结构Block 的结构及参数程序框图程序框图程序框图程序框图程序框图建符号表ENTER 程序框图查表程序POSITION 第二章编译程序的实现 50 1 识别PROGRAMmain 2 调用BLOCK BLOCK 可以递归调用 1 CONST说明 2 VAR说明 3 PROCEDURE说明 4 调用Statement 3 判别PERIOD 主程序结构 P305 第二章编译程序的实现 51 PROCEDUREBlock LEV TX VARDX Statement Block 的结构 P300 P301 第二章编译程序的实现 52 Block 的参数 参数 LEV 本层的静态 定义 层次 TX 当前TABLE表中有信息的最后单元的位置 DX 当前运行栈中第一个可用单元 初值为3 相对地址 第二章编译程序的实现 53 框图 SYM IDENT GETSYM SYM EQL GETSYM ENTER CONSTANT SYM NUMBER ERROR 2 常量说明中 之后不是数字 Y N 常量说明中标识符的后继不是 ERROR 3 ERROR 4 结束 Y Y N N Const var procedure后应为标识符 写符号表 第二章编译程序的实现 54 框图 SYM CONSTSYM GETSYM CONSTDECLARATION SYM COMMA GETSYM CONSTDECLARATION SYM SEMICOLON GETSYM ERROR 5 A 常量定义 变量说明部分 Y N Y N 漏掉了 或 Y N CONST 第二章编译程序的实现 55 框图 SYM IDENT ENTER VARIABLE ERROR 4 Y N GETSYM 结束 写符号表 Const var procedure后应为标识符 第二章编译程序的实现 56 框图 SYM VARSYM GETSYM VARDECLARATION SYM COMMA GETSYM VARDECLARATION SYM SEMICOLON GETSYM ERROR 5 B 变量定义 过程说明部分 A N Y VAR Y N 漏掉了 或 N 第二章编译程序的实现 57 框图 SYM PROCSYM GETSYM ENTER PROCEDURE SYM IDENT GETSYM GETSYM SYM SEMICOLON Block LEV 1 ERROR 5 B N Y Statement 结束 ERROR 4 N Y Const var procedure后应为标识符 分程序递归调用 写符号表 语句 PROCEDURE Y N 第二章编译程序的实现 58 建符号表ENTER 程序框图 K PROCEDURE TX TX 1 K CONSTANT TABLE TX NAME IDTABLE TX KIND K TABLE TX LEVEL LEV K VARIABLE TABLE TX LEVEL LEVTABLE TX ADR DXDX DX 1 Y N TABLE TX VAL NUM 结束 Y N Y 第二章编译程序的实现 59 功能 P293 检查出现在语句Statement 中的标识符在符号表Table 中是否定义以及属性 KIND 赋值语句 读语句 调用语句 查表程序POSITION 第二章编译程序的实现 60 实验要求 实验名称 语法分析程序实验目的 实现功能 实验的输入和输出 实验报告内容 第二章编译程序的实现 61 设计 编制 调试一个典型的语法分析程序 实现对词法分析程序所提供的单词序列进行语法检查和结构分析 进一步掌握自顶向下递归子程序的语法分析方法 实验目的 第二章编译程序的实现 62 1 通过对PL0语法规则的分析 并在词法分析程序的基础上 编制语法分析程序 2 对于有语法和词法错误的源程序 给出出错报告 3 建立符号表 实现功能 第二章编译程序的实现 63 目的要求 算法描述 程序结构 主要变量名说明 程序清单 调试情况 设计技巧 心得体会 实验报告内容 第二章编译程序的实现 64 输入 PL0源程序输出 1 源程序的词法分析结果 2 源程序的语句类型 3 符号表TABLE 实验的输入和输出 第二章编译程序的实现 65 PROGRAMmysource CONSTa 10 VARb c PROCEDUREp VARd PROCEDUREq CONSTe 5 VARf PROCEDUREr VARg BEGINg a e f g WRITE g END PL 0程序如下 BEGINCALLr WRITE f f a e f WRITE f d END BEGINd a b WRITE d CALLqEND PROCEDUREs BEGINCALLp b 10 WRITE b END BEGINb 8 READ c WHILEc 0DOBEGINWRITE b CALLs b b c WRITE b READ c END CALLpEND r过程体 q过程体 p过程体 主程序体 s过程体 第二章编译程序的实现 66 符号表TABLE 第二章编译程序的实现 67 三 PL 0编译程序的伪代码生成 伪代码的形式伪代码指令伪代码生成 第二章编译程序的实现 68 伪代码的形式 其中 F 伪操作码 L 调用层和说明层的层差 A 位移量 相对地址 第二章编译程序的实现 69 层差 动态层次 静态层次动态层次 调用层次 在Block 中的参数LEV 静态层次 定义层次 Table 表中的LEVEL项 伪代码中层差的获得 第二章编译程序的实现 70 INT 为被调用的过程 包括主程序 在运行栈S中开辟数据区 L 0A 所需数据单元 包括SL DL RA 个数 8条伪代码的指令 第二章编译程序的实现 71 CAL 调用过程 L 层差 A 被调用过程的过程体 过程体之前一条指令 在目标程序区的入口地址 8条伪代码的指令 第二章编译程序的实现 72 LIT 将常量送到S栈的栈顶 L 0 A 常量值 8条伪代码的指令 第二章编译程序的实现 73 LOD 将变量送到S栈的栈顶 L 层差 A 变量所在说明层的相对地址 8条伪代码的指令 第二章编译程序的实现 74 STO 将运行栈S的栈顶内容送入某变量单元中 L 层差 A 变量所在说明层的相对地址 8条伪代码的指令 第二章编译程序的实现 75 JMP 无条件转移 L 0 A 转向地址 8条伪代码的指令 第二章编译程序的实现 76 JPC 条件转移 当运行栈S的栈顶的布尔值为0时 则转向A所指目标程序地址 否则顺序执行 L 0 A 转向地址 8条伪代码的指令 第二章编译程序的实现 77 OPR 关系或算数运算 L 0 A 具体运算 0 6 8 13 运算对象取自S栈栈顶和次栈顶 8条伪代码的指令 第二章编译程序的实现 78 OPR 0 0调用返回 OPR 0 1取 负 运算 OPR 0 2加法运算 OPR 0 3减法运算 OPR 0 4乘法运算 OPR 0 5除法运算 OPR 0 6取奇运算 8条伪代码的指令 第二章编译程序的实现 79 OPR 0 8关系运算 OPR 0 9关系运算 OPR 0 10关系运算 OPR 0 12关系运算 OPR 0 13关系运算 8条伪代码的指令 第二章编译程序的实现 80 PROCEDUREStatement 中 赋值语句 STO 层差 ADR读语句 OPR 0 16STO 层差 ADR写语句 OPR 0 14OPR 0 15过程调用语句 CAL 层差 ADR 入口地址 伪代码的生成 第二章编译程序的实现 81 当型语句 JPC 0 0 A 0 需要返填 JMP 0 CX1条件语句 JPC 0 0 A 0 需要返填常量 LIT 0 VAL变量 LOD 层差 ADR 伪代码的生成 第二章编译程序的实现 82 1 当进入一个分程序 则产生一个无条件转向语句 JMP0A A值需要返填 2 为每一个过程产生目标程序块 入口地址为A 伪代码的生成顺序 第二章编译程序的实现 83 PROGRAMmain VAR PROCEDUREP1 VAR PROCEDUREP2 VAR PROCEDUREP3 VAR BEGIN END P3 BEGIN END P2 BEGIN END P1 BEGIN END main 伪代码的生成顺序 示意性程序结构如下 1 为主程序产生第一个无条件转移语句 JMP0L 2 为过程P1产生第二个无条件转移语句 JMP0L1 3 为过程P2产生第三个无条件转移语句 JMP0L2 4 为过程P3产生第四个无条件转移语句 JMP0L3 伪代码生成顺序如下 第二章编译程序的实现 84 5 为过程体P3产生目标代码程序块 其入口地址为L3 L3 INT0A3 过程P3所需单元个数 OPR00 返回到调用P3语句的下一条语句 伪代码的生成顺序 第二章编译程序的实现 85 6 为过程P2产生目标代码程序块 其入口地址为L2 L2 INT0A2 过程P2所需单元个数 OPR00 返回到调用P2语句的下一条语句 伪代码的生成顺序 第二章编译程序的实现 86 7 为过程P1产生目标代码程序块 其入口地址为L1 L1 INT0A1 过程P1所需单元个数 OPR00 返回到调用P1语句的下一条语句 伪代码的生成顺序 第二章编译程序的实现 87 8 为主程序main产生目标代码程序块 其入口地址为L L INT0A1 主程序main所需单元个数 OPR00 伪代码的生成顺序 第二章编译程序的实现 88 JMP0LJMP0L1JMP0L2JMP0L3L3 过程P3目标程序代码L2 过程P2目标程序代码L1 过程P1目标程序代码L 主程序main目标程序代码 伪代码的生成顺序 第二章编译程序的实现 89 PROGRAMmysource CONSTa 10 VARb c PROCEDUREp VARd PROCEDUREq CONSTe 5 VARf PROCEDUREr VARg BEGINg a e f g WRITE g END PL 0程序如下 CXFLA0JMP052 主程序的入口地址 JMP032 P3的入口地址 JMP015 P2的入口地址 JMP04 P1的入口地址 INT04r过程 4 14 LIT010取a值LI