《第2章__PL0编译程序的实现.ppt》由会员分享，可在线阅读，更多相关《第2章__PL0编译程序的实现.ppt（150页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、温故知新编译原理的内容及学习意义编译原理的内容及学习意义翻译器、编译器的定义翻译器、编译器的定义编译器的阶段划分及前端、后端的概编译器的阶段划分及前端、后端的概念念“遍遍”的概念的概念遍遍编译的几个阶段常用编译的几个阶段常用编译的几个阶段常用编译的几个阶段常用一遍一遍一遍一遍（passpass）扫描实现，一扫描实现，一扫描实现，一扫描实现，一遍扫描包括读一个输入文遍扫描包括读一个输入文遍扫描包括读一个输入文遍扫描包括读一个输入文件和写一个输出文件。件和写一个输出文件。件和写一个输出文件。件和写一个输出文件。词法分析器词法分析器词法分析器词法分析器语法分析器语法分析器语法分析器语法分析器语义分析
2、器语义分析器语义分析器语义分析器源程序源程序源程序源程序中间代码中间代码中间代码中间代码生成器生成器生成器生成器代码优化器代码优化器代码优化器代码优化器代码生成器代码生成器代码生成器代码生成器目标程序目标程序目标程序目标程序出错管理器出错管理器出错管理器出错管理器符号表符号表符号表符号表管理器管理器管理器管理器 编译器从逻辑上可以分成若干阶编译器从逻辑上可以分成若干阶段，每个阶段把源程序从一种表段，每个阶段把源程序从一种表示变换成另一种表示示变换成另一种表示遍单遍扫描与多遍扫描单遍扫描与多遍扫描：每一遍的扫视可完成上述一个阶段或多个阶段的工作。每一遍的输入都是上一遍的输出，第一遍的输入是源程序
3、正文，最后一遍的输出是目标代码。单遍与多遍的比较单遍与多遍的比较：遍数多：编译器结构清晰，但时间效率不高遍数少：编译速度快，但对机器的内存要求高遍数的确定：遍数的确定：主要因素是源程序和机器（目标机）的特征。前端和后端：把编译过程分成前端和后端两部分前端：只依赖于源程序，独立于目标机器（生成中间代码）后端：依赖于目标机器，与源程序无关，只与中间语言有关（从中间代码生成目标代码）好处：提高开发编译器的效率取一个编译器的前端，重写它的后端以产生同一源语言在另一机器上的编译器不同的前端使用同一个后端，从而得到一个机器上的几个编译器（采用同一中间语言）源程序源程序源程序源程序目目目目标标标标机机机机器
4、器器器1 1目目目目标标标标机机机机器器器器2 2目目目目标标标标机机机机器器器器3 3目目目目标标标标机机机机器器器器n n编译器编译器编译器编译器不区分前端和后端的编译器不区分前端和后端的编译器不区分前端和后端的编译器不区分前端和后端的编译器源程序源程序源程序源程序目目目目标标标标机机机机器器器器1 1目目目目标标标标机机机机器器器器2 2目目目目标标标标机机机机器器器器3 3目目目目标标标标机机机机器器器器n n编译器前端编译器前端编译器前端编译器前端编译器后端编译器后端编译器后端编译器后端区分前端和后端的编译器区分前端和后端的编译器区分前端和后端的编译器区分前端和后端的编译器下列程序中
5、哪些不是编译程序的组成部分？A 词法分析 B代码读入C 语法分析 D代码生成 对下列错误信息，请指出可能是编译的哪个阶段报告的。else没有匹配的if数组下标越界声明和使用的函数没有定义零做除数在数中出现非数字字符语法分析语法分析语义分析或代码生成语义分析或代码生成语义分析语义分析代码优化或语义分析代码优化或语义分析词法分析词法分析B代码读入代码读入判断高级语编写的源程序都必顺通过编译,产生目标代码后才能运行.多遍扫描的编译程序的多遍是指多次重复读源程序.就执行速度而言,编译后再执行程序比解释执行程序慢.()()()出错处理程序语法分析程序语义分析程序目标代码生成程序词法分析程序中间代码生成程
6、序代码优化程序表格管理程序注意 上述编译过程的阶段划分只是一种典型的分法，上述编译过程的阶段划分只是一种典型的分法，事实上并不是所有的编译程序都分成这样几个事实上并不是所有的编译程序都分成这样几个阶段的。阶段的。有些编译程序对优化没有什么要求，优化阶段有些编译程序对优化没有什么要求，优化阶段就可省去。在某些情况下，为了加快编译速度，就可省去。在某些情况下，为了加快编译速度，中间代码产生阶段也可以去掉。有些最简单的中间代码产生阶段也可以去掉。有些最简单的编译程序是在语法分析的同时产生目标代码。编译程序是在语法分析的同时产生目标代码。但是，多数实用编译程序的工作过程大致都像但是，多数实用编译程序的
7、工作过程大致都像上面所说的那六个阶段。上面所说的那六个阶段。其它编译程序的另外两个重要的工作是表格管理和出错处理。编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作；如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。一个好的编译程序应该：全全 最大限度发现错误准准 准确指出错误的性质和发生地点局部化局部化 将错误的影响限制在尽可能小的范围内若能自动校正错误自
8、动校正错误则更好，但其代价非常高代价非常高源程序中的错误通常分为：语法错误语法错误 不符合语法（或词法）规则的错误语义错误语义错误 不符合语义规则的错误单词拼写错误、括号不匹配.说明错误、作用域错误、类型不匹配.现代编译技术必须面对应用需求和目标体系结构的多样化 高性能计算（High Performance Computing）指令级并行（Instruction Level Parallelism）线程级并行（Thread Level Parallelism）处理机级并行（Processor Level Parallelism）系统级并行（Thread Level Parallelism）嵌入
9、式计算（Embedded Computing）需求多样性（实时、资源限制、功耗、多目标）其它多媒体计算（Multimedia Computing）网络计算（Network Computing）编译技术重要方向并行编译技术 面向高性能计算交叉编译技术 面向嵌入式计算第第2 2章章 PL/0 PL/0编译程序的实现编译程序的实现本章目的：以本章目的：以PL/0PL/0编译程序编译程序为实例为实例,学习编译程序实现的基本学习编译程序实现的基本步骤和相关技术步骤和相关技术1 PL/0编译程序的结构编译程序的结构2 PL/0编译程序的分析工作编译程序的分析工作(词法，语法和语义）实现词法，语法和语义）实
10、现3 PL/0编译程序的编译程序的错误处理方法错误处理方法4 目标代码生成和目标代码生成和类类pcodepcode代码解释器代码解释器PL/0语言描述它由世界著名计算机科学家N.Wirth编写PL/0语言：PASCAL语言的子集，功能简单，结构清晰，可读性强，具备了一般高级语言的必备部分它充分体现一个高级语言编译程序实现的基本方法和技术本书提供了两种形式的PL/0语言的语法描述：语法图：用语法图描述语法规则的优点是直观、易读EBNFPL/0的非形式化描述数据类型只有整型标识符的有效长度是10，以字母开始的字母数字串数最多为14位作用域规则（内层可引用包围它的外层定义的标识符)过程无参，可嵌套定
11、义（最多三层），可递归调用语句类型：赋值语句，if.then.,while.do.,read,write,call,复合语句（begin.end），说明语句（const.,var.,procedure）13个保留字：if,then,while,do,read,write,call,begin,end,const,var,procedure,odd 1.PL/0编译程序的结构编译程序的结构 PL/0编译编译程序程序 PL/0 语言程序语言程序 类类 pcode 代码代码源语言源语言(PL/0)目标语言目标语言(类类 pcode)实现语言（实现语言（pascal/C)PL/0 类类 pcode p
12、ascal/C PL/0PL/0编译程序编译程序类类 p pcodecode解释解释程序程序类类 pcode代码代码PL/0源程序源程序输入数据输入数据输出数据输出数据PL/0PL/0编译系统的结构框架编译系统的结构框架PL/0PL/0语言语言 PL/0 PL/0语言：语言：PASCALPASCAL语言的语言的子集子集 PL/0 PL/0程序示例程序示例 PL/0 PL/0的的语法描述图语法描述图 PL/0 PL/0语言语言的的EBNFEBNF表示表示 PL/0 PL/0程序示例程序示例 CONST A=10;CONST A=10;（*常量说明部分常量说明部分*）VAR B,C;VAR B,C
13、;（*变量变量说明部分说明部分*）PROCEDURE PROCEDURE P;P;（*过程过程说明部分说明部分*）VAR D;VAR D;（*P*P的局部变量的局部变量说明部分说明部分*）PROCEDURE PROCEDURE Q;Q;（*P*P的局部过程的局部过程说明部分说明部分*）VAR X;VAR X;BEGINBEGIN READ(X);READ(X);D:=X;D:=X;WHILE X#0 WHILE X#0 DO CALL P;DO CALL P;END;END;BEGINBEGIN WRITE(D);WRITE(D);CALL Q;CALL Q;END;END;BEGINBEGI
14、N CALL P;CALL P;END.END.Q过程体过程体p过程体过程体主主程序程序体体 输入圆柱的半径和高，计算一些面积、体积等输入圆柱的半径和高，计算一些面积、体积等 var r,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.计算最大公约数计算最大公约数 lvar m,n,r,q;l 计算计算m和和n的最大公约数的最大公约数 lprocedure gcd;l
15、beginl while r#0 do l beginl q:=m/n;l r:=m-q*n;l m:=n;l n:=r;l endlend;lbeginl read(m);l read(n);l 为了方便，规定为了方便，规定m=n l if m 0 thenl beginl fact:=fact*m;l m:=m-1;l call factorial;l end;lend;lbeginl 读入n l read(n);l sum:=0;l while n 0 dol beginl m:=n;l fact:=1;l call factorial;l sum :=sum+fact;l n:=n-1
16、;l end;l 输出n!l write(sum);lend.2.1.1 PL/0 语言的语法描述图语法描述图中的符号说明：语法描述图中的符号说明：A或或A：表示终结符（表示终结符（构成语言文法的单词，语法构成语言文法的单词，语法成分的最小单位）成分的最小单位）中文中文 ：表示非终结符表示非终结符（用终结符和非终结符串（用终结符和非终结符串 或终结符串定义）或终结符串定义）通常称第一个非终结符为文法的开始符号。如通常称第一个非终结符为文法的开始符号。如“程序程序”图图2.1(a)程序语法描述图程序语法描述图 图图2.1(b)分程序语法描述图分程序语法描述图 图图2.1(c)语句语法描述图语句语
17、法描述图 图图2.1(d)条件语法描述图条件语法描述图 图图2.1(e)表达式语法描述图表达式语法描述图 图图2.1(f)项语法描述图项语法描述图 图图2.1(g)因子语法描述图因子语法描述图 BNF（BACKUS-NAUR FORM）是根据美国的John W.Backus与丹麦的Peter Naur来命名的，它从语法上描述程序设计语言的元语言。采用BNF就可说明哪些符号序列是对于某给定语言在语法上有效的程序构成构成EBNFEBNF的元素的元素（非终结符，终结符，开始符，规则）（非终结符，终结符，开始符，规则）EBNF EBNF 的元符号：的元符号：用左右尖括号括起来的内容为用左右尖括号括起来
18、的内容为非终结符非终结符=读做读做定义为定义为=的的左部由左部由右部右部定义定义 读做读做定义为定义为 的的左部由左部由右部右部定义定义|读做读做或或 表示右部候选内容表示右部候选内容 表示花括号内的内容表示花括号内的内容可重复可重复任意次或限任意次或限 定次数定次数 表示方括号内的内容为表示方括号内的内容为任选项任选项()()表示圆括号内的内容表示圆括号内的内容优先优先2.1.2 PL/0语言文法的EBNF表示PL/0语言文法的语言文法的EBNF表示：表示：v程序程序=分程序分程序.v分程序分程序=常量说明部分常量说明部分变量说明部分变量说明部分 过程说明部分过程说明部分语句语句v常量说明部
19、分常量说明部分=CONST常量定义部分常量定义部分，常，常 量定义量定义；v常量定义常量定义:=标识符无符号整数标识符无符号整数;v无符号整数无符号整数=数字数字数字数字v变量说明部分变量说明部分=VAR标识符标识符，标识符，标识符；标识符标识符=字母字母字母字母|数字数字v过程说明部分过程说明部分:=过程首部分程序；过程首部分程序；过程说明部分过程说明部分v过程首部过程首部:=PROCEDURE标识符；标识符；v语句语句:=:=赋值语句条件语句当型赋值语句条件语句当型 循环语句过程调用语句读语句写语循环语句过程调用语句读语句写语 句复合语句空句复合语句空v赋值语句赋值语句 :=标识符标识符:
20、=:=表达式表达式v复合语句复合语句 :=BEGINBEGIN语句；语句语句；语句ENDENDv条件条件 :=表达式关系运算符表达式表达式关系运算符表达式 ODDODD表达式表达式v表达式表达式 :=项加法运算符项加法运算符 项项v项项 :=因子乘法运算符因子因子乘法运算符因子v因子因子 :=标识符无符号整数标识符无符号整数（表达式表达式）v加法运算符加法运算符 :=v乘法运算符乘法运算符 :=*/v关系运算符关系运算符 :=v条件语句条件语句 :=IFIF条件条件THENTHEN语句语句v过程调用语句过程调用语句 :=CALLCALL标识符标识符v当型循环语句当型循环语句 :=WHILEWH
21、ILE条件条件DODO语句语句v读语句读语句 :=READREAD（标识符，标识符标识符，标识符 ）v写语句写语句 :=WRITEWRITE（表达式，表达式表达式，表达式 ）v字母字母 :=a|b|a|b|X|Y|Z|X|Y|Zv数字数字 :=0|1|0|1|8|9|8|9例：用例：用EBNFEBNF描述描述 的定义的定义 ：=+|-=+|-=0|1|2|3|4|5|6|7|8|9=0|1|2|3|4|5|6|7|8|9 或或 =+|-=+|-|0|0=1|2|3|4|5|6|7|8|9=1|2|3|4|5|6|7|8|9 =0|=0|2.2 PL/0编译程序的结构PL/0的目标程序为假想栈式
22、计算机的汇编语言，与计算机无关PL/0的编译程序和目标程序的解释执行程序可用各种语言编写。2.2 PL/0编译程序的结构1、PL/0编译程序的特点（1）编译程序采用一遍扫描方式，以语法分析程序为核心，词法分析程序和代码生成程序为一个独立过程，被语法分析程序所调用。（2）用表格管理程序建立变量，常量和过程标识符的说明与引用之间的信息联系。（3）用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错误性质。（4）当源程序编译正确时，PL/0编译程序自动调用解释执行程序，对目标代码进行解释执行。2.PL/0编译程序的结构词法分析程词法分析程序序语法语义分析程序语法语义分析程序代码生成程
23、序代码生成程序表格管理程序表格管理程序出错处理程序出错处理程序PL/0PL/0源程序源程序目标程序目标程序PL/0PL/0编译程序编译程序解释执行解释执行程序程序目标代码目标代码PL/0源程序源程序输入输入输出输出PL/0PL/0编译系统的结构框架编译系统的结构框架下面对Pascal语言书写的PL/0编译程序构造技术进行分析说明PL/0编译程序（包括主程序）是由18个嵌套及并列的过程 或函数组成:vPL/OPL/O编译程序的过程与函数定义层次结构图编译程序的过程与函数定义层次结构图vPL/O编译程序总体流程图编译程序总体流程图 目标代码目标代码类类p-codep-code目标代码目标代码类类p
24、-codep-code是是一种一种栈式机栈式机的的汇编语言汇编语言。栈式机系统结构栈式机系统结构:没有累加器和寄存器，只有存储栈指针没有累加器和寄存器，只有存储栈指针 所有运算都在栈顶（零地址机）所有运算都在栈顶（零地址机）指令格式：指令格式：f l af l af f功能码功能码l l层次差层次差 （标识符标识符引用引用层层减去减去定义定义层层）a a根据不同的指令有所区别根据不同的指令有所区别 PL/0PL/0编译程序的结构编译程序的结构词法分析程词法分析程序序语法语义分析程序语法语义分析程序代码生成程序代码生成程序表格管理程序表格管理程序出错处理程序出错处理程序PL/0PL/0源程序源程
25、序目标程序目标程序PL/0PL/0编译程序的总体设计编译程序的总体设计以语法以语法、语义分析语义分析程序程序为核心为核心 词法分析词法分析程序和程序和代码生成代码生成程序都作为一个程序都作为一个过程过程，当语法分析需要读单词时就调用词法分析程序，当语法分析需要读单词时就调用词法分析程序，而当语法而当语法、语义分析正确，需要生成相应的目标语义分析正确，需要生成相应的目标代码时，则调用代码生成程序。代码时，则调用代码生成程序。表格管理表格管理程序实现程序实现变量变量，常量常量和和过程过程标识符的标识符的信信息的登录与查找息的登录与查找。出错处理出错处理程序，对词法和语法程序，对词法和语法、语义分析
26、遇到的语义分析遇到的错误给出在源程序中错误给出在源程序中出错的位置出错的位置和与和与错误错误 性质有性质有关关的编号，并进行错误恢复。的编号，并进行错误恢复。2 PL/0编译程序的分析工作编译程序的分析工作(词法，语法词法，语法和语义）和语义）2.1PL/0编译程序词法分析的实现识别的单词：识别的单词：保留字或关键字：如：保留字或关键字：如：BEGINBEGIN、END END、IF IF、THEN THEN等等运算符运算符：如：如：+、-、*、/、：、：=、#、=、=等等标识符标识符：用户定义的变量名、常数名、过程名用户定义的变量名、常数名、过程名常数常数：如：如：1010、2525、100
27、100等整数等整数界符界符：如：如：,、.、;、(、)等等词法分析过程词法分析过程GETSYMGETSYM所要完成的任务：所要完成的任务：从源程序读字符（从源程序读字符（getch)getch)滤空格滤空格识别识别保留字保留字识别标识符识别标识符拼数拼数识别单字符单词识别单字符单词拼双字符单词拼双字符单词词法分析过程词法分析过程:GETSYMGETSYM框图（见教材图框图（见教材图2.52.5）程序（程序（procedure getsymprocedure getsym）当识别到标识符时先查当识别到标识符时先查保留字保留字表表保留保留字字表：（表：（begin (*main*)begin (*
28、main*)）word1:=word1:=begin begin ；word2:=word2:=callcall ；.word13:=word13:=writewrite ；查到时找到相应的查到时找到相应的内部表示内部表示Wsym1:=beginsym;wsym2:=callsym；wsym13:=writesym；字符对应的字符对应的单词表：单词表：ssym+:=ssym+:=plusplus;ssym-:=;ssym-:=minusminus;ssym;:=ssym;:=semicolonsemicolon;词法分析如何把单词传递给语法分析词法分析如何把单词传递给语法分析 type sym
29、bol=(type symbol=(nulnul,identident,numbernumber,plusplus,varsymvarsym,procsymprocsym)；3 3个个全程量全程量 SYMSYM:symbol;:symbol;IDID:alfa;:alfa;NUMNUM:integer;:integer;通过三个通过三个全程量全程量 SYMSYM 、IDID和和NUMNUM 将识别出的单词信息将识别出的单词信息传递传递给给语法语法分析分析程序。程序。SYMSYM：存放单词的类别：存放单词的类别 如：有程序段落为：如：有程序段落为：begin initial:=60begin i
30、nitial:=60；endend 对应单词对应单词翻译后变为：翻译后变为：begin begin beginsymbeginsym,initial ,initial identident,:=:=becomesbecomes,60 ,60 numbernumber,；semicolonsemicolon，end end endsymendsym 。IDID：存放用户所定义的标识符的值存放用户所定义的标识符的值 如：如：initial initial（在（在SYMSYM中放中放identident，在，在IDID中中放放initialinitial）NUMNUM：存放用户定义的数：存放用户定义
31、的数 如：如：60 60（在在SYMSYM中放中放number,number,在在NUMNUM中中放放6060）使用状态转换图实现词法分析程序的设计方法使用状态转换图实现词法分析程序的设计方法词法分析程序的设计词法分析程序的设计-使用状态转换图实现使用状态转换图实现表示表示状态状态，对应每个状态编一段程序，对应每个状态编一段程序，每个状态每个状态调用调用取字符取字符程序，根据当前字程序，根据当前字符符转到不同的状态，并做相应操作。转到不同的状态，并做相应操作。表示表示终态终态，已，已识别出一个识别出一个单词单词。2.2 2.2 PL/0PL/0编译程序语法分析编译程序语法分析 自顶向下自顶向下
32、的语法分析的语法分析 递归子程序法递归子程序法（上下文无关文法）上下文无关文法）句型的分析句型的分析句型分析句型分析就是就是识别识别一个符号串是否为某文法的一个符号串是否为某文法的句型的句型的过程，过程，或者说是某个或者说是某个推导推导的构造过程。的构造过程。对于一个给定的文法，要想判定一个符号串是否为该文法的对于一个给定的文法，要想判定一个符号串是否为该文法的句子，需要考察是否可以从该文法的开始符号派生出（推句子，需要考察是否可以从该文法的开始符号派生出（推导出）此符号串。编译程序的语法分析工作。导出）此符号串。编译程序的语法分析工作。分析算法分类分析算法分类分析算法可分为：分析算法可分为：
33、自上而下分析法自上而下分析法：从文法的开始符号出发从文法的开始符号出发，寻找寻找与与输入符号串输入符号串匹配匹配的的推导，推导，或者说，为输入串寻找一个最左推导。或者说，为输入串寻找一个最左推导。自下而上分析法自下而上分析法：从从输入符号串输入符号串开始开始，逐步进行逐步进行归约归约，直至，直至归约归约到到文法的文法的开开始符号始符号。语法分析（从概念上讲）建立一棵与输语法分析（从概念上讲）建立一棵与输入串相匹配的语法树。入串相匹配的语法树。语法树推导的几何表示语法树推导的几何表示句型句型aabbaa的可能的可能推导推导序列和语法树序列和语法树 例例:GS:SaASASbAASSSaAba S
34、 a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa两种方法反映了语法树的两种构造过程。两种方法反映了语法树的两种构造过程。自上而下方法自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上方法自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树自上而下的语法分析的一般过程自上而下的语法分析的一般过程例：文法例：文法G：S cAd A ab A a识别输入串识别输入串w=cabd是
35、否为该文法的是否为该文法的句子句子SSScAdcAd a b推导过程：推导过程：S cAd cAd cabd 程序程序分程序分程序.constidentnumber=,;varident,;procedureident;分程序分程序语句语句分程序分程序identreadend;语句语句表达式表达式：=begin语句语句语句语句)(ident,自顶向下的语法分析自顶向下的语法分析VAR A;VAR A;BEGINBEGIN READ(A)READ(A)END.END.VARVAR ；A A BEGINBEGIN ENDEND READREAD （）A A 为文法的为文法的开始符号开始符号，以开，
36、以开始符号作为根结始符号作为根结点构造一棵倒挂点构造一棵倒挂着的语法树。着的语法树。递归子程序法递归子程序法-语法分析程序由一组递归过语法分析程序由一组递归过程组成程组成对应对应每个非终结符（每个非终结符（语法单元），编一个独立的处理过程（或函语法单元），编一个独立的处理过程（或函数，子程序）。数，子程序）。由由 （即开始符）开始，沿语法描述图即开始符）开始，沿语法描述图箭头箭头所指出的方所指出的方向进行分析（规则右部）向进行分析（规则右部）遇到遇到非终结符非终结符（进入了又一个语法单元），则（进入了又一个语法单元），则调用调用相应的相应的处处理过程理过程 遇到遇到终结符终结符，则判断当前读入
37、的单词是否与该终结符，则判断当前读入的单词是否与该终结符相匹配相匹配，若匹配，再读取下一个单词继续分析。若匹配，再读取下一个单词继续分析。也称为也称为递归下降分析器（递归下降分析器（recursive-descent parser）例：表达式的语法分析程序（递归子程序）例：表达式的语法分析程序（递归子程序）项项表达式表达式+-项项+-项项 因子因子 因子因子 */语法图语法图因子的语法图因子的语法图因子因子identnumber(表达式表达式)表达式的表达式的EBNF表达式表达式=+|-+|-项项（+|-+|-）项）项 项项=因子因子（*|/*|/）因子）因子 因子因子=标识符标识符|无符号整
38、数无符号整数|（表达式表达式）表达式表达式=+|-+|-项项（+|-+|-）项）项 pascalpascal表达式表达式的分析程序（的分析程序（递归子程序）递归子程序）procedure procedure exprexpr;beginbegin if sym in if sym in plusplus,minusminus then then begin begin getsym;getsym;termterm;end end else else termterm;while sym in while sym in plusplus,minusminus do do begin begin
39、getsym;getsym;termterm;end endend;end;项项=因子因子（*|/*|/）因子）因子 pascalpascal项项的分析程序（的分析程序（递归子程序）递归子程序）procedure procedure termterm;beginbegin factorfactor;while sym in while sym in timestimes,slashslash do do begin begin getsym;getsym;factorfactor;end endend;end;因子因子=标识符标识符|无符号整数无符号整数|（表达式表达式）因子因子的分析程序（的
40、分析程序（递归子程序）递归子程序）procedure procedure factorfactor;begin begin if sym if sym identident then then begin begin if sym if sym numbernumber then then begin begin if sym=if sym=(then then begin begin getsym;getsym;exprexpr;if sym=if sym=)then then getsym getsym else error else error end end else error el
41、se error end end else getsym else getsym end end else getsym else getsym end;end;表达式表达式=+|-+|-项项（+|-+|-）项）项 in Cin Cint expression(bool*fsys,int*ptx,int lev)if(sym=plus|sym=minus)/*开头的正负号，当前表达式被看开头的正负号，当前表达式被看作一个正的或负的项作一个正的或负的项*/getsymdo;termdo(nxtlev,ptx,lev);/*处理项处理项*/else/*此时表达式被看作项的加减此时表达式被看作项的加
42、减*/termdo(nxtlev,ptx,lev);/*处理项处理项*/while(sym=plus|sym=minus)getsymdo;termdo(nxtlev,ptx,lev);/*处理项处理项*/return 0;项项=因子因子（*|/*|/）因子）因子 int term(bool*fsys,int*ptx,int lev)factordo(nxtlev,ptx,lev);/*处理因子处理因子*/while(sym=times|sym=slash)getsymdo;factordo(nxtlev,ptx,lev);return 0;因子因子=标识符标识符|无符号整数无符号整数|（表达
43、式表达式）int factor(bool*fsys,int*ptx,int lev)if(sym=ident)/*因子为常量或变量因子为常量或变量*/getsymdo;else if(sym=number)/*因子为因子为*/getsymdo;else if(sym=lparen)/*因子为表达式因子为表达式*/expressiondo(nxtlev,ptx,lev);if(sym=rparen)getsymdo;else error(22);/*缺少右括号缺少右括号*/return 0;=beginbegin（*main*)*main*)(*initialize*)(*initialize*
44、)(*r/w file set*)(*r/w file set*)getsym;getsym;block();block();if sym period then error.if sym period then error.end.end.。程序程序 pl0分程序分程序 block语句语句 statement条件条件 condition表达式表达式expression项项 term因子因子 factor语语法法调调用用关关系系图图编编译译系系统统总总体体流流程程图图2.3 2.3 PL/0PL/0编译程序语义分析的设计与实现编译程序语义分析的设计与实现 PL/0PL/0编译程序语法编译程序语
45、法、语义分析的的核心语义分析的的核心程序是程序是BLOCKBLOCK过程过程哪些语义分析工作？哪些语义分析工作？如何实现？如何实现？-语义分析环境（符号表）语义分析环境（符号表）说明部分的分析说明部分的分析与处理与处理表格管理表格管理过程体过程体(语句）的分析语句）的分析与处理与处理因子因子=标识符标识符|无符号整数无符号整数|（表达式表达式）语义分析语义分析int factor(bool*fsys,int*ptx,int lev)if(sym=ident)/*因子为常量或变量因子为常量或变量*/i=position(id,*ptx);/*查找名字查找名字*/if(i=0)error(11);
46、/*标识符未声明标识符未声明*/elseswitch(tablei.kind)case constant:/*名字为常量名字为常量*/break;case variable:/*名字为变量名字为变量*/break;case procedur:/*名字为过程名字为过程*/error(21);/*不能为过程名不能为过程名*/登录符号表登录符号表说明部分的分析说明部分的分析与处理与处理对每个过程（含主程序）对每个过程（含主程序）说明的对象说明的对象（变量变量，常量常量和和过程过程）造造符号表符号表 登录登录标识符的标识符的属性属性。标识符的属性标识符的属性:种类，所在种类，所在层次层次,值值和分配的
47、和分配的相对位置相对位置。登录信息由登录信息由ENTERENTER过程完成。过程完成。符号表结构Enum object constant,variable,procedur ;Struct tablestruct char nameal;enum object kind;int val;int level;int adr;int size;Struct tablestruct tabletxmax;符号表结构说明种类的定义：object=(constant,variable,procedur)（定义定义纯量纯量/枚举枚举类型）类型）符号表的定义 table:array0.txmax of re
48、cord name:alfa;case kind:object of constant:(val:integer);variable:procedur:(level,adr,size:integer);例程序说明部分为：例程序说明部分为：CONST A=35CONST A=35，B=49B=49；VAR C VAR C，D D，E E；PROCEDURE P PROCEDURE P；VAR G VAR G；符号表符号表 名字名字 种类种类 层次层次/值值 地址地址 存储空间存储空间对应名字表对应名字表txtx ：tabletable表表的下标指针的下标指针,是以是以值参数值参数形式使用的。形式
49、使用的。dx:计算每个变量在运行栈中相对本计算每个变量在运行栈中相对本过程过程基地址基地址的的偏移量偏移量，放在放在table表表中的中的adr域，域，生成生成目标代目标代码码时再时再放在放在codecode中的中的a域域变量定义语句的处理变量定义语句的处理(C)语法：语法：:=varvar ，；程序：程序：if(sym=varsym)if(sym=varsym)/*/*收到变量声明符号，开始处理变量声明收到变量声明符号，开始处理变量声明*/*/getsymdo;getsymdo;do do vardeclarationdo(&tx,lev,&dx);vardeclarationdo(&tx,
50、lev,&dx);while(sym=comma)while(sym=comma)getsymdo;getsymdo;vardeclarationdo(&tx,lev,&dx);vardeclarationdo(&tx,lev,&dx);if(sym=semicolon)if(sym=semicolon)getsymdo;getsymdo;else error(5);else error(5);while(sym=ident);while(sym=ident);注意：注意：&tx&tx变量说明处理变量说明处理(C)int vardeclaration(int*ptx,int lev,int*p