编译原理 - 自下而上的语法分析ppt课件

1、第五章第五章 语法分析语法分析自下而上分析自下而上分析内容内容 自下而上分析基本问题自下而上分析基本问题 算符优先分析算符优先分析5.1 自下而上分析基本问题自下而上分析基本问题 自下而上分析基本问题自下而上分析基本问题 归约归约 规范归约规范归约 符号栈的使用符号栈的使用 语法树的表示语法树的表示 算符优先分析算符优先分析5.1.1 自下而上分析自下而上分析 自下而上分析自下而上分析bdbaceSABAabbcdeaAbcde (A b)aAcde (A Ab)aAcBe (B d)S (S aAcBe)从输入字符的角度而言从输入字符的角度而言从输入开始从输入开始逐步进行逐步进行“归约归约”

2、直至归约到文法的开始符号直至归约到文法的开始符号从语法树的角度而言从语法树的角度而言从语法树的末端开始从语法树的末端开始步步向上步步向上“归约归约”直到根结直到根结5.1.2 自下而上分析法的基本思想自下而上分析法的基本思想 自下而上分析法自下而上分析法 是一种是一种“移进移进-归约法归约法 基本思想基本思想 用一个寄存符号的先进后出栈用一个寄存符号的先进后出栈 把输入符号一个一个地移进到栈里把输入符号一个一个地移进到栈里 当栈顶形成某个产生式的候选式时，把栈当栈顶形成某个产生式的候选式时，把栈顶的这一部分替换成顶的这一部分替换成(归约为归约为)该产生式的左该产生式的左部符号部符号5.1.3

3、先进后出栈先进后出栈 例：设文法例：设文法GSGS： (1) S (1) S aAcBe aAcBe (2) A (2) A b b (3) A (3) A Ab Ab (4) B (4) B d d 试对试对abbcdeabbcde进行进行“移进移进- -归约分析。归约分析。a bbcdeba bcdeAa bcdebAa cdeAa cdecAa dedcAa eabbcdeeBcAa S 5.1.4 移进移进-归约分析归约分析例：设文法例：设文法GSGS： (1) S (1) S aAcBe aAcBe (2) A (2) A b b (3) A (3) A Ab Ab (4) B (4

4、) B d d试对试对abbcdeabbcde进行进行“移进移进- -归约分析。归约分析。步步骤骤: :1 12 23 34 45 56 67 78 89 91 10 0动动作作: :进进a a进进b b归归( (2 2) )进进b b归归( (3 3) )进进c c进进d d归归( (4 4) )进进e e归归( (1 1) )e ed dB BB Bb bc cc cc cc cb bA AA AA AA AA AA AA Aa aa aa aa aa aa aa aa aa aS S5.1.5 归约的语法树分析法归约的语法树分析法 分析树和语法树分析树和语法树 不一定一致不一定一致 自下

5、而上分析过程自下而上分析过程 边输入单词符号，边输入单词符号，边归约边归约 核心问题核心问题 识别可归约串识别可归约串bdbaceSABA5.1.6 规范归约简述规范归约简述 定义：令定义：令G G是一个文法，是一个文法，S S是文法的开始符是文法的开始符号，假定号，假定是文法是文法G G的一个句型，如果的一个句型，如果有有 且且 AS*A那么那么称是句型称是句型相对于非终结符相对于非终结符A A的的短语。短语。 特别是，如果有特别是，如果有A A, ,则称则称是句型是句型相对于规则相对于规则A A的直接短语的直接短语 一个句型的最左直接短语称为该句型一个句型的最左直接短语称为该句型的句柄的句

6、柄5.1.7 规范归约例一规范归约例一 例：文法GE： EE+T|T TT*F|F F(E)|F|id 考虑文法GE上的句子id1+id2*id3 其最右推导和分析树如图5.1(a)、(b)所示图5.1 id1+id2*id3的最右推导、分析树与短语(a) 最右推导；(b) 分析树；(c) 短语 (a) (b) (c)E1 (1)= E2 + T1 (2)= E2 + T3 * F2 (3)= E2 + T3 * id3 (4)= E2 + F3 * id3 (5)= E2 + id2 * id3 (6)= T2 + id2 * id3 (7)= F1 + id2 * id3 (8)= id1

