编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法

Presentation on theme: "编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法"— Presentation transcript:

1 编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法
第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法 第六章 自底向上优先分析方法 第七章 LR分析方法 第八章 语法制导翻译和中间代码生成 第九章 符号表 第一○章 代码优化 第一一章 代码生成

2 复习：第5章自顶向下语法分析方法 一、确定的自顶向下分析思想 二、LL(1)文法的判别 三、某些非LL(1)文法到LL(1)文法等价变换
四、不确定的自顶向下分析思想 五、确定的自顶向下分析方法

3 确定的自顶向下分析方法 当文法满足 LL(1)文法时，可进行确定的自顶向下分析
递归子程序法：对应文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串。 预测分析方法： 预测分析程序 先进后出栈 预测分析表

4 表驱动的预测分析程序模型

5 实现步骤： （1） 判断文法是否为LL(1)文法。 如果文法中含有左递归，必须先消除左递归 （2）构造预测分析表 ： Select(A  ) （3）列出预测分析过程

6 第6章：自底向上分析方法 自底向上分析方法，也称移进归约分析法 实现思想（是推导的逆过程）：
对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的可归约串时，就用该产生式的左部非终结符代替相应右部的文法符号串，称为归约。重复这一过程，直到归约到栈中只剩下文法的开始符号时，则分析成功。 关键问题

7 移进—规约分析（Shift-reduce parsing)
要点：建立符号栈，用来纪录分析的历史和现状，并根据所面临的状态，确定下一步动作是移进还是规约。 # S.R.P 符号栈 输入串 7 7

8 # S.R.P 符号栈 输入串 分析过程：把输入符号串从左向右一一地移进符号栈（一次移一个），检查栈中符号，当在栈顶的若干符号形成当前句型的可归约串时，就根据规则进行规约，将句柄从符号栈中弹出，并将相应的非终结符号压入栈内（即规则的左部符号），然后再检查栈内符号串是否形成新的可归约串，若有就再进行规约，否则移进符号。分析一直进行到读到输入串的右界符为止。最后，若栈中仅含有左界符号和识别符号，则表示分析成功，否则失败。 8 8

9 SaAcBe A b A Ab B d 例1：文法 输入串abbcde#分析

10 归约分析过程（移进归约）： 步骤 符号栈 输入符号串 动作 1 # abbcde# 移进 2 #a bbcde# 3 #ab bcde#
4 #aA 5 #aAb cde# 归约（A→Ab) 6 7 #aAc de# 8 #aAcd e# 归约（B→b） 9 #aAcB 10 #aAcBe 规约S→aAcBe 11 #S 接受

11 上述的每一步规约可以构造一颗语法树： A b A b S A b a c e B d B d 问题的提出：
①在构造语法树的过程中，何时规约？ 当可归约串出现在栈顶符号串中就可以规约。 ②如何知道在栈顶符号串中已经形成可归约串？ 通过自底向上分析算法中的优先关系来计算

12 自下而上分析的关键问题： 如何确定可归约串？
简单优先分析法：寻找句柄 算符优先分析法：寻找最左素短语

13 优先分析法又可分简单优先分析法和算符优先分析法。
一、自底向上优先分析法概述 优先分析法又可分简单优先分析法和算符优先分析法。 ①简单优先分析法：按一定原则求出文法中所有符号（终结符和非终结符）的优先关系，按这种关系求出句柄。（规范归约——从左向右的规约）； ②算符优先分析法：只考虑算符（终结符）之间的优先关系，不考虑非终结符之间的优先关系。按这种关系求出最左素短语。（不规范归约） 简单优先分析法：准确规范，但分析效率低，实际使用价值不大； 算符优先分析法：不规范，但分析速度快，适于实际使用。

14 句柄的定义： 令G是一文法，S是文法的开始符号，δ是文法G的一个句型。（为δ 确定可归约串）如果有SA 且 A，则称是句型δ相对于非终结符A的短语。 若有A，则称是句型 δ 相对A 的直接短语。一个句型的最左直接短语称为该句型的句柄。 句柄是自底向上句法分析中当前时刻需要规约的符号串。如果能够自动计算出当前的句柄，则可执行自动句法分析。 * +

