教学课件编译原理－金锄头文库

资源描述

《教学课件编译原理》由会员分享，可在线阅读，更多相关《教学课件编译原理（439页珍藏版）》请在金锄头文库上搜索。

1、编译原理第一章编译概述编译器和解释器编译器和解释器编译器的功能分解和组织结构编译器的功能分解和组织结构编译器的伙伴程序编译器的伙伴程序编译器的实现途径编译器的实现途径编译技术的作用编译技术的作用1. 编译器和解释器编译器和解释器程序设计语言的历史程序设计语言的历史机器语言机器语言：能够被计算机的硬件系统直接执行的指令程序。汇编语言：将硬件指令用一些助记符表示。如ADD表示加法操作， SUB表示减法操作等等高级语言：使用便于理解的自然语言。 1. 编译器和解释器编译器和解释器翻翻译译程程序序( (器器) )：接接受受某某种种语语言言的的源源语语言言程程序序后后，将它改造成另一种逻辑上等

2、价的目标语言程序。将它改造成另一种逻辑上等价的目标语言程序。l汇汇编编程程序序：源源语语言言为为汇汇编编语语言言，目目标标语语言言为为机机器器语语言的翻译程序。言的翻译程序。l编编译译程程序序（器器）：源源语语言言为为高高级级语语言言，目目标标语语言言是是低级语言（汇编或机器语言）的翻译程序。低级语言（汇编或机器语言）的翻译程序。高级语言程序（源程序）低级语言程序（目标程序）编译程序（器）1. 编译器和解释器编译器和解释器解解释释程程序序(器器)：是语言的另一种实现方式。接受所输入的用程序语言(源语言)编写的程序(源程序)，然后直接解释执行源程序。相当于源程序的抽象执行机。解释程序（器

3、）高级语言程序（源程序）数据计算结果1. 编译器和解释器编译器和解释器编译器和解释器的比较编译器和解释器的比较编译器编译器解释器解释器程序规模程序规模规模较大规模较大中小规模中小规模内部形式内部形式机器代码机器代码(低级低级)数据结构数据结构(高级高级)运行机构运行机构硬件硬件CPU软件系统软件系统运行速度运行速度相对较快相对较快相对较慢相对较慢2. 编译器的功能分解和组织结构编译器的功能分解和组织结构表处理错误处理目标代码生成中间代码优化中间代码生成语义分析语法分析词法分析目标程序源程序2. 编译器的功能分解和组织结构编译器的功能分解和组织结构编译器的前端：编译器的前端：一般

4、包括词法分析、语法分析、一般包括词法分析、语法分析、符号表构造、语义分析、中间代码生成、代码优符号表构造、语义分析、中间代码生成、代码优化和错误处理等。此部分工作的特点是不依赖于化和错误处理等。此部分工作的特点是不依赖于具体机器。具体机器。编译器的后端编译器的后端：主要是指中间代码到目标代码生：主要是指中间代码到目标代码生成的阶段。此部分紧密地依赖于中间代码和目标成的阶段。此部分紧密地依赖于中间代码和目标机机遍遍：对源程序或源程序的中间表示形式从头到尾：对源程序或源程序的中间表示形式从头到尾扫描一次，生成新的中间结果或目标程序扫描一次，生成新的中间结果或目标程序3. 编译器的伙伴程序编译器

5、的伙伴程序编辑器编辑器 (editor) 除一般的文本编辑功能外，除一般的文本编辑功能外，还可以对正在编辑的文本进行分析、提示、自还可以对正在编辑的文本进行分析、提示、自动提供关键字匹配等功能。动提供关键字匹配等功能。预处理器预处理器(preprocessor) 删除源程序中的注释、删除源程序中的注释、执行宏替换以及包含文件的嵌入等。执行宏替换以及包含文件的嵌入等。连接程序连接程序(linker) 将不同的目标文件连接到一将不同的目标文件连接到一个可执行的文件中。个可执行的文件中。装入程序装入程序(loader) 将程序加载到内存中，以便将程序加载到内存中，以便执行。执行。调试程序调试程序(d

6、ebugger) 在被编译的程序中判定执在被编译的程序中判定执行错误的程序行错误的程序需预处理的源程序预处理器源程序编译程序目标汇编程序汇编程序可重定位的目标代码连接/装配程序绝对目标代码高级语言程序到可执行代码的转换过程4. 编译器的实现途径预处理方法预处理方法用于语言的扩充。设已有L语言的编译器，其扩充语言L1的编译器可通过语言转换程序将L1程序转换为L程序，利用L的编译器，从而实现L1的编译器。移植法移植法同一语言的编译器在同一语言的编译器在不同机器间的移植。方法： a a 目标代码的转换目标代码的转换 b b 修改中间代码到目标代码的转换修改中间代码到目标代码的转换自展法自展法自我

7、扩展，自己编写自己的编译器。工具法工具法利用编译阶段各个部分的自动生成工具自动生成。理论法理论法利用形式化描述理论，实现自动化。5. 编译技术的作用理解语言，编写出高效的代码理解语言，编写出高效的代码灵活设计实现自定义语言灵活设计实现自定义语言提高软件设计技术提高软件设计技术应用于涉及元级操作的实现应用于涉及元级操作的实现其它领域其它领域第二章一个微小的编译器z小语言小语言ToyLToyL的定义的定义zToyLToyL语言词法分析器语言词法分析器zToyLToyL语言语法分析器语言语法分析器zToyLToyL语言解释器语言解释器zToyLToyL语言编译器语言编译器1. 小语言

9、( x1 ) ; z1 :=z1 + x1 z1 :=z1 + x1 endend1. 小语言ToyL的定义2. ToyL语言词法分析器语言词法分析器任务：从程序文本中分离出单词，并确任务：从程序文本中分离出单词，并确定其类别定其类别 ToyL语言单词的种类：语言单词的种类：整数：整数：numnum 变量：变量：idid 保留字：保留字：begin, end, read, write,begin, end, read, write, 运算符：运算符：+ +，* *，:=:= 格式符：空格，回车，换行，文件结束符格式符：空格，回车，换行，文件结束符EOFEOF 分隔符：分隔符：(,),;(,)

10、,; 2. ToyL语言词法分析器语言词法分析器单词的内部表示单词的内部表示Token: (class, seman) begin: (BEGIN, “begin”) end: (END, “end”) read: (READ,”read”) write: (WRITE, “write”) num: (NUM, digit(num) id: (ID, name(id) +: (PLUS, “+”) *: (MULT, “*”) :=: (ASSIG, “:=”) (: (OPEN, “(”) ): (CLOSE, “)”) ; : (SEMI, “;”) eof: (EOF, “0”)2.

11、ToyL语言词法分析器语言词法分析器词法分析过程：词法分析过程：读当前字符流，直至文件结束。如果是：读当前字符流，直至文件结束。如果是： (1)标识符时判断是保留字还是变量标识标识符时判断是保留字还是变量标识符，构造符，构造Token表示表示 (2)数字时判断是整型还是实型，构造数字时判断是整型还是实型，构造 Token表示表示 (3)构造其它合法的符号的构造其它合法的符号的Token表示表示 (4)遇到非法符号则报错。遇到非法符号则报错。2. ToyL语言词法分析器语言词法分析器假设有ToyL语言程序文本:begin x:= 10; read(y); x := x + y end则经过词

12、法分析后的Token表示如下。 01(BEGIN,begin)09(CLOSE,)02(IDEN,x)10(SEMI,;)03(ASS ,:=)11(IDEN,x)04(NUMB,10) 12(ASS,:=)05(SEMI,; )13(IDEN,x)06(READ,read)14(PLUS,+)07(OPEN,( )15(IDEN,y)08(IDEN,y )16(END,end)3. ToyL语言语法分析器语言语法分析器任务：检查源程序是否是合法的单词序列，若任务：检查源程序是否是合法的单词序列，若有错误，则指出错误的位置和性质。有错误，则指出错误的位置和性质。构造语法构造语法短语的表示形式（

13、语法树）短语的表示形式（语法树）输入：是词法分析后所得的输入：是词法分析后所得的TokenToken序列。序列。说明：语法分析只用到单词的说明：语法分析只用到单词的TokenToken表示，并表示，并不改变单词的不改变单词的TokenToken表示。表示。3. ToyL语言语法分析器语言语法分析器三个函数：三个函数：next_token(tk)、token(CLASS)、back_token()只读而不检查的只读而不检查的Token函数函数next_token(tk )读并检查的读并检查的Token 函数函数token(CLASS)将程序文件的指针倒退到已读单词的第一字符将程序文件的指针倒退到

14、已读单词的第一字符位置上的回溯函数位置上的回溯函数back_token()。为了能倒退。为了能倒退到已读单词的位置上，每当读新单词时，把当到已读单词的位置上，每当读新单词时，把当前单词的文件位置保存到前单词的文件位置保存到old_fp中。中。3. ToyL语言语法分析器语言语法分析器void prog_parser() token(BEGIN);while( tk.class!=END )next_token(tk);switch(tk.class) case READ : token(OPEN);token(IDEN); token(CLOSE); break;case WRITE: tok

15、en(OPEN); expr_parser(); token(CLOSE); break;case IDEN: token(ASS);expr_parser(); break;default :error() token(SEMI); token(END); return; 3. ToyL语言语法分析器语言语法分析器void expr_parser()1000next_token(tk);if (tk.class!=NUMB & tk.class!=IDEN) error();2000next_token(tk);if (tk.class=PLUS | tk.class=MULT ) goto

16、 1000; 3000back_token(); return; 4. ToyL语言解释器语言解释器虚拟存储器：为存放变量的值需要开辟一个空间，不妨称此空间为存储器空间，或简称存储器(Memory) 。它可用变量名和值的对偶表来表示。虚拟输入器：为描述read(x)语句解释执行过程，需要设置程序的输入数据所在的介质，我们称其为输入介质，或简称为虚拟输入器，并记为Inp。可用整型数组来模拟虚拟输出器：为描述Write(E)语句解释执行过程，需要设置程序的输出数据所在的介质，我们称其为输出介质，或简称为虚拟输出器，并记为Out 。也用整型数组来模拟4. ToyL语言解释器语言解释器表达式处理需

17、要的数据结构和符号约定表达式处理需要的数据结构和符号约定DS : DS : 数据栈数据栈OS : OS : 运算符栈运算符栈RE : RE : 剩余表达式剩余表达式Push(s,a) : Push(s,a) : 将将a a压入栈压入栈s sPop(s,i) : Pop(s,i) : 从栈从栈s s中弹出中弹出i i个元素个元素无括号表达式无括号表达式求值求值算法思想算法思想运算分量运算分量N/I N/I : push(DS,N/I) 运算符运算符 : L: if OStop= then push(OS, ) if OStop then push(OS, ) else goto L； RE=#

18、 : while OStop do DStop 表示表达式的最终值表示表达式的最终值 ProcessProcessd1= pop(DS,1) ; d2= pop(DS,1);op= pop(OS,1) ; v= d2 op d1; push(DS,v) ; 4. ToyL语言解释器语言解释器interpreter() ( 一遍扫描解释器一遍扫描解释器)rp = 0; op = 0;pp = 0; mp = -1; dsp= -1; osp = 0; OS0= HEAD; token(BEGIN); while( tk.class!=END ) next_token(tk ； switch(tk

19、.class) case READ :token(OPEN);token(IDEN); update (tk.seman, read_num()token(CLOSE); break;case WRITE: token(OPEN); write_num ( evaluate_expr();token(CLOSE); break;case IDEN: token(ASS); update (tk.seman,evaluate_expr();break;default:error() next_token(tk) 5. ToyL语言编译器语言编译器目标代码功能：目标代码功能：把表达式的值计算出来，

20、把表达式的值计算出来，并存到某临时变量，我们称此临时变量并存到某临时变量，我们称此临时变量为结果变量。为结果变量。目标代码例：目标代码例： CODE(10)CODE(10): (-,-,10,T: (-,-,10,T1 1) ) CODE(x): (-,-,x,T CODE(x): (-,-,x,T1 1) ) CODE(a+10*x):(*,10,x,T CODE(a+10*x):(*,10,x,T1 1) ) (+,a,T (+,a,T1 1,T,T2 2) )表达式代码生成中用到的数据结构和辅助函数表达式代码生成中用到的数据结构和辅助函数DSDS同前同前OSOS同前同前RERE同前同前C

21、ODECODE代码部分代码部分格局组成格局组成：（DS,OS,RE,CODE)DS,OS,RE,CODE)初始格局：初始格局：DS,OS,CODE= ,REDS,OS,CODE= ,RE为初始表达式为初始表达式终止格局：终止格局：DSDS只含一个元素（表达式的结果变量）。只含一个元素（表达式的结果变量）。 OS,REOS,RE为空，为空，CODECODE为被生成的代码部分为被生成的代码部分函数函数NewTemp:NewTemp:自定义函数，每调用一次，它将返回一自定义函数，每调用一次，它将返回一个新临时变量。个新临时变量。表达式代码生成算法思想算法思想与表达式求值的思想基本一致算法思想与表达

22、式求值的思想基本一致区别只在于区别只在于ProcessProcess部分部分我们只需把我们只需把ProcessProcess中中求值求值的部分改为的部分改为代码生代码生成成部分即可部分即可: : T:=NewTemp T:=NewTemp 生成代码生成代码: :（ , ,DStop-1, DStop,T),DStop-1, DStop,T), / / = = OStopOStop pop(DS,2) pop(DS,2) pop(OS,1) pop(OS,1) push(DS,T) push(DS,T) 第三章有穷自动机与词法分析器第三章有穷自动机与词法分析器词法分析基础词法分析基础有穷自

23、动机有穷自动机正则表达式正则表达式词法分析器的设计和构造词法分析器的设计和构造1. 词法分析的基础词法分析的基础词法分析器功能：词法分析器功能：读源程序的字符序列读源程序的字符序列, ,逐个拼出单词逐个拼出单词, ,并构并构造相应的内部表示造相应的内部表示TOKEN.TOKEN.同时检查源程序中的同时检查源程序中的词法错误词法错误. .引入引入TokenToken的原因：的原因：编译程序总是用某种程序语言书写的程序，编译程序总是用某种程序语言书写的程序，语言的操作对象只能是该语言规定的各种数据。语言的操作对象只能是该语言规定的各种数据。而编译程序的操作对象是程序中的各种语法单而编译程序

24、的操作对象是程序中的各种语法单位，因此，必须把它们表示成某种数据结构形位，因此，必须把它们表示成某种数据结构形式。式。词法分析器的两种形式词法分析器的两种形式CharList 独立词法分析器语法分析TokenList 附属词法分析器语法分析callTokenCharList Token Token定义定义TokenToken表示最小的语义单位表示最小的语义单位- -单词的信息。即单词的信息。即单词内部表示的数据结构形式。单词内部表示的数据结构形式。单词不是程序设计语言中的语法概念，是编译程单词不是程序设计语言中的语法概念，是编译程序中引进的一个概念。是最小的语义单位，不能分序中引进的

25、一个概念。是最小的语义单位，不能分割割TokenToken中需要记录有关单词的信息：中需要记录有关单词的信息：单词的标志码单词的标志码($($id,$intC,id,$intC,) )标识单词的种类标识单词的种类-词法信息词法信息单词的特征属性（标识符名，符号表地址等）单词的特征属性（标识符名，符号表地址等） - -语义信息语义信息标识符和常量的处理标识符和常量的处理：词法信息可确定，语义信息形式的确定词法信息可确定，语义信息形式的确定： a a 语义信息的长度有限制时，直接用语义信息的长度有限制时，直接用标识符或常量本身标识符或常量本身 b b 没有长度限制时，构造标识符或常没有长度

26、限制时，构造标识符或常量表，语义信息中为其在表中的地量表，语义信息中为其在表中的地址（字符串空间址（字符串空间节省存贮空间）节省存贮空间）保留字的处理保留字的处理：识别保留字的方法：识别保留字的方法： 1.1.建立保留字表；顺序、散列、散列顺序建立保留字表；顺序、散列、散列顺序 2. 2.拼写的同时进行判断拼写的同时进行判断自动机自动机运算符的处理运算符的处理：不区分，统一成一类不区分，统一成一类区分，每个运算符为一类区分，每个运算符为一类空格符和制表符以及换行符的处理空格符和制表符以及换行符的处理 1. 1.无用的空格符和制表符要删掉；无用的空格符和制表符要删掉； 2. 2.字

27、符串内的空格不能删；字符串内的空格不能删； 3. 3.换行符不能删。用于错误定位换行符不能删。用于错误定位复合型特殊符，如复合型特殊符，如“:=”“:=”的处理的处理读到读到“:”“:”时不能判断是否为冒号，必须时不能判断是否为冒号，必须读下读下一字符。一字符。括号类配对预检括号类配对预检括号类：括号类： begin begin end ,if end ,if then, , ,( ) then, , ,( )处理方法：处理方法：对每类括号设置一个计数器（初值对每类括号设置一个计数器（初值=0=0）每当遇到开括号，则计数器加每当遇到开括号，则计数器加1 1 每当遇到闭括号时，计数器减

28、每当遇到闭括号时，计数器减1 1 词法分析结束时，如果计数器词法分析结束时，如果计数器 0 0，则，则表明括号不匹配。表明括号不匹配。字符串空间字符串空间目的：减少冗余，节省空间，提高访问速度目的：减少冗余，节省空间，提高访问速度方法：字符数组存放字符串，描述字符串信息：方法：字符数组存放字符串，描述字符串信息：下标下标长度长度词法错误校正词法错误校正词法错误种类：词法错误种类：语言不允许的符号：语言不允许的符号：# # 括号类配对错误：括号类配对错误：单词的后继符错（偶尔）：单词的后继符错（偶尔）：词法错误校正：词法错误校正： a a 删除已被读过的字符，并重新扫删除已被读过的字

29、符，并重新扫描未被读过的字符描未被读过的字符 b b 删除已读过的第一个字符，重新删除已读过的第一个字符，重新扫描它的后继部分的字符。扫描它的后继部分的字符。校正后的标示校正后的标示词法分析的结束词法分析的结束程序结束标志程序结束标志endend文件结束符文件结束符Eof.Eof.2.2.有穷自动机有穷自动机FAFA 描述程序设计语言中的单词字，进一步为词法描述程序设计语言中的单词字，进一步为词法分析程序的自动构造寻找特殊的方法和工具。分析程序的自动构造寻找特殊的方法和工具。主要内容：主要内容：确定有限自动机确定有限自动机DFADFA 确定有限自动机确定有限自动机DFADFA的实现的实现

30、非确定有限自动机非确定有限自动机NFANFA NFA NFA到到DFADFA的转换的转换 DFA DFA的化简的化简确定有限自动机确定有限自动机DFADFA确定有限自动机（确定有限自动机（DFADFA：Deterministric Deterministric Finite Automata )Finite Automata ) 为一个五元组为一个五元组 ( ( , ,SS,SSS,S0 0, ,f f,TS),TS)，其中：其中：是一个有穷字母表，它的每个元素称为一个是一个有穷字母表，它的每个元素称为一个输入字符；输入字符；SSSS是一个有穷集，它的每个元素称为一个状态；是一个有穷集，

31、它的每个元素称为一个状态；S S0 0 SSSS是唯一的一个初始状态；是唯一的一个初始状态；f f是在是在SSSS SSSS上的转换函数上的转换函数TSTS SSSS，是一个终止状态集，又称为接受状态是一个终止状态集，又称为接受状态集集DFADFA的两种表示方式的两种表示方式状态转换图：状态转换图：结点表示状态，转换边表示转换函数，结点表示状态，转换边表示转换函数，边边的箭头方向指向转换函数中定义的转换的箭头方向指向转换函数中定义的转换方方向。标识出初始状态和终止状态。向。标识出初始状态和终止状态。状态转换表：状态转换表：可用二维数组描述。标识出初始状态和可用二维数组描述。标识出初

32、始状态和终终止状态。止状态。 Trans（ S SI I ，a） S SJ J一个DFA的例子DFA M=(a,b,S,U,V,Q, S,f,Q),其中其中 f 定义为：定义为： f ( S, a )=U f ( V, a )=U f ( S, b )=V f ( V, b )=Q f ( U, a )=Q f ( Q, a )=Q f ( U, b )=V f ( Q, 1 )=QSUVQabbabaa,b状态转换图字符字符状态状态a ab bS SU UV VU UQ QV VV VU UQ QQ QQ QQ Q状态转换表DFADFA接受的字符串接受的字符串对于对于 * *中的任何字符

33、串中的任何字符串t,t,若存在一条从初始若存在一条从初始结点到某一终止结点的路径结点到某一终止结点的路径，且这条路上所且这条路上所有弧的标记符连接成的字符串等于有弧的标记符连接成的字符串等于t,t,则称则称t t可可为为DFA MDFA M所所接受（识别）接受（识别）。DFA M DFA M 所能接受的字符串的全体记为所能接受的字符串的全体记为L(M).L(M).DFADFA的确定性的确定性初始状态唯一。初始状态唯一。转换函数转换函数f:SSf:SSSSSS是一个单值函数，也是一个单值函数，也就是说，对任何状态就是说，对任何状态S S SS,SS,和输入符号和输入符号a a , f(S,a),

34、 f(S,a)唯一地确定了下一个状态。即至唯一地确定了下一个状态。即至多确定一个状态。多确定一个状态。没有空边。即没有输入为没有空边。即没有输入为（）DFADFA的实现的实现1 1状态转换表的形式：状态转换表的形式： 1.1.当前状态当前状态StateState置为初始状态置为初始状态 2.2.读一个字符读一个字符 CurrentCharCurrentChar 3.3.如果如果CurrentCharCurrentChar EofEof并且并且 T(State,CurrentChar) T(State,CurrentChar) errorerror 则当前状态转为新的状态则当前状态转为新的状

35、态T(State,Current)T(State,Current)，读下一字符。重复第读下一字符。重复第3 3步工作。步工作。 4. 4.如果当前字符为如果当前字符为EofEof并且当前状态属于终止状态，并且当前状态属于终止状态，则接受当前字符串，程序结束。否则报错则接受当前字符串，程序结束。否则报错特点：特点：程序短小，但占用存储空间多程序短小，但占用存储空间多bDFADFA的实现的实现2 2状态转换图的形式：状态转换图的形式：每个状态对应一个带标号的每个状态对应一个带标号的casecase语句语句转向边对应转向边对应gotogoto语句语句特点：特点：程序长，但占用存储空间少

36、程序长，但占用存储空间少 ijkaLi: case CurrentChar of a ：goto Lj b : goto Lk other : Error( )非确定有限自动机非确定有限自动机NFANFA定义定义1 1：一个非确定有限自动机一个非确定有限自动机( (NFA)ANFA)A是是一个五元组一个五元组A=(A=( ,SS,S,SS,S0 0,f,TS).,f,TS).其中其中是字母表是字母表 SS SS是状态集是状态集 S S0 0是初始状态集是初始状态集 f f是转换函数，但不要求是单值的是转换函数，但不要求是单值的 f: SS f: SS ( ( ) 2 2SSSS TS TS是

37、终止状态集是终止状态集非确定有限自动机非确定有限自动机NFANFA定义定义2 2：设设A A是一个是一个NFANFA，A= (A= ( ,SS,S,SS,S0 0,f,TS),f,TS)则定义则定义L(A)L(A)为从任意初始状态到任意终止状为从任意初始状态到任意终止状态所接受的字符串。态所接受的字符串。 L(A)=L(A)= | |s s0 0 s s, s, s0 0 S S0 0 s s TS 定义定义3 3：设设A A1 1和和A A2 2是同一个字母表上的自动机，是同一个字母表上的自动机，如果有如果有L(AL(A1 1)=L(A)=L(A2 2),),则称则称A A1 1和和A A2

38、 2等价。等价。NFANFA到到DFADFA的转换的转换定理定理1 1 对于每一个非确定自动机对于每一个非确定自动机A,A,存在一个存在一个确定自动机确定自动机A A, ,使得使得L(A)=L(AL(A)=L(A).).转换转换：符号合并符号合并同一状态的不同输出边标有相同的字符。同一状态的不同输出边标有相同的字符。合并合并含有含有边边 NFANFA到到DFADFA的转换的转换符号合并符号合并：A A：NFA, ANFA, A:FA:FA 1. 1.令令A A的初始状态为的初始状态为S S0 0=S=S1 1,S,S2 2, ,S Sk k, 其中其中S S1 1S Sk k是是A

39、A的全部初始状态。的全部初始状态。 2. 2.若若S S=S=S1 1, ,S,Sm m 是是A A的一个状态，的一个状态， a a则定义则定义 f f(S(S,a)=f(S,a)=f(S1 1,a),a) f(Sf(S2 2,a),a) f(Sf(Sm m,a),a) 3. 3.重复步骤直至不出现新的状态为止。重复步骤直至不出现新的状态为止。 4. 4.若若S S=S=S1 1, ,S,Sn n 是是A A的一个状态的一个状态, ,且存且存在一个在一个S Si i是是A A的终止状态，则令的终止状态，则令S S为为A A 的终止状态。的终止状态。NFANFA到到DFADFA的转换的转换合

40、并合并（Close(S)Close(S)） 1. 1.对对S S状态寻找状态寻找边，如果有令边，如果有令SsSsSS 2. 2.对任意状态对任意状态SiSi Ss,Ss,如果有：如果有：f(Si,f(Si, )=)= SjSj则则消除消除边：边：Ss= SSs= Ss s SjSj 重复上述操作直至没有重复上述操作直至没有边边 3. 3.对对a a f( f(SsSs,a)= ,a)= f( f(SkSk, ,a a) ) Ss=S1, Ss=S1,Sm,k=1,Sm,k=1,m.,m. 4. 4.如果如果SsSs中包含中包含初始状态则初始状态则SsSs也为初始状态，也为初始状态，

41、如果有终止状态，则如果有终止状态，则SsSs为终止状态。为终止状态。 NFANFA到到DFADFA的转换的转换NFANFA到到DFADFA的转换过程的转换过程: :1. NFA1. NFA初始状态集的初始状态集的合并集作为合并集作为DFADFA的初始状的初始状态。态。2. 2. 对对DFADFA中一状态中一状态S S，对对a a, ,进行符号合并和进行符号合并和合并得到的状态设为合并得到的状态设为S S, ,定义定义DFADFA的转换的转换函数为函数为f(S,a)=Sf(S,a)=S. .3. 3. 直至没有新状态产生为止。直至没有新状态产生为止。将如下的将如下的NFA转化为转化为DFA

42、bbbaa012435678910DFADFA的化简（极小化）的化简（极小化）状态等价状态等价对对DFADFA中的两个状态中的两个状态S S1 1和和S S2 2，如果将它，如果将它们看作是初始状态，所接受的符号串相们看作是初始状态，所接受的符号串相同，则定义同，则定义S S1 1和和S S2 2是等价的。是等价的。方法方法: :状态分离法状态分离法初始化为两个不等价状态集组：非终初始化为两个不等价状态集组：非终止状态组和终止状态组。止状态组和终止状态组。对每组中的某个状态分离出与之不等对每组中的某个状态分离出与之不等价的状态组，直至所有状态组内部状态价的状态组，直至所有状态组内部状

43、态都等价为止。都等价为止。 3. 正则表达式正则表达式描述程序设计语言中单词的一种简单而描述程序设计语言中单词的一种简单而且数学化工具。且数学化工具。表示符号串的构成模式表示符号串的构成模式正则表达式正则表达式r r定义了一个符号串集合定义了一个符号串集合rs, rs, rsrs内的每个符号串都与内的每个符号串都与r r所定义的模式相所定义的模式相匹配，匹配，rsrs称为由称为由r r生成的语言生成的语言L(r)L(r)正则表达式中出现的所有符号构成的集正则表达式中出现的所有符号构成的集合为该正则表达式的字母表合为该正则表达式的字母表，用用表示。表示。正则表达式正则表达式主要内容：主要内容

44、：基本概念基本概念正则表达式定义及一些性质正则表达式定义及一些性质正则定义正则定义扩扩充充的的正正则则表表达达式式及及程程序序设设计计语语言言中中单词的定义单词的定义正则表达式的局限性。正则表达式的局限性。正则表达式正则表达式基本概念：基本概念：字母表：字母表：非空有限集，非空有限集，，其元素称为符号或字母，其元素称为符号或字母. .符号串：符号串：符号的有限序列，也称为符号的有限序列，也称为字字。或或表示空表示空串串空串集空串集不同于空集不同于空集。符号串长度：符号串长度：符号串中字符的个数符号串中字符的个数.|.| | |符号串连接：符号串连接：和和都是符号串，则都是符号

45、串，则为符号串的连接为符号串的连接特别有：特别有： = = = = 符号串集的乘积：符号串集的乘积：A A和和B B是符号串的集合，则称是符号串的集合，则称 AB= AB=| | A A， B B 特别有：特别有：A=AA=A=A=A，其中其中表示空集。表示空集。符号串的方幂：符号串的方幂：设设A A是符号串的集合，则称是符号串的集合，则称A Ai i为符号为符号串集串集A A的方幂，其中的方幂，其中i i是非负整数。是非负整数。 A A0 0 = = A A1 1 = A , A= A , A2 2 = A A = A A A AK K = AA.A(k = AA.A(k个个) ) 符

46、号串集合的正闭包：符号串集合的正闭包： A A+ + =A =A1 1 A A2 2 A A3 3 . . 符号串集合的星闭包：符号串集合的星闭包： A A* * =A =A0 0 A A1 1 A A2 2 A A3 3 . . 正则表达式及其一些性质正则表达式及其一些性质为给定的字母表，则每个为给定的字母表，则每个上的正则表达上的正则表达式将定义式将定义上的一个字符串集。上的一个字符串集。用用R R 表示表示上的正则表达式上的正则表达式，用用L(RL(R ) )表示表示R R 所表示的字所表示的字符串集合符串集合。即：函数。即：函数L L表示表示正则表达式正则表达式字符串集的

47、映射。字符串集的映射。则则R R 的定义及其含义如下：的定义及其含义如下：是正则表达式，即R 。其中L()= 。是正则表达式，即 R 。其中L()= 。 c 是正则表达式，即c R 。其中 L(c)= c 。 A和B是正则表达式，即A R，B R ，则有( A )R，L( (A) )= L(A)A | BR，L( A | B )= L(A)L(B)A BR，L( A B )= L(A)L(B)A*R，L( A*)= L(A)* 正则表达式例正则表达式例 = = a,b .a,b . 正则表达式e1.ab*2. a(a|b)*L(e)1.上所有以a为首后跟任意多个（包括0个）b的字符

48、串集2.上所有以a为首的字符串集正则表达式的性质正则表达式的性质q A | B = B | A | 的可交换性q A | (B | C) =(A | B ) C | 的可结合性q A (B C) =(A B )C 连接的可结合性q A (B | C) =A B | A C 连接的可分配性q (A | B ) C =A C | B C 连接的可分配性q A* =A* 幂的等价性q A=A=A 是连接的恒等元素扩充的正则表达式扩充的正则表达式一次或多次重复一次或多次重复: : A+ 任何符号任何符号: “” : “” 在字母表中任何符号在字母表中任何符号. . |.|. 符号范围符号范围: 0

49、-9 : 0-9 a-z A-Z 不在给定范围内的符号不在给定范围内的符号: (: (a|b|c)或或 L La L Labc 0或或1 1次次( (可选可选): ): r?=( |r)正则定义正则定义为较长的正则表达式提供一个简化了的名为较长的正则表达式提供一个简化了的名字。如要为一个或多个数字序列写一个正字。如要为一个或多个数字序列写一个正则表达式，则可写作：则表达式，则可写作：（0|1|2|0|1|2|9)(0|1|2|9)(0|1|2|9)9)* *或写作或写作 digit digitdigit digit* * 其中其中 digit= digit= 0|1|2|0|1|2|9|9就是

50、名字就是名字digitdigit的正则定义，表示为：的正则定义，表示为： digit digit 0|1|2| 0|1|2|9|9程序设计语言中单词的程序设计语言中单词的正则表达式定义正则表达式定义保留字保留字如如 BeginBeginbeginbegin标识符标识符 letter=a-zletter=a-z，A-ZA-Z digit=0-9digit=0-9 identifier=letter(letter|digit)identifier=letter(letter|digit)* * 数字数字整数整数IntInt1-9Digit1-9Digit* *|0 |0 实数实数realre

51、alIntInt. .IntInt 特殊符号特殊符号 +|-| +|-|正则表达式的局限性正则表达式的局限性正则表达式不能用于描述配对或嵌套的结正则表达式不能用于描述配对或嵌套的结构构正则表达式不能用于描述重复串正则表达式不能用于描述重复串例：例： w c w | w是是a和和b的串的串无法用正则无法用正则表达式表示（保证两边表达式表示（保证两边w是相同的）。是相同的）。正则表达式与有限自动机等价正则表达式与有限自动机等价定理：对任一确定有限自动机定理：对任一确定有限自动机A A，存在一正存在一正则表达式则表达式e,e,使得使得L(A)=L(e),L(A)=L(e),反之亦然。反之亦然。

52、关系图：关系图：DFA正则表达式NFA正则表达式到NFA的转换规则：13a b12a | b13 b*123ab12ab123bl首先扩展转换图：XW123ab12ab12313a b12a | b13a b* cabcDFA到正则表达式的转换规则：4. 词法分析器的工作过程词法分析器的工作过程词法分析器（Scanner）输入流词法描述（正则表达式）NFADFATokenListerror词法分析器的设计词法分析器的设计人工构造词法分析器过程：人工构造词法分析器过程： 1. 1.确定词法分析器的接口，即确定词法分析确定词法分析器的接口，即确定词法分析器是作为语法分析的一个子程序还是作为器是作

53、为语法分析的一个子程序还是作为独立一遍。独立一遍。 2. 2.确定单词分类和确定单词分类和TokenToken结构。结构。 3. 3.根据根据2 2步，构造每一类单词的描述步，构造每一类单词的描述正则表达式正则表达式NFANFADFADFA。 4. 4.根据根据3 3步设计算法实现步设计算法实现DFADFA。利用工具自动生成：利用工具自动生成：ScanGen LexScanGen Lex第四章第四章文法与语法分析文法与语法分析语法分析概述语法分析概述文法和文法分析文法和文法分析进行语法分析的几种方法进行语法分析的几种方法1. 语法分析概述语法分析概述q语法分析器和识别器语法分析器

54、和识别器q语法分析的功能语法分析的功能q语法错误类别语法错误类别q语法错误的处理语法错误的处理语法分析器和识别器语法分析器和识别器语法分析器的功能：语法分析器的功能：语法错误类别语法错误类别程序的开始符，语句（表达式）的开始符程序的开始符，语句（表达式）的开始符（后继符）错（后继符）错标识符（常量）错：该出现时未出现标识符（常量）错：该出现时未出现括号类错误：不匹配括号类错误：不匹配分隔符错：分隔符错：assignment;assignment; Token/TokenListParser语法树/语法错误信息语法错误处理语法错误处理要求：报告错误出现的位置要求：报告错误出现

55、的位置修复错误并继续检查后续部分修复错误并继续检查后续部分执行开销不应太大执行开销不应太大修改策略：修改策略：插入插入/ /删除删除/ /修改修改应急方式恢复应急方式恢复: : 定义同步符号集合定义同步符号集合( (分隔符，分隔符，end,end,某些某些语句头符，语句头符， elseelse等等) ) 发现错误时，跳过一些发现错误时，跳过一些TokenToken，直到找直到找到某个同步符号，再继续进行分析。到某个同步符号，再继续进行分析。同步符号保证接下来的分析是从正确的同步符号保证接下来的分析是从正确的头位置开始。头位置开始。2. 文法和文法分析文法和文法分析文法能清晰

56、地描述程序设计语言的语法构成文法能清晰地描述程序设计语言的语法构成易于理解。易于理解。文法能自动地构造有效的语法分析器，检文法能自动地构造有效的语法分析器，检查源程序是否符合语言规定地语法形式。查源程序是否符合语言规定地语法形式。文法定义可以了解程序设计语言的结构，有文法定义可以了解程序设计语言的结构，有利于将源程序转化为目标代码，以及检查出利于将源程序转化为目标代码，以及检查出语法错误。语法错误。基于文法实现的语言易于扩展基于文法实现的语言易于扩展文法的定义文法的定义文法文法G定义为四元组定义为四元组( (VT, ,VN, ,S, ,P)VT是有限的终极符集合是有限的终极符集合 VN

57、是有限的非终极符集合是有限的非终极符集合S是开始符，是开始符，S VNP是产生式的集合，且具有下面的形式：是产生式的集合，且具有下面的形式：，其中，其中， (VT VN )*文法的分类文法的分类 O O型型文文法法: : 也也称称为为短短语语文文法法，其其产产生生式式具具有有形形式式: : ，其其中中 , ,( (VT VN)*，并并且且至至少少含含一一个非终极符个非终极符。 1 1型型文文法法: : 也也称称为为上上下下文文有有关关文文法法。它它是是0 0型型文法的特例，即要求文法的特例，即要求| | | | | | | (| (S 例例外外，但但S不得出现于产生式右部不得出现于产生

58、式右部) )。 2 2型型文文法法: : 也也称称为为上上下下文文无无关关文文法法。它它是是1 1型型文文法法的的特特例例，即即要要求求产产生生式式左左部部是是一一个个非非终终极极符符: : A 。 3 3型型文文法法: : 也也称称为为正正则则文文法法。它它是是2 2型型文文法法的的特特例例，即即其其产产生生式式的的右右部部至至多多有有两两个个符符号号，而而且且具具有下面形式之一有下面形式之一: : A a ，A a B其中其中A,B VN ，a VT 。上下文无关文法（上下文无关文法（CFG）定义为四元组定义为四元组( (VT, ,VN, ,S, ,P)VT是有限的终极符集合是有限的终极

59、符集合 VN是有限的非终极符集合是有限的非终极符集合S是开始符，是开始符，S VNP是产生式的集合，且具有下面的形式：是产生式的集合，且具有下面的形式： AX1X2Xn 其中其中A VN，Xi ( (VT VN) ，右部可空。右部可空。推导推导：如果：如果A是一个产生式，则有是一个产生式，则有 A ,其中其中表示一步推导表示一步推导( (用用A )。这时称这时称是由是由 A 直接推导的。直接推导的。的含义的含义是，使用一条规则，代替是，使用一条规则，代替左边的某个符左边的某个符号，产生号，产生右端的符号串右端的符号串 + + : : 表示表示通过一步或多步可推导出通过一步或多步可推导出 *

60、 * : : 表示表示通过通过0 0步或多步可推导步或多步可推导出出句型：句型：如果有如果有S* ，则称符号串则称符号串为为CFG的的句句型型。我们。我们用用SF(G)表示文法表示文法G的所有句型的所有句型的集合的集合句子：句子：如果如果只包含终极符，则称只包含终极符，则称为为CFG的句的句子子，其中其中S是文法的开始符是文法的开始符语言：语言： L( G ) = u | S + u , u VT* 。文法文法G所所定义的语言是其开始符所能推导的所有定义的语言是其开始符所能推导的所有终极符号串终极符号串( (句子句子) )的集合。的集合。最左（右）推导：最左（右）推导：

61、如果进行推导时选择的是句型中的最左如果进行推导时选择的是句型中的最左( (右）右）非终极符，则称这种推导为最左非终极符，则称这种推导为最左( (右右) )推导，推导，并用符号并用符号lmlm（r mr m）表示最左（右）推导。表示最左（右）推导。左（右）句型：左（右）句型：用最左推导方式导出的句型，称为左句型，用最左推导方式导出的句型，称为左句型，而用最右推导方式导出的句型，称为右句型而用最右推导方式导出的句型，称为右句型( (规范句型规范句型) )。结论：结论：每个句子都有相应的最右和最左推导（但对每个句子都有相应的最右和最左推导（但对句型此结论不成立）句型此结论不成立）语法分析树

62、与二义性语法分析树与二义性q语法分析树语法分析树( (简称分析树简称分析树) )用来描述句型的结构，是用来描述句型的结构，是句型推导的一种树型表示。文法句型推导的一种树型表示。文法 G=(VG=(VN N,V,VT T,S,P),S,P)，则则称满足下面条件的树为称满足下面条件的树为G G的一棵分析树：的一棵分析树：1. 1. 每个结点都有每个结点都有G G的一个文法符号，并且根结点标的一个文法符号，并且根结点标有初始符有初始符S S，非叶结点标有非终极符，叶结点标有非叶结点标有非终极符，叶结点标有终极符或非终极符或终极符或非终极符或。 2. 2.如果一个非叶结点如果一个非叶结点A A有

63、有n n个儿子结点个儿子结点( (从左到右）为从左到右）为 X1,X2,.,XnX1,X2,.,Xn，则则G G一定有产生式一定有产生式AX1X2 .Xn AX1X2 .Xn 。q线性推导：线性推导：我们称用我们称用符号进行的推导为线性推导符号进行的推导为线性推导。q树型推导与线性推导的不同：树型推导与线性推导的不同：线性推导指明了推导线性推导指明了推导的顺序，而树型推导则没有指明推导的顺序。因此，的顺序，而树型推导则没有指明推导的顺序。因此，句型一般只有一棵分析树句型一般只有一棵分析树( (如果无二义性如果无二义性) )，而线性，而线性推导则可很多。推导则可很多。二义性文法文法文法G=(+

64、,*,I,(,),E,E,P),其中其中P为：为： E i E E + E E E * E E ( E )E+EEE*Eii推导1的语法树EE*EE+Eii推导2的语法树句型i*i+i:推导1: E E + E E * E + E i * E + E i * i + E i * i + i推导1: E E * E i * E i * E + E i * i + E i * i + iii if then else if then .假设有条件语句 if e1 then if e2 then s1 else s2则可有下图所示的两棵不同的语法分析树： if语句的二义性ififthenelseth

65、ene1e2S1S2elsethenifthenife1e2S1S1文法二义性的消除文法二义性的消除q二义性文法的判定是递归不可解的二义性文法的判定是递归不可解的q消除二义性的方法：消除二义性的方法： 1. 1.设置一规则，该规则可在产生二义设置一规则，该规则可在产生二义性的情况下，指出哪一个分析树是正确的性的情况下，指出哪一个分析树是正确的 2. 2.将文法改变成一个强制正确分析树将文法改变成一个强制正确分析树的构造格式的构造格式定义表达式的无二义性文法定义表达式的无二义性文法E TE E + TT FT T * FF ( E )F ilET|E+TlTF|T*FlF(E)|iIf语句的无二

66、义性文法定义语句的无二义性文法定义 stmt matched_stmt | unmatched_stmt matched_stmt if E then matched_stmt else matched_stmt | other unmatched_stmt if E then stmt | if E then matched_stmt else unmatched_stmt有关文法实用中的一些说明有关文法实用中的一些说明有关文法的实用限制有关文法的实用限制有害规则有害规则 U U U U 多余规则多余规则不可到达的，不可终止的不可到达的，不可终止的上下文无关文法中的上下文无关文法中的

67、规则规则 A A 文法文法G Gss: :1)1) S S B e B e2)2) B B C e C e3)3) B B A f A f4)4) A A A e A e5)5) A A e e6)6) C C C f C f7)7) C C C C8)8) D D f f求能推出求能推出的非终极符的非终极符 S_Lambda = Aj j | A| Aj j PSet PSet; 对对p PsetPset：A Ap p X X1 1X Xn n, , 如果如果X Xi i S_Lambda, 0S_Lambda, 0 i i n n，则则 S_Lambda = S_Lambda S_Lam