7、 + id2 * id3 (9)E1E2T1T2F1id1T3*F2F3id2id3 id1+id2*id3(E1) id2*id3(T1) id1(E2, T2, F1) id2(T3, F3) id3(F2)直接短语 ：id1(F1)、 id2(F3)、id3(F2)句柄 ：id1(F1)短语： 归约的分析树归约的分析树 分析树的叶子与短语、直接短语和句柄有下述关系分析树的叶子与短语、直接短语和句柄有下述关系 短语短语 以非终结符为根的子树中所有从左到右排列的叶子以非终结符为根的子树中所有从左到右排列的叶子 直接短语直接短语 只有父子关系的树中所有从左到右排列的叶子只有父子关

8、系的树中所有从左到右排列的叶子 树高为树高为2 句柄句柄 最左边父子关系树中所有从左到右排列的叶子最左边父子关系树中所有从左到右排列的叶子 句柄是唯一的句柄是唯一的 短语短语以非终结符为根的子树中所有从左到右排列的叶子以非终结符为根的子树中所有从左到右排列的叶子从文法开始符号经过从文法开始符号经过0步推导得到步推导得到E1，从，从E1经过若干步推导得到经过若干步推导得到id1+id2*id3，所以，所以id1+id2*id3是句型是句型id1+id2*id3相对于相对于E1的短语的短语id1+id2不是句型不是句型id1+id2*id3中相对于任何非终结符的短语，因为找不中相对于

9、任何非终结符的短语，因为找不到任何一个非终结符，它的子树中的所有叶子构成到任何一个非终结符，它的子树中的所有叶子构成id1+id2(a) (b) (c)E1 (1)= E2 + T1 (2)= E2 + T3 * F2 (3)= E2 + T3 * id3 (4)= E2 + F3 * id3 (5)= E2 + id2 * id3 (6)= T2 + id2 * id3 (7)= F1 + id2 * id3 (8)= id1 + id2 * id3 (9)E1E2T1T2F1id1T3*F2F3id2id3 id1+id2*id3(E1) id2*id3(T1) id1(E2, T2, F

10、1) id2(T3, F3) id3(F2)直接短语 ：id1(F1)、 id2(F3)、id3(F2)句柄 ：id1(F1)短语： 直接短语与句柄直接短语与句柄 只有父子关系的树中所有从左到右排列的叶子只有父子关系的树中所有从左到右排列的叶子 从考虑推导从考虑推导E1 E2+id2*id3 T2+id2*id3 F1+id2*id3 id1+id2*id3 id1是相对于非终结符是相对于非终结符E2、T2和和F1的短语的短语 特别地，相对于特别地，相对于F1的直接短语，也是句柄的直接短语，也是句柄(a) (b) (c)E1 (1)= E2 + T1 (2)= E2 + T3 *

11、 F2 (3)= E2 + T3 * id3 (4)= E2 + F3 * id3 (5)= E2 + id2 * id3 (6)= T2 + id2 * id3 (7)= F1 + id2 * id3 (8)= id1 + id2 * id3 (9)E1E2T1T2F1id1T3*F2F3id2id3 id1+id2*id3(E1) id2*id3(T1) id1(E2, T2, F1) id2(T3, F3) id3(F2)直接短语 ：id1(F1)、 id2(F3)、id3(F2)句柄 ：id1(F1)短语：EFFTTTi1+*EFi3i25.1.8 规范归约例二规范归约例二例：考虑文法

12、例：考虑文法GEGEE ET|E+T TT|E+T TF|TF|T* *F FF F(E)|I(E)|I和句型和句型i1i1* *i2+i3i2+i3在一个句型对应的语法树中，以某非终结符为根的两代在一个句型对应的语法树中，以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语，如果子树只有两代，则该短语就非终结符的一个短语，如果子树只有两代，则该短语就是直接短语。是直接短语。E E E+T E+T E+F E+F E+i3 E+i3 T+i3 T+i3 T T* *F+i3 F+i3 T T* *i2+i3 i

13、2+i3 F F* *i2+i3 i2+i3 i1 i1* *i2+i3i2+i3短语：短语： i1i1，i2i2，i3i3， i1i1* *i2i2， i1i1* *i2+i3i2+i3直接短语：直接短语： i1i1，i2i2，i3i3句柄：句柄： i1i15.1.2 规范归约简述规范归约简述 可用句柄来对句子进行归约 例：设文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B d句型 归约规则abbcde (2) A baAbcde (3) A AbaAcde (4) B daAcBe (1) S aAcBe SbdbaceSABA5.1.2 规范归约简述规范归