15 二、简单优先分析法 x =. y 表示X与Y的优先关系相等 x > . y 表示X的优先性大于Y
1、优先关系的表示 x =. y 表示X与Y的优先关系相等 x > . y 表示X的优先性大于Y x <. y 表示X的优先性小于Y 对任意两个文法符号X、Y按其在句型中可能会出现的相邻关系来确定优先关系：  

16 确定优先关系的规则 （1）X =. Y 当且仅当G中存在产生式A …XY…（在语法树的同一层）
（2） X <. Y 当且仅当G中存在产生式A …XB…，且B Y…（ Y 在 X 的下一层） （3）X > . Y 当且仅当G中存在产生式A …BD…，且B …X和D Y… （ X在 Y 的下一层或X比 Y先归约——规范归约/最左归约 ） + + *

17 例：有文法G(S): S→bAb A→( B | a B→Aa ) 解：文法符号优先关系推导如下：   (1)   求=.关系: 由S→bAb ， A→( B， B→Aa ) b =. A， A =. b， (=. B， A =. a， a =. )

18 (2) 求<.关系： 由S→bAb 且A （B 可得 b <.( A  a 可得 b <. a
(2) 求<.关系： 由S→bAb 且A （B 可得 b <.( A  a 可得 b <. a 由A→( B 且B ( B… 可得 (<. ( B aa… 可得 (<. a B Aa ) 可得 (<. A ＋ ＋ ＋ ＋ ＋

19 由S→bAb，且A…) 可得 ) > . b A…B 可得 B > . b A a 可得 a > . b
A(B(Aa) …) A(B…B Aa (3) 求> .关系: 由S→bAb，且A…) 可得 ) > . b A…B 可得 B > . b A a 可得 a > . b 由B→Aa )，且A…) 可得 ) > . a Aa 可得 a > . a A…B 可得 B > . a ＋ ＋ ＋ ＋ ＋ +

20 所有符号>.# 优先关系矩阵表示法： S b A ( B a ) # >. =. <. 寻找句柄

21 简单优先文法的定义： （1）在文法符号集中，任意两个符号之间最多只有一种优先关系； （2）在文法中任意两个产生式没有相同的右部。

22 语法树结构如下： S b A （ B a ） S b A （ B a ） S b A （ B S b A a

23 (3) 当ab、aa出现在某一句型中，左边a在句柄中，则右边的a、b不可能在句柄中。因此有左边a >. b，左边a >. a。
从上图可以看出： (1) 当b( 、ba出现在某一句型中，则（和a在句柄中，b不在句柄中，则（和a必须先规约。因此b <.( ,b <.a。 (2) 同样可以看出，当(( ，(a ，(A出现在某一句型中，右边的( ，a，A出现在句柄中，左边的(不在句柄中。因此，左边(<.右边的(，左边(<. a，左边(<. b。 (3) 当ab、aa出现在某一句型中，左边a在句柄中，则右边的a、b不可能在句柄中。因此有左边a >. b，左边a >. a。

24 因此，可以根据文法符号之间的优先关系确定句柄。
在规范归约（最左归约）过程中，出现在栈顶的优先级相同的连续符号串就是句柄。

25 简单优先分析法的操作步骤 首先根据已知优先文法构造优先关系 矩阵，设置符号栈S，算法步骤如下：P105 分析器结构: 分析程序 优先关系矩阵
输入串 # 符号栈 分析程序 # 优先关系矩阵

26 三、算符优先分析 1) 这是一种经典的自底向上分析法，简单直观，并被广泛使 用，开始主要是对表达式的分析，现在已不限于此。可以
用于一大类上下无关的文法. 2) 称为算符优先分析是因为这种方法是仿效算术式的四则运算 而建立起来的，作算术式的四则运算时，为了保证计算结果 和过程的唯一性，规定了一个统一的四则运算法则，规定运 算符之间的优先关系。 1.乘除的优先大于加减 2.同优先级的运算符左大于右 3.括号内的优先级大于括号外 于是： 4+8-6/2*3 运算过程和结果唯一。

27 ①简单优先分析法：求出文法中所有符号（终结符和非终结符）的优先关系，按这种关系求出句柄。（规范归约——从左向右的规约）；
②算符优先分析法：只考虑算符（终结符）之间的优先关系，不考虑非终结符之间的优先关系。按这种关系求出最左素短语。（不规范归约） 算符优先关系的定义

28 仿效四则运算过程，预先规定相邻终结符之间的优 先关系，然后利用这种优先关系来确定句型的可归约串 ， 并进行规约。
3)算符优先分析的特点: 仿效四则运算过程，预先规定相邻终结符之间的优 先关系，然后利用这种优先关系来确定句型的可归约串 ， 并进行规约。 4)分析器结构: 输入串 # 符号栈 分析程序 # 优先关系矩阵

29 (2) 算符优先文法的定义 【算符文法定义】 设有一文法G，如果G中没有形如A→…BC…的产生式，其中B和C为非终结符，则称G为算符文法(或称OG文法)。

30 〖要点〗任何一个产生式中都不包含两个非终结符相邻的情况，就是是算符文法。 或：两个非终结符之间一定通过1个或多个终结符相连。
性质1：在算符文法中任何句型都不包含两个相邻的非终结符。 性质2：如果Ab或（bA）出现在算符文法的句型中，其中AVN . b  VT,，则中任何含b的短语必含有A。 （含b的短语必含A，含A的短语不一定含b）

31 【算符优先关系的定义 】 设G是一个算符文法，a和b是任意两个终结符，A，B，C是非终结符，算符优先关系如下：
(1)a=.b当且仅当G中含有形如A→…ab…或A→…aBb…的产生式; (2) a <.b当且仅当G中含有形如A→…aB…的产生式，且Bb…或BCb…； (3) a >. b当且仅当G中含有形如A→…Bb…的产生式，且B…a或B…aC 。 与简单优先关系区别：区分终结符与非终结符，非终结符忽略不计 ＋ ＋ ＋ ＋

32 【算符优先文法的定义】 设有一不含产生式的算符文法G，如果对任意两个终结符a，b之间至多只有=. ，<.和>.三种关系的一种成立，则称G是一个算符优先文法(也称OPG文法)。 即a =. b，a <.b，a >. b只有一种成立，但允许a <.b，b <. a同时存在。 例：E→E+E | E*E | (E) | i 证明不是OPG文法。

33 【算符优先文法的定义】 设有一不含产生式的算符文法G，如果对任意两个终结符a，b之间至多只有=. ，<.和>.三种关系的一种成立，则称G是一个算符优先文法(也称OPG文法)。 A →aB ，a＝+，B＝E， B Cb…，b＝* 即a =. b，a <.b，a >. b只有一种成立，但允许a <.b，b >. a同时存在。 例：E→E+E | E*E | (E) | i 证明不是OPG文法。 因为：E→E+E ， EE*E 则有 + <. * 又因为：E→E*E, EE+E 则有 + >. * 所以不是算符优先文法。 ＋ ＋ A →Bb ， B＝E ， b＝*， B  … aC，a＝+

34 算符优先分析法的实现： # 分析程序 优先关系矩阵 符号栈 输入串 当栈内终结符的优先级＜＝栈外的终结符的优先级时，移进；栈内终结符的优先级＞栈外的终结符的优先级时，归约。表明找到了素短语的尾，再往前找其头，并进行规约。

35 (3) 算符优先关系表 构造步骤： （根据算符优先关系的定义 ） 用表格形式来表示各终结符号的优先关系，这种表称为优先表。
(3) 算符优先关系表 用表格形式来表示各终结符号的优先关系，这种表称为优先表。 构造优先关系表的方法：①按照定义来构造 ②按关系图来构造 构造步骤： （根据算符优先关系的定义 ） 定义两个集合：firstVT集合lastVT集合。 firstVT(B)={b|Bb… 或 BCb…} lastVT(B)={a|B…a 或 B…aC} + + + +

36 三种优先关系的计算： 则 a =. b 则 a <. b a) =. 关系： A→…ab… A→…aBb… b) <.关系：
对于每个非终结符B的firstVT(B)有形如A→…aB…中，对每一个 b∈firstVT(B)。 则 a =. b 则 a <. b

37 c) >.关系： 每个非终结符B的lastVT(B)有形如A→…Bb…中，对每一个a∈lastVT(B) 则a >. b 例：为文法 E’→#E# T→F E→E+T F→P↑F|P E→T P→（E ） T→T*F P→i 构造算符优先关系表

38 IF xi和xi+1均为终结符,THEN 置 xi=.xi+1 IF i≤n-2，且xi和xi+2都为终结符号但
构造优先关系矩阵的算法 FOR 每条规则U→x1x2…xn DO FOR i:=1 TO n-1 DO BEGIN IF xi和xi+1均为终结符,THEN 置 xi=.xi+1 IF i≤n-2，且xi和xi+2都为终结符号但 xi+1为非终结符号 THEN 置 xi=.xi+2 IF xi为终结符号xi+1为非终结符号 THEN FOR FIRSTVT(xi+1)中的每个b DO 置xi<.b IF xi为非终结符号xi+1为终结符号 THEN FOR LASTVT(xi)中的每个a DO 置a>.xi+1 END .

39 构造FIRSTVT(U)的算法 1)若有规则U → b…或U → Vb…(存在Ub…或UVb…) 则b∈FIRSTVT(U)
+ 2)若有规则U → V…且b∈FIRSTVT(V), 则b∈FIRSTVT(U) 说明:因为Vb…或VWb…,所以有UV…b…或 UV… Wb… +

40 F[U,b]=TRUE iff b∈FIRSTVT(U)
具体方法如下: 设一个栈S和一个二维布尔数组F F[U,b]=TRUE iff b∈FIRSTVT(U) PROCEDURE INSERT(U,b) IF NOT F[U,b] THEN BEGIN F[U,b]:=TRUE 把(U,b)推进S栈 /* b∈FIRSTVT(U) */ END BEGIN {main} FOR 每个非终结符号U和终结符b DO F[U,b]:=FALSE /*赋初值*/ FOR 每个形如U→b…或U→Vb… 的规则 DO INSERT(U,b)

41 WHILE S栈非空 DO BEIGN 把S栈的顶项弹出,记为 (V,b)/* b∈FIRSTVT(V)*/ FOR 每条形如U→V…的规则 DO INSTER(U,b); /* b∈FIRSTVT(U)*/ END OF WHILE END 上述算法的工作结果是得到一个二维的布尔数组F,从F 可以得到任何非终结符号U的FIRSTVT FIRSTVT(U)={b|F[U,b]=TRUE}

42 构造LASTVT(U)的算法 1.若有规则U→…a或U→=…aV,则a∈LASTVT(U)
2.若有规则U→…V,且a∈LASTVT(V)则a∈LASTVT(U) 设一个栈ST,和一个布尔数组B PROCEDURE INSERT(U,a) IF NOT B[U,a] THEN BEGIN B[U,a]→TRUE;把(U,a)推进ST栈; END;

43 BEGIN FOR 每个非终结符号U和终结符号a DO B[U,a]:=FALSE; FOR 每个形如U→…a或U→…aV的规则 DO INSERT (U,a); WHILE ST栈非空 DO 把ST栈的栈顶弹出,记为(V,a); FOR 每条形如U→…V的规则 DO INSERT(U,a); END OF WHILE; END;

44 firstVT(B)={b|Bb… 或 BCb…}
解: (1)求firstVT和lastVT集 firstVT(E’)={#} firstVT(E)={+,*,↑, ( , i ) firstVT(T)={*,↑, ( , i ) firstVT(F)={↑, ( , i ) firstVT(P)={ ( , i ) lastVT(E’)={#} lastVT(E)={+,*,↑, ) , i } lastVT(T)={*,↑, ) , i } E’= #E# E’ #… EE+T ETT*F ETFP↑F ETP(E) i lastVT(B)={a|B…a 或 B…aC}

45 lastVT(F)={ ) ,↑, i } lastVT(P)={ i , ) } (2) 求 =.关系 E’→#E# # =. # P→(E) (=. ) (3) 求 <. 关系 E’ → #E# 则 # <.firstVT(E) 所以 # <.+, # <.*, # <.↑, # <. ( ， # <.i

46 E’ →E+T 则 + <.firstVT(T)
T→T*F 则 * <. firstVT(F) 所以 * <. ↑, * <. ( , * <. i F→P↑F 则↑ <. firstVT(F) 所以 ↑ <. ↑, ↑ <. ( , ↑ <. i P→（E ) 则（ <. firstVT(E) 所以 (<. +, (<. *, (<. ↑, (<.( , (<. i

47 (4) 求 >.关系 E’ →#E# 则 lastVT(E) >. # 所以 + >. #, * >. # ，↑ >. # , ) >. #, i >. # E→E+T 则lastVT(E) >. + 所以 + >. +, * >. +, ↑ >. + , ) >. +, i >. + T→T*F 则lastVT(T) >. * 所以 * >. *, ↑ >. *, i >. *, ) >. * F→P↑F 则lastVT(P) >. ↑ 所以 i >. ↑, ) >. ↑ P→(E) 则lastVT(E) >.) 所以 + >.) , * >.) , ↑ >.) , i >.) , ) >.)

48 算符优先关系表 + * ↑ i ( ) # >. <. =.

49 算符优先分析法的实现： 详见P117 图6.8 # 分析程序 优先关系矩阵 符号栈 输入串 当栈内终结符的优先级＜＝栈外的终结符的优先级时，移进；栈内终结符的优先级＞栈外的终结符的优先级时，归约。表明找到了素短语的尾，再往前找其头，并进行规约。 49 49

50 实例比较 算符优先归约 （P115表6.8） 规范归约（P115表6.8）
算符优先分析法的可归约串不是句柄而是最左素短语。 P116 “算符优先分析的关键是如何找最左素短语…… ”

51 五、最左素短语 定义：设有文法G[S]，其句型的素短语是一个短语，它至少包含一个终结符，并除自身外不包含其它素短语，最左边的素短语称最左素短语。 与句柄的区别：至少包含一个终结符。（从而去掉了单非终结符的归约） 例：文法G[E]: E→E+T|T T→T*F|F F→P↑F|P P→（E）|i 句型#T+T*F+i#的语法树如下：

52 E T + F * P i 根据语法树可知： 句型#T+T*F+i#的短语有： T — 相对非终结符E的短语 T*F — 相对非终结符T的短语 T+T*F — 相对非终结符E的短语 i — 相对非终结符P、F、T的短语 T+T*F+i —相对非终结符E的短语

53 根据素短语的定义可知： i和T*F为素短语。 其中：T+T*F (含其他T*F素短语)和 T+T*F+i 不是素短语。 T*F为最左素短语。 T为句柄——最左直接短语

54 算符优先分析法的关键： 如何确定当前句型的最左素短语？ 算符文法的任一句型形式为#N1a1N2a2…NnanNn+1# (NiVN 或Ni = , ai  VT) 定理：一个OPG句型的最左素短语是满足下列条件的 最左子串：aj-1Njaj…NiaiNi+1ai+1 其中 aj-1<.aj aj=.aj+1, aj+1=. aj+2 ,…, ai-2= .ai-1, ai-1=.ai ai>. ai+1

55 算符优先分析法的实现： 根据该定理,要找句型的最左素短语就是要找满足 上述条件的最左子串. 详见P117 图6.8
基本部分是找句型的最左子串（最左素短语） 并进行规约。

56 六、优先函数： 矩阵表示法(空间大) 优先函数法 算符优先关系表示法 1、优先函数的定义： 当a =. b，令f(a)=g(b)

57 2、优先函数的构造 构造规则 a) 对终结符a∈VT(包括#号)令f(a)=g(a)=1(初始化) b)如果a >. b，而f(a)≤g(b)，则令f(a)=g(b)+1 c)如果a <.b，而f(a)≥g(b)，则令g(b)= f(a)+1 d)如果a=.b，而f(a)≠g(b)则令min{f(a),g(b)}=max{f(a),g(b)} 重复b)~d)过程，直到收敛。若重复过程中有一个值>2n(n为终结符个数)，则该文法不存在算符优先函数。

58 例1：有优先表如下，构造优先函数。 + *  >. <. 【解】(1) 赋初值 + *  f 1 g

59 (2) 对a>.b关系有： + *  >. <. ＋>.＋ f(+)=g(+)+1 + *  f 2 1 g * >.＋ * >. *  >.＋  >. * + *  f 2 1 g + *  f 2 g 1

60 (3) 对a <.b关系有 + *  >. <. ＋ <. * g(*)= f(+)+1 + <.  g()=f(+)+1 + *  f 2 g 1 3 (4) 对a =. b没有 重复过程(2)、(3) * <.   <.  + *  f 2 g 1 3

61 (2) 对a>.b关系 + *  >. <. + >. + + *  f 2 g 1 3  >  >. * f()=g(*)+1 * >.+ * >.* f(*)=g(*)+1 + *  f 2 4 g 1 3 + *  f 2 4 g 1 3

62 (3) 对a <.b关系 + <.* + <. + *  >. <. + *  f 2 4 g 1 3 * <.  <. g()=f()+1 + *  f 2 4 g 1 3 5

63 重复以上过程得： + *  f 2 4 g 1 3 5 结果同上步，因此收敛 所以存在优先函数为： + *  f 2 4 g 1 3 5

64 例2：已知优先关系表，构造优先函数。 + *  i ( ) # >. <. 

65 构造过程 (1) 初始化 + *  i ( ) # f 1 g (2) 对a>.b关系
+> >.) +>.# + *  i ( ) # f 2 1 g

66 *>.+ *>.* *>.) *>.#
 i ( ) # f 2 1 g >.+ >.*  >.) >.# + *  i ( ) # f 2 1 g

67 i >.+ i >.* i>. i >.) i >.#
( ) # f 2 1 g )>.+ ) >.* ) >. ) >.) ) >.# + *  i ( ) # f 2 1 g

68 (3) 对a<.b关系 + <.* + <.  + <.i <.( + *  i ( ) # f 2 1 g 3 * <. * <.i * <.( + *  i ( ) # f 2 1 g 3

69  <.  <.i  <.( + *  i ( ) # f 2 1 g 3 ( <.+ ( <.* ( <.  ( <.i ( <.( + *  i ( ) # f 2 1 g 3

70 (4) 对a  b关系 #<.+ # <.* # <.  # <.i # <.( + *  i ( )
f 2 1 g 3 (4) 对a  b关系 (  ) #  # + *  i ( ) # f 2 1 g 3

71 第二次重复以上过程(2,3,4步） 对于a>.b关系 + *  i ( ) # f 3 4 1 g 2 对于a <.b关系 + *  i ( ) # f 3 4 1 g 2 5

72 对于a  b关系 + *  i ( ) # f 3 4 1 g 2 5 第三次重复以上过程 对于a >. b关系 + *  i ( ) # f 3 5 6 1 4 g 2

73 对于a <.b关系 + *  i ( ) # f 3 5 6 1 4 g 2 对于a  b关系 + *  i ( ) # f 3 5 6 1 4 g 2

74 第四次重复过程 对于a >. b关系 + *  i ( ) # f 3 5 7 1 g 2 4 6 对于a <.b关系 + *  i ( ) # f 3 5 7 1 g 2 4 6

75 第五次重复过程 对于a  b关系 + *  i ( ) # f 3 5 7 1 g 2 4 6 + *  i ( ) # f 3 5

76 第五次结果同第四次，表示收敛了。 因此优先函数为： + *  i ( ) # f 3 5 7 1 g 2 4 6

77 作业 P122 练习1、2