68、bda = S_Lambda A Ap p 重复第二步，直至重复第二步，直至S_LambdaS_Lambda收敛为止收敛为止消除空产生式算法消除空产生式算法S_Lambda = Aj j | A| Aj j + + ;删除所有的空产生式和只能导出空串的删除所有的空产生式和只能导出空串的非终极符。非终极符。对剩余的每个产生式对剩余的每个产生式P：AC1C2Cp 如果有如果有Ci，因为删除了所有的空产生因为删除了所有的空产生式，需要扩充一些产生式式，需要扩充一些产生式 AC1Ci-1Ci+1Cp。重复上述过程直至不出现新的产生式为重复上述过程直至不出现新的产生式为止。止。句型分析的有关问题句型

69、分析的有关问题短语：短语：设设S是文法的开始符，是文法的开始符，是句型是句型( (即有即有S * ），），如果满足条件：如果满足条件：S * A A + 则称则称是句型是句型的一个短语。的一个短语。直接短语（简单短语）：直接短语（简单短语）：如果满足条件：如果满足条件：S * A A 则称则称是句型是句型的一个简单短语。的一个简单短语。句柄：句柄：一个句型可能有多个简单短语，其中最一个句型可能有多个简单短语，其中最左的简单短语称之为句柄。左的简单短语称之为句柄。文法G: E T | E + T T F | T * F F ( E ) | i(T+i)*i+F是G的一个句型。其推

70、导过程如下：E E+T T+T T*F+T F*F+T ( E ) * F+T ( E + T ) * F+T ( T + T ) * F + T ( T + F ) * F +T ( T + i ) * i + F短语有短语有8 8个：个： 1.( 1.(T+i)*i+F 2.(T+i)*iT+i)*i+F 2.(T+i)*i 3.(T+i) 4.T+i 5.T 3.(T+i) 4.T+i 5.T 6. 6.第一个第一个i 7.i 7.第二个第二个i 8.Fi 8.F简单短语有简单短语有4 4个：个： T,T,第一个第一个i,i,第二个第二个i,Fi,F句柄有句柄有1 1个：个：T T一个有

71、用的定理一个有用的定理定义定义1 1：由某一结点及其所属分支组成的部分树称由某一结点及其所属分支组成的部分树称为原树的一棵子树。为原树的一棵子树。定义定义2 2：只有单层分支的子树称为简单子树。只有单层分支的子树称为简单子树。定理定理1 1： 1. 1.每个句型都有一棵语法树，每个语法树的叶每个句型都有一棵语法树，每个语法树的叶组成一句型。组成一句型。 2. 2.每棵子树的叶组成短语，每棵简单子树的叶每棵子树的叶组成短语，每棵简单子树的叶组成简单短语，最左简单子树的叶组成句柄。组成简单短语，最左简单子树的叶组成句柄。 3. 3.用语法树可证明每个句子都有一规范推导。用语法树可证明每个句子都有一

72、规范推导。l短语有8个： 1.(T+i)*i+F 2.(T+i)*i 3.(T+i) 4.T+i 5.T 6.第一个i 7.第二个i 8.Fl简单短语有4个： T,第一个i,第二个i,Fl句柄有1个：TEE+TTT*FiF(E)E+TTiFF文法G: E T | E + T T F | T * F F ( E ) | i i (1) *i (2) +i (3)是G的一个句子，（1）画出该句子的语法分析树（2）给出该句子的最左推导和最右推导（3）找出该句子的所有短语，简单短语，句柄First集的定义设设G=(VT，VN，S，P)是上下文无关文法是上下文无关文法 First( ) = a VT |

73、 * a. (if * then else ) 可可以以根根据据当当前前的的输输入入符符号号是是属属于于哪哪个个产产生生式式右右部部的的首首符符集集而而决决定定选选择择相相应应产产生生式式进进行推导。行推导。文法文法G3S: S aA | d A bAS | 输入串输入串W=abd。自顶向下的推导过程为自顶向下的推导过程为: : S aA abAS abS abd 相应的语法树为：相应的语法树为：SaAbASdFollow集的定义设设G=(VT，VN，S，P)是上下文无关文法，是上下文无关文法，A VN，S是开始符号是开始符号Follow(A) = a VT | S+ .Aa. (if S*

74、.A then # # else )当文法中存在形如：当文法中存在形如：A ,A 的产生式，的产生式，并且并且，不同时推出不同时推出时，如果满足时，如果满足 First( ) ( First( ) Follow(A) )= 时，对时，对于非终极符于非终极符A的替换仍可唯一的确定候选产的替换仍可唯一的确定候选产生式。生式。三个集合的定义三个集合的定义 First( ) = a VT | * a. (if * then else ) Follow(A) = a VT | S+ .Aa. (if S*.A then # # else ) Predict(A ) = First( ) ，当当F

75、irst( ) = = First( )- Follow(A) ，当当 First( ) 三个集合的定义三个集合的定义 First( ) = a VT | * a. (if * then else ) Follow(A) = a VT | S+ .Aa. (if S*.A then # # else ) Predict(A ) = First( ) ，当当First( ) = First( )- Follow(A) ，当，当 First( ) 计算First(X)集对每一文法符号对每一文法符号X计算计算First(X)若若X VT,First(X)=X若若X VN则则 First(X)=a|

76、 Xa PSet,a VT若若X VN,且有产生式且有产生式X,则则 First(X)若若X VN,有产生式有产生式XY1Y2Yn ，且，且Y1,Y2,Yi VN 当当Y1,Y2,Yi-1* ，则则First(Y1)- , First(Y2)- , First(Yi-1)- , First(Yi)都包含在都包含在First(X)中。中。当当Yi * (i=1,2,n), 将将并入并入First(X) 中。中。计算First()集若符号串若符号串 =X1X2Xn，当当X1,X2,Xi-1* ，Xi不能不能 * * ，则，则First( )= 1i-1(First(Xj)- ) First(

77、Xi)若所有若所有Xi都能都能* * ，则，则First( )= 1nFirst(Xj)计算Follow集1: 对所有对所有A VN，令，令Follow(A):= ；对开始符；对开始符 S,令令Follow(S):=# # ； 2: 若有产生式若有产生式AxBy，如果如果First(y) 则：则： Follow(B):=(First(y) ) Follow(A) 否则否则 Follow(B):= First(y) 3: 重复重复2和和3，直至对所有，直至对所有A VN，Follow(A)收收敛为止。敛为止。计算计算Predict集集lPredict(A)=First()，当First()不

78、含=First()Follow(A)，当First()含 E T E E + T E | T F T T * F T | F id | ( E ) Predict( ETE ) = first(TE) = id , ( Predict( E +TE ) = first(+TE) = + Predict( E ) = follow(E) = ) , # Predict( T FT ) = first(FT) = id , ( Predict( T *FT ) = first(*FT) = * Predict( T ) = follow(T) = + , ) , # Predict( F id )

79、 = first(id) = id Predict( F (E) ) = first(E) = ( 语法分析方法的分类语法分析方法的分类自顶向下分析方法自顶向下分析方法递归子程序法递归子程序法 LLLL分析方法分析方法自底向上分析方法自底向上分析方法优先关系法优先关系法 LRLR分析方法分析方法自顶向下分析概述自顶向下分析概述从文法开始符出发试图推导出所给的终极符串。从文法开始符出发试图推导出所给的终极符串。例例 Gz : 1 Z aBd 2 B d 3 B c 4 B bB 对给定的终极符串对给定的终极符串abcd，推导过程：推导过程： Z 1 1 aBd aBd 4 4 abB

80、d abBd 33 abcd abcd aBd # abcd # Match Bd # bcd # Derivation bBd # bcd # Match Bd # cd # Derivation cd # cd # Match d # d # Match # # Success 自顶向下的语法分析过程【Sf, Rest, Action(D/M/S/E)】 Z # abcd # Derivation自底向上分析概述自底向上分析概述从终极符串出发归约（从终极符串出发归约（reduce）出文法的开始符。出文法的开始符。例例 Gz : 1 Z aBd 2 B d 3 B c 4 B bB 对给

81、定的终极符串对给定的终极符串abcdabcd，归约过程：归约过程： abcd abcd 3 3 abBdabBd 4 4 aBdaBd 33 Z Z #a bcd # Shift #ab cd # Shift #abc d # Reduce 3 #abB d # Reduce 4 #aB d # Shift #aBd # Reduce 1 #Z # Success 自底向上的语法分析过程【Analysis ST, Input, Action(S/R/E/S)】 # abcd # Shift文法文法G1S: S pA | qB A cAd | a 输入串输入串W=p c c a d d。自顶向下

82、的推导过程为自顶向下的推导过程为: : S pA pcAd pccAdd pccadd 相应的语法树为：相应的语法树为：pAcAdcAdaS文法文法G2s: S Ap |Bq A a |cA B b |dB 输入串输入串W=ccap。自顶向下的推导过程为自顶向下的推导过程为: : S Ap cAp ccAp ccap 相应的语法树为：相应的语法树为：SApcAcAa自顶向下分析自顶向下分析递归下降法递归下降法递归下降法递归下降法( (Recursive-Descent Parsing)Recursive-Descent Parsing) 对每个非终极符按其产生式结构产生相应对每个非终极符按其产

83、生式结构产生相应语法分析子程序语法分析子程序. . 终极符产生匹配命令终极符产生匹配命令非终极符则产生调用命令非终极符则产生调用命令文法递归相应子程序也递归，所以称这种文法递归相应子程序也递归，所以称这种方法为方法为递归子程序方法或递归下降法。递归子程序方法或递归下降法。例：Stm while Exp do Stm 则对应产生式右部的语法分析程序部分如下：begin Match($while)； Exp； Match($do)； Stm end while xy do if xz then x:= x+y else x:= y Begin Match($while); Exp; Match

84、($do); Stm End 当产生式中形如当产生式中形如: : A A 1 1| | 2 2| | | | n n 则按下面的方法编写子程序则按下面的方法编写子程序A A： procedure A( )procedure A( ) begin if token begin if token Predict(APredict(A1 1) then ) then ( ( 1 1) ) else else if token if token Predict(APredict(A2 2) then ) then ( ( 2 2) ) else else if token if token Predi

85、ct(APredict(An) then n) then ( ( n n) ) else else err( ) err( ) end end 其中对其中对 i=X1X2Xn， ( i) = (X1); (X2); (Xn); 如果如果X V VN N， ( (X)= X 如果如果X V VT T， (X)= Match(X) 如果如果X= , ( ) = skip(空语句空语句) )假设有文法Z a B aB b B | c则相应的递归子程序可如下：procedure Z( )begin if token=a then Match(a)； B； Match(a) else err( )end

86、;procedure B ( )begin if token = b then Match(b); B; else if token = c then Match(c); else err( )end;主程序：Begin ReadToken; Z endReadTokenReadTokenq递归子程序方法的条件： (1)predict(Ak) predict(Aj )=，当k j (2)任一非终极符A都不是左递归的。q产生式A被选择的条件是：当前的输入符属于predict(A)。q至多一个产生式被选择的条件是： predict(Ak) predict(Aj )=，当k j文法的等价变换文法的

87、等价变换某个非终极符某个非终极符A A有如下的两个产生式：有如下的两个产生式： A A ，A A ( (即有左公共前缀即有左公共前缀) )某个非终极符某个非终极符A A有直接左递归产生式：有直接左递归产生式：A A A A | . | . 消除左公共前缀消除左公共前缀消除左递归消除左递归消除公共前缀消除公共前缀变换步骤：变换步骤：1.产生式形如：A1|2|n| 表示不以开头的字符串。2.引进非终极符A，使产生式替换为： A A | A 1|2 | nStm id := ExpStm id (ExpL)ExpL Exp ExpL Exp,ExpL Stm id StmStm := ExpSt

88、m ( ExpL )ExpL Exp ExpLExpL , Exp ExpLExpL 消除公共前缀的例子消除公共前缀的例子消除公共前缀的例子2 2A A adadA A BcBcB B aAaAB B bBbBlA adlA aAclA bBclB aAlB bBlAa(d|Ac)lA bBclB aAlB bBlA aAlA dlA Ac A bBc B aA B bB替换提因子引进A左递归左递归一个文法含有下列形式的产生式时一个文法含有下列形式的产生式时（1 1）A AA A A A V VN N, , V V* *（2 2）A AB B B BA A A,B A,B V VN N, ,

90、 B | | | b | b 按照直接左递归方式消除。去掉多余的按照直接左递归方式消除。去掉多余的产生式产生式例：1 A B 1 | a 2 B C 2 | b 3 C A 3 | c A B 1 C 2 1 A 3 2 1 3 C ( B 1| a ) 3 | c 3 C C 2 1 3 |b 1 3 |a 3 |c 4 C (b 1 3 | a 3 | c ) C5 C 2 1 3 C | 1,2,4,5与原文法等价LLLL分析方法分析方法自顶向下分析自顶向下分析LL(1)LL(1)是是LL(k)LL(k)的特例的特例, ,其中的其中的k k则表示向前看则表示向前看k k个符号。个符号。

91、 LL(1)LL(1)方法和递归下降法属于同一级别的自顶方法和递归下降法属于同一级别的自顶向下分析法，但有一些区别向下分析法，但有一些区别. . 递递归归下下降降法法对对每每个个非非终终极极符符产产生生子子程程序序，而而LL(1)LL(1)方方法则产生法则产生LLLL分析表；分析表；递递归归下下降降法法能能判判断断每每个个产产生生式式的的结结束束，而而LL(1)LL(1)方方法法则不能；则不能；递递归归下下降降法法分分析析法法不不用用符符号号栈栈，而而LL(1)LL(1)方方法法则则用用符符号栈。号栈。LL(1)LL(1)分析方法的条件分析方法的条件对对于于任任一一非非终终极极符符A A，其

92、其任任意意两两个个产产生生式式AA 和和AA ，都要满足下面条件：都要满足下面条件： Predict(APredict(A ) ) Predict(APredict(A )= )= 满足这一条件的文法称为满足这一条件的文法称为LL(1)LL(1)文法。文法。 LL(1)LL(1)分析例分析例文法文法GA: A GA: A a B c a B c11 B B d d 22| b B| b B33输入串：输入串：abbdcabbdc分析过程：分析过程：( (A,abbdc)A,abbdc)1 1(cBa,abbdc) (cBa,abbdc) (cB,bbdc) (cB,bbdc) 3 3(cBb,

93、bbdc) (cBb,bbdc) (cB,bdc) (cB,bdc) 3 3 (cBb,bdc) (cBb,bdc) (cB,dc) (cB,dc) 2 2 (cd,dc) (cd,dc) (c,c) (c,c) ( , )( , )LL(1)LL(1)分析的动作分析的动作替换：替换：当当X X1 1 V VN N时选相应候选式时选相应候选式去替换去替换X X1 1。匹配：匹配：当当X X1 1 V VT T时它与时它与Y Y1 1进行匹配，其结果可进行匹配，其结果可能成功，也可能失败，如果成功则去掉能成功，也可能失败，如果成功则去掉X X1 1和和Y Y1 1，否则报错。否则报错。接受：接

94、受：当格局为（空，空）时报分析成功。当格局为（空，空）时报分析成功。报错：报错：出错后，停止分析。出错后，停止分析。LL(1)LL(1)分析表分析表T T：V VN N V VT T P P Error Error T(A,t)=AT(A,t)=A 若若t t Predict( Predict( AA ) ) T(A,t)=Error T(A,t)=Error 否则否则其中其中P P表示所有产生式的集合表示所有产生式的集合 LL(1)LL(1)分析的驱动器分析的驱动器StackInputa 栈为空情形的处理 X VT情形的处理 X VN情形的处理 XLL1分析表LL_Driver11初始化：

95、初始化： Stack :=emptyStack :=empty；Push(S)Push(S)；22读下一个输入符：读下一个输入符： Read(a)Read(a)；33若当前格局是若当前格局是( ( empty, # )empty, # )，则成功结束；则成功结束；否则转下；否则转下；44设当前格局为（设当前格局为（. X, a.). X, a.)，则则若若 X X V VT T & X=a& X=a 则则 Pop(1)Pop(1)；Read(a)Read(a)；goto 3 goto 3 若若 X X V VT T & X & X a a 则则 ErrorError；若若 X X V V

96、N N，则：则： if T(X,a)=XYif T(X,a)=XY1 1Y Y2 2Y Yn n then Pop(1)then Pop(1)；Push(YPush(Yn n , ,.,Y,Y1 1) )；goto3 goto3 else Error else Error LLLL分析实例分析实例文法文法G:G: E T E1 E + T E2 | 3 T F T4 T * F T5 | 6 F id7 | ( E )8符号串 i + i * i # 的LL1分析过程：Predict( 1 ) = first(TE) = id , ( Predict( 2 ) = first(+TE) = +

97、 Predict( 3 ) = follow(E) = ) , # Predict( 4 ) = first(FT) = id , ( Predict( 5 ) = first(*FT) = * Predict( 6 ) = follow(T) = + , ) , # Predict( 7 ) = first(id) = id Predict( 8 ) = first(E) = ( 分析栈S 输入流T 矩阵元素# E i + i * i # LL E ,i = 1# E T i + i * i # LL T ,i = 4# E T F i + i * i # LL F ,i = 7# E T

98、i i + i * i # Match# E T + i * i # LL T,+ = 6# E +i * i # LL E,+ = 2# E T+ +i * i # Match# E T i * i # LL T,i =4# E T F i* i # LL F,i = 7# E T i i * i # Match# E T * i # LL T,* = 5# ETF* * i # Match# ETF i # LLF,i = 7# ETi i # Match# ET # LLT,# = 6# E # LLE, # = 3# # okIf-then-elseIf-then-else语句语句BL

99、BL语言语言 i i j j | i =j=0 | i =j=0 不是不是LLLL文法文法条件语句的产生式是无法变换成条件语句的产生式是无法变换成LL1LL1型型产生式的。产生式的。自底向上分析自底向上分析LRLR分析概述分析概述自底向上分析的思想和主要问题自底向上分析的思想和主要问题几种几种LRLR分析方法：分析方法： LR(0) LR(0) SLR(1) SLR(1) LR(1) LR(1) LALR(1) LALR(1) 主要内容： LR的几个基本概念线性正则式的状态机LRSM短语：短语：设设S S是文法的开始符，是文法的开始符，是句型是句型( (即即有有S S * *），），如果满

100、足条件：如果满足条件：S S * * A A A A + + 则称则称是句型是句型的一个短语。的一个短语。直接短语（简单短语）：直接短语（简单短语）：如果满足条件：如果满足条件：S S * * A A A A 则称则称是句型是句型的一个简单短语。的一个简单短语。句柄：句柄：一个句型可能有多个简单短语，其中一个句型可能有多个简单短语，其中最左的简单短语称之为句柄。最左的简单短语称之为句柄。一个有用的定理一个有用的定理定义：定义：由某一结点及其所属分支组成的部分由某一结点及其所属分支组成的部分树称为原树的一颗子树。只有单层分支的子树称为原树的一颗子树。只有单层分支的子树称为简单子树。树称

101、为简单子树。定理：定理： 1. 1.每个句型都有一颗语法树，每个语法每个句型都有一颗语法树，每个语法树的叶组成一句型。树的叶组成一句型。 2. 2.每棵子树的叶组成短语，每颗简单子每棵子树的叶组成短语，每颗简单子树的叶组成简单短语，最左简单子树的叶组树的叶组成简单短语，最左简单子树的叶组成句柄。成句柄。l句型: (T+i)*i+F EE+TTT*FiF(E)E+TTiFFl短语： 1.(T+i)*i+F 2.(T+i)*i 3.(T+i) 4.T+i 5.T 6.第一个i 7.第二个i 8.Fl简单短语： T,第一个i,第二个i,Fl句柄：T规范句型：规范句型：用最右推导导出的句型用最右推导导

102、出的句型( (也称右句也称右句型）。型）。规范前缀：规范前缀：若存在规范句型若存在规范句型，且，且是终极符是终极符串或空串，则称串或空串，则称为规范前缀。为规范前缀。规范活前缀：规范活前缀：若规范前缀若规范前缀不含句柄或含一个不含句柄或含一个句柄并且具有形式句柄并且具有形式 = =( ( 是句柄是句柄) )，则称规范，则称规范前缀前缀为规范活前缀为规范活前缀( (简称活前缀）。简称活前缀）。归约规范活前缀：归约规范活前缀：若活前缀若活前缀是含句柄的活前是含句柄的活前缀，即有缀，即有 = =，且，且是句柄，则称活前缀是句柄，则称活前缀为为归约规范活前缀（简称归约活前缀）。归约

103、规范活前缀（简称归约活前缀）。例：例：S S aAcBe aAcBe 11 A A b b 22 A A Ab Ab 33 B B d d 44输入流：输入流：abbcdeabbcde。规范推导过程为：规范推导过程为：逆过程:(分析栈，输入流)( -, abbcde)(a,bbcde)(ab,bcde) (aA,bcde)(aAb,cde)(aA,cde)(aAc,de)(aAcd,e)(aAcB,e)(aAcBe,-)(S,-) S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1活前缀的描述性定义：活前缀的描述性定义：形成可归前缀之形成可归前缀之前，包括可归前缀在

104、内所有规范句型的前，包括可归前缀在内所有规范句型的前缀都称为活前缀。前缀都称为活前缀。活前缀活前缀为一个或若干规范句型的前缀。为一个或若干规范句型的前缀。在规范归约过程中的任何时刻已分析过在规范归约过程中的任何时刻已分析过的部分，即在分析栈（符号栈）中的符的部分，即在分析栈（符号栈）中的符号串均为号串均为规范句型的活前缀规范句型的活前缀，表明输入，表明输入串的已被分析过的部分是该文法某规范串的已被分析过的部分是该文法某规范句型的一个正确部分。句型的一个正确部分。线性正则式状态机线性正则式状态机LRSMLRSM线性正则式：线性正则式：不含不含* *符号的正则表达式符号的正则表达式LRSMLRSM

105、：( (Linear Regular States Machine)Linear Regular States Machine) (1) (1)从从LRSMLRSM可构造出恰好接受给定所有正可构造出恰好接受给定所有正则式的确定自动机则式的确定自动机DADA； (2) (2)从从LRSMLRSM的终止状态可判定接受的是哪的终止状态可判定接受的是哪个正则式；个正则式； (3) (3)从从LRSMLRSM的状态可判定一个正则式是不的状态可判定一个正则式是不是另一正则式的前缀。是另一正则式的前缀。项目：项目：假设假设 PP是一个正则式，则我们称形是一个正则式，则我们称形如如 PP的表示为项目，

106、其中的表示为项目，其中P P是正则式编号。是正则式编号。其中黑点可出现于任何位置上。其中黑点可出现于任何位置上。项目集：项目集：用用ISIS表示表示ISIS( (X)X) ： SubItems(IS,X)=SubItems(IS,X)= X XP|P|X X PP IS,XIS,X SymbSetSymbSet 简记为简记为ISIS(X)(X) 假设有线性正则项集:IS = abd1,abc2,bc3,de4, dec5, 则有：IS(a) = abd1, abc2 IS(b) = bc3 IS(c) = dec4 线性正则式到线性正则式到LRSMLRSM的构造的构造给定正则式集给定正则式

107、集 1 1, , 2 2, , n n ：构构造造初初始始项项目目集集ISIS0 0=1 11,.,1,.,n nnn，并并给给ISIS0 0标上标上NO(NO(表示未处理）。表示未处理）。从从已已构构造造的的LRSMLRSM部部分分图图选选择择被被标标为为NONO的的任任一一项项目目集集ISISi i，并做下面动作：并做下面动作： 1 1 对每个符号对每个符号X X SymbSetSymbSet：若若ISISi iX X非空，给非空，给ISISi iX X标上标上NONO，并在并在ISISi i和和ISISi iX X之间之间画有向画有向X X边边: :ISISi i ISISi iX

108、X。 2 2 给给ISISi i标上标上OKOK。重复上述步骤二，直至在重复上述步骤二，直至在LRSMLRSM中没有被标记为中没有被标记为NONO的的状态（项目集）结点为止。状态（项目集）结点为止。 abdcdbecdabc1abd2 ad3 bec4bed5S0abc1abd2 ad3 S1=S0aabc1abd2S3bec4bed5S2bec4bed5S5abc1S6abd2S7ad3S4bec4S8bed5S9正则式到LRSM的转换例LRSMLRSM的性质的性质展望符展望符：Lookup(S)Lookup(S)有效前缀集有效前缀集 Prefix(S)Prefix(S)状态状态SiSi

109、中的项目中的项目 PP表示表示部分已被部分已被输入，而且是输入，而且是SiSi的前缀的后缀，的前缀的后缀，表示待表示待输入部分。输入部分。可构造接受给定正则式集合的可构造接受给定正则式集合的DADA严格前缀：严格前缀：某状态中既含有定位点在尾处某状态中既含有定位点在尾处的项目又含有定位点不在尾处的项目，则的项目又含有定位点不在尾处的项目，则一个正则式是另一个正则式的严格前缀。一个正则式是另一个正则式的严格前缀。派生定理u 开始符产生式的右部是归约活前缀。开始符产生式的右部是归约活前缀。u 如果如果 A A 是归约活前缀，且是归约活前缀，且AA 是产生式，是产生式，则则也是归约活前缀。也是

110、归约活前缀。u 任何归约活前缀，都可按上述方式被派生。任何归约活前缀，都可按上述方式被派生。设文法开始符的产生式是设文法开始符的产生式是： S S 1 1| | 2 2| | | n n RPSRPSG G= 1 1, , , n n | | A ARPSRPSG G,A,AP P k 例有文法例有文法Gs: Gs: S aAcS aAc11 A AbbA Abb22 A bA b33 可归前缀集： aAc aAbb ab Y LR(0) LR(0)项目：项目：若若AA是产生式，是产生式，则称则称AA为为LR(0)LR(0)项目项目( (简称项目），也简称项目），也写作写作 pp形式。形

111、式。Y 项目集的投影：项目集的投影：假设假设ISIS是是LR(0)LR(0)项目集，则项目集，则称下面称下面ISIS(X)(X) 为为ISIS关于关于X X的投影集：的投影集： ISIS(X)(X) = A = A X X | A | AX X IS, IS, X X (V (VT T V VN N ) . ) .Y 项目集的闭包：项目集的闭包：假设假设ISIS是是LR(0)LR(0)项目集，则项目集，则称下面称下面CLOSURE(IS)CLOSURE(IS)为为ISIS的闭包集：的闭包集： CLOSURE(IS)= IS CLOSURE(IS)= IS A A | | YYA ACLOS

112、URE(IS)CLOSURE(IS) A A 是产生式是产生式两个重要的性质两个重要的性质Z 归约活前缀的性质：若归约活前缀的性质：若 A A 是归约活前是归约活前缀，缀，AA 是产生式，则是产生式，则也是归约活也是归约活前缀。前缀。 Z 活前缀状态机性质：若有活前缀状态机性质：若有 Prefix(ISPrefix(ISi i ) )，且且AAISISi i ，则则是归约活前缀。是归约活前缀。若有若有 Prefix(ISPrefix(ISi i ) )，YYA AISISi i ，则则根据性质根据性质2 2( (活前缀状态机的性质），活前缀状态机的性质）， A A 是归约活前缀。再

113、根据派生原理，若是归约活前缀。再根据派生原理，若 AA 是是A A的产生式，则的产生式，则也是归约活前缀。也是归约活前缀。构造构造LRSMLRSM的思想：的思想：如果在状态项目集如果在状态项目集ISISi i 中有项目中有项目AAB B ，且且BB 是是B B的产生式，则在的产生式，则在ISISi i 中增加项目中增加项目 B B；对于对于ISISi i 这个过程继续到不可再这个过程继续到不可再扩扩充为止。充为止。构造构造LR(0)活前缀状态机活前缀状态机LRSM的算法要点的算法要点： u构构造造初初始始状状态态ISIS0 0：ISIS0 0=CLOSURE(Z=CLOSURE(Z

114、S)S)，并并给给ISIS0 0标上标上NONO。u从从已已构构造造的的LRSMLRSM部部分分图图选选择择被被标标为为NONO的的任任一一状状态态ISIS，并做并做 1 1 对每个符号对每个符号X X V VT T V VN N，做下面动作：做下面动作： 1) 1) 令令ISISj j = CLOSURE( IS= CLOSURE( IS(X)(X) )，若非空。若非空。 2) 2) 若在若在LRSMLRSM部分图中已有部分图中已有ISISk k与与ISISj j有相同项目有相同项目集，则令集，则令m=km=k；否则构造否则构造ISISj j的状态点的状态点ISISj j，并给并给ISI

115、Sj j标上标上NONO，同时令同时令m=jm=j。 3) 3) 在在ISIS和和ISISm m之间画有向之间画有向X X边：边：IS IS ISISm m 。 2 2 给给ISIS标上标上OKOK。u重复上一步骤，直至没有被标记为重复上一步骤，直至没有被标记为NONO的状态结点为止。的状态结点为止。xk 例：构造例：构造LR(0)状态机状态机 S E E E + T E T T id T ( E )0 S E E E+T E T T id T ( E )1 SE EE +T 5 Tid 3 EE+ T T id T (E) 4 EE+T 9 ET 6 T( E) E E+T E T T id

116、 T ( E )7 T(E ) EE +T 8 T(E) TT(idETid)E+id(GE的LRSM+2 SE Z LRSM LRSM给出了所有的可归活前缀给出了所有的可归活前缀Z LRSM LRSM中的每个状态将对应一个饱和项目集：中的每个状态将对应一个饱和项目集：（1 1）其中一部分是由先驱状态分出来）其中一部分是由先驱状态分出来 ( (称为基本项目称为基本项目) )；（2 2）一部分则是由基本项目扩展出来的）一部分则是由基本项目扩展出来的 ( (称为扩展项目或派生项目称为扩展项目或派生项目) )。派生部。派生部分项目的特点是其中的分项目的特点是其中的“ ”出现在出现在产产生式右

117、部的最左侧。生式右部的最左侧。Y 形如形如A A PP的项目称为的项目称为归约型项目归约型项目Y 形如形如AA PP的项目称为的项目称为移入型项目移入型项目Y 移入归约冲突移入归约冲突Y 归约归约冲突归约归约冲突Y LRSMLRSM不能直接用于不能直接用于LRLR分析分析Y LRSMLRSM提供的信息：提供的信息：（1 1）合法性检查信息）合法性检查信息 AAa a （2 2）移入）移入/ /归约信息归约信息 AAa a ； AA （3 3）移入）移入/ /归约后的转向状态信息归约后的转向状态信息#X1X2 Xk XtSi0Si1Si2 Sik Sitaiai+1an#移入动作：设Sit的a

118、i输入边所指向的状态为S*#X1X2 Xk XtSi0Si1Si2 Sik SitaiS*归约动作：设按AXk+1Xk+2Xt进行归约，则首先归约为ASik的A输出边所指向的状态设为S*，则格局变为：#X1X2 XkSi0Si1Si2 SikAS*设当前格局是：#X1X2 XkSi0Si1Si2 SikAZ LRSMLRSM给出了所有的可归活前缀给出了所有的可归活前缀Z LRSM LRSM中的每个状态将对应一个饱和项目集：中的每个状态将对应一个饱和项目集：（1 1）其中一部分是由先驱状态分出来）其中一部分是由先驱状态分出来 ( (称为基本项目称为基本项目) )；（2 2）一部分则是由基本项

119、目扩展出来的）一部分则是由基本项目扩展出来的 ( (称为扩展项目或派生项目称为扩展项目或派生项目) )。派生部。派生部分项目的特点是其中的分项目的特点是其中的“ ”出现在出现在产产生式右部的最左侧。生式右部的最左侧。Y 形如形如A A PP的项目称为的项目称为归约型项目归约型项目Y 形如形如AA PP的项目称为移入型项目的项目称为移入型项目Y 移入归约冲突移入归约冲突Y 归约归约冲突归约归约冲突Y LRSMLRSM不能直接用于不能直接用于LRLR分析分析Y LRSMLRSM提供的信息：提供的信息：（1 1）合法性检查信息）合法性检查信息 AAa a （2 2）移入）移入/ /归约信息归约

120、信息 AAa a ； AA （3 3）移入）移入/ /归约后的转向状态信息归约后的转向状态信息# #X X1 1X X2 2 X Xk k X Xt tS Si0i0S Si1i1S Si2i2 S Sikik S Sititaiai+1an#移入动作：设Sit的ai输入边所指向的状态为S*# #X X1 1X X2 2 X Xk k X Xt tS Si0i0S Si1i1S Si2i2 S Sikik S Sitita ai iS S* *归约动作：设按AXk+1Xk+2Xt进行归约，则首先归约为ASik的A输出边所指向的状态设为S*，则格局变为：# #X X1 1X X2 2 X Xk

121、kS Si0i0S Si1i1S Si2i2 S SikikA AS S* *设当前格局是：# #X X1 1X X2 2 X Xk kS Si0i0S Si1i1S Si2i2 S SikikA ALRLR分析模型分析模型OutputStack#anaia1LR分析驱动器gotoactionInputS St tX Xt t LRLR分析表分析表ActionAction矩阵：行代表状态，列代表输入符，矩阵：行代表状态，列代表输入符，而矩阵元素则表示相应的分析动作：而矩阵元素则表示相应的分析动作： Shift / Reduce? / Accept / ErrorShift / Reduce?

122、/ Accept / Error GoToGoTo矩阵：行代表状态，而列则代表语法矩阵：行代表状态，而列则代表语法符号（非终极符，终极符），而矩阵元素符号（非终极符，终极符），而矩阵元素则表示归约后的转向状态。则表示归约后的转向状态。LR(0)投影函数投影函数 0 动作集动作集 : : Shift,Reduce1,Reduce2, . Shift,Reduce1,Reduce2, . 投影函数投影函数 0 0：StateSet2StateSet2 0 0(S)=Reduce j|B(S)=Reduce j|BS,S,且且BB 是产生是产生式式jj (if (if ( (存存在在XXa aS S

123、且且a a V VT T ) ) then Shift ) then Shift )LR(0)文法文法如果其如果其LRSMLRSM0 0的每个状态的每个状态S S都有都有| | 0 0( (S)|=1S)|=1，即即 0 0( (S)S)只包含一个元素，我们称文法只包含一个元素，我们称文法G G是是LR(0)LR(0)文法。文法。若若 0 0( (S)= Shift S)= Shift ，则表示则表示S S只含移入项只含移入项目目若若 0 0( (S)= Reduce j S)= Reduce j ，则表示则表示S S只含一只含一个个 jj归约项目。归约项目。 Z每个状态的移入每个状态的移

124、入/ /归约动作的确定没有冲归约动作的确定没有冲突，而且不依赖于输入符号。突，而且不依赖于输入符号。 Action表的构造表的构造Action( S)= Shift .Action( S)= Shift .当当 0 0 ( (S)=ShiftS)=ShiftAction( S)= Reduce j .Action( S)= Reduce j .当当 0 0 ( (S)=Reduce j S)=Reduce j （j j不是拓广产生式号）不是拓广产生式号）Action( S)= Accept .Action( S)= Accept .当当 0 0 ( (S)=Reduce jS)=Reduce

125、j （j j是拓广产生式号）是拓广产生式号）Action( S)= Error .Action( S)= Error .当当 0 0 ( (S)=S)= Action(Action( )= Error .)= Error . 是特别引进的是特别引进的错误状态标记错误状态标记 GOTO表的构造表的构造GoTo( S, X) = S GoTo( S, X) = S ，当当LRSMLRSM0 0中有中有S SS S GoTo( S, X) = GoTo( S, X) = ，否则否则 Xk LR(0)分析例分析例文法如下：文法如下：S E #E E+T | TT id | (E)# #+ +idi

126、d( () )E ET TS S0 0S S5 5S S6 6S S1 1S S9 9S S1 1S S2 2S S3 3S S2 2S S3 3S S5 5S S6 6S S4 4S S4 4S S5 5S S6 6S S5 5S S6 6S S7 7S S9 9S S7 7S S3 3S S8 8S S8 8S S9 9GoTo表ShiftShiftAcceptShiftReduce2Reduce4ShiftShiftReduce5Reduce3ActionLR(0)LR(0)驱动程序驱动程序u1 1：Push(S0) ；u2：Scan(a)；u3：S := TopOf( StateSta

127、ck)；u4：case Action( S ) of Error ErrorProcess； Accept Finish； Shift Push(GoTo(S,a) )；goto 2 Reduce j Pop(JJ)； Push(GoTo(S-JJ,Lj)；goto3 endLR(0)分析实例分析实例状态栈符号栈输入串 Action Goto0 id+id# shift 505 id +id# reduce4 909 T +id# reduce3 101 E +id# shift 3013 E+ id# shift 50135 E+id # reduce4 40134 E+T # redu

128、ce2 101 E # shift 2012 E# accept id+id# id+id#LR(0)分析方法的不足分析方法的不足ZLR(0)方法对文法的要求严格。方法对文法的要求严格。ZLR(0)方法容易出现冲突状态。方法容易出现冲突状态。一个文法例一个文法例: : G GE E: SE # 1: SE # 1EE + T 2EE + T 2ET 3ET 3TT TT P 4 P 4 TP 5TP 5Pid 6Pid 6 P( E ) 7P( E ) 7 图4.5.5.3 GE 的LRSM0 +EPid#+Pid(TTid( idE(P ) 4 E T T T P 7 P id 5 E E

129、+ T T T P T P P id P (E) 3 T P 4 S E # E E + T 1 S E # 1 E E+T 2 E T 3 T TP 4 T P 5 P id 6 P (E) 7 0 T T P P id P (E) 8 T T * P 9 E E+T T T P 11 P (E ) E E +T 12 P(E) 10P(T P ( E ) E E+T E T T TP T P P id P (E) 6 7 8 S E# 2如果某个状态有如下项目集：如果某个状态有如下项目集： A , B , D d ，则存在则存在着归约着归约- -归约，归约归约，归约- -移入冲突移入冲突

130、若用若用A 归约，则当前输入符应在归约，则当前输入符应在A的的Follow集中集中若用若用B 归约，则当前输入符应在归约，则当前输入符应在B 的的Follow集集若移入，则当前输入符应为若移入，则当前输入符应为d。SLR(1)分析条件分析条件LRSM0中存在着状态中存在着状态 A1 1 ，An n ， B1 1 a1r1，Bn n anrn Follow(A1) Follow(An) a1,an= SLR(1)SLR(1)文法的定义文法的定义SLR(1)文法的投影函数文法的投影函数 1 1定义如下：定义如下： 1 1：StateSet (VT #) 2 1 (S,a) = Reduce j

131、 |BS,a Follow(B),B P (if存存在在 XaS且且 a VT then Shift) Z如果如果LRSM0中的每个状态中的每个状态S，对任意对任意 a VT，使得使得| | 1 1( (S,a)| 1，则称相应文法为则称相应文法为SLR(1)文文法。法。 SLR(1)_Action表的构造表的构造若若 1 1(S,#)=Shift Action( S, # )=Accept若若 1 1(S,a)=Shift 且且a # Action( S, a) =Shift若若 1 1(S,a)=Reduce j Action( S, a) =Reduce j若若 1 1(S,a)= A

132、ction( S, a) = ErrorSLR(1)_GoToSLR(1)_GoTo表的构造表的构造GoTo( S, X) = S ，当当LRSM0中有中有S S GoTo( S, X) = error，否则否则合并的合并的SLR(1)分析表，合并方法分析表，合并方法: : Action ( S, a) = Shift i , 当当 Action (S, a)= Shift且且GoTo(S,a)=Si GoTo ( S, X) = Si , 当当GoTo(S,X)=Si 且且X VNX 图4.5.5.3 GE 的LRSM0 +EPid#+Pid(TTid( idE(P ) 4 E T T

133、T P 7 P id 5 E E + T T T P T P P id P (E) 3 T P 4 S E # E E + T 1 S E # 1 E E+T 2 E T 3 T TP 4 T P 5 P id 6 P (E) 7 0 T T P P id P (E) 8 T T * P 9 E E+T T T P 11 P (E ) E E +T 12 P(E) 10P(T P ( E ) E E+T E T T TP T P P id P (E) 6 7 8 S E# 2+ id()#0SS1SA23SS4R5R5R5R55R6R6R6R66SS7R3SR3R38SS9R4R4R4R410

134、R7R7R7R711R2SR7R712SSStateActionLookahead id()#ETP0S5S61741S3A23S5S61144R5R5R5R55R6R6R6R66S5S612747R3SR3R38S5S699R4R4R4R410R7R7R7R711R2S8R2R212S3S10StateActionLookaheadGoToSLR(1)驱动器驱动器11：Push(S0，-) ；2：Scan(a)；3：S := TopOf( StateStack)；4：case Action( S,a ) of Error ErrorProcess； Accept Finish； Shift

135、i begin Push(Si,a)；goto2 end ; Reduce jbegin Pop(JJ)； Push( GoTo(S- JJ, Lj),Lj); goto 3 end end分析栈符号栈输入串分析动作转向状态0idid+id# S50,5 id id+id# R6 40,4 P id+id# R5 70,7 T id+id# S80,7,8 T id+id# S50,7,8,5 Tid +id# R6 90,7,8,9 TP +id# R4 70,7 T +id# R3 10,1 E +id# S30,1,3 E+ id# S50,1,3,5 E+id # R6 40,1,3,

136、4 E+P # R5 110,1,3,11 E+T # R2 10,1 E # AcceptSLR(1)与与LR(0)ZSLR(1)和和LR(0)具有相同的状态机具有相同的状态机ZLR(0)只看分析栈的内容，不考虑当前输入符只看分析栈的内容，不考虑当前输入符 SLR(1)考虑输入符，用考虑输入符，用follow集来解决冲突，集来解决冲突，因此因此SLR(1)要比要比LR(0)分析能力强分析能力强 Z E E (L,E) E S L L,E L E S id S (S)Z EE(L,E)ESSidS (S)0E(L,E)S(S)LL,ELEE(L,E)ESSidS(S)1ESS(S)2(S1(S

137、2, ) ) = Shift, Reduce3ZLR(0)LR(0)方法不依赖输入流，直接判定归约，容方法不依赖输入流，直接判定归约，容易出现冲突。易出现冲突。ZSLR(1)SLR(1)方法简单的把非终极符的方法简单的把非终极符的followfollow集做集做为可归约的依据，并不精确。为可归约的依据，并不精确。Z一个非终极符在不同的位置上出现，它所允一个非终极符在不同的位置上出现，它所允许的后继符是不同的。许的后继符是不同的。LR(1)LR(1)针对不同产生式针对不同产生式上的非终极符，分别定义其后继符集（展望上的非终极符，分别定义其后继符集（展望符集符集ReducelookupReduce

138、lookup），），减少了移入减少了移入/ /归约冲突。归约冲突。LR(1)LR(1)分析方法分析方法LR(1)LR(1)方法研究的对象是二元组：方法研究的对象是二元组：( ( , , b)b)，其中其中是活前缀，而是活前缀，而b b是一个输入符号。我是一个输入符号。我们称上述们称上述( ( , , b)b)为为LRLR1 1前缀模式前缀模式。如果如果是文法的归约活前缀，是文法的归约活前缀，b b是是的合法后的合法后继续符，则称继续符，则称( ( , , b)b)为为LRLR1 1归约前缀模式。归约前缀模式。LRLR1 1归约前缀的派生定理归约前缀的派生定理假设假设 0 0是拓广产生式的

139、右部，是拓广产生式的右部，# #是输入流是输入流的结束符，则有：的结束符，则有： ( ( 0 0 p, # )p, # )是是LRLR1 1归约前缀模式。归约前缀模式。设设( ( A A p, b )p, b )是是LRLR1 1归约前缀模式，归约前缀模式，且且AA 是是q q产生式，则产生式，则( ( q , a)q , a)也也是是LRLR1 1归约前缀模式，其中归约前缀模式，其中a a First(First( b)b)。 LR(1)LR(1)项目：项目： AA, a , a 。LR(0)LR(0)项目及一个项目及一个V VT T #的展望符集合的展望符集合IS:IS:LR(1)LR(

140、1)项目集项目集ISIS(X)(X): : IS IS(X)(X) = A = A X X,a ,a |A|AX X ,a,a IS IS CLOSURE ( IS )CLOSURE ( IS ) = IS = IS BB,b ,b |A|AB B ,a,a CLOSURE(IS), CLOSURE(IS), BB 是是产产生生式式 , , b b First(First( a)a) LRSMLRSM1 1的构造算法的构造算法1.1.初始项目集：初始项目集： ISS=CLOSURE( Z ISS=CLOSURE( Z S, # )S, # )2.2.若所有状态都处理完，则结束若所有状态都处理完

141、，则结束3.3.选一未处理完状态选一未处理完状态ISIS，对所有语法符号对所有语法符号 X X （V VT T V VN N #),#),求求ISISX X, ,令令 IS IS = CLOSURE(IS= CLOSURE(ISX X) )，若若ISIS不为空：不为空：若若ISIS为新状态，则增加为新状态，则增加IS ISIS IS, ,把把ISIS加加入入LRSMLRSM1 1中；否则为图中某个状态中；否则为图中某个状态ISISj j，则在则在ISIS 和和ISISj j之间增加一条转换边：之间增加一条转换边：IS ISIS ISj j4.4.转到步骤转到步骤2 2XX 非非SLR(1)

142、SLR(1)文法：文法： Z SZ S S L= R S L= R S R S R L aR L aR L b L b R L R L 0ZSSL=RSRLaRLbRL#= #= #1ZS #2SL =RRL #6SL= RR LLaRLb#7SL=R #3SR #4Lb =#10LaR #=5La RRLLaRLb# =# =# =# =11RL # =8La RRLLaRLb#9RL #12Lb #13RaR #SLabRb=RLRLabaaLRbLR(1)LR(1)文法文法投影函数投影函数 2 2 : : 2 2：StateSet ( ( VT#) 2 2 2( (S,a)= Reduc

143、ej |B, a S, B 是产生式是产生式j ( if Aa , b S then Shift ) Z如果如果LR(1)状态机的任一状态状态机的任一状态S和输入符和输入符a，都使得都使得| | 2(S,a)|1，则称文法为则称文法为LR (1)文法文法 . .LRLR(1) 分析表的构造分析表的构造Action 表的构造：表的构造： Action(S, a) = Error 若若 2 2( (S, a) = Action(S, #) = Accept 若若 2 2( (S,#)=Reduce 1 Action(S,a) = Reduce j 若若 2 2( (S,a)= Reduce j

144、Action(S, a) = Shift i 若若 2 2( (S,a)= Shift and GoTo(S,a)=SiGoTo表的构造：表的构造： GoTo(S, X) = Si 若若S与与Si状态有状态有X转向边，转向边， X为非终极符。为非终极符。R413R512R6R611R4R410R69139S12S88R2779S12S861011S4S55R5R54R33R6S62A1321S4S50RLS#=baLR(1)驱动程序驱动程序LR(1)的驱动程序与的驱动程序与SLR(1)的驱动程序是相的驱动程序是相同的，可共用一个。同的，可共用一个。状态栈符号栈输入串 Action GoTo

145、0 aab=b# S5 0,5 a ab=b# S50,5,5 aa b=b# S4 0,5,5,4 aab =b# R5 110,5,5,11 aaL =b# R6 100,5,5,10 aaR =b# R4 110,5,11 aL =b# R6 10 0,5,10 aR =b# R4 20,2 L =b# S60,6 L= b# S120,6,12 L=b # R5 9 0,6,9 L=L # R6 70,6,7 L=R # R2 10,1 S # ALALR(1)LALR(1)方法方法它具有它具有SLR(1)SLR(1)的状态数少的优点和的状态数少的优点和LR(1)LR(1)的适用范围广

146、的优点。的适用范围广的优点。 LALR(1)LALR(1)方法的功能介于方法的功能介于SLR(1)SLR(1)和和LR(1)LR(1)之之间。间。LALR(1)LALR(1)状态机的状态个数和状态机的状态个数和LR(0)LR(0)状态机状态机的状态个数相同，而其展望符则即不采用的状态个数相同，而其展望符则即不采用SLR(1)SLR(1)的的FollowFollow集方法，也不采用集方法，也不采用LR(1)LR(1)的完全精确法。的完全精确法。 LALR(1)LALR(1)的思想来源的思想来源LR(1)LR(1)状态机和状态机和LR(0)LR(0)状态机从它们所表状态机从它们所表示的自动机角度来

147、看是等价的；示的自动机角度来看是等价的；自动机可通过合并等价状态来减少状态自动机可通过合并等价状态来减少状态个数。个数。在在LR(1)LR(1)状态机出现很多同心状态，而状态机出现很多同心状态，而LALR(1)LALR(1)状态机则不产生同心的状态，状态机则不产生同心的状态，从而大大减少状态数，这就是从而大大减少状态数，这就是LALR(1)LALR(1)和和LR(1)LR(1)的主要差别。的主要差别。 LALR(1)LALR(1)状态机的定义方式：状态机的定义方式：用用LR(1)LR(1)状态机来定义；状态机来定义；用用LR(0)LR(0)状态机来定义。状态机来定义。LALR(1)LALR

148、(1)状态机的构造方法：状态机的构造方法：先构造先构造LR(1)LR(1)状态机，后构造状态机，后构造LALR(1)LALR(1)状态机状态机按按LR(1)LR(1)状态机的方式构造，但发现同心状态状态机的方式构造，但发现同心状态时不产生新状态，而是采用合并状态的方法。时不产生新状态，而是采用合并状态的方法。先构造先构造LR(0)LR(0)状态机，而后用传播方式求出每状态机，而后用传播方式求出每个项目的展望符集。个项目的展望符集。相关的术语相关的术语假设假设 AA, b, b是是LR(1)LR(1)项目，则称其项目，则称其中中的的LR(0)LR(0)项目部分项目部分AA为该为该项目的心

149、。项目的心。如果如果LR(1)LR(1)状态机中的两个状态具有相同的状态机中的两个状态具有相同的心，则称它们为心，则称它们为同心状态。同心状态。b 例例假设在假设在LR(1)状态机中有状态状态机中有状态S1和和S2： S1 = A, a1 ，B, b1 , S2 = A, a2 ，B, b2 Core(S1)= A, B , Core(S2)= A, B ，SameCoreState( S1 )= S 1, S2 Merge(S1, S2) = A, a1, a2 ， B, b1 ,b2 由由LR(1)SMLR(1)SM构造构造LALR(1)SMLALR(1)SM的算法的算法u初始化：初始

150、化： OldSS:=LR(1) OldSS:=LR(1)状态机的状态集；状态机的状态集；NewSSS:=NewSSS:=； u构造构造LALR(1)LALR(1)的状态集：的状态集： while OldSS while OldSS do do begin S :=OneStateOf(OldSS) begin S :=OneStateOf(OldSS)； NewSSS:=NewSSSSameCoreState(S) NewSSS:=NewSSSSameCoreState(S)； OldSS :=OldSS- SameCoreState(S) OldSS :=OldSS- SameCoreSta

151、te(S)； end endu确定确定LALRLALR状态给的转向边：状态给的转向边：对于对于SSSS1 1,SS,SS2 2 NewSSSNewSSS，画画Merge(SSMerge(SS1 1) ) Merge(SSMerge(SS2 2) ) 当且仅当存在当且仅当存在S S1 1 SSSS1 1和和S S2 2 SSSS2 2，使得使得S S1 1 S S2 2 (LR(1)(LR(1)状态机状态机) )XXLALR(1)LALR(1)的投影函数的定义的投影函数的定义 3 3 ：StateSet0 (VT# ) 2 3 3( (S,a) Reduce j | B, a Cognate(

152、S) B 是产生式是产生式j if 存在存在 Aa , ? S then Shift S是由是由LR(0)项目组成的项目组成的LALR状态状态 ; ; Cognate(S)则表示在则表示在LR(1)状态机中以状态机中以S为心的所为心的所有状态的有状态的LR(1)项目之集。项目之集。当且仅当对任一当且仅当对任一LALR状态状态S和和a (VT# # )都都有有| | 3 3 ( (S,a)| 1，称文法称文法G是是LALR(1)文法文法。 LALR(1)LALR(1)分析表的构造分析表的构造Action表的构造：表的构造：Action(S, a)=Shift i，若若 3 3 ( (S,a)

153、=Shift 且且 a #，GoTo(S,a)=SiAction(S, a)=Reduce j ，若若 3 3 ( (S,a)=Reduce jAction(S, #)=Accept ，若若 3 3 ( (S,)=Reduce1 Action(S, a)=Error ，若若 3 3 ( (S,a)=GoTo表的构造：表的构造： GoTo(S,a)=Si, 若存在若存在S* States_Contain(S) Si* States_Contain(Si)，使得在使得在LR(1)状态机状态机中有中有S*到到Si*的的a输出边。输出边。LALR(1)驱动程序驱动程序LALR(1)的驱动程序与的驱动

154、程序与SLR(1)、LR(1)的驱动的驱动程序是相同的，可共用一个。程序是相同的，可共用一个。LALR(1)分析实例文法文法Gz: Z BB BB B B aB aB B B b b试通过构造试通过构造LR(1)LR(1)状态机，然后合并同心状状态机，然后合并同心状态的方法构造态的方法构造LALR(1)LALR(1)状态机，并写出状态机，并写出LALR(1)LALR(1)分析表分析表#ababZBBBaBBb0#ZBBBaBBb1#BaB5abababBaBBaBBb4#Bb6a bBb3#BaBBaBBb7BbaaaB#ZBB2abBaB8baBBbb(3,6)(4,7)(5,8)LR（1）

155、SM#ababZBBBaBBb0#ZBBBaBBb1ab#BaB5ab#ab#ab#BaBBaBBb4a b #Bb3BbaaB#ZBB2bbBLALR（1）SMLALR(1)分析表ab#B0S4S311S4S322A3R3R3R34S4S355R2R2R2状态栈符号栈输入串 Action GoTo0 abaab# S4 0,4 a baab# S30,4,3 ab aab# R3 50,4,5 aB aab# R2 10,1 B aab# S4 0,1,4 Ba ab# S4 0,1,4,4 Baa b# S3 0,1,4,4,3 Baab # R3 50,1,4,4,5 BaaB #

156、R2 50,1,4,5 BaB # R2 20,1,2 BB # A 0型项目：黑点在最前的项目；它们是别的项目派生出来的(增广项目例外）。例如AaBc。 Afirst ：AFirst(AX)= First() *型项目：若AFirst(I)包含，则称(S, I)为* 型项目，表示其展望符可传播。 LALR(1)SM的传播构造方法展望符的产生展望符的产生如果项目如果项目( (S, I)是由项目是由项目( (Si, Ij),i=,j=产生，则称产生，则称这些项目这些项目( (Si, Ij)为为发射发射( (S, I)的项目的项目。令。令(S,I)的展望符的展望符集为集为L。若若(S,I

157、)=A X 为非为非0 0型项目：发射型项目：发射( (S,I) 的项的项目目 ( (Si,Ij)具有形式具有形式A X ，令展望符集为令展望符集为Lij，则则有有等式等式： L= Lij 若若( (S,I)=A 为为0 0型项目：发射型项目：发射( (S,I)的项目具有的项目具有形形式式D iA i，令展望符集为令展望符集为Li，则有等式：则有等式： L = Li* Li*= if First( i) then First( i)- Li else First( i)传播部分自生部分展望符传播算法：u构造LR(0)状态机时，对于每个项目(Si,Ij)构造其传播表。u展望符初始化：令增广项

158、目ZS的展望符集为#，令其它项目的展望符集为。u计算自生展望符：顺次扫描下一项目(S , I ) ；若(S,I)形如Aa(aVT)，不做处理，否做下面工作：计算AFirst(S , I )并加到(S , I )所发射到的所有0型项目的展望符集上；若 AFirst(S , I )，则给(S , I )加可传播标记 * ；重复上述过程，直至全扫描完为止。（转下）(接上)u传播展望符：若不产生新的传播项则结束，否则继续进行选择一个未处理过的项目(S, I, L) ；将L追加到(S,I)所发射的非0型项目的展望符集上；若(S,I)是*型项目，则把L追加到(S, I) 发射的

159、所有0型项目的展望符集上；重复上述传播过程。#ZBBBaBBb ZBBBaBBb B aBBaB Bb BbZBBBaBBBbbabaaBAFirst(0,1)= a,b012345AFirst(2,1)=#a,b*AFirst(3,1)=#ab#ab#ab#ab#ab#带传播的LR(0)状态机425310 ZB B ZB B Z BB B aB B aB B b B b Ba B Ba B B aB Bb B bLRSM0L1=a,bL2=#L3=#,a,bAfirst(2,1)=Afirst(0,1)=a,bLRLR分析方法的比较分析方法的比较状态数：状态数： LR(0)=SLR(1)

160、=LALR(1)LR(1) LR(0)=SLR(1)=LALR(1)LR(1)展望符的确定：展望符的确定： LR(0)LR(0)无展望符；无展望符；SLR(1)SLR(1)利用利用FollowFollow集解集解决冲突决冲突;LR(1);LR(1)针对不同位置确定展望符，针对不同位置确定展望符， LALR(1) LALR(1)利用合并利用合并/ /传播方法计算展望符。传播方法计算展望符。分析能力：分析能力： LR(0) SLR(1) LALR(1) LR(1) LR(0) SLR(1) LALR(1) LR(1)应用：应用： LALR(1)LALR(1)较通用，较通用，LR(1)LR(1)属

161、于理论方法。属于理论方法。第五章第五章语义分析语义分析n语义分析基础语义分析基础p意义、任务、时间、方法意义、任务、时间、方法p标识符、类型、值的内部表示标识符、类型、值的内部表示n符号表符号表n类型表达式类型表达式n声明的语义分析声明的语义分析n执行体的语义分析执行体的语义分析语义分析概述语义分析概述n意义意义p词法分析检查程序词法分析检查程序拼写拼写上的错误上的错误 begin: begn 123x p语法分析检查程序语法分析检查程序结构结构上的错误上的错误 x = x +y; y = z; p语义分析检查程序语义分析检查程序含义含义上的错误上的错误 int x; x(a,b);语义分析

162、概述语义分析概述n任务任务p进行语义检查和构造标识符的符号表进行语义检查和构造标识符的符号表p语义检查包括语义检查包括类型检查类型检查和和一般的语义检查一般的语义检查p类型检查类型检查：运算分量的类型是否相容、赋值语句：运算分量的类型是否相容、赋值语句左右部的类型是否相容、形参和实参的类型是否左右部的类型是否相容、形参和实参的类型是否相容、函数说明中函数类型和返回值的类型是否相容、函数说明中函数类型和返回值的类型是否相容等；相容等；p一般的语义检查一般的语义检查：VE、V.id、V、y+f(a,b)、使、使用性用性标识符有否声明、定符有否声明、定义性性标识符有否重复声符有否重复声明、明、标号有

163、否重复声明和重复定位号有否重复声明和重复定位错误等；等；语义分析概述语义分析概述n时间时间p语义分为静态语义和动态语义语义分为静态语义和动态语义p类型是重要的静态语义，静态语义问题主要是类类型是重要的静态语义，静态语义问题主要是类型相容问题型相容问题p语义分析可在语法分析或中间代码生成阶段进行语义分析可在语法分析或中间代码生成阶段进行语义分析语义分析($id，idname)($id，Entry)语义分析概述语义分析概述n方法方法* *p语义分析包括对分析的描述和对分析算法的实现语义分析包括对分析的描述和对分析算法的实现p常使用的描述语义分析的方法是常使用的描述语义分析的方法是属性文法属性文法p

164、语义分析依赖语法分析，因此语义分析器分为自语义分析依赖语法分析，因此语义分析器分为自顶向下和自底向上两种顶向下和自底向上两种p本章采用递归下降法描述语义分析过程本章采用递归下降法描述语义分析过程标识符、类型、值的内部表示标识符、类型、值的内部表示n标识符的内部表示标识符的内部表示p标识符的种类：标识符的种类：常量标识符、类型标识符、变量标识符、函数标识常量标识符、类型标识符、变量标识符、函数标识符、过程标识符、记录域标识符符、过程标识符、记录域标识符pTYPE idkind=( consKind, typeKind, varKind, fieldKind, procKind,funcKind

165、)p内部表示：内部表示：常量常量类型类型变量变量域名域名*过过/函函CodeCodeValueValueKindKindTypePtrTypePtrForwardForwardKindKindTypePtrTypePtrOffOffLevelLevelAccessAccessKindKindTypePtrTypePtrHostTypeHostTypeOffOffKindKindTypePtrTypePtrSizeSize ForwardForwardClassClassParmParmLevelLevelKindKindTypePtrTypePtrOffOffb 例有声明如下：例有声明如下：

166、CONST pai= 3.14 ;CONST pai= 3.14 ; TYPE vector=ARRAY1.10 OF TYPE vector=ARRAY1.10 OF integer;integer; VAR x, y : real ; VAR x, y : real ; r, s : vector ; r, s : vector ; 设当前层数和可用设当前层数和可用offsetoffset值分别为值分别为L L和和0 0，构造标识符构造标识符 pai, vector, x, y, r pai, vector, x, y, r 和和s s 的属性表示的属性表示, ,假设整数类型占假设整数类型

167、占1 1个单元，实个单元，实数类型占数类型占2 2个单元。个单元。类型的内部表示类型的内部表示n 类型的种类：类型的种类：标准、子界、枚举、数组、记录、标准、子界、枚举、数组、记录、集合、文件、指针类型等等。集合、文件、指针类型等等。 TypeKind=(intTy,boolTy,charTy,realTy,enumTy, subTy,arrayTy,recordTy,setTy,fileTy,pointerTy)n 内部表示：内部表示：( (TypeIR)TypeIR) 标准类型：标准类型： sub: enum: array: UpLowHostTypeKindSizeLengElemsK

168、indSizeElemTypeIndexTypeKindSizeKindSizerecord: FixBody: VariBody:set: file:pointer: VariBodyFixBodyKindSizeNextOffFixUnitTypeidVariUnitsCaseUnitNextVariBodyFixBodyOffCaseTypeidBaseTypeKindSizeCompTypeKindSizeTypeNameKindSizeb例有如下的类型定义：例有如下的类型定义： at = ARRAY 1.10 OF at = ARRAY 1.10 OF ARRAY1.100 OF i

169、nteger; ARRAY1.100 OF integer; rt = RECORD x : real ; a : at; rt = RECORD x : real ; a : at; CASE u: boolean OF CASE u: boolean OF false:(k : integer); false:(k : integer); true:(y: real; b: boolean) true:(y: real; b: boolean) END END 构造类型的内部表示。构造类型的内部表示。值的内部表示值的内部表示n结构类型没有值结构类型没有值 n非结构类型值的内部表示：非结构

170、类型值的内部表示：p 实数和整数有直接对应的机器表示实数和整数有直接对应的机器表示p 有序类型均可表示为整数形式有序类型均可表示为整数形式整型常量：整型常量：ord(N) = Nord(N) = N布尔常量：布尔常量：ord(false)=0, ord(true) = 1ord(false)=0, ord(true) = 1字符常量：字符常量：ord(C) = ASC(C)ord(C) = ASC(C)枚举常量：枚举常量：设有枚举类型设有枚举类型( (D,A,B),D,A,B),则有则有 ord(D)=0,ord(A)=1,ord(B)=2ord(D)=0,ord(A)=1,ord(B)=2子

171、界常量：子界常量：设有子界类型设有子界类型C C1 1.C.C2 2, ,则值空间则值空间为为 ord(Cord(C1 1).ord(C).ord(C2 2) 符号表符号表n符号表的作用符号表的作用：为语义检查和代码生成为语义检查和代码生成提供标识符的语义信息提供标识符的语义信息n符号表的框架符号表的框架： (id，Attribute(id)p线性表结构线性表结构(顺序查表法顺序查表法)；p二叉树结构二叉树结构(二分查表法二分查表法)；pHash表表(散列查表法散列查表法)；n有关符号表的操作：有关符号表的操作：添加、查询、局部化处理添加、查询、局部化处理标识符的特点标识符的特点n标识符的

172、出现：标识符的出现：定义性出现和使用性出现定义性出现和使用性出现n标识符的作用域标识符的作用域：标识符在程序中起作用的范围。：标识符在程序中起作用的范围。n嵌套作用域规则嵌套作用域规则：当存在标识符的嵌套声明时，最近定义：当存在标识符的嵌套声明时，最近定义的属性为标识符的当前属性的属性为标识符的当前属性n局部化单位：局部化单位：允许有声明的程序段允许有声明的程序段P:P:Var x ,y,zVar x ,y,zVar x,m,nVar x,m,nx:=1;x:=1;m:=x+y;m:=x+y;y:=x+1;y:=x+1;x:=0;x:=0;Q Q: :int x,y; float x,y;

173、x = x*y; x = x *y;符号表局部化处理的基本思想符号表局部化处理的基本思想n每当进入局部化区时，记住本层符号表的始地址。每当进入局部化区时，记住本层符号表的始地址。n每当遇到定义性标识符时，构造其语义信息并查每当遇到定义性标识符时，构造其语义信息并查本层本层符号表，若查到同名标识符，则表示有错，符号表，若查到同名标识符，则表示有错，否则往符号表里填写标识符和语义信息。否则往符号表里填写标识符和语义信息。n每当遇到使用性标识符时，查整个符号表每当遇到使用性标识符时，查整个符号表( (从后往从后往前前) )，若查不到同名标识符，则表示有错，否则找，若查不到同名标识符，则表示有错，否则

174、找出相应语义信息并将它传给有关部分。出相应语义信息并将它传给有关部分。n每当结束一个局部化区时，每当结束一个局部化区时，“删除删除”本层符号表本层符号表符号表局部化处理的实现符号表局部化处理的实现n真删除法真删除法：当退出一个局部化单位时，删除掉相应的符号：当退出一个局部化单位时，删除掉相应的符号表部分表部分( (即当前层的符号表即当前层的符号表) )； s := Scopes := Scope -1 -1 := := -1; -1; n驻留法驻留法：保留表项，采取措施不去查那些已经无效的符号：保留表项，采取措施不去查那些已经无效的符号表项。表项。p加标记法加标记法：每个表项增加一个标记域，当

175、某个表项无效：每个表项增加一个标记域，当某个表项无效时，就将该标记域设为无效；时，就将该标记域设为无效；p跳转法跳转法: : 每当退出一个局部化区时，将一个跳转项添入每当退出一个局部化区时，将一个跳转项添入到符号表中：到符号表中：s := s +1; s := s +1; SymbTabs:=(#,Scope( SymbTabs:=(#,Scope()-1);)-1);简单简单C语言的符号表语言的符号表n简单简单C C语言语言( (不考虑分程序不考虑分程序) )的特点：的特点：程序由一些并列的函数构成，每个函数的层程序由一些并列的函数构成，每个函数的层数是相同的，每个函数可以有自己的局部变量

176、数是相同的，每个函数可以有自己的局部变量nC C语言的符号表结构：局部符号表语言的符号表结构：局部符号表void add(int *e, int *f, int ii) int i; void reduce(int * x, int *y) int g; main() float i; int j; add (); reduce()Pascal语言的符号表语言的符号表nPascalPascal语言的特点：允许嵌套的过程声明语言的特点：允许嵌套的过程声明nPascalPascal语言的符号表：全局符号表语言的符号表：全局符号表( (顺序表顺序表和散列表和散列表) )proc P() var i,

177、 j,k: integer; t1 proc Q() var a, b:real; proc R()t2 var a, b: boolean; t3 begin R的过程体的过程体 end begin Q的过程体的过程体 end proc S() var c, e:char; t4 begin S的过程体的过程体 end t5 begin P的过程体的过程体 end 带分程序结构的符号表带分程序结构的符号表n分程序也是一个局部化区，而且可以嵌套分程序也是一个局部化区，而且可以嵌套n处理思想：与处理思想：与PascalPascal语言嵌套式符号表的处理思语言嵌套式符号表的处理思想相似。想相似。m

178、ain() int a; float b, d; int c; float a; int d; float c; float d; a = b + c + d; 语义分析例子语义分析例子program p()program p()type at=array1.100 of array1.10 of integertype at=array1.100 of array1.10 of integervar x:real; a:at; i:integer;var x:real; a:at; i:integer;proc p1(var a1:atproc p1(var a1:at； a2:at)a2:

179、at)var x:integer; a:real;var x:integer; a:real;proc p2(n:integer)proc p2(n:integer)var m:1.50; x:real;var m:1.50; x:real;m,n,x(m,n,x(使用性出现使用性出现) )endenda1,a2,x,a,ia1,a2,x,a,i（使用性出现）（使用性出现）endendx,a,ix,a,i（使用性出现）（使用性出现）endend类型分析类型分析n 类型的等价性和相容性：类型的等价性和相容性：p类型的等价性：类型的等价性：按名等价：按名等价：type tp=array1.10o

180、f integer;type tp=array1.10of integer; var a,b:tp; var a,b:tp; 则称则称a,ba,b是相同类型的变量是相同类型的变量结构等价：结构等价：type tp1=array1.10of integertype tp1=array1.10of integer type tp2=array1.10of integer;type tp2=array1.10of integer; var a:tp1; b:tp2;var a:tp1; b:tp2; 则称则称a,ba,b是相同类型的变量是相同类型的变量类型分析类型分析n 类型的等价性和相容性：类

181、型的等价性和相容性：p类型的相容性：类型的相容性：运算分量类型的相容性；运算分量类型的相容性；赋值语句左右类型的相容性；赋值语句左右类型的相容性；形参和实参类型的相容性；形参和实参类型的相容性；p类型相容的判定：类型相容的判定：类型等价则相容类型等价则相容整型或整型子界类型与整型、实型相容整型或整型子界类型与整型、实型相容两个子界类型定义的范围相包含则相容两个子界类型定义的范围相包含则相容对结构类型，如果同一结构，且子类型相容则相容对结构类型，如果同一结构，且子类型相容则相容类型分析类型分析n作用：把类型表示转换成类型的内部表示作用：把类型表示转换成类型的内部表示n分析过程：读

182、分析过程：读TokenToken序列，识别出各种类型，序列，识别出各种类型，返回类型内部表示的地址返回类型内部表示的地址array 1.10of integerarrKindlow=1 tp1=intPtrup=10 tp2=intPtr IndexPtr= (1,subTy, intPtr , 1 ,10)ElemPtr=intPtr size=(up-low+1) * sizeof (int)aPtr:=(size,arrTy,IndexPtr,ElemPtr)类型分析类型分析n 类型的等价性和相容性：类型的等价性和相容性：p类型的相容性：类型的相容性：运算分量类型的相容性；运算分量类型

183、的相容性；赋值语句左右类型的相容性；赋值语句左右类型的相容性；形参和实参类型的相容性；形参和实参类型的相容性；p类型相容的判定：类型相容的判定：类型等价则相容类型等价则相容整型或整型子界类型与整型、实型相容整型或整型子界类型与整型、实型相容两个子界类型定义的范围相包含则相容两个子界类型定义的范围相包含则相容对结构类型，如果同一结构，且子类型相容则相容对结构类型，如果同一结构，且子类型相容则相容类型分析类型分析n 类型出现的位置类型出现的位置- 类型定义类型定义 TYPE id = t; TYPE id = t; -变量声明变量声明 VAR id : t;VAR id : t;-过

184、过/ /函声明函声明 Proce/Func P(AProce/Func P(A1 1:t:t1 1, ,)(:t)(:t)n 类型的种类类型的种类-name,subrange,enum,array,record,set,name,subrange,enum,array,record,set, file,pointer file,pointern 类型分析类型分析-返回类型的内部表示地址返回类型的内部表示地址PtrPtr和和ForwardForwardNameType形式：形式：id (id (类型标识符类型标识符) )处理思想：处理思想：查符号表查符号表无声明错无声明错 typekind

185、? typekind ? TypePtr TypePtr 为为PtrPtr的值的值 Forward:=0Forward:=0EnumType形式：形式：（a a0 0, , ,a ,an n）处理思想：处理思想：生成生成a a0 0, ,a an n的符号表的符号表EntryList:EntryList: ( (a ai i，PtrPtr，consKindconsKind，i)i)，PtrPtr需回填需回填生成内部表示生成内部表示: : Ptr:= Ptr:=(enumSize(enumSize，enumTy,EntryList)enumTy,EntryList) 回填回填EntryLi

186、stEntryList中的中的PtrPtr值值 Forward:=0Forward:=0SubRangeType形式：形式：c c1 1.c.c2 2 处理思想：处理思想：从从C C1 1 求出其内部类型地址求出其内部类型地址PtrPtr1 1和值和值N N1 1；从从C C2 2 求出其内部类型地址求出其内部类型地址PtrPtr2 2和值和值N N2 2；检查检查PtrPtr1 1PtrPtr2 2，N N1 1 N N2 2； Ptr:=Ptr:=(subSize,subTy,Ptr(subSize,subTy,Ptr1 1,N,N1 1,N,N2 2) ) Forward := 0

187、 Forward := 0 ArrayType形式：形式：array Tarray T0 0 of T of T1 1 处理思想：处理思想：返回返回T T0 0,T,T1 1的内部表示地址的内部表示地址IndexPtr,ElemPtrIndexPtr,ElemPtr 判定判定IndexPtrIndexPtr是否为下标类型是否为下标类型计算计算size = (IndexPtrsize = (IndexPtr. Up-Up- IndexPtr IndexPtr. Low +1)Low +1) (ElemPtr(ElemPtr. Size); Size); Ptr:=Ptr:=(size,arr

188、ayTy,IndexPtr,ElemPtr)(size,arrayTy,IndexPtr,ElemPtr) Forward := 0Forward := 0SetType 形式：形式：set of T set of T 处理思想：处理思想：返回返回T T的内部表示地址的内部表示地址BasePtr;BasePtr; 检查检查BasePtr BasePtr 是否为有序类型是否为有序类型; ; Ptr:=Ptr:=(setSize,setTy,BasePtr) (setSize,setTy,BasePtr) Forward:=0Forward:=0FileType 形式：形式：file of T

189、file of T 处理思想：处理思想：返回返回T T的内部表示地址的内部表示地址compPtrcompPtr； Ptr:=Ptr:=(fileSize,fileTy,CompPtr)(fileSize,fileTy,CompPtr) 返回地址返回地址PtrPtr。 Forward := 0Forward := 0PointerType 形式：形式：Q Q 处理思想：处理思想：由由Q Q查表，若找到并且查表，若找到并且Q Q为类型标识符，其内为类型标识符，其内部表示指针返回给部表示指针返回给QEntryQEntry，并且令并且令 Forward := 0 Forward := 0；否则

190、否则QEntryQEntry等待回填，令等待回填，令Forward:= 1Forward:= 1； Ptr:= Ptr:= (PoinSize,PoinTy,QEntry(PoinSize,PoinTy,QEntry)； RecordType 形式：形式：record record 不变体；变体不变体；变体 end end 处理思想：处理思想：构造不变体部分内部表示返回地址构造不变体部分内部表示返回地址fixBodyPtrfixBodyPtr 构造变体部分内部表示返回地址构造变体部分内部表示返回地址variBodyPtrvariBodyPtr 计算记录类型长度计算记录类型长度RecordSi

191、zeRecordSize Ptr:=Ptr:=(Size,recordTy,fixBodyPtr,variBodyPtr)(Size,recordTy,fixBodyPtr,variBodyPtr) Forward:Forward:0 0 Offset 原理原理初始：初始：off := 0; off := 0; 不变体：不变体：id:T id:T Offset(id):= off; off:= off + size(T) Offset(id):= off; off:= off + size(T) ；变体：变体：case u:Tcase u:Tu u of C of Ci i: RecBod

192、y: RecBodyi i ; ; Offset(u):= off; off:=off + size(T Offset(u):= off; off:=off + size(Tu u) ) ； Offset(RecBody Offset(RecBodyi i)=off; )=off; off offi i:=off + sizeof(RecordBody:=off + sizeof(RecordBodyi i) ) off := Max(offoff := Max(offi i) ) RecordSize := off; RecordSize := off;FixBody 形式：形式：FixUn

193、it ; FixBodyFixUnit ; FixBody FixUnit = id : Type FixUnit = id : Type 处理思想：处理思想：构造构造FixUnitFixUnit的内部表示结点的内部表示结点fixUfixU： fixU := fixU := (name,tp,off,nil) (name,tp,off,nil) 如果如果FixBodyFixBody部分为空，则部分为空，则fixB := fixU; fixB := fixU; 否则否则重复上述过程构造重复上述过程构造FixBodyFixBody部分的内部表部分的内部表示示fixBfixB。 fixB :=

194、 Link(fixU,fixB) fixB := Link(fixU,fixB)；VariBody 形式：形式：CaseUnit VariUnitsCaseUnit VariUnits 处理思想：处理思想：构造构造CaseUnitCaseUnit的内部表示的内部表示caseUcaseU： caseU := (name, tp, off); caseU := (name, tp, off); 构造构造VariUnitsVariUnits的内部表示的内部表示variUS:variUS: variU := variU := (c,fixB, variB);(c,fixB, variB); vari

195、US:= variUS:= Link(variU,variUS)Link(variU,variUS) 变体部分的内部表示变体部分的内部表示variBvariB： variB := variB := (caseU, variUS)(caseU, variUS) 声明的语义分析声明的语义分析Z 语义分析工作：语义分析工作：建立符号表；建立符号表；检查标识符的重复声明；检查标识符的重复声明；Z 声明部分：声明部分：标号声明：标号声明：LabelDecPartLabelDecPart；常量声明：常量声明：ConsDecPartConsDecPart；类型声明：类型声明：TypeDecPart

196、TypeDecPart；变量声明：变量声明：VarDecPartVarDecPart；过函声明：过函声明：RoutDecPartRoutDecPart；标号声明标号声明LabelDecPartLabelDecPartZ 标号出现的位置：标号出现的位置：标号声明：标号声明：label label 1 1, , 2 2, , , , n n; ; 标号定位标号定位（语句前）：语句前）： i i：StatementStatement；标号使用（标号使用（GotoGoto后）：后）：goto goto i i; ;Z 标号部分的语义错误：标号部分的语义错误：标号重复声明；标号重复声明；标号

197、重复定位；标号重复定位；标号有定位而无声明；标号有定位而无声明；标号有使用而无定位；标号有使用而无定位； GotoGoto语句有非法转入。语句有非法转入。标号部分语义分析原理标号部分语义分析原理设置三种表：设置三种表： LDEC(LDEC(子程序子程序) )，LDEF(LDEF(结构语句结构语句) )， LUSE( LUSE(结构语句结构语句) )： * * 标号声明部分标号声明部分label label 1 1, , 2 2, , , n n：( (填写填写LDECLDEC表表) ) 建立本层建立本层LDECLDEC；检查是否有重复声明；检查是否有重复声明；标号定位部分标号定位部分

198、 :Statement:(:Statement:(填写填写LDEF,LUSELDEF,LUSE表表) ) 查找查找LDECLDEC是否有是否有 ; ;若无则表示该标号未声明；若无则表示该标号未声明；否则否则查本层的查本层的LDEFLDEF表，若有表，若有则表示有重复定位；则表示有重复定位；否则将否则将填入填入LDEFLDEF表中。若本层表中。若本层LUSELUSE中有中有则则将其删除。将其删除。标号使用标号使用 goto goto ： ( (填写填写LUSELUSE表表) ) 检查本层的检查本层的LDEFLDEF表，若其中没有表，若其中没有，则将则将填入填入本层本层LUS

199、ELUSE表中，表示表中，表示的定位在后。的定位在后。结构体结束：结构体结束：删除本层删除本层LDEFLDEF表，如本层表，如本层LUSELUSE表非空，则查外表非空，则查外层层LDEFLDEF表，直至最外层如都没有表，直至最外层如都没有则有无定位。则有无定位。退出过函：退出过函：删除本层删除本层LDECLDEC表；表；程序结束程序结束：检查检查LUSELUSE是否为空，若不为空，则表示有非法是否为空，若不为空，则表示有非法转入或使用了无定位的标号。转入或使用了无定位的标号。常量声明的语义处理常量声明的语义处理形式：形式：ConsDecPart ConsDecPart co

200、nstconst ConsDecList ConsDecList ConsDecList ConsDecList ConsDec ;ConsDecList ConsDec ;ConsDecList ConsDec ConsDec id = C id = Cid = C id = C 的语义处理原理：的语义处理原理：求求C.type , C.val C.type , C.val 查符号表是否有标识符查符号表是否有标识符idid；若有则重复若有则重复声明错误声明错误否则构造否则构造 ( (id,C.type,consKind,C.value)id,C.type,consKind,C.valu

201、e) 填写到符号表中填写到符号表中类型声明的语义处理类型声明的语义处理形式：形式：TypeDecPart TypeDecPart type TypeDecListtype TypeDecList TypeDecList TypeDecList TypeDec ;TypeDecList TypeDec ;TypeDecList TypeDec TypeDec id = T id = T id = Tid = T的语义的语义分析要点：分析要点：对对T T进行类型分析返回进行类型分析返回内部表示指针内部表示指针TPtr;TPtr; 检查符号表是否有检查符号表是否有重复声明；重复声明；若无则构

202、造符号表若无则构造符号表: : ( ( id , TPtr, typeKind, false/true)id , TPtr, typeKind, false/true) 当整个类型声明部分结束时，进行超前指针类当整个类型声明部分结束时，进行超前指针类型结点的回填工作型结点的回填工作变量声明部分变量声明部分形式：形式：VarDecPart VarDecPart var VarDecList VarDecList VarDecList VarDecList VarDec ; VarDecListVarDec ; VarDecList VarDec VarDec idList : T idLis

203、t : T idid1 1, ,id,idK K:T:T的语义分析的语义分析要点：要点：检查符号表是否有重复声明；检查符号表是否有重复声明；构造符号表项构造符号表项: 1 : 1 j j K,K, (id(idj j,tp,varKind,Access,Level,off,tp,varKind,Access,Level,offj j),),其中其中tptp 和和offoffj j的值等待回填；的值等待回填；对对T T进行类型分析返回指针进行类型分析返回指针TPtrTPtr；回填符号表中的回填符号表中的tptp指针；指针； offoff的确定的确定：off:=off+sizeof(T);

204、 off:=off+sizeof(T); 过过/ /函声明的处理函声明的处理形式：形式：RoutDecPart RoutDec;RoutDecPart RoutDec;RoutDec; ;RoutDec; RoutDec ProcHead; Block | FuncHead;Block RoutDec ProcHead; Block | FuncHead;Block ProHead ProHead procedure id (ParamDecList) id (ParamDecList) FuncHead FuncHeadfunction id (ParamDecList):Type id

206、首部的处理子程序声明部分的处理子程序声明部分的处理子程序语句部分的处理子程序语句部分的处理过函首部的处理过函首部的处理过函名过函名idid：填写符号表项：填写符号表项： (id,void/?,routKind,L,?,actual,?,?,?)(id,void/?,routKind,L,?,actual,?,?,?) 形参：形参：进入新的局部化区进入新的局部化区level:=L+1level:=L+1；第一个形参的第一个形参的offsetoffset由由系统确定设为系统确定设为offoff0 0；构造第构造第i i个形参个形参x xi i的符号表项：的符号表项：值参：值参：( (x

207、xi i,tp,tpi i,varKind,dir,L+1,off,varKind,dir,L+1,offi i) ) off offi+1 i+1 := off:= offi i + sizeof(tp+ sizeof(tpi i) ) 变参：变参：( (x xi i,tp,tpi i,varKind,indir,L+1,off,varKind,indir,L+1,offi i) ) off offi+1 i+1 := off:= offi i + 1+ 1 过函形参：过函形参：( (r,void/?,routKind,L+1,?,formal,offr,void/?,routKind,L+

208、1,?,formal,offr r) ) 进入新的局部化区进入新的局部化区leve:= L+2leve:= L+2，形参同上处理，形参同上处理，但但offoff值为空。结束时结束局部化区；回填值。值为空。结束时结束局部化区；回填值。首部结束：首部结束：回填形参表及类型地址。回填形参表及类型地址。 forwardforward值：值：如果过函体为如果过函体为forward则为则为1 1否则为否则为0 0子程序首部的处理例子子程序首部的处理例子Procedure p(x:real ; var y : boolean ;Procedure p(x:real ; var y : boolean ;

209、 function F(i,j:integer):integer) function F(i,j:integer):integer)当前层数为当前层数为L,L,则则：falsefalsesizesizecodecodeactualactualparaPparaPL LroutKindroutKindvoidvoidp p1 1L+1L+1dirdirvarKindvarKindrealPtrrealPtrx x2 2L+1L+1indirindirvarKindvarKindboolPtrboolPtry y3 3formalformalparaFparaFL+1L+1routKindrout

210、KindintPtrintPtrf fpEntrypEntryxEntryxEntryyEntryyEntryfEntryfEntryiEntryiEntryjEntryjEntryL+2L+2dirdirvarKindvarKindintPtrintPtri iL+2L+2dirdirvarKindvarKindintPtrintPtrj j执行体的语义分析执行体的语义分析表达式的语义分析表达式的语义分析语句的语义分析语句的语义分析赋值语句的语义分赋值语句的语义分析析调用语句的语义分析调用语句的语义分析标号语句的语义分析标号语句的语义分析结构语句的语义分析结构语句的语义分析表达式

212、 Vtp和和EtpEtp，检查二者是否相容。检查二者是否相容。分析过程分析过程过程调用语句的语义分析过程调用语句的语义分析分析重点：分析重点：检查检查p p的语义错误；形参与实参的语义错误；形参与实参类型是否相容，个数是否一致。类型是否相容，个数是否一致。分析过程分析过程结构语句的语义分析结构语句的语义分析问题：问题：结构语句结束符对应多个结构语句结构语句结束符对应多个结构语句结束。结束。解决办法解决办法：对结构化语句重新定义，使得：对结构化语句重新定义，使得每个结构化语句都自带结束符。每个结构化语句都自带结束符。分析重点：分析重点：对标号语句的局部化的处理对标号语句的局部化

213、的处理分析过程：分析过程：进入结构语句时建立本层进入结构语句时建立本层LDEFLDEF和和 LUSE LUSE表，结束时删除本层表，结束时删除本层LDEFLDEF和和LUSELUSE表。表。修改后的结构语句修改后的结构语句StatementStatementIFIF Expr Expr THENTHEN Statement Statement FIFIStatementStatementIFIF Expr Expr THENTHEN Statement Statement ELSEELSE Statement Statement FIFIStatementStatementWHILEWHIL

214、E Expr Expr DODO Statement Statement ODODStatementStatementFORFOR . . DODO Statement Statement ODODStatementStatementBEGINBEGIN StatemenList StatemenList ENDEND 第六章第六章运行时的存储环境运行时的存储环境运行时存储空间的结构和分配运行时存储空间的结构和分配过程活动记录过程活动记录ARAR运行时变量的访问环境运行时变量的访问环境运行时的存储空间结构运行时的存储空间结构| 要保存的信息：要保存的信息：目标代码；数据；库函数代码；目标代

215、码；数据；库函数代码；过程活动的控制信息等过程活动的控制信息等| 运行时的存储空间结构：运行时的存储空间结构：目标代码空间目标代码空间静态区空间静态区空间库代码空间库代码空间堆区空间堆区空间栈区空间栈区空间最大地址最大地址最小地址最小地址运行时静态区的分配运行时静态区的分配| 存储对象的存储位置在程序的整个生命存储对象的存储位置在程序的整个生命周期是固定的。周期是固定的。 | 分配对象：分配对象：全程变量全程变量常量常量信息表信息表| 分配方法：分配方法：块地址法：块地址法：( (DataArea,Offset)DataArea,Offset) 变址模式：变址模式：( (Regis

216、ter,Offset)Register,Offset)栈区的存储分配栈区的存储分配| 存在递归调用存在递归调用| 存储对象：存储对象：过程中被声明的形参、局部变量过程中被声明的形参、局部变量临时变量临时变量| 分配方法：分配方法：对每个被调用过程分配一段存储空间，对每个被调用过程分配一段存储空间，spsp存放当前存放当前过程空间的开始地址；对变量过程空间的开始地址；对变量X X：（：（LevelLevel，off),off), 则其存放地址为则其存放地址为offspoffsp。过程结束时自动释放空间；过程结束时自动释放空间；| 不能存储：不能存储：值的生命周期长于过程的变量；值的生

217、命周期长于过程的变量；动态申请空间的变量；动态申请空间的变量；堆区的存储分配堆区的存储分配| 可随时分配和释放空间可随时分配和释放空间| 存储对象：存储对象：动态申请空间的变量的值动态申请空间的变量的值| 释放空间方法：释放空间方法：显示释放：显示释放：隐式释放：单指针释放隐式释放：单指针释放计数释放法计数释放法标记释放法标记释放法| 分配空间方法：分配空间方法：最佳符合法；首次优先法；循环首次优先法最佳符合法；首次优先法；循环首次优先法运行时的过程活动记录与运行时的过程活动记录与栈区的组织结构栈区的组织结构| 过程活动记录过程活动记录( (AR)AR): :过程的一个现场记录过

218、程的一个现场记录| 记录内容：记录内容：过程控制信息：过程控制信息：先行活动记录的动态链指针、先行活动记录的动态链指针、返回地址、层数和长度等返回地址、层数和长度等机器状态信息：机器状态信息：寄存器状态等寄存器状态等全局变量信息全局变量信息: :非局部变量的信息非局部变量的信息局部变量值：局部变量值：形参变量、局部变量和临时变量形参变量、局部变量和临时变量ARAR的结构：的结构：动态链指针动态链指针返回地址返回地址过程层数过程层数机器状态机器状态全局变量环境全局变量环境返回值返回值形参变量区形参变量区局部变量区局部变量区临时变量区临时变量区控制状态信息控制状态信息机器状态信息机器状态

219、信息全局变量信息全局变量信息本层变量和返回值本层变量和返回值spsp例：例：Procedure p(i:integer);Procedure p(i:integer);Var y:real; a:array1.10of interger;Var y:real; a:array1.10of interger;Begin y:=ai*25 endBegin y:=ai*25 end则过程则过程p p被调用时的活动记录被调用时的活动记录ARAR结构如下：结构如下：控制信息控制信息机器信息机器信息全局信息全局信息返回值返回值 i i y y a aOffset = 10Offset = 10O

220、ffset = 11Offset = 11Offset = 13Offset = 13Offset = 23Offset = 23spspOffset = 0Offset = 0动态链动态链| 调用链调用链：过程名序列过程名序列若若M M是主程序名，则（是主程序名，则（M M）是一个调用链；是一个调用链；若若( ( M, M, , R ), R )是调用链，且在是调用链，且在R R中有中有S S的的调用，则（调用，则（ M, M, , R, S, R, S）也是调用链。也是调用链。记为：记为：CallChain(S)= (M, CallChain(S)= (M, ,R, S),R,

221、S)| 动态链：动态链：如果有调用链如果有调用链CallChain(S)=(M,CallChain(S)=(M,R, S),R, S)，则它对应的动态链为：则它对应的动态链为： DynamicChain=DynamicChain= AR(M),AR(M),AR(R),AR(S),AR(R),AR(S)| 调用过程调用过程Q Q时时: : 新产生活动记录新产生活动记录NewARNewAR 填写填写NewARNewAR的内容的内容: : 动态链指针动态链指针:=sp;:=sp; 填写返回地址、层数、大小和机器状态填写返回地址、层数、大小和机器状态 sp:=sp+CurrentAR.Size;s

222、p:=sp+CurrentAR.Size; 转向转向Q Q子程序。子程序。| 退出过程退出过程Q Q时：时： ( (R R1 1,R,R2 2,.,R,.,Rn n) ) := CurrentAR.Machine; := CurrentAR.Machine; Value:=CurrentAR.ReturnValue; Value:=CurrentAR.ReturnValue; sp:=CurrentAR.DynPointer;. sp:=CurrentAR.DynPointer;. 按原按原CurrentAR.returnCurrentAR.return返回；返回；活跃活动记录活跃活动记录(

223、(LAR)LAR)|LiveARLiveAR（LARLAR）: : 一个过程一个过程S S在动态链中可有多个在动态链中可有多个ARAR，但其中只有最但其中只有最新新AR(SAR(S ) )是可访问的，称此是可访问的，称此AR(S)AR(S)为为S S的活跃活动记的活跃活动记录，并记为录，并记为LiveAR(S)LiveAR(S)，简写为简写为LARLAR（S S）。）。| 例：例：假设有当前调用链是（假设有当前调用链是（M,PM,P1 1,P,P2 2,Q,Q1 1, R, R1 1,R,R2 2,R,R3 3 ) ) 则当前动态则当前动态ARAR链为：链为： AR(M),AR(PAR(M),

224、AR(P1 1),AR(P),AR(P2 2),AR(Q),AR(R),AR(Q),AR(R1 1),AR(R),AR(R2 2),AR(R),AR(R3 3) ) 活跃活动记录活跃活动记录LARLAR为：为： LAR( M ) = AR(M) LAR( M ) = AR(M) LAR( P ) = AR(PLAR( P ) = AR(P2 2) ) LAR( Q ) = AR(Q LAR( Q ) = AR(Q1 1) ) LAR( R ) = AR(RLAR( R ) = AR(R3 3) ) 运行时的变量访问运行时的变量访问| 过程声明链过程声明链( (DeclaChain):Decla

225、Chain):过程名序列过程名序列（M M）是过程声明链，是过程声明链，M M是主程序名；是主程序名；若若( (M,M,P),P)是过程声明链，且是过程声明链，且P P中有过程中有过程Q Q 的声明，则的声明，则( (M,M,P,Q),P,Q)也是过程声明链；也是过程声明链；记为：记为：DeclaChain(Q)=( M,DeclaChain(Q)=( M,P,Q ),P,Q )| 当前变量访问环境当前变量访问环境VarVisitEnv:VarVisitEnv: 若若DeclaChain(Q)= M,DeclaChain(Q)= M,P,Q,P,Q则则 VarVisitEnv(LAR(Q

226、)= VarVisitEnv(LAR(Q)= LAR(M), LAR(M),LAR(P),LAR(Q),LAR(P),LAR(Q)| 若若( (M,M,P,Q),P,Q) CallChain(CallChain(Q)Q)，且，且Q Q的层数为的层数为N N，则有则有 DeclaChain(Q)= DeclaChain(P)DeclaChain(Q)= DeclaChain(P)N N Q Q| 设设 AR(M),AR(M),AR(P,AR(Pi i),AR(Q),AR(Qj j) DynamicChain(Q),DynamicChain(Q),且且Q Q 的层数为的层数为N N，则有：则有：

227、 VarVisitEnv(AR(QVarVisitEnv(AR(Qj j)=VarVisitEnv(AR(P)=VarVisitEnv(AR(Pi i)N N AR(QAR(Qj j) )PROC P;PROC P; BeginBegin Q QEndEnd PROC P; PROC P; Begin Begin Q Q End End PROC Q; PROC Q; Begin Begin endend PROC P; PROC P; PROC Q PROC Q Begin End Begin End Begin Q End Begin Q End PROC Q; PROC Q; PROC

228、P; PROC P; Begin Q Begin Q End End Begin End Begin End Display Display表方法表方法全局表法全局表法局部表法局部表法静态链方法静态链方法寄存器方法寄存器方法变量访问环境的实现方法变量访问环境的实现方法局部局部DisplayDisplay表方法表方法| 对于每个对于每个ARAR求出其变量访问环境，并把它以求出其变量访问环境，并把它以地址表的形式地址表的形式( (DisplayDisplay表）保存在表）保存在ARAR中。因中。因为每个为每个ARAR都自带都自带DisplayDisplay表，称这种方法为表，称这种方

229、法为局局部化部化DisplayDisplay表方法。表方法。| 如果层数为如果层数为N N的过程的过程P P的变量访问环境为：的变量访问环境为： VarVisitEnv(AR(P)=AR VarVisitEnv(AR(P)=ARi1i1, ,AR,ARi,n+1i,n+1, ar arijij表示表示ARARijij的始地址，则的始地址，则 arari1i1, ,ar,ari,n+1i,n+1 是是AR(P)AR(P)的的DisplayDisplay表表. . DisplayDisplay表的求法表的求法| NewAR.Display= CurrentAR.DisplayNewAR.Disp

230、lay= CurrentAR.Display的前的前N N项项 newspnewsp动态链指针动态链指针 DisplayDisplay表表 newspnewsp动态链指针动态链指针 DisplayDisplay表表 spsp arar0 0,ar,ar1 1, ,ar,arN-1N-1, , arar0 0,ar,ar1 1, ,ar,arN-1N-1,newsp,newsp例：例：有过程有过程M,Q,R,SM,Q,R,S，其中其中level(M)=0;level(Q)=1;level(R)=1;level(S)=2level(M)=0;level(Q)=1;level(R)=1;level(

231、S)=2，各各ARAR的的DisplayDisplay表分别如下：表分别如下：Z Z单元单元ar0ar0ar1ar1newspnewspX X单元单元Y单元单元AR(M)AR(M)AR(Q)AR(Q)AR(R)AR(R)AR(S)AR(S)ar1ar1ar2ar2ar0ar0spspDisplayDisplay 表表Off-Off-DisplayDisplay局部局部DisplayDisplay表时变量的访问表时变量的访问| 对一个变量对一个变量X(L, off)X(L, off)，地址为：地址为：当当L= CurrentAR.levelL= CurrentAR.level时：时：addr(

232、X)addr(X)=sp+off=sp+off 否则否则: : addr(X)addr(X)=CurrentAR.DisplayL+ off=CurrentAR.DisplayL+ off静态链方法静态链方法| 原原DisplayDisplay表部分变成一个单元，称为静态链表部分变成一个单元，称为静态链单元，存放静态链指针。单元，存放静态链指针。| 静态链指针的确定：静态链指针的确定：若若NewAR.level= CurrentAR.level+1-kNewAR.level= CurrentAR.level+1-k，则则 NewAR.StaticChainPointer=Indir(sp,

233、k) NewAR.StaticChainPointer=Indir(sp,k) 其中其中Indir(sp,k)Indir(sp,k)表示表示spsp的的k k次间接内容。次间接内容。nilnilAR(M)AR(M)ar0ar0ar0ar0AR1AR1ar1ar1ar1ar1AR2AR2ar2ar2ar2ar2CurrentARCurrentARar3ar3 ar? ar?NewARNewARar4ar4spsp使用静态链时变量的访问使用静态链时变量的访问| 变量变量X(L,off)X(L,off)的地址：的地址：若若L= CurrentAR.Level,L= CurrentAR.Level,

234、则则addr(X)addr(X)= sp+ off = sp+ off 若若L= CurrentAR.Level +1 -k,L= CurrentAR.Level +1 -k,则则 addr(X)addr(X)= Indir(sp,k)+ off= Indir(sp,k)+ off全局全局DisplayDisplay表和寄存器方法表和寄存器方法| 设置一个总的设置一个总的DisplayDisplay表，其长度为最大嵌表，其长度为最大嵌套层数（系统确定），其中套层数（系统确定），其中DisplayiDisplayi存放存放第第i i层最新层最新ARAR的指针。的指针。DiDi表示。表示。|

235、当层数为当层数为j j的过程的过程Q Q被调用时：被调用时：将旧的将旧的DjDj的内容保存到的内容保存到NewAR(Q)NewAR(Q)中：中： NewAR(Q).RessumeAddr = Dj;NewAR(Q).RessumeAddr = Dj; 改写改写DjDj的内容：的内容：Dj=NewAR(Q)Dj=NewAR(Q)的地址；的地址；当退出当退出Q Q时：时：恢复原来恢复原来DjDj的内容：的内容： Dj = CurrentAR.ResumeAddr Dj = CurrentAR.ResumeAddr| 变量变量X(L,off)X(L,off)的地址：的地址：addr(X)= ad

236、dr(X)= DL+offDL+off全局全局DisplayDisplay表方法的实现表方法的实现D(3)D(3)D(2)D(2)D(1)D(1) AR AR5 5(T)(T) AR AR4 4(S)(S) AR AR3 3(R)(R) AR AR2 2(Q)(Q) AR AR1 1(P)(P)spsp全局全局DisplayDisplay表表proc P;proc P; proc Q;proc Q; begin R end begin R end proc R;proc R; proc S; proc S; begin T end begin T end proc T; proc T; beg

237、in end begin end begin S endbegin S endbegin Q endbegin Q end第七章第七章面向语法的语义描述面向语法的语义描述Z 语义处理的抽象描述语义处理的抽象描述- -语法制导方法语法制导方法Z 动作文法及其应用动作文法及其应用Z 属性文法及其应用属性文法及其应用1.1.动作文法动作文法Z 动作文法：动作文法：产生式右部带有动作符的文产生式右部带有动作符的文法法Z 动作符：动作符：区别于语法符号的一种符号，区别于语法符号的一种符号， #Name#Name 可出现于产生式的右部的任何地方可出现于产生式的右部的任何地方没有语法意义，只代表某种语

238、义动作，可看作是没有语法意义，只代表某种语义动作，可看作是无参的语义子程序的名字无参的语义子程序的名字动作文法的产生式：动作文法的产生式： L 1 X1 2 X2 k Xk k+1其中其中i表示动作符，表示动作符，Xi表示语法符号，当然可表示语法符号，当然可以没有动作符以没有动作符 1.1.动作文法动作文法Z 动作文法的例子：动作文法的例子：给定下图所示的文法给定下图所示的文法GSGS，试写出一个动作，试写出一个动作文法，它描述这样一个处理器：输入文法，它描述这样一个处理器：输入0 0、1 1串，求其中串，求其中0 0和和1 1的出现个数，并分别赋给变量的出现个数，并分别赋给变量n0n0和和

239、n1n1，最后将其结，最后将其结果打印出来。果打印出来。 SLLLDLD0D1SLLLDLD0D1:n0,n1:=0:print(n0,n1):n0:=n0+1:n1:=n1+11.1.动作文法动作文法Z动作文法的应用动作文法的应用：凡是和程序文本有关的语义凡是和程序文本有关的语义动作，均可用动作文法来描述动作，均可用动作文法来描述Z 尾动作文法：尾动作文法：动作符只出现于产生式末尾的动动作符只出现于产生式末尾的动作文法作文法Z 动作文法的实现：动作文法的实现：依赖于文法的实现方式，可依赖于文法的实现方式，可以是递归下降，以是递归下降，LL,LRLL,LR实现实现 void S()L();vo

240、id L() next(ch);if (ch=0)L();if (ch=1)L();if (ch=a)return;else error();void S()init;L();out;void L() next(ch);if (ch=0)add0;L();if (ch=1)add1;L();if (ch=a)return;else error();2.2.动作文法的动作文法的LLLL实现实现 LLLL动作文法：动作文法：动作文法满足动作文法满足LL(1)LL(1)文法的条件。文法的条件。实现组成：实现组成： LL(1)LL(1)分析表，分析表，LLLL驱动器，语义子程序。驱动器，语义子程序

241、。驱动程序的分类驱动程序的分类：不带语义栈控制：不带语义栈控制：由用户实现语义栈的管由用户实现语义栈的管理，即将语义栈的处理写在语义子程序中。理，即将语义栈的处理写在语义子程序中。带语义栈控制：带语义栈控制：由驱动器来控制语义栈。由驱动器来控制语义栈。2.2.带语义栈控制的带语义栈控制的LLLL驱动器驱动器LRCTLRCT指针：指针： LeftIndexLeftIndex：指向当前产生式左部符号的语义栈地址指向当前产生式左部符号的语义栈地址 RightIndexRightIndex：指向当前产生式右部的语义栈基地址指向当前产生式右部的语义栈基地址 CurrentIndexCurrentI

242、ndex：指向当前符号的语义栈地址指向当前符号的语义栈地址 TopIndexTopIndex：指向当前第一自由地址指向当前第一自由地址LeftIndexRightIndexCurrentIndexTopIndexSemantic Stack带语义栈控制的带语义栈控制的LL(1)驱动器驱动器算法要点：s 语法栈顶是终极符a:判断a是否与输入流匹配，若匹配：Sem(C):= a.val; C:=C+1;PopSynStack(1) 否则报错；s 语法栈顶是非终极符X: 对当前输入LL分析表有 X Y1Y2Yn:将PushSynStack(Eop,Yn,Y2Y1) 调整LRCT指针。s 语法栈顶是

243、动作符：调用相应的语义动作子程序。s 若语法栈顶是Eop：PopSynStack(1),恢复LRCT指针， C:=C+1动作文法的动作文法的LRLR实现实现尾动作文法的尾动作文法的LRLR实现：实现：不带语义栈控制：不带语义栈控制：归约动作执行前先执行语义动作。归约动作执行前先执行语义动作。带语义栈控制：带语义栈控制：语法栈和语义栈同步语法栈和语义栈同步: : 移入时：移入时：输入符压入语法栈中，输入符输入符压入语法栈中，输入符的语义信息压入语义栈中；的语义信息压入语义栈中；归约时：归约时：执行语义动作，语法栈和语义栈同时执行语义动作，语法栈和语义栈同时退退N N个，将产生式左

244、部压入语法栈，个，将产生式左部压入语法栈，语义信息压入语义栈中。语义信息压入语义栈中。动作文法的应用动作文法的应用用动作文法描述表达式计算：用动作文法描述表达式计算： Z E outE TE T+E addT PT P*T multP n pushP (E)out :print(vtop)add : vtop-1:=vtop-1+vtop;top:=top-1mult:vtop-1:=vtop-1+vtop;top:=top-1 push:top:=top+1; vtop:=val_Lex动作文法的应用动作文法的应用用动作文法描述表达式抽象树的构造：用动作文法描述表达式抽象树的构造： E

245、 TE E+T mknode(ADD,stop-1,stop)T PT T*P mknode(MUL,stop-1,stop)P n mkleaf(n,val_Lex)P id mkleaf(id,name_Lex)P (E)动作文法的应用动作文法的应用用动作文法描述语句抽象树的构造：用动作文法描述语句抽象树的构造： S id:=E S id(E)S if E then S else SS while E do SS repeat S until ES Name:=E build_assS Name(E) build_callS if E then S else S build_ifS wh

246、ile E do S build_whileS repeat S until E build_repName id build_name抽象动作文法抽象动作文法抽象变量：抽象变量：E.val = E1.val+E2.valE.val = E1.val+E2.val 特点是：用抽象概念描述语义值，不是用存储概念表示特点是：用抽象概念描述语义值，不是用存储概念表示抽象动作文法：抽象动作文法：含有抽象变量的动作文法含有抽象变量的动作文法特点是：抽象度高，语义表达清晰，自动化程度高特点是：抽象度高，语义表达清晰，自动化程度高抽象尾动作文法例：抽象尾动作文法例： E T E.val:= T.Va

247、lE T+E1 E.val:=T.val+E1.valT P T.val:= P.valT P*T1 T.val:= P.val*T1.valP n P.val:= n.valP (E) P.val:= E.val属性文法属性文法用于描述语言的静态语义用于描述语言的静态语义主要思想：主要思想：对每个语法符号定义相关属性；对每个语法符号定义相关属性；对每个产生式定义属性求值规则对每个产生式定义属性求值规则例例：valval属性属性E E n n E.val:= n.valE.val:= n.val E (EE (E1 1) )E.val:= EE.val:= E1 1.val.valE

248、 EE E1 1 + E + E2 2 E.val:= EE.val:= E1 1.val+E.val+E2 2.val.val 继承属性和综合属性继承属性和综合属性继承属性相当于输入属性，综合属性相当于输出属性继承属性相当于输入属性，综合属性相当于输出属性从属性语法树的角度来说，结点的继承属性值由其父亲从属性语法树的角度来说，结点的继承属性值由其父亲节点和兄弟结点的属性值决定，综合属性值由本节点的节点和兄弟结点的属性值决定，综合属性值由本节点的继承属性和儿子节点的属性值决定。继承属性和儿子节点的属性值决定。属性定义属性定义定义属性名字定义属性名字定义属性类型定义属性类型( (数据结

249、构数据结构) ) 定义属性类别定义属性类别( (继承继承/ /综合综合) )例：例： E senv :SEnv denv :DEnv etype :EType eval :EValue id name :String n val :integer 属性变量属性变量X.a,X.a,其中其中X X是语法符号，是语法符号，a a是是X X的一个属性符号的一个属性符号( (继承，综合继承，综合) )属性变量的类型取决于其中属性符号的类型属性变量的类型取决于其中属性符号的类型属性规则属性规则 L X1 X2 Xk X1.i = e1 Xk.i = ek L.s = e0 属性规则属性规则属性规则次序没

250、有顺序关系；属性规则次序没有顺序关系；属性规则并不表示在此刻要进行属性值的计算；属性规则并不表示在此刻要进行属性值的计算；Xi的属性值可依赖于其后符号的属性值；的属性值可依赖于其后符号的属性值；没有定义产生式右部符号综合属性值的属性规则；没有定义产生式右部符号综合属性值的属性规则；没有定义产生式左部符号继承属性值的属性规则。没有定义产生式左部符号继承属性值的属性规则。属性文法例属性文法例1(1(不带变量表达式不带变量表达式) )产生式生式属性属性规则属性定属性定义E PE PE.valE.val= P.val= P.valEval :integerEval :integerPval :i

251、ntegerPval :integernval :integer nval :integer E E1 1 E E2 2 + P + P E E1 1.val = E.val = E2 2.val + .val + P.valP.valP nP nP.valP.val= n.val= n.valP(E)P(E)P.valP.val= E.val= E.val 属性文法例属性文法例2(2(带变量表达式带变量表达式) )有变量，需要有表示变量值的环境有变量，需要有表示变量值的环境( (动态环境动态环境) )动态环境动态环境envenv是对偶是对偶(id,v)(id,v)的数组或链表的数组或链表Lo

252、okup(name,env)Lookup(name,env)表示用表示用namename去查动态环境表去查动态环境表env,env,结果是得到一结果是得到一个值个值EnvEnv是继承属性，需要从父亲节点即产生式左部符号那里得到是继承属性，需要从父亲节点即产生式左部符号那里得到产生式生式属性属性规则属性定属性定义E PE PE.envE.env= P.env= P.envE.valE.val= P.val= P.valEenv:DEnv val :integer Eenv:DEnv val :integer Penv:Denv val :integerPenv:Denv val :integer

253、nval :integer nval :integer idname :string idname :string E EE E1 1 + P + P E E1 1.env.env= E.env= E.envP.envP.env= E.env= E.envE.val = EE.val = E1 1.val + .val + P.valP.valP nP nP.valP.val= n.val= n.valP idP idP.valP.val= = lookup(id.name,P.denvlookup(id.name,P.denv) )P(E)P(E)P.valP.val= E.val= E.v

254、al 属性语法树和属性依赖图属性语法树和属性依赖图根据给出的属性计算规则，对于每一条产生式根据给出的属性计算规则，对于每一条产生式可以画出一个有向图，它表示本产生式中各符可以画出一个有向图，它表示本产生式中各符号的属性之间的依赖关系图，称之为属性规则号的属性之间的依赖关系图，称之为属性规则图。图。关于产生式关于产生式E1P+E2的属性规则的属性规则图的属性规则的属性规则图envvalEenvvalPenvvalE+ 属性语法树和属性依赖图属性语法树和属性依赖图假设给定一个属性文法，并且给定一个输入串假设给定一个属性文法，并且给定一个输入串(终极符串终极符串)，则可构造出相应的一棵语法树。，则

255、可构造出相应的一棵语法树。即带有属性的语法树。即带有属性的语法树。表达式表达式x+y的属性语法树的属性语法树valSdenvvalEdenvvalPname:xid+denvvalEdenvvalPname:yid 属性语法树和属性依赖图属性语法树和属性依赖图对于每棵属性语法树，可画出所谓的属性依赖对于每棵属性语法树，可画出所谓的属性依赖图图(属性数据流图属性数据流图)。表达式表达式x+y的属性依赖图的属性依赖图valSdenvvalEdenvvalPname:xid+denvvalEdenvvalPname:yid 属性计算属性计算属性计算就是根据属性数据流图计算出文法开属性计算就是根据

256、属性数据流图计算出文法开始符号结点的综合属性值。不难看出有很多计始符号结点的综合属性值。不难看出有很多计算顺序，都可以算出开始结点的综合属性值。算顺序，都可以算出开始结点的综合属性值。合理的属性文法应不依赖于计算顺序的选择。合理的属性文法应不依赖于计算顺序的选择。基于依赖图的计算方法基于依赖图的计算方法对于给定输入构造属性依赖图（同时计算终对于给定输入构造属性依赖图（同时计算终极符结点的综合属性）；极符结点的综合属性）；选择一个还未被计算而可计算的属性结点，选择一个还未被计算而可计算的属性结点，并计算它；并计算它；重复上述过程，直至全部算完为止。重复上述过程，直至全部算完为止。例初始de

257、nv=(x,10),(y,20), ，则最终计算结果是S.val=30.缺点是占用空间缺点是占用空间属性文法与尾动作文法的区别属性文法与尾动作文法的区别属性文法中的属性规则部分并不表示在此处要做属性文法中的属性规则部分并不表示在此处要做语义动作；语义动作；属性规则部分只定义了属性求值规则，而且规则属性规则部分只定义了属性求值规则，而且规则间的顺序是随便的；间的顺序是随便的；在一个产生式的属性规则中，每个属性只能被定在一个产生式的属性规则中，每个属性只能被定义一次，不能像动作子程序那样重复赋值；义一次，不能像动作子程序那样重复赋值；属性规则中的左部能写哪些属性变量是有规定的。属性规则中的

258、左部能写哪些属性变量是有规定的。属性文法在编译器设计中的应用属性文法在编译器设计中的应用类型树的属性文法描述类型树的属性文法描述表达式中间代码的属性文法描述表达式中间代码的属性文法描述变量中间代码的属性文法描述变量中间代码的属性文法描述语句中间代码的属性文法描述语句中间代码的属性文法描述正则表达式到自动机转换的属性文法描述正则表达式到自动机转换的属性文法描述 S-属性文法及其属性计算属性文法及其属性计算 S-S-属性文法属性文法是文法符号只有综合属性的一是文法符号只有综合属性的一种特殊的属性文法。种特殊的属性文法。最大特点是容易实现，而且任意一个属性最大特点是容易实现，而且任意一个

259、属性文法都可以改写成等价的文法都可以改写成等价的S-S-属性文法。属性文法。对于对于S-S-属性文法来说，属性计算都在产生属性文法来说，属性计算都在产生式末尾进行，因此可以用式末尾进行，因此可以用LLLL方法和方法和LRLR方法实方法实现现S-属性文法的递归实现属性文法的递归实现 LL_S_LL_S_属性文法属性文法：产生式满足产生式满足LL(1)LL(1)条件的条件的S-S-属性文法属性文法称之为称之为LL_S_LL_S_属性文法属性文法。递归实现原理：递归实现原理：1 1 确定计算顺序。确定计算顺序。2 2 属性文法中每个属性变量对应递归程序中的一个变量：属性文法中每个属性变量对应递归

260、程序中的一个变量：X.aX.a转转换成换成X_aX_a的形式。的形式。3 3 对于每个对于每个V VT T定义一个过程定义一个过程terminalterminal，其调用形式是，其调用形式是terminal(a,a_s)terminal(a,a_s)。 4 4 对于每个对于每个V VN N，定义一个带参数的过程，定义一个带参数的过程A(A_s1,A_s2,A(A_s1,A_s2,A_sn),A_sn),其其中中A_siA_si都是引用型参数，将在别处调用时分别得到相应的综合属性都是引用型参数，将在别处调用时分别得到相应的综合属性值。值。5 5 把综合属性计算部分改变为语句形式写在递归子程序的末

261、尾。把综合属性计算部分改变为语句形式写在递归子程序的末尾。S-属性文法的递归实现属性文法的递归实现实现例子实现例子：产生式产生式属性计算规则属性计算规则属性定义属性定义AaBBA.S=u(a.s,B.s,B.s)A s,B s,a s,b sBbB.S=r(b.s)procedure A(out A_s) var a_s, B_s, B_s; Terminal(a,a_s); B(B_s); B(B_s); A_s:=u(a_s,B_s,B_s) Procedure B(out B_s) var b_s; terminal(b,b_s); B_s:=r(b_s)S-属性文法的属性文法的LR实

262、现实现 LR_S-LR_S-属性文法转换成属性文法转换成LR_LR_尾动作文法尾动作文法 LR_S-LR_S-属性文法例属性文法例1 1产生式生式属性属性计算算规则属性定属性定义E PE PE.valE.val= P.val= P.valEval :integerEval :integerPval :integerPval :integernval :integer nval :integer E EE E1 1 + P + P E.val = EE.val = E1 1.val + P.val.val + P.valEE E E1 1 - P - PE.val = EE.val = E1 1

263、.val - P.val.val - P.valP nP nP.valP.val= n.val= n.val属性文法的动作文法可转换成如下：1 EP Acc:= Rval 2 EE + P Acc:= Acc+ Rval 3 EE - P Acc:= Acc- Rval 4 Pn Rval:= n_val S-属性文法的属性文法的LR实现实现 LR_S-LR_S-属性文法例属性文法例2 2产生式生式属性属性计算算规则属性定属性定义E PE PE.val = P.valE.val = P.valEval :integerEval :integerPval :integerPval :intege

264、rnval :integer nval :integer E P + EE P + E1 1E.val = P.val + EE.val = P.val + E1 1.val.valEE P - E P - E1 1 E.val = P.val - EE.val = P.val - E1 1.val.valP nP nP.val = n.valP.val = n.val属性文法的动作文法可转换成如下：1 EP semntop:= semtop 2 EP + E semntop:= semtop-2+ semtop 3 EP + E semntop:= semtop-2- semtop 4 Pn

265、 semntop:= semtop L-属性文法及其属性计算属性文法及其属性计算L-L-属性文法属性文法是属性文法的一大子类。是属性文法的一大子类。若若AX1X2.XiXN是属性文法是属性文法AG中的任一产生中的任一产生式，如果它满足下面条件式，如果它满足下面条件, 则称则称AG为为L-属性文法：属性文法：Xi 的继承属性只依赖于的继承属性只依赖于A的继承属性和的继承属性和X1,X2,.,X(i-1)的的属性；属性；A 的综合属性只依赖于的综合属性只依赖于A的继承属性和产生式右部符号的的继承属性和产生式右部符号的属性。属性。L-属性文法的最大特点就是产生式右部符号的继承属性文法的最大特点就是

266、产生式右部符号的继承属性不依赖于其右部符号的任何属性。这一特点决属性不依赖于其右部符号的任何属性。这一特点决定了有可能通过一遍扫描来求出属性值，而且不需定了有可能通过一遍扫描来求出属性值，而且不需要建立属性语法树。要建立属性语法树。L-属性文法的递归实现属性文法的递归实现 LL_L_LL_L_属性文法属性文法：产生式满足产生式满足LL(1)LL(1)条件的条件的L-L-属性文法属性文法称之为称之为LL_L_LL_L_属性文法。属性文法。递归实现原理：递归实现原理：1 1 属性文法中每个属性变量对应递归程序中的一个变属性文法中每个属性变量对应递归程序中的一个变量：量：X.aX.a转换成转换成X_

267、aX_a的形式。的形式。2 2 对于每个对于每个V VT T定义一个过程定义一个过程terminalterminal，其调用形式是，其调用形式是terminal(a,a_s)terminal(a,a_s)。 3 3 对于每个对于每个V VN N，定义一个带参数的过程，定义一个带参数的过程A(A_s1,A_s2,A(A_s1,A_s2,A_sn),A_sn),其中其中A_siA_si都是引用型参数，将在都是引用型参数，将在别处调用时分别得到相应的综合属性值。别处调用时分别得到相应的综合属性值。4 4 把综合属性计算部分改变为语句形式写在递归子程把综合属性计算部分改变为语句形式写在递归子程序的末尾

268、。序的末尾。L-属性文法的递归实现属性文法的递归实现实现例子实现例子：产生式：产生式：A AaBAaBAb b 属性定义：属性定义：A h s B h1 h2 s， a s， b s 属性计算规则：属性计算规则： B.h1 = a.s B.h2 = f(A.h) A1.h = g(A.h ,B.s) A.s = u(B.s,A1.s,b.s) procedure A(in A_h,out A_s) var a_s, B_h1, B_h2, B_s,A_h, A_s, b_s; terminal(a,a_s); B_h1:=a_s; B_h2:=f(A_h); B(B_h1,B_h2,B_s

269、); A_h:=g(A_h,B_s); A(A1_h,A1_s); terminal(b,b_s); A_s:=u(B_s,A1_s,b_s); L-属性文法的属性文法的LR实现实现实现思想：实现思想：-根据输入串构造分析树；根据输入串构造分析树；-按确定顺序访问结点并计算其属性值；按确定顺序访问结点并计算其属性值；-每个内结点对应一条属性计算规则。假设当前结点为每个内结点对应一条属性计算规则。假设当前结点为N(对应对应X0),并且对应并且对应X0的如下一条规则：的如下一条规则：-X0X0X1X2X1X2Xn / X1.h = Xn / X1.h = ; ; Xn.h= Xn.h=; ; X0

270、.s = X0.s = / /-同时假设已算出的同时假设已算出的X0X0的继承属性值的继承属性值h,h,则访问结点函数则访问结点函数visit(N,h)visit(N,h)将以将以h h作为作为N N结点的继承属性，通过访问其子结点的继承属性，通过访问其子树的所有结点，最终计算出树的所有结点，最终计算出N N结点的综合属性值结点的综合属性值X0.s X0.s L-属性文法的属性文法的LR实现实现Visit(N，h)：1 把把h送入送入X0.h空间中；空间中；2 j:=1;3 计算计算N的第的第j个儿子结点的继承属性个儿子结点的继承属性Xj.h值：值：visit(child(N,j),Xj.h)

271、;5 j:=j+16 若若j n则则重复重复3-6，否则，否则7 计算结点计算结点N的综合属性的综合属性X0.s的值的值 n是是X0对应产生式右部符号的个数对应产生式右部符号的个数L-属性文法的属性文法的LR实现实现p1 ABC / B.h=f(A.h); C.h=g(B.s); A.s= r(C.s)p2 AaA1 / A1.h = u(a.s) ;A.s= q(A.h,A1.s)function A(N,h) var A.h ,B.h, B.s, C.h, C.scase production_numb(N) of p1:A.h := h ;B.s := B(child(N,1),f(A.

272、h);C.s := C(child(N,2),g(B.s);A.s := r(C.s)return A.s p2: A.h := h;a.s := synth_val(child(N,1);A1.s := A(child(N,2),u(a,s);A.s := q(A.h,A1.s) ;return A.s L-属性文法的属性文法的LR实现实现产生式产生式属性计算规则属性计算规则1SBB.h=10 S.s=B.s2BB1B2B1.h=B.h B2.h=B.h B.s=max(B1.s,B2.s)3BB1aB2B1.h=B.h B2.h=f(B.h) B.s=g(B1.s,B2.s)4BbB.S=

273、r(b.s,B.h)L-属性文法的属性文法的LR实现实现产生式产生式属性计算规则属性计算规则1SBB.h=10 S.s=B.s2BB1B2B1.h=B.h B2.h=B.h B.s=max(B1.s,B2.s)3BB1aB2B1.h=B.h B2.h=f(B.h) B.s=g(B1.s,B2.s)4BbB.S=r(b.s,B.h)L-属性文法的属性文法的LR实现实现1function S(N) var B.h, B.s, C.s(可省)； case production_numb(N) of 1:B.h := 10 ; B.s := B(child(N,1),B.h); S.s := B.s

274、return S.s 1function B(N,h)var B1_h ,B2_h ,B1_s ,B2_s, B_s(可省)；case production_numb(N) of 2: B1_h := h ;B1_s := B(child(N,1),B1_s);B2_h := h ;B2_s := B(child(N,2),B2_s);B_s := max(B1_s,B2_s); return B_s3: B1_h := f(h);B1_s := B(child(N,1),B1_s);B2_h := h ;B2_s := B(child(N,2),B2_s);B_s := g(B1_s,B2_

275、s);return B_s4: B_s := r(val(child(N,1),h)return B_s 第八章第八章中间代码生成中间代码生成Z 中间语言中间语言Z 简单表达式的中间代码生成简单表达式的中间代码生成Z 原子语句的中间代码生成原子语句的中间代码生成Z 结构语句的中间代码生成结构语句的中间代码生成Z 声明的中间代码声明的中间代码中间语言中间语言Z 后缀式后缀式-逆波兰式逆波兰式Z 三地址中间代码（三元式、四元式）三地址中间代码（三元式、四元式）Z 图结构中间代码（语法树、图结构中间代码（语法树、DAG)DAG)三地址中间代码三地址中间代码三元式：三元式：i:(i:( ,op1,

276、op2),op1,op2) 四元式四元式：（ ,op1,op2,op1,op2，result)result)如：a:= bc+bd三元式三元式四元式四元式(1)(,b,c)(1)(,b,c,t1)(2)(,b,d)(2)(,b,d,t2)(3)(+,(1),(2)(3)(+,t1,t2,t3)(4)(:=,(3),a)(4)(:=,t3,a,)简单表达式的中间代码形式简单表达式的中间代码形式sE E C C Tuple(E)=Tuple(E)=空，空，ARG(E)= C.valARG(E)= C.valsE E x x Tuple(E)=Tuple(E)=空，空，ARG(E)= x.valAR

277、G(E)= x.valsE E E E1 1 E E2 2 Tuple(E)= Tuple(ETuple(E)= Tuple(E1 1)| Tuple(E)| Tuple(E2 2) ) | ( | ( ,ARG(E,ARG(E1 1),ARG(E),ARG(E2 2),t),t) ) ARG(E)= t, tARG(E)= t, t是临时变量是临时变量表达式的语义信息：表达式的语义信息：表达式种类：表达式种类：E.kindE.kind表达式的类型：表达式的类型：E.typeE.type表达式的结果值表达式的结果值ARGARG：E.Arg E.Arg 或或 ARG(E)ARG(E) 标号标

278、号L L：ARG(L)= LabelFormARG(L)= LabelForm(L)(L) 整数整数C C：ARG(C)= ValueFormARG(C)= ValueForm(C)(C) 源程序变量源程序变量X X：ARG(X)= AddrFormARG(X)= AddrForm(L,Off, Mode)(L,Off, Mode) 临时变量临时变量T T：ARG(T)= AddrFormARG(T)= AddrForm(-1, off, Mode)(-1, off, Mode)表达式的中间代码：表达式的中间代码：E.tupleE.tuple产生一条中间代码的子程序产生一条中间代码的子程序Ge

279、nCode(GenCode( ) )：运算分量运算分量( (栈顶和次栈顶栈顶和次栈顶) )类型检查；类型检查；如需类型转换：生成类型转换中间代码；如需类型转换：生成类型转换中间代码；生成生成操作的操作的中间代码中间代码; ; 从栈中删除运算分量的语义信息；从栈中删除运算分量的语义信息；表达式结果的语义信息压栈表达式结果的语义信息压栈简单表达式中间代码简单表达式中间代码的的LR语法制导语法制导E E T T E E E+T E+T #GenCode(+)#GenCode(+)T T P P T T T TP P # #GenCode(GenCode() )P P C C Push(C.

280、type,C.Arg)Push(C.type,C.Arg) P P id id Push(VarType(entry),VarArg(entry)Push(VarType(entry),VarArg(entry) P P (E) (E) 简单表达式的简单表达式的LLLL语法制导语法制导E T EsEs +T #GenAdd Es Es T PTsTs *P #GenMul TsTs P id #VPrimaryP C #CPrimaryP (E)GenAdd : GenCode(+) ; GenMul: GenCode()Vprimary，Cprimary: 同上。变量中间代码结构变量中间代码

281、结构V.tuple=空V V1.id V1.tuple (AADD,V1.Arg,offset(id),V.Arg)V V1E V1.tuple E.tuple (SUBI, E.Arg, low, t1)(MULTI, t1, size, t2)(AADD, V1.Arg, t2, V.Arg)V V1 V1.tuple(ASSIGN,V1.Arg, V.Arg)V id 变量中间代码的变量中间代码的LR语法制导语法制导sV V id id Push(VarType(entry),VarArg(entry)Push(VarType(entry),VarArg(entry) sV V V V1

282、 1.id.id #FieldVar#FieldVar FieldVar: FieldVar: L:= Semtop-1; R:= Semtop;L:= Semtop-1; R:= Semtop; ResultArg:= NewTemp(indir); ResultArg:= NewTemp(indir); Generate(AADD,L.Arg, R.arg,ResultArg) Generate(AADD,L.Arg, R.arg,ResultArg) Pop(2),Push(R.type, ResultArg) Pop(2),Push(R.type, ResultArg)sV V V V

283、1 1EE #IndexVar#IndexVarIndexVar:IndexVar: L:= Semtop-1; R:= Semtop; L:= Semtop-1; R:= Semtop; ResultArg:=NewTemp(indir); ResultArg:=NewTemp(indir); ResultType:= L.Type.ElemType; ResultType:= L.Type.ElemType; Low:=L.Type.Low;Size:= L.Type.ElemSize; Low:=L.Type.Low;Size:= L.Type.ElemSize; Generate(SU

284、BI, R.Arg, Low, t1); Generate(SUBI, R.Arg, Low, t1); Generate(MULI, t1, Size, t2); Generate(MULI, t1, Size, t2); Generate(AADD, L.Arg,t2, ResultArg); Generate(AADD, L.Arg,t2, ResultArg); POP(2); Push(ResultType,ResultArg); POP(2); Push(ResultType,ResultArg);sV V V V1 1 #DenoVar#DenoVar DenoVar:DenoV

285、ar: ResultArg:=NewTemp(indir); ResultArg:=NewTemp(indir); ResultType:= Semtop.Type.BaseType; ResultType:= Semtop.Type.BaseType; Generate(ASSIG, Semtop.Arg, ResultArg)Generate(ASSIG, Semtop.Arg, ResultArg) POP(1); Push(ResultType, ResultArg)POP(1); Push(ResultType, ResultArg)表达式中间代码生成的例子表达式中间代码生成的例子a

286、5+i.x + m * za5+i.x + m * z 其中，其中，i,m:integer; z:real;i,m:integer; z:real;a:array1.100 of rt; a:array1.100 of rt; rt = record y:int;x:real endrt = record y:int;x:real end1.(ADDI, 5, i, t1) 2.(SUBI, t1 ,1, t2) 3.(MULTI, t2, 2,t3)4.(AADD, a , t3, t4)5. (AADD , t4, 1, t5) 6. (FLOAT , m, t6) 7. (MULTF ,

287、 t6, z, t7) 8. (ADDF , t5, t7,t8)原子语句的中间代码原子语句的中间代码输入输出语句：输入输出语句：S Write(E) E.tuple (WRITE, E.Arg); S Read(V) V.tuple （READ, V.Arg）语法制导：S Read(V) #READS Write(E) #WRITE赋值语句：赋值语句形式：V:=E Vptr:=V1ptr f:=E Vstr:=V1str赋值语句的中间代码形式：(ASSIGN,Arg1,Arg2,n) 或 (FLOAT,Arg1,Arg2)S L:= R L.tuple R.tuple (ASSIGN, R

288、,Arg, L.Arg, size) 或 (FLOAT, R.Arg, L.Arg)动作文法： S L:=R #ASSIGN过函调用语句S id(E1，E2，En)E1.tuple En.tuple(ACT,E1.Arg) (ACT,En.Arg)(CALL,result) 或(CALL,) 传给形参形参实参结合中间代码:(VALACT, Ei.Arg, offseti, sizei)值参(VARACT, Ei.Arg, offseti, sizei)变参(FUNCACT, Ei.Arg, offseti, sizei)函数参数(PROACT, Ei.Arg, offseti, sizei)过

289、程参数过/函调用代码：(call , true, result) 静态转向地址(call , false, result) 动态转向地址GOTOGOTO语句和标号语句的中间代码语句和标号语句的中间代码LABEL LLABEL L1 1,L,L2 2,.,L,.,Ln n 空空S SGOTO LGOTO Li i （JUMP, ARG(LJUMP, ARG(Li i) ) )S SL Li i:S :S ( LABEL,ARG(L( LABEL,ARG(Li i) ) ) S.tuple S.tuple结构语句的中间代码结构语句的中间代码Z 条件语句的中间代码条件语句的中间代码Z While W

290、hile语句的中间代码语句的中间代码Z Repeat Repeat语句的中间代码语句的中间代码Z For For语句的中间代码语句的中间代码Z Case Case语句的中间代码语句的中间代码条件语句的中间代码条件语句的中间代码IF E THEN S1 ELSE S2E.Tuple(JUMP0,E.Arg,S.ElseL)S1.Tuple(JUMP,S.OutL)(LABEL,S.ElseL)S2.Tuple(LABEL,S.OutL)S IF E THEN S1E.Tuple(JUMP0,E.Arg,S.OutL)S1.Tuple(LABEL,S.OutL)条件语句代码生成的条件语句代码生成的

291、LLLL文法文法Sif #StartIF E then #TestIF S1 ElsePart #EndIFElsePart else #GenJump #GenElseL S2 #GenOutLElsePart #GenOutL#StartIF:PUSH(S.ElseL);PUSH(S.OutL);#TestIF:Generate(JUMP0,Semtop.Arg,Semtop-2);POP(1)#GenJump:Generate(JUMP,Semtop.Arg )#GenElseL: Generate(LABEL,Semtop-1.Arg)#GenOutL: Generate(LABEL,

292、 Semtop.Arg)#EndIF: POP(2)WhileWhile语句的中间代码语句的中间代码S WHILE E DO S1E.Tuple(JUMP0,E.Arg,S.OutL)S1.Tuple(JUMP,S.StartL)(LABEL,S.OutL)(LABEL,S.StartL)WhileWhile语句代码生成的语句代码生成的LLLL文法文法 S while #StartWhile E do #WhileTest S1 #FinishWhile#StartWhile :PUSH(S.StartL);PUSH(S.OutL); Generate(LABEL,Semtop-1.Arg)#

293、WhileTest: Generate(JUMP0,Semtop.Arg,Semtop-1.Arg) POP(1);# FinishWhile: Generate(JUMP, S.StartL) Generate(LABEL, S.OutL) POP(2)RepeatRepeat语句的中间代码语句的中间代码S repeat S1 until ES1.Tuple(JUMP0, E.Arg,S.StartL)E.Tuple(LABEL, S.StartL)RepeatRepeat语句代码生成的语句代码生成的LLLL文法文法S repeat #StartRepeat S1 do E #FinishR

294、epeat#StartRepeat :PUSH(S.StartL) Generate(LABEL, Semtop.Arg ) #FinishRepeat: Generate(JUMP0,Semtop.Arg, Semtop-1.Arg) POP(2)ForFor语句的中间代码语句的中间代码for V:=E1 to E2 do S1E1.TupleE2.Tuple(GT,E1.Arg, E2.Arg,t1)(JUMP1, t1, S.OutL)(ASSIG, E1.Arg, V.Arg)S1.Tuple(ADDI, V.Arg, 1, t2)(ASSIG, t2, V.Arg)(GT,V.Arg

295、, E2.Arg, t3)(JUMP0, t3, S.LoopL)(LABEL, S.OutL)(LABEL, S.LoopL)for V:=E1 downto E2 do S1E1.TupleE2.Tuple(LT,E1.Arg, E2.Arg,t1)(JUMP1, t1, S.OutL)(ASSIG, E1.Arg, V.Arg)S1.Tuple(SUBI, V.Arg, 1, t2)(ASSIG, t2, V.Arg)(LT,V.Arg, E2.Arg, t3)(JUMP0, t3, S.LoopL)(LABEL, S.OutL)(LABEL, S.LoopL)ForFor语句代码的语句

296、代码的LLLL动作文法动作文法SSforfor #StartFOR#StartFOR V:=E FORKIND E V:=E FORKIND E dodo #ForDO#ForDO S S #FinishFOR#FinishFOR FORKIND FORKIND to to #ToKind#ToKindFORKIND FORKIND downtodownto #DownKind#DownKindStarFOR: StarFOR: 产生新标号产生新标号S.LoopLS.LoopL和和S.OutL;S.OutL;ToKind/DownKind :ToKind/DownKind :标记循环种类；标记

297、循环种类；ForDOForDO：FinishFOR:FinishFOR:CaseCase语句的中间代码语句的中间代码 E.tuple (JUMP, Search) L1:S1的中间代码 (JUMP,OutL）. . OtherL:S* 的中间代码 (JUMP,OutL) Table: Search: (LABEL,OutL)case E of C1： S1； Cn： Sn； Other：S*end搜索表方法：Table: (C1, L1) (C2, L2) (Cn, Ln)(-,OtherL)Search: 用E.Arg查Table表并转向相应Sj转向表方法：最小、最大分支常数: MinC，M

298、axC;Table: (JUMP,Li) 或（JUMP,OtherL）Search: (LT,E.Arg,MinC,t1) (JUMP1,t1,OtherL) (GT,E.Arg,MaxC,t2) (JUMP1,t2,OtherL) (JUMPX,E.Arg,Table,MinC)语法制导：语法制导：S S casecase #StartCase#StartCase E E ofof #StartOptionList#StartOptionList OptionList OptionList OtherOption OtherOption endend #FinishCase#FinishC

299、aseOptionList OptionList C C #Choice#Choice:S;:S;#FinishOption#FinishOption OptionList OptionListOptionList OptionList OtherOption OtherOption otherother: :#StartOther#StartOther S S #FinishOtherOption#FinishOtherOption过过/ /函声明的中间代码函声明的中间代码形式：形式：Procedure Procedure P(FormDecList)P(FormDecList) Label

300、Dec LabelDec ConstDec ConstDec TypeDec TypeDec VarDec VarDec ProDec ProDec1 1 ProDec ProDecn n Body Body中间代码结构：(Entry,Label,Size,Level) ProDec1.tuple ProDecn.tuple Body.Tuple(EndProc/EndFunc,-,-,-)过程声明的例子过程声明的例子procedure Q( x: real );procedure Q( x: real );var u : real ;var u : real ;function f( k:

301、real ); function f( k: real ); begin begin f := k +k f := k +k end; end;beginbegin u := f(50); u := f(50); y:= u * x y:= u * x endend； (EntryQ,LabelQ,SizeQ,LQ)(Entryf,Labelf,Sizef,Lf)(ADDF, k, k, t0)(ASSIG, t0,f)(ENDFUNC,)(VALACT, 50,0,1)(CALL, Labelf,t1)(ASSIG, t1, u)(MULTR, u,x, t2)(ASSIG, t2, y)(

302、ENDPROC, )第九章第九章中间代码优化中间代码优化Z 引言引言Z 常量表达式优化常量表达式优化Z 公共表达式优化公共表达式优化Z 循环不变式外提循环不变式外提例 i:=0; j:=0; while i10 do begin while j10 do begin Aij:=Aij+Aij+1; j:=j+1; end i:=i+1; end 优化的目标：优化的目标：优化的要求：优化的要求：优化的对象：优化的对象：深层循环和下标变量地址的计算深层循环和下标变量地址的计算优化的种类：优化的种类：常表达式优化（合并常数项）常表达式优化（合并常数项）公共表达式优化（消除重复操作）公共表

303、达式优化（消除重复操作）循环不变表达式外提循环不变表达式外提削减运算强度等等削减运算强度等等优化方法：优化方法：全局优化：全局信息全局优化：全局信息局部优化：局部信息局部优化：局部信息基本块和程序流图基本块和程序流图基本块：基本块：单入口单出口的程序段。单入口单出口的程序段。程序流图：程序流图：以基本块为结点的有向图，有向边表示以基本块为结点的有向图，有向边表示程序执行的流程。程序执行的流程。中间代码基本块的划分：中间代码基本块的划分：初始代码为第一个基本块的入口初始代码为第一个基本块的入口遇转移性中间代码时，结束当前基本块，下一条遇转移性中间代码时，结束当前基本块，下一

304、条代码作为新基本块的入口代码作为新基本块的入口遇标号性代码结束当前基本块，代码本身作为新遇标号性代码结束当前基本块，代码本身作为新基本块的入口。基本块的入口。遇（遇（ASSIG, A, XASSIG, A, X）时，如果时，如果X X为引用型形参时结为引用型形参时结束当前块，并作为该块的出口。束当前块，并作为该块的出口。基本块划分的例子基本块划分的例子B1:( ASSIGN,1, Y ) B6:( LABEL, L6)B2:( LABEL, L0 ) (ADDI, X, Y,t3 ) ( AND，A, B, t ) (GT, t3, 0, t4 ) ( JUMP0, t, L4) (

305、JUMP0, t4, L8)B3:( ASSIGN, 0, X ) B7:( SUBI, X, 1,t5 ) ( JUMP, L5 ) ( ASSIGN, t5, X )B4:( LABEL, L4) ( JUMP, L6 ) ( ASSIG,0, Y ) B8:( LABEL, L8 )B5:( LABEL, L5 ) ( ASSIGN, 0, Z ) ( ADDI, X, 1, t1) ( STOP ) ( ASSIGN, t1, X ) ( SUBI Y, 1, t2 ) ( ASSIGN, t2, Y)B1B2 B4B3B5B6B8B7 程序流图例常表达式局部优化常表达式局部优化常表

306、达式常表达式：任何时候都取固定常数值的表达式：任何时候都取固定常数值的表达式处理思想：处理思想：针对每个基本块，如果一个多元式的两针对每个基本块，如果一个多元式的两个分量的值已知，则计算其值，并删掉个分量的值已知，则计算其值，并删掉相应的中间代码。相应的中间代码。原理：原理：常量定值表常量定值表ConstDefConstDef：( (Var,Val)Var,Val)。基本块入口置基本块入口置ConstDefConstDef为空；为空；对当前多元式的分量利用对当前多元式的分量利用ConstDefConstDef表进行值代换；表进行值代换；新多元式新多元式形如（形如（，A, B,t

307、A, B,t）: :如果如果A A和和B B是常数，是常数，则计算则计算A A B B的值的值v v，并将（并将（t,vt,v）填入填入ConsDefConsDef表。表。形如（形如（ASSIGASSIG，A, BA, B）: :如果如果A A是常数，则把（是常数，则把（B,AB,A）填入填入ConsDefConsDef表，若已有表，若已有B B项，只需修改其值；项，只需修改其值；否则从否则从ConsDefConsDef中删除中删除B B的登记项。的登记项。常表达式局部优化的例子常表达式局部优化的例子源程序中间代码 ConstDef 优化后的代码a:=1 (ASSIGN, 1,a)

308、 (a,1 ) (ASSIGN,1,a)b:=a+1 (ADDI,a,1,t1) (a,1)(t1,2) （ )(ASSIGN,t1,b) (a,1)(t1,2)(b,2) (ASSIGN,2,b)a:=x (ASSIGN, x,a) (t1,2)( b,2) (ASSIGN,a,x)c:=b+5 (ADDI,b,5,t2) (t1,2)(b,2)(t2,7) ( )(ASSIGN,t2,c) (t1,2)(b,2) (t2,7)(c,7) (ASSIGN,7,c) 基于常量定值分析的常量表达式全局优化基于常量定值分析的常量表达式全局优化思想：思想：可利可利用基本块外的常量信息进行优化。基本

309、块用基本块外的常量信息进行优化。基本块入口处的入口处的ConstDefConstDef不简单的定义为空，基本块出口不简单的定义为空，基本块出口处的处的ConstDefConstDef还在后面的基本块中用到。还在后面的基本块中用到。问题：问题：计算入口处和出口处的常量定值集合。计算入口处和出口处的常量定值集合。方法：方法：用常量定值的数据流分析。用常量定值的数据流分析。计算四种集合：计算四种集合： in-c(Bi)in-c(Bi)：在在BiBi块的入口处可用的常量定值之集。块的入口处可用的常量定值之集。 out-c(Bi):out-c(Bi):在在BiBi块的出口处可用的常量定值之集。

310、块的出口处可用的常量定值之集。 def-c(Bi):def-c(Bi):在在BiBi块内产生并且在块内产生并且在BiBi的出口处可用的出口处可用的常量定值之集。的常量定值之集。 kill-c(Bi):kill-c(Bi):被被BiBi块所杀死的常量定值之集。若块所杀死的常量定值之集。若BiBi 块有对块有对X X的赋值，则称的赋值，则称BiBi块将杀死块将杀死X X的常量定值。的常量定值。def-c(Bi) 和kill-c(Bi)可以确定 out-c(Bi)= (in-c(Bi) - kill-c(Bi) def-c(Bi)in-c(Bi)= jpre(i) out-c(Bj)应用in_c(

311、Bi)可以对Bi进行常量表达式优化。常表达式优化原理：对每一基本块Bi求出in-c(Bi)集合，其中in-c(B0)为空；用in-c(Bi)代替基本块Bi的ConstDef；优化过程同局部常表达式优化原理，x:=1y:=2z:=a+1z:=3u:=x+5w:=9b:=y-1z:=3k:=7m:=k+zn:=m+1b:=k+1d:=m+nl:=z+yd:=k+xx:=1y:=2z:=a+1z:=3u:=6w:=9b:=1z:=3k:=7m:=10n:=11b:=8d:=21l:=5d:=8x:=1y:=x+1z:=a+1z:=3u:=x+5w:=6+zb:=y-1z:=3k:=7m:=k

312、+zn:=m+1b:=k+1d:=m+nl:=z+yd:=k+x123456基于相似性的公共表达式局部优化基于相似性的公共表达式局部优化相似多元式：相似多元式：设设( ( 1 1, ,A A1 1,B,B1 1,T,T1 1) )和和( ( 2 2 , ,A A2 2,B,B2 2,T,T2 2) ) 是两个非赋值型多元式，是两个非赋值型多元式， 1 1 = = 2 2，且，且A A1 1和和A A2 2，B B1 1 和和B B2 2的名字彼此相同，则称这两个多元式相似。的名字彼此相同，则称这两个多元式相似。公共子表达式（可节省的公共代码公共子表达式（可节省的公共代码ECCECC）：）：

313、 didi所定义的表达式在所定义的表达式在dkdk处是处是可用的；可用的； UsableExpr:UsableExpr:可用表达式集可用表达式集等价表等价表( (PAIR)PAIR)：(t(ti i,t,tj j) )表示表示t ti i和和t tj j是等价的，需用是等价的，需用t tj j 替换替换t ti i。.di: ( , A, B, ti ).dk: ( , A, B, tk ).基于相似性的基于相似性的ECCECC优化算法优化算法| 设设UsableExp UsableExp 和和 PAIR PAIR 为空；为空；| 对当前多元式根据对当前多元式根据PAIRPAIR来进行等价

314、替换，生成来进行等价替换，生成 NewTuple; NewTuple;| 如果如果NewTuple NewTuple 形如：形如： dk:( dk:( , A, B, tk ):, A, B, tk ): 若若UsableExp UsableExp 中存在相似表中存在相似表达式达式di:(di:( , A, B, tj ), A, B, tj )，则删掉则删掉dk,dk,并在并在PAIR PAIR 表中填入表中填入( (tk,tj)tk,tj)；否则；否则dkdk不优化，把不优化，把dkdk加到加到 UsableExpr UsableExpr中；中； dk:( ASSIG, A, B )dk

315、:( ASSIG, A, B )：从从UsableExprUsableExpr删除含删除含B B的所的所有可用表达式代码。有可用表达式代码。优化前优化前优化后优化后UEUEPAIRPAIR1.(,C,B,t1)2.(,D,t1,t2)3.(:=,t2,D)4.(,C,B,t3)5.(,D,t3,t4)6.(:=,t4,A)7.(,C,B,t5)8.(,D,t5,t6)9.(:=,t6,C)10.(,C,B,t7)11.(,D,t7,t8)12.(:=,t8,A)(,C,B,t1)(,D,t1,t2)(:=,t2,D)()(,D,t1,t4)(:=,t4,A)()()(:=,t4,C)(,C,

316、B,t7)(,D,t7,t8)(:=,t8,A)11,2111,51,51,51,555,105,10,115,10,11(t3,t1). .(t3,t1),(t5,t1)(t3,t1),(t5,t1),(t6,t4) . . 实例： D:=D+CB; A:=D+CB; C:=D+CB; A:=D+CB；基于值编码的公共表达式局部优化基于值编码的公共表达式局部优化| 按值等价原理按值等价原理| 优化思想：优化思想：对一个多元式的分量分别编码，具对一个多元式的分量分别编码，具有相同编码的分量等价。有相同编码的分量等价。| 值编码表值编码表ValuNnm:ValuNnm:| 可用表达式代码表可

317、用表达式代码表UsableExprUsableExpr| 临时变量等价表临时变量等价表TempEquaTempEqua基于值编码的基于值编码的ECCECC优化算法优化算法|入口处初始化：入口处初始化：ValueNum,UsableExpValueNum,UsableExp和和TempEquaTempEqua为空。为空。|对当前多元式用对当前多元式用TempEquaTempEqua等价替换，生成等价替换，生成NewTuple.NewTuple.|如果如果NewTupleNewTuple的的A A和和B B分量是未编码的，则编新码；分量是未编码的，则编新码；|如果多元式形如：如果多元式形如： dk

318、:(dk:( , , A A , , B B , , tk tk ) )若若存存在在didi UsableExprUsableExpr使使得得dkdk是是 di di的的ECCECC，则删掉则删掉dkdk，将将( (tk,ttk,ti i) )填入填入TempEquaTempEqua表；表；否则，为否则，为tktk编码；把编码；把dkdk加入到加入到UsableExprUsableExpr表；表； dk:(ASSIG, dk:(ASSIG, A A , , B B ) )则则令令B B 的的值值编编码码等等于于A A 的的值值编码，编码，填入填入ValuNumValuNum表中；表中；从从

319、UsableExprUsableExpr删除所有含删除所有含B B的的中间代码。中间代码。基于值编码的优化实例基于值编码的优化实例中间代码中间代码映象映象TempEqua UETempEqua UE 优化代码优化代码( (, ,B,C,t1)B,C,t1)( (, ,B,C,t2)B,C,t2)(+,t1,t2,t3)(+,t1,t2,t3)(:=, t3,A)(:=, t3,A)(:=, B,D)(:=, B,D)( (, ,D,C,t4)D,C,t4)( (, ,B,C,t5)B,C,t5)(+,t4,t5,t6)(+,t4,t5,t6)(:=,t6,E)(:=,t6,E)(1,2,3

320、)(1,2,3)(1,2,3)(1,2,3)(3,3,4)(3,3,4) ( (A)=4A)=4 ( (D)=1D)=1(1,2,3)(1,2,3)(1,2,3)(1,2,3)(3,3,4)(3,3,4) ( (E)=4E)=4 1 1( (t2,t1) t2,t1) 1 1 1,31,3 . . . .(t4,t1) .(t4,t1) .(t5,t1) . (t5,t1) . (t6,t3) .(t6,t3) . . .( (, ,B,C,t1)B,C,t1)( )( )(+,t1,t1,t3(+,t1,t1,t3) )(:=, t3,A)(:=, t3,A)(:=, B,D)(:=, B,

321、D)( )( )( )( )( )( )(:=,(:=,t3,E)t3,E)循环不变式外提优化循环不变式外提优化循环的识别：循环的识别：识别循环的入口、重复体、出口部分。识别循环的入口、重复体、出口部分。识别方法：识别方法：基于程序文本，基于程序图。基于程序文本，基于程序图。外提对象：外提对象：循环不变式循环不变式安全性安全性: : 除法表达式不能外提除法表达式不能外提( (除零溢出除零溢出) ) 赋值表达式不能外提赋值表达式不能外提( (不一定执行该循环）不一定执行该循环）外提原理：外提原理：定义定义LoopDefLoopDef是在循环体内被定义的变量集合是在循环体内被定义的变量

322、集合; ; 对每层循环记录对每层循环记录LoopDef;LoopDef; 若循环体内的多元式若循环体内的多元式( ( , ,A,B,tA,B,t) )中的中的A,BA,B不在本不在本层的层的LoopDefLoopDef中中, ,则把则把( ( , ,A,B,t)A,B,t)外提到循环体外提到循环体的入口处。的入口处。外提实例外提实例FOR i :=0 TO 9 DO FOR j :=0 TO 9 DOFOR k:=0 TO 9 DO Aijk:=(ij)k ENDFOR ENDFOR ENDFOR ( , i ,100, t1 ) ( , A,t1, t2 ) ( , j ,10, t3

323、) ( , t2, t3, t4 ) ( , t4, k , t5 ) ( , i , j, t6 ) ( , t6,k, t7 ) ( , t7, t5 ) ( , i ,100, t1 ) ( , A,t1, t2 ) ( , j ,10, t3 ) ( , t2, t3, t4 ) ( , i , j, t6 ) ( , t4, k , t5 ) ( , t6,k, t7 ) ( , t7, t5 ) ( , i ,100, t1 ) ( , A,t1, t2 ) ( , j ,10, t3 ) ( , t2, t3, t4 ) ( , i , j, t6 ) ( , t4, k , t

324、5 ) ( , t6,k, t7 ) ( , t7, t5 )第十章第十章目标代码生成目标代码生成| 目标代码目标代码| 临时变量的存储空间分配临时变量的存储空间分配| 寄存器的分配和释放寄存器的分配和释放| 基于三地址中间代码的目标代基于三地址中间代码的目标代码生成码生成目标代码生成概述目标代码生成概述n目标代码生成器的输入和输出目标代码生成器的输入和输出p输入：中间代码输入：中间代码/TokenList+符号表符号表p输出：输出：绝对机器代码：执行速度快，缺乏灵活性绝对机器代码：执行速度快，缺乏灵活性可重定位机器代码：可分模块编译，需连接和装入可重定位机器代码：可分模块编译，需连接和装入

325、汇编代码：必须经过汇编程序汇编汇编代码：必须经过汇编程序汇编n衡量目标代码质量的标准衡量目标代码质量的标准在保证在保证语义相等语义相等的情况下，生成的目标的情况下，生成的目标指令的条指令的条数越少数越少和和执行速度越快执行速度越快虚拟机虚拟机n指令格式为：指令格式为：op destination source 其中其中destination和和source不能同为存不能同为存储字储字n虚拟机的寻址方式和相应的汇编语言表示虚拟机的寻址方式和相应的汇编语言表示形式形式n虚拟机的指令系统虚拟机的指令系统p LD R LD R，Source Source 从从Source Source 读出送入读出送

326、入R Rp Op R Op R，Source Source Source op RSource op R结果结果送入送入R Rp ST Target ST Target，R R R R的内容送入的内容送入Target Target 三种硬件地址模式三种硬件地址模式|硬件地址模式：硬件地址模式：# #c -c -立即式立即式 d(R) - d(R) -变址式变址式 R - R -寄存式寄存式 |指令格式：指令格式： Op #C R Op #C R （立即立即-寄存器）寄存器） Op d(R1) R2 Op d(R1) R2 （存储器存储器-寄存器）寄存器） Op R1 R2 Op R1 R2

327、（寄存器寄存器-寄存器）寄存器）|几个常见指令的含义几个常见指令的含义： Load Source R Load Source R 从从Source Source 读出送入读出送入R R Op Source R Source op R Op Source R Source op R结果结果送入送入R R Store Target R R Store Target R R的内容送入的内容送入Target.Target.临时变量临时变量| 特点：寿命短；一次定义一次使用| 存储空间分配：尽可能采用共享办法随用随分配的动态分配：调用一个过程时，分配一个新的AR空间(不包括临时变量部分)，

328、每当要保存一个临时变量时，动态分配到栈区的可用单元中按共享法静态分配：先计算出临时变量的空间，在过程调用时和源变量一起申请空间。即调用时将临时变量安排在AR中临时变量的静态分配临时变量的静态分配| 定值点：定值点：如果如果i中间代码给临时变量中间代码给临时变量T定值，定值，则称则称i为临时变量为临时变量T的定值点。的定值点。| 引用点：引用点：如果如果j中间代码使用中间代码使用T，则称则称j为为T的的引用点。引用点。| 活动区间：活动区间：如果如果i是是T的定值点，的定值点，j是是T的最后的最后引用点，则称引用点，则称 i, j是是T的的活动区间。活动区间。| 活动区间活动区间

329、i, j和和 m, n不严格相交：不严格相交：如果如果m j或或i n。| 空间分配：空间分配：如果两个临时变量的活动区间不严格相交，则可如果两个临时变量的活动区间不严格相交，则可以以共享单元共享单元T1T2T3T4T5Offset = m Offset = m+1 Offset = m+1 Offset = m+1 Offset = m例：变量的状态描述变量的状态描述|变量：变量：源变量和临时变量源变量和临时变量|描述内容：描述内容：变量是否在寄存器中：变量是否在寄存器中：变量的现行值是否在内存中：变量的现行值是否在内存中：变量的值在其后是否还使用：变量的值在其后是否还使用：变量

330、的下次引用距离：变量的下次引用距离： | 状态描述形式（状态描述形式（DL, SNS） DL: 如果从下一位置开始，到变量如果从下一位置开始，到变量A重新被赋值或基本重新被赋值或基本块结束，没有块结束，没有A的当前值的引用，则定义当前该变量的当前值的引用，则定义当前该变量的的DL为为D; ;否则定义为否则定义为L。表示此后变量的状态。表示此后变量的状态。 SNS: 如果如果A的值在寄存器但不在内存，而且当该寄存的值在寄存器但不在内存，而且当该寄存器被剥夺时需要保存变量的值，则当前该变量的器被剥夺时需要保存变量的值，则当前该变量的SNS的值为的值为S(Store)，否则取否则取NS。寄存器寄存器

332、构造R:B(L/D, NS)| 生成生成( (Op , A, B, T)的目标代码为：的目标代码为： Load A，B Op B，R 时：时：把把T(L, NS) 加入加入R的状态表中，从的状态表中，从R中删除中删除A项项| 申请寄存器时申请寄存器时R的状态表为空，释放时表也为空的状态表为空，释放时表也为空（可能生成一些（可能生成一些store指令）。指令）。寄存器的分配寄存器的分配| 分配原则：分配原则：选择代价最小的寄存器选择代价最小的寄存器| 寄存器的选择代价：寄存器的选择代价：Store代价、代价、Load代价代价把寄存器中的现行值回送内存的把寄存器中的现行值回送内存的Store指

333、令总代价；指令总代价；由于寄存器被剥夺，下次重新装入寄存器的由于寄存器被剥夺，下次重新装入寄存器的Load指指令的总代价；令的总代价；如果申请到的是未分配过的新寄存器，则代价为如果申请到的是未分配过的新寄存器，则代价为0 0。| 释放代价：释放代价： X (D, NS) -0 X(D, S) -0 X(L, NS) -2 X(L, S) -4| 分配算法：分配算法：选择最小释放代价，下次引用距离最远选择最小释放代价，下次引用距离最远的寄存器的寄存器四元式到目标代码的翻译四元式到目标代码的翻译n翻译过程：从头到尾逐条扫描四元式，每扫翻译过程：从头到尾逐条扫描四元式，每扫描完一条四元式就

334、把它翻译成对应的目标代描完一条四元式就把它翻译成对应的目标代码码( (一条四元式可能会对应若干条目标指令一条四元式可能会对应若干条目标指令) ) n限定条件：目标机只有一个寄存器、不考虑限定条件：目标机只有一个寄存器、不考虑效率、当前地址为效率、当前地址为A A表达式和赋值语句的翻译表达式和赋值语句的翻译n表达式四元式：形如（表达式四元式：形如（OpOp，A A，B B，T T）：）：汇编指令：汇编指令：LD RLD R，A A； Op R Op R，B;B; ST T, R ST T, Rn赋值语句四元式：形如赋值语句四元式：形如( (ASSIG,A,-ASSIG,A,-，B)B)：汇编

335、指令：汇编指令：LD RLD R，A A； ST B ST B，R Rn例：例：Z:= X*(a+b)* Y* (a+b)Z:= X*(a+b)* Y* (a+b) ( (ADDI,a,b,t1)ADDI,a,b,t1)LD RLD R，a; Add Ra; Add R，b; ST t1,Rb; ST t1,R( (MULTI,X,t1,t2)MULTI,X,t1,t2)LD R,t1; LD R,t1; MUlT R,X; MUlT R,X; ST t2,RST t2,R( (MULTIMULTI, ,t2,Y,t3)t2,Y,t3)LD R,t2; LD R,t2; MUlT R,Y; M

336、UlT R,Y; ST t3,RST t3,R( (MULTIMULTI, ,t3,t1,t4)t3,t1,t4)LD R,t3; LD R,t3; MUlT R,t1;MUlT R,t1;ST ST t4,R;t4,R;( (ASSIG,t4,-,Z)ASSIG,t4,-,Z)LD R, t4; ST Z,RST Z,R输入输入/ /输出语句的翻译输出语句的翻译n输入语句四元式形如：(READ, A,-,-）汇编指令：IN R； ST A , Rn输出语句四元式形如：(WRITE,A,-,-）汇编指令：LD R , A； OUT R 条件语句四元式的翻译n（THEN, t,_ , _TH

337、EN, t,_ , _）生成的汇编代码为）生成的汇编代码为：LD R，tJUMP0 R，_n（ELSE,_,_,_ELSE,_,_,_）生成的汇编代码为）生成的汇编代码为：JMP _ 同时回填JUMP0指令的目的地址n（ENDIF,_,_,_）不产生目标代码，只负责完成ELSE子句的地址回填工作。循环语句的翻译循环语句的翻译n（WHILE,_,_,_WHILE,_,_,_）不产生目标代码，只用来标记不产生目标代码，只用来标记whilewhile语句的入口地址，将地址语句的入口地址，将地址A A入栈入栈S;S;n（DO , t ,_ ,_）产生的目标代码为：产生的目标代码为：LD R , tJ

338、UMP0 R , _ 将将“JUMP0 R , _” 入栈入栈Q;n（ENDWHILE, _, _, _）产生的目标代码：产生的目标代码：JMP A 回填前面回填前面DO四元式所产生的半条指令四元式所产生的半条指令 JUMP0 R , B 标号和标号和goto语句的翻译语句的翻译n（LABEL, _, _,L）不产生目标代码，只向不产生目标代码，只向L所分配到所分配到的存储单元写入转向地址。的存储单元写入转向地址。 n（GOTO, _, _, L）生成的目标代码为生成的目标代码为JMP *L过程、函数说明的翻译过程、函数说明的翻译n( ENTRY, Q, , ) 不产生目标代码，只需将当前指不

339、产生目标代码，只需将当前指令地址令地址A填入填入Q的相应语义信息中。的相应语义信息中。n(ENDPROC, ,)或或(ENDFUNC,) 1. 将本层活动记录中保存的机器状态恢复过来，对应一组读指令。2. 删除本层活动记录，使动态外层的活动记录成为当前活动记录；3. 按1(top)中记载的返回地址返回。目标代码为: ST top,sp LD sp ,0(top) / 作废当前活动记录 JMP 1(top) /按返回地址返回过程、函数调用语句的翻译过程、函数调用语句的翻译n值参情形值参情形 (ValACT , t , Offset , size )a. 若若t为间接变量，则生成的目标代码为：为

340、间接变量，则生成的目标代码为：LD R , * tST offset（sp） , Rb. 若若t 为直接变量为直接变量，则生成的目标代码为：，则生成的目标代码为： LD R ,t ST offset（sp） , R c. 若若t 为数组，则生成的目标代码为：为数组，则生成的目标代码为：moveB t , offset（sp） , size n 变参情形变参情形 (VarACT , t, Offset , size )a. 若若t为直接变量，则生成的目标代码为：为直接变量，则生成的目标代码为：LEA R , tST offset（sp） , Rb. 若若t为间接变量为间接变量,，则生成的目标代

341、码为：，则生成的目标代码为：LD R , t ST offset（sp） , R 过程、函数调用语句的翻译过程、函数调用语句的翻译n过程、函数调用语句过程、函数调用语句 (CALL , f , true, t ) 1. 生成填写变量访问环境指令生成填写变量访问环境指令2. 把机器状态把机器状态(寄存器内容寄存器内容)保存到活动记录的机器保存到活动记录的机器状态区中状态区中,一般应生成一组存的指令一般应生成一组存的指令3. 要填写管理信息要填写管理信息.首先填写过程层数首先填写过程层数.从过程从过程f的的语义信息中取其层数语义信息中取其层数,填入到填入到2(top)中中,生成指令为生成指令为LD

342、 R , semf.levelST 2(top) , R过程、函数调用语句的翻译过程、函数调用语句的翻译4. 填写动态链指针填写动态链指针ST 0(top) , sp5. 填写返回地址填写返回地址LD R , A+5 / AST 1(top) , R / A+1 6. 生成过程活动记录生成过程活动记录ST sp , top / A +2ST top , top + semf.size / A+37. 生成转向过程生成转向过程f入口的指令入口的指令JMP semf.code / A+48. 如果是函数调用，则把函数值读到寄存器中如果是函数调用，则把函数值读到寄存器中LD R ， 4(top) /

343、 A+5ST t , R 第十一章第十一章对象式语言的实现对象式语言的实现| SOOL语言的语法语言的语法| SOOL语言的语义语言的语义| SOOL的语义分析的语义分析| SOOL的目标代码生成的目标代码生成1. SOOL语法语法-程序程序| 程序：由一串类声明、一串函数声明和一个主程序组成。每个类声明定义一个类，每个函数声明定义一个函数，而主程序则是由变量声明和语句列组成的一个分程序Block，它是整个程序的启动部分。 ; .; .; main 1. SOOL语法语法-分程序分程序| 分程序：Block用来定义主程序体、函数体、方法体。分程序由两部分组成，其一是声明部分，其二是语句部分。

344、为了简单起见，我们假设Block内的声明里没有函数、方法声明，即只有变量（称为临时变量）；另外还假设语句部分里不能有Block语句。 begin end 1. SOOL语法语法-类声明类声明| 类声明：每一个类声明均由保留字class打头，并定义一个Class名。每个类都有其父类，没有父类的类名定义为Object（根类）。类的成员分为公有(Public)型和私有（Private）型两种；成员又可分为变量成员和方法成员。 class id extend id public ; | private ; | ;,; ;, ;1. SOOL语法语法-类型类型| 类型：整数类型，实数类型，布尔类型，类

345、类型，虚类型。其中虚类型用void符号来表示，其含义与C语言相同。 integer | real | boolean | void | classname 1. SOOL语法语法-变量声明变量声明| 变量声明:变量声明均由保留字var打头，并定义一些变量标识符，例如： var i,j,k :integer; var x,y : C ( C是类名)由Class名定义的变量称之为对象变量。对象变量的值是一个对象，而对象则代表一个对象空间。对象空间都包含哪些内容，完全依赖于定义对象变量的类Class。 var : 1. SOOL语法语法-函数函数&方法声明方法声明| 函数声明和方法声明: 函数声明由

346、保留字function打头，而方法声明则由保留字method打头，每个函数和方法声明都有其类型，若其类型标志为void，则没有返回值，否则有返回值。 function id (): method id (): , id : 方法和函数的主要区别是它们的调用方式不同，即如果m是方法名，则只能以发消息的语句或表达式Receiver.m(e1,.,en)形式调用方法m；如果f是函数名，则按通常的方式f()调用函数f。 1. SOOL语法语法-语句语句| 语句: 除通常语句外，增加了对象创建语句和发消息语句。 1 V := new (ClassName) 创建对象语句 2 reseiver.m( E

347、xpList) 发送消息语句其中ClassName 是Class名，reseiver是对象变量或虚对象变量self。 1. SOOL语法语法-变量变量| 变量: 除通常变量外，增加了成员变量：即x.a，其中x是一个对象变量，a是一个成员变量名。其作用完全类似于记录类型中的域选择变量，对象变量类似指向记录的指针变量，成员变量则类似记录中的域名。变量x.a的空间是x所指向对象空间中对应成员变量a的空间。变量按其结构可分为三种： 1 自定义变量名id（一般变量，形参变量，成员变量） 2 虚变量名self （预定义对象变量名） 3 复合型变量x.a （选域变量）因为SOOL语言没有复杂类型的变量，因

348、此变量的语法结构可描述如下： id | self | .id 1. SOOL语法语法-表达式表达式| 表达式: 除通常表达式外，增加了发消息表达式：x.m()，其中x是接受消息的对象变量，m是消息的方法名。 C | | | f()| .m( ) , 2. SOOL语义语义-的作用域的作用域z 全程作用域规则：X 由Class声明定义的类名在整个程序内有效X 由Function声明定义的函数名在整个程序内有效z BLOCK作用域规则： VarDecList;StmList X 由VarDecList声明的变量(称其为临时变量)标识符号，在StamList内有效。 z METHOD作用域规则：X

349、在方法声明中被声明的形参名，在其Block内有效。2. SOOL语义语义-声明声明的作用域声明声明的作用域z CLASS作用域规则：X public成员变量名和成员方法名，在本类和子孙类有效。X private成员变量名和成员方法名，只在本类有效。为了简化起见，SOOL特别规定私有名只在私有范围内有效，即公有方法里不出现私有成员名。X 若receiver有效，并且成员变量名x关于receiver有效，则receiver.x有效。X 若receiver有效，并且成员函数名m关于receiver有效，则receiver.m有效。X假设receiver的类为A ，并且从A类开始往祖先类的顺序能查到i

350、d的声明，则称id关于receiver有效。 2. SOOL语义语义-Class声明的语义声明的语义z 类声明class B extend A.定义一个类名B，其中A是使用出现，称A为B的父类名，而称B为A的子类名。z 一个类中的公有成员变量名不能与其祖先类中公有成员变量名相重。z 一个类中的方法名可与其祖先类中的成员方法名相重（即允许重载）。z Object是预定义的类名，它没有成员变量和成员函数，是所有类的祖先类。z 每个类只有一个父类(Object无父类)。z 每个类可继承其祖先类公有成员的声明，换句话说，在一个类中出现的公有成员声明对于本类和子孙类均有效。z 类名用来定义对象变量。 2

351、. SOOL语义语义-语句的语义语句的语义z 赋值语句：v:=y y的类型必须与v的类型相容。当它们为对象变量时，其相容性定义为如下，即y的类与v的类一致，或y的类是v的子孙类。动态语义：把y单元的内容送入v单元。如果v和y是对象变量，则送的是对象空间的地址。当v为对象变量时，关于赋值后V之类的问题，可有两种定义法，其一是定义赋值动作不改变左部变量v的类（称之为静态类方法），其二是定义赋值动作将改变左部变量v的类，具体说v的类被改变为y的当前类（称之为动态类方法）。C+语言采用了静态类方法。 2. SOOL语义语义-语句的语义语句的语义z 创建语句：v:=new(C) v必须是对象变量。

352、v的类必须是C 或C的祖先类。动态语义：在堆区(Heap)里开辟一个初始化的C类对象空间，并将其对象空间地址赋给v。 2. SOOL语义语义-语句的语义语句的语义z 发消息语句：receiver.m(e1,en)分为两种情形：一是receiver为实变量v，一是receiver为虚变量self。假设receiver的当前类为C，则从类C开始往祖先类查方法m，若查不到，则表示此m无定义，否则第一个查到m的方法体代码为所要调用的代码。 receiver.m(e1,.,en)的含义是把消息m(e1,.,en)发给receiver所指向的对象（空间）。通常在m方法中有成员变量的访问，这样当方法m被

353、执行时，自然访问receiver 所指向的对象空间。因此，把消息m(e1,.,en) 发给receiver 所指向的对象，可理解为让方法m(e1,.,en)作用于receiver所指向的对象空间。当receiver为self时，其对象空间就是当前对象空间。 3. SOOL语言的语义分析语言的语义分析z 标识符的符号表项：SOOL新增三种标识符：类名标识符、成员变量标识符和成员方法标识符z 类名标识符的符号表项： z 成员变量标识符的符号表项：z 成员方法标识符的符号表项： idclasskind type super size id var kind type off acc mem idf

354、unckind type entry size mem3. SOOL语言的语义分析语言的语义分析z 符号表结构：class A extend Object public var a; method m1(x)var y; 语句 private var z1; method u1(x)var y;语句Aam1xyz1u1xyAam1xyz1u1xy3. SOOL语言的语义分析语言的语义分析z 符号表结构：class B extend A public var b; method m2(x)var y; 语句 private var z2; method u2(x)var y;语句Bbm2xyz2

355、u2xyBbm2xyz2u2xy3. SOOL语言的语义分析语言的语义分析z 符号表结构：class C extend A public var c; method m3(x)var y; 语句 private var z3; method u3(x)var y;语句Ccm3xyz3u3xyCcm3xyz3u3xy3. SOOL语言的语义分析语言的语义分析z 符号表结构：function f(x) var a; 语句 fxafxafunction g(x) var a; 语句 gxagxamain var a; 语句 aa在main体内，A,B,C,f,g,a的有效表项有效3. SOOL语言的

356、语义分析语言的语义分析z 符号表的局部化Class名，Function名，在整个期间都有效，不作废。Class声明中用Private声明的标识符，只在本Class内有效，因此结束一个Class时，需要把其符号表项作废掉。 Class声明中用Public声明的标识符，不仅在本Class内有效，而且在子孙类也有效，因此结束一个Class声明时，不能把其Public名的符号表作废掉。 Method和Function声明中的形参声明和其Block中的临时变量声明，对该方法外部永远无效，因此当一个方法声明结束时，需要把形参变量和临时变量的符号表均作废掉。对Main主程序中的语句来说，在主程序层中被声明

357、的变量标识符和类名以及函数名标识符对其都有效。要把它们一直保留起来。 4. SOOL的目标代码的目标代码z 对象空间对象空间动态被生成。对象空间在堆区。对象空间由语句x:= new(C)创建。对象空间内容包括两部分：成员变量空间（包括私有成员变量）和类信息单元。对象变量单元的内容是某对象空间的始地址。表示A的某种信息，比如编号或地址等。成员变量的类型可以是类，即成员变量也可能是对象变量。 V3V2V1op01234. SOOL的目标代码的目标代码z 当前对象self self表示当前对象的虚指针变量。z self的值 self的值是一个对象空间的地址。当x.m(.)中的m(.)

358、被执行期间，self的值是x单元指向的对象空间地址。当方法调用m(.)结束时，self的值是执行 m(.)前的self值。 4. SOOL的目标代码的目标代码z 增加当前对象恢复功能的活动记录结构局部变量局部变量返回地址返回地址老老sp01sptop局部变量局部变量返回地址返回地址self单元单元老老sp12sptop04. SOOL的目标代码的目标代码z 成员变量的目标地址z op表示指向当前对象空间的专用寄存器，表示成员变量a的相对对象空间的偏移量 p self.a情形：op p a是成员变量情形: 单独出现a等价于self.a ，因此其访问地址为opp x.a情形： Load

359、 sp,R ， R4. SOOL的目标代码的目标代码z 成员变量的offset确定原理非成员变量的Offset是相对过程活动记录空间而言，而成员变量的Offset则是相对一个对象空间而言。成员变量的Offset要考虑到公有成员变量的继承问题。子类的初始Offset值取其父类公有变量Offset的输出值。这里假设了先是公有变量空间后私有变量空间，而且还假设公有方法不引用私有变量。 Offset的步长依赖于成员量的类型。 4. SOOL的目标代码的目标代码z 成员变量的offset确定原理a1,a2s1Ab1s2BCd1Ds3EOffset(a1)=1Offset(a2)=2Offset(a

360、3)=3Offset(b1)=3Offset(s2)=4Offset(d1)=3Offset(s3)=34. SOOL的目标代码的目标代码z 类的多态性 self.m(EL)，虚对象变量self的类是不确定的z 方法的动态绑定假设有receiver.m()，则首先分析receiver是多态还是单态，如果是单态，则采用静态绑定法，否则采用动态绑定法。动态绑定法中的主要问题是，方法调用代码中的最后转向代码如何动态地生成所调方法的入口地址的问题。解决此问题的最基本的思想是，根据receiver求其类C（信息），再利用方法名m，动态求m_?C成立的方法m的入口地址，然后按此地址转向方法体代码。实现方法大体可分为：全查表法，半查表法，不查表法。

展开阅读全文

教学课件编译原理

最新文档