14、约简述 定义：假定是文法G的一个句子，我们称序列 n， n-1， ，0 是一个规范归约，如果此序列满足： 1 n= 2 0为文法的开始符号，即0=S 3 对任何i，0 i n， i-1是从i经把句柄替换成为相应产生式左部符号而得到的。5.1.2 规范归约简述规范归约简述 把上例倒过来写，则得到：把上例倒过来写，则得到： S aAcBe aAcde aAbcde abbcde 显然这是一个最右推导。显然这是一个最右推导。 规范归约是关于是一个最右推导的逆过程规范归约是关于是一个最右推导的逆过程 最左归约最左归约 规范推导规范推导 由规范推导推出的句型称为规范句型。由规范推导推出的句型称为规范句型

15、。 规范归约的中心问题：确定句型的句柄。规范归约的中心问题：确定句型的句柄。5.1.2 规范归约简述规范归约简述 最右推导，推导的每一步结果都是一个右句最右推导，推导的每一步结果都是一个右句型。该推导即分析树型。该推导即分析树 “剪句柄的全过程。剪句柄的全过程。SaAeAb c dBbSaAeAb c dBSaAedBSaAeB(a)(b)(c)(d)S(e)图3.18 剪句柄的过程(a) 句子；(b) 剪去b之后；(c) 剪去Abc之后；(d) 剪去d之后；(e) 开始符号 5.1.3 符号栈的使用与语法树的表示符号栈的使用与语法树的表示 从分析树上直观地看，“剪句柄的方法十分简单。但是若在

16、语法分析器中实现剪句柄，则有两个问题必须解决： 确定右句型中将要归约的子串(确定句柄)； 确定如何选择正确的产生式进行归约。 具体实现采用移进归约方法，用一个栈“记住将要归约句柄的前缀，并用一个分析表来确定何时栈顶已形成句柄，以及形成句柄后选择哪个产生式进行归约。5.1.3 符号栈的使用与语法树的表示符号栈的使用与语法树的表示 在移进归约分析模式中，符号栈的使用有以下四种操作形式。 移进(shift): 把当前输入中的下一个终结符移进栈； 归约(reduce): 句柄在栈顶已形成，用适当产生式左部代替句柄； 接受(accept): 宣告分析成功； 报错(error): 发现语法错误，调用错误恢

17、复例程。 考察文法GS： SaABe Ab AAbc Bd 的输入序列abbcde，移进归约方法分析的符号栈变化过程如下所示。步骤栈内容当前输入动作(0)(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)#a#ab#aA#aAb#aAbc#aA#aAd#aAB#aABe#Sabbcde#bbcde#bcde#bcde#cde#de#de#e#e#shiftshiftreduced by Abshiftshiftreduced by AAbcshiftreduced by Bdshiftreduced by SaABeaccept5.2 算符优先分析算符优先分析 自下而上分析基本问题

18、自下而上分析基本问题 算符优先分析算符优先分析 算符优先文法及优先表构造算符优先文法及优先表构造 算符优先分析算法算符优先分析算法 优先函数优先函数 算符优先分析中的出错处理算符优先分析中的出错处理5.2 算符优先分析算符优先分析 考虑二义文法文法G(E)： G(E)： E i| E+E|E-E|E*E|E/E|(E) 它的句子有几种不同的规范归约。 归约即计算表达式的值。归约顺序不同，则计算的顺序也不同，结果也不一样。 起决定作用的是相邻的两个算符之间的优先关系。如果规定算符的优先次序，并按这种规定进行归约，则归约过程是唯一的。 所谓算符优先分析法就是定义算符之间的某种优先关系，借助于这种关

19、系寻找“可归约串和进行归约。5.2 算符优先分析算符优先分析 定义任何两个可能相继出现的终结符a与b的优先关系： 三种关系 a b a的优先级低于b a b a的优先级等于b a b a的优先级高于b 留意：与数学上的、=不同，a b并不意味着b a5.2.1 算符优先文法及优先表构造算符优先文法及优先表构造 一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部： QR 则我们称该文法为算符文法。 商定： a、b代表任意终结符； P、Q、R代表任意非终结符； 代表由终结符和非终结符组成的任意序列，包括空字。 假定G是一个不含-产生式的算符文法。对于任何

20、一对终结符a、b，我们说： 1. ab 当且仅当文法G中含有形如Pab或PaQb的产生式； 如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一： a b，a b， a b 则称G是一个算符优先文法。2. a b 当且仅当G中含有形如PaR的产生式，而R b或R Qb；3. a b 当且仅当G中含有形如PRb的产生式，而R a或R aQ。5.2.1 算符优先文法及优先表构造算符优先文法及优先表构造 例:考虑下面的文法GE： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i 由第(4)条规则，有 ( )； 由规则EET和TT*

21、F， 有 *； 由(2)和(3)，可得* ； 由(1)EET和E E+T，可得+ +； 由(3)FPF和F PF，可得 。 由(4)P(E)和 EE+TT+TT*F+TF*F+T PF*F+TiF*F+T 有 ( +、( *、( 和( i。5.2.1 算符优先文法及优先表构造算符优先文法及优先表构造 优先关系表（优先关系表（#为终结符）为终结符） 从算符优先文法从算符优先文法G构造优先关系表的算法：构造优先关系表的算法： 通过检查通过检查G的每个产生式的每个候选式，可找出的每个产生式的每个候选式，可找出所有满足所有满足ab的终结符对。的终结符对。 确定满足关系确定满足关系 和和 的所有终结符对

22、：的所有终结符对： 首先需要对首先需要对G的每个非终结符的每个非终结符P构造两个集合构造两个集合FIRSTVT(P)和和LASTVT(P)：5.2.1 算符优先文法及优先表构造算符优先文法及优先表构造FIRSTVT Pa PaPQaaVQVTN( ) |,或而,|)(NTVQVaaQPaPaPLASTVT而或5.2.1 算符优先文法及优先表构造算符优先文法及优先表构造有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系 和 的所有终结符对。如：假定有个产生式的一个候选形为 aP 那么，对任何bFIRSTVT(P)，有 a b。假定有个产生式的一个候选形为 Pb 那么，对任何aLAS

23、TVT(P)，有 a b。FIRSTVT(P)的算法 构造集合构造集合FIRSTVT(P)的算法：的算法： 按其定义，可用下面两条规则来构造集按其定义，可用下面两条规则来构造集合合FIRSTVT(P)： 1. 若有产生式若有产生式Pa或或PQa，则，则aFIRSTVT(P)； 2. 若若aFIRSTVT(Q)，且有产生式，且有产生式PQ，则则aFIRSTVT(P)。FIRSTVT(P)的算法 数据结构： 布尔数组FP，a，使得FP，a为真的条件是，当且仅当aFIRSTVT(P)。开始时，按上述的规则(1)对每个数组元素FP，a赋初值。 栈STACK，把所有初值为真的数组元素FP，a的符号对(P

24、，a)全都放在STACK之中。 运算： 如果栈STACK不空，就将顶项逐出，记此项为(Q，a)。对于每个形如PQ的产生式，若FP，a为假，则变其值为真且将(P，a)推进STACK栈。 上述过程必须一直重复，直至栈STACK拆空为止。FIRSTVT(P)的算法 如果把这个算法稍为形式化一点，我们可得如下所示的一个程序(包括一个过程和主程序)： 过程 PROCEDURE INSERT(P，a)； IF NOT FP，a THEN BEGIN FP，a:=TRUE； 把(P，a)下推进STACK栈 END；FIRSTVT(P)的算法主程序：BEGIN FOR 每个非终结符P和终结符a DO FP，a

25、:=FALSE； FOR 每个形如Pa或PQa的产生式 DO INSERT(P，a)； WHILE STACK 非空 DO BEGIN 把STACK的顶项，记为(Q，a)，上托出去； FOR 每条形如PQ的产生式 DOINSERT(P，a)；END OF WHILE；ENDFIRSTVT(P)的算法 这个算法的工作结果得到一个二维数组F，从它可得任何非终结符P的FIRSTVT。 FIRSTVT(P)a | FP，a=TRUE 同理，可构造计算LASTVT的算法。5.2.1 算符优先文法及优先表构造算符优先文法及优先表构造 使用每个非终结符P的FIRSTVT(P)和LASTVT(P)，就能够构造

26、文法G的优先表。构造优先表的算法是： FOR 每条产生式PX1X2Xn DO FOR i:=1 TO n-1 DO BEGIN IF Xi和Xi+1均为终结符 THEN 置XiXi+1 IF in-2且Xi和Xi+2都为终结符 但Xi+1为非终结符 THEN 置XiXi+2； IF Xi为终结符而Xi+1为非终结符 THENFOR FIRSTVT(Xi+1)中的每个a DO 置 Xi a； IF Xi为非终结符而Xi+1为终结符 THEN FOR LASTVT(Xi)中的每个a DO 置 a Xi+1 END5.2.1 算符优先文法及优先表构造算符优先文法及优先表构造 例: 考虑下面的文法GE

27、： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i 1. 计算文法G的FIRSTVT和LASTVT; 2. 构造优先关系表; 3. G是算符优先文法吗?+ * ()iE TFP(,)(,*,)(,)(,*,)(iPFIRSTVTiEFIRSTVTiFFIRSTVTiTFIRSTVT+ * ()iE T F P ),)(),*,)(),)(),*,)(iPLASTVTiELASTVTiFLASTVTiTLASTVT G的算符优先关系表：的算符优先关系表： 结论结论: G是算符优先文法是算符优先文法5.2.2 算符优先分析算法算符优先分析算法

28、 为了解决在算符优先分析过程中如何寻找到可归约串的问题，引进最左素短语的概念。 一个文法G的句型的素短语是指这样一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。 最左素短语是指处于句型最左边的那个素短语。考虑下面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i句型：T+F*P+i短语：T+F*P+i, T, F， P, F*P, i, T+F*P直接短语：T, F, P, i句柄：T素短语： F*P, i最左素短语： F*P5.2.2 算符优先分析算法算符优先分析算法EEF+*TiFTFTP+ET

29、P5.2.2 算符优先分析算法算符优先分析算法 算符优先文法句型(括在两个之间)的一般形式写成： #N1a1N2a2NnanNn+1# 其中，每个ai都是终结符，Ni是可有可无的非终结符。 定理： 一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串 NjajNiaiNi+1， aj-1 aj aj aj+1，ai-1 ai ai ai+15.2.2 算符优先分析算法算符优先分析算法 算符优先分析法是一种广为应用、行之有效的方法。算符优先分析法是一种广为应用、行之有效的方法。 用于分析各类表达式用于分析各类表达式 ALGOL 60 算符优先分析法特点：算符优先分析法特点： 优点优点

30、: 简单，快速简单，快速 缺陷缺陷: 可能错误接受非法句子，能力有限可能错误接受非法句子，能力有限. 算符优先分析算法：算符优先分析算法： 使用一个符号栈使用一个符号栈S，用它寄存终结符和非终结符，用它寄存终结符和非终结符，k代表代表符号栈符号栈S的使用深度。的使用深度。5.2.2 算符优先分析算法算符优先分析算法1 k:=1; Sk:=#;2 REPEAT3 把下一个输入符号读进a中；4 IF SkVT THEN j:=k ELSE j:=k-1;5 WHILE Sj a DO6 BEGIN7 REPEAT8 Q:=Sj;9 IF Sj-1VT THEN j:=j-1 ELSE j:=j-2

31、10 UNTIL Sj Q;11 把Sj+1Sk归约为某个N；12 k:=j+1;13 Sk:=N14 END OF WHILE;15 IF Sj a OR Sja THEN16 BEGIN k:=k+1; Sk:=a END17 ELSE ERROR /*调用出错诊察程序*/18 UNTIL a=#5.2.2 算符优先分析算法算符优先分析算法 在算法的工作过程中，若出现j减1后的值小于等于0时，则意味着输入串有错。在正确的情况下，算法工作完毕时，符号栈S应呈现：# N #。 算法的第11行中的N是指那样一个产生式的左部符号，此产生式的右部和Sj+1Sk 构成如下一一对应关系：自左至右，终结符

32、对终结符，非终结符对非终结符，而且对应的终结符相同。由于非终结符对归约没有影响，因此，非终结符根本可以不进符号栈S。5.2.2 算符优先分析算法算符优先分析算法 算符优先分析一般并不等价于规范归约算符优先分析一般并不等价于规范归约EE+*iTP+iPiPiPiEEF+*TiFTFTP+ETiFPPiP5.2.3 优先函数优先函数 把每个终结符与两个自然数f()与g()相对应，使得 假设1 2，则f(1) g(2) f称为入栈优先函数，g称为比较优先函数。 优点:便于比较，节省空间； 缺陷:原来不存在优先关系的两个终结符，由于自然数相对应，变成可以比较的。要进行一些特殊的判断。5.2.3 优先函数优先函数 文法GE (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i 的优先函数如下表：+ * ()i#F 2 4 4 0 6 6 0G 1 3 5 5 0 5 0 有许多优先关系表不存在优先函数，如： 不存在对应的优先函数f和g 假定存在f和g，则有 f(a)=g(a)，f(a)g(b)， f(b)=g(a)，f(b)=g(b) 导致如下矛盾: f(a) g(b) = f(b) = g(a) = f(a) 如果优先函数存在，则不唯一(无穷多)5.2.3 优先函数优先函数abab 如果优先函数