学年计算机方向课程大二下编译技术lect7-syntax3

1、信息科学技术学院2015年春季学期编译技术第 4 章语法分析（3）Syntax Analysis (3)4.5-4.6】【对应内容提要o 语法分析简介o 上下文无关文法o 文法的设计方法o 自顶向下的语法分析o 自底向上的语法分析o 简单LR分析：LR(0), SLRo 更强大的LR分析：LR(1), LALRo 二义性文法的使用o 语法分析器生成工具YACC22015年春季学期编译技术课程信息科学技术学院回顾：自顶向下的语法分析o 自顶向下分析是从文法的开始符号出发，试构造 出一个最左推导，从左至右匹配输入的单词串。o LL(1)文法：对于任意两个不同的产生式Aà|n First(

2、) Ç First()=;n 如果First()，那么First () Ç Follow(A)=；反之亦然。o LL(1)文法的判别：计算First和Follow集合o LL(1)文法的分析：首先构造LL(1)分析表n 编写不含回溯的递归分析子程序n 表格驱动的（非递归）分析方法32015年春季学期编译技术课程信息科学技术学院自底向上的语法分析o 为一个输入串构造语法分析树的过程；o 从叶子（输入串中的终结符号，将位于分析树 的底端）开始，向上到达根结点；n 在实际的语法分析过程中并真的构造出相应的分析树，但是分析树概念可以方便理解；o 自底向上语法分析的通用框架n “移进

3、-归约”分析oLR：最大的可以构造出移进-归约语法分析器的语法类42015年春季学期编译技术课程信息科学技术学院自底向上分析的例子SaASSbAaaba52015年春季学期编译技术课程信息科学技术学院ÞaSbbaaÞaabbaaSÞaASÞaAaÞaSbAa文法：S®aAS½aA ®SbA ½SS ½ba句子：aabbaa归约（Reduce）o 可以把自底向上语法分析过程看成从串 w“归约”为文法开始符号S的过程；o 归约步骤：n 一个与某产生式右部相匹配的特定子串被替换 为该产生式左部的非终结

4、符号；o 问题：n 何时归约（归约哪些符号串）?n 归约到哪个非终结符号?62015年春季学期编译技术课程信息科学技术学院归约的例子o id * id的归约过程n id * id <= F*id <= T*id <= T*F <= T <= Eo 对于句型T*id，有两个子串和某产生式右部匹配n T是EàT的右部；n id是Fàid的右部；n 为什么选择将id归约为F，而不是将T归约为E？o 原因：T归约为E之后，E*id不再是句型；o 问题：如何确定这一点？72015年春季学期编译技术课程信息科学技术学院句柄剪枝o 对输入从左到右扫描，并进行

5、自底向上语法分 析，实际上可以反向构造出一个最右推导o 句柄（handle）：n 最右句型中和某个产生式右部匹配的子串，对它的 归约代表了该最右句型的最右推导的最后一步；n 定义：如果SAww；那么紧跟之后的是 (对应Aà的) 一个句柄o 在一个最右句型中，句柄右边只有终结符号o 如果文法是无二义性的，那么每个句型都有且 仅有一个句柄。82015年春季学期编译技术课程信息科学技术学院句柄的例子o输入：id *idT92015年春季学期编译技术课程信息科学技术学院移进-归约分析 (Shift-Reduce Parsing)o建立符号栈，用来分析的历史和现状，并根据所的状态，确定下一步动

6、作是移进还是归约。输入符号串102015年春季学期编译技术课程信息科学技术学院S.R.P符号栈主要分析动作o 移进：将下一个输入符号移动到栈顶；o 归约：将句柄归约为相应的非终结符号;n 句柄总是在栈顶。n 具体操作时弹出句柄，压入被归约到的非终结 符号。o 接受：宣布分析过程成功完成；o 报错：发现语法错误，调用错误恢复子程序112015年春季学期编译技术课程信息科学技术学院分析过程开始时刻：栈中只包含$，而输入为w$；成功结束时刻：栈中$S，而输入$；在分析过程中，不断地移进符号，并在识别到 句柄时进行归约；ooo句柄被识别时总是出现在栈的顶部o122015年春季学期编译技术课程信息科学技

7、术学院输入符号串S.R.P符号栈移进-归约分析过程的例子栈内符号串 +未处理输入符号串= 当前句型句柄都在栈顶132015年春季学期编译技术课程信息科学技术学院为什么句柄总是在栈顶？o分别考虑最右推导的两个连续步骤的两种情况x, y, z VT* (VT U VN*)142015年春季学期编译技术课程信息科学技术学院移进-归约分析中的o有时候，即使知道了栈中所有内容、以及下面k个输入符号，仍然无法知道是否该进行归约，或者不知道按照什么产生式进行归约o 分别对应两种n “移进-归约”n “归约-归约”o “移进-归约”情形：的例子：n 设栈中符号串是，接下来的k个符号是x，产生移进/归约的原因是

8、存在y和y使得axy是最右句型且是句柄，而axy也是最右句型，但是句柄还在右边。152015年春季学期编译技术课程信息科学技术学院归约/归约的例子o输入为 id ( id , id )时的格局：n 栈：id ( idn 输入：, id ) o某个语言中，数组的表示方法。162015年春季学期编译技术课程信息科学技术学院LR 分析简介也称为LR(k)分析，是一种常用的自底向上分析。n L 指的是从左向右扫描输入符号串n R 指的是构造最右推导的逆过程（即规范归约）n k 指的是决定动作时向前看的符号个数，通常取0或1LR分析的过程是进行规范归约，即每次归约的都 是句柄。LR 分析的主要特点：1)

9、 适合文法类足够大：比LL(k)文法的范围大2) 分析效率高（无回溯）3) 报错及时4) 可以自动生成ooo172015年春季学期编译技术课程信息科学技术学院LR(k) 项（LR(k) Item）定义: A,称为文法G的一个LR(k)项。n 其中，A是G的一个产生式；n 是一个长度为 k 的由终结符和 $ 构成的符号串， 称为搜索符串。n 其中的圆点 表示语法分析程序已读到（可能经过若干次归约）的符号串，而构成圆点后面的符号串（可能经过归约）尚未读到。n 搜索串用于辅助确定是否在栈顶形成了句柄。n k 取 0 时，LR(0)项简写为A。n 产生式A相应的项有|+1 个。182015年春季学期编

10、译技术课程信息科学技术学院LR(0)项o产生式 A®XYZ，有下面四个项：A® XYZA® XY ZA® X YZA® XYZ oLR(0)项可分为四类：A® a ab, A® a Bb, A® a S´®S aÎVT BÎVN移进项待归约项归约项接受项nnnn对应于产生式 A®e 的唯一项是 A® ，它是归约项。no 项也可以用一对整数表示。n (i,j)表示第i条规则，点位于右部第j个位置192015年春季学期编译技术课程信息科学技术学院构造LR(0)

11、项集族与LR(0)自 图4-31 202015年春季学期编译技术课程信息科学技术学院规范LR(0)项集族的构造o 拓广文法：n 增加一条产生式 SS 拓广文法Gn 对文法中的产生式进行编号o 规范LR(0)项集族即LR(0)自o 构造过程中用到的子函数n CLOSURE(I)：I的项集闭包o 对应于DFA化算法的 -CLOSUREn GOTO(I,X)：I的X后继o 对应于DFA化算法的转换边的状态集合；212015年春季学期编译技术课程信息科学技术学院计算 closure(I)1. 把I中每一个项都加到初始为空的closure(I)中2. 若项 Aa B Î closure(I)

12、且 BÎP则把 B 加进 closure(I)中。3反复执行(2)直到closure不再增大为止。上面第二步的分析含义：项Aà B表示期望在接下来的输入中归约到B。显然，要归约到B，首先要扫描归约到B的某个产生式的右部；因此对每个产生式Bà，加入Bà ；表示它期望能够扫描归约到。222015年春季学期编译技术课程信息科学技术学院构造闭包算法的伪代码描述232015年春季学期编译技术课程信息科学技术学院闭包构造的例子项集EàE的闭包E' ®EE ®E+TE ®TT ®T*F T ®FF &

13、#174;(E)F ®id例： (0)(1)(2)(3)(4)(5)(6)242015年春季学期编译技术课程信息科学技术学院E' ®EE ®E+TE ®TT ®T*F T ®FF ® (E)F ®idLR(0)项集中的内核项和非内核项在算法中，在加入某个项B à时，所有以B为左部的产生式所对应的（点在最左边的）项都会被加入内核项：初始项S àS、以及所有点不在最左边的项非内核项：除了S àS之外、点在最左边的项；实现算法时可以考虑只保存相应的非终结符 号；甚至可以只保存内核项，

14、而在要使用非内核项时调用CLOSURE函数重新计算。oooo252015年春季学期编译技术课程信息科学技术学院GOTO函数oGOTO(I,X)：项集AàX | AàX I的闭包n 根据项的的含义，GOTO(I,X)表示或者归约到一个X之后的情况。输入中的Xn GOTO(I,X)定义了LR(0)自转换。o 例如：n I=EàE,EàE+T；n GOTO(I,+)计算如下：中状态I在X之上的oI中只有一个项的点后面跟着+，对应的项为EàE+ToCLOSURE(EàE+T) = EàE+T，TàT*F, TàF

15、，Fà(E)，Fàid。262015年春季学期编译技术课程信息科学技术学院求LR(0)项集规范族的算法o 从初始项集开始，不断计算各种可能的后继，直到生成所有的项集。o 可以和NFA的子集构造算法类比272015年春季学期编译技术课程信息科学技术学院LR(0)自的构造o 构造方法：n 规范LR(0)项集族中的项集可以作为LR(0)自动 机的状态n GOTO(I,X)=J，则从I到J有一个标号为X的转换n 初始状态为CLOSURE(S àS)对应的项集n 接受状态：包含形如A à 的项集对应的状态282015年春季学期编译技术课程信息科学技术学院I1TI6

16、+I9FidI8*I7(I3IIEI045E(+I6FidI)3(I11I5FI3idI5idI10TIF(I7*I4292015年春季学期编译技术课程信息科学技术学院T ®T* F2E ®TT ®T*FT ®T* F F ® (E) F ®idF ®idT ®FF ® (E)F ® (E) E ®E+TE´®EE ®E+T E ®TT ®T*F T ®FF ® (E) F ®idF ® (E)

17、E ®E+T E ®TT ®T*F T ®FF ® (E) F ®idTI2E´®EE ®E+TE ®E+T T ®T*FE ®E+T T ®T*F T ®FF ® (E) F ®idLR(0)自的作用（1）假设文法符号串 使LR(0)自行到状态（项集）j如果j中有一个形如Aà的项。那么n 在之后添加一些终结符号可以得到一个最右句型，n 是的后缀，且Aà是这个句型的句柄n 表示可能找到了当前最右句型的句柄如果j中存在

18、一个项BàX。那么n 在之后添加X，然后再添加一个终结符号串可得 到一个最右句型，n 在这个句型中BàX是句柄n 此时表示还没有找到句柄，需要移进从开始状态运ooo302015年春季学期编译技术课程信息科学技术学院LR(0)自的作用（2）oLR(0)自的使用n 移进-归约时，LR(0)自被用于识别句型n 已经归约/移进得到的文法符号序列对应于LR(0)自 的一条路径；n 如果路径到达接受状态，表明栈上端的某个符号串 可能是句柄。o 不需要每次用归约/移进得到的串来运行LR(0)自动 机n 路径被放到栈中；且文法符号可以省略，因为由LR(0)状 态可以确定相应文法符号n 在移

19、进后，根据原来的栈顶状态即可知道新的状态；n 在归约时，根据归约产生式的右部长度弹出相应状态， 仍然可以根据此时的栈顶状态计算得到新状态。312015年春季学期编译技术课程信息科学技术学院LR(0)的作用演示：分析id*ido根据LR(0)自状态和符号的对应关系，可以得到符号栏中的符号串。322015年春季学期编译技术课程信息科学技术学院使用图4-31的LR(0)自LR分析的结构o LR分析表（依赖于具体文法）n 由两个矩阵组成，其功能是指示分析器的动作是移 进还是归约，根据不同的文法类要采用不同的构造 方法o 驱动程序o执行分析表所规定的动作，输入符号串对栈进行操作。o分析栈o放置分析器状态

20、和文法符号。332015年春季学期编译技术课程信息科学技术学院分析程序(LR分析表)分析栈LR分析器的结构id+id*id$342015年春季学期编译技术课程信息科学技术学院Sm Xm Sm-1 Xm-1S0动作action转移gotoLR驱动程序输出LR分析表o分析表的第一列是状态、第二栏是action部分，由(|T|+1)列构成、第三栏是goto部分， 由|V|列构成：移进Si归约 rj :接受出错a 和状态i进栈出栈k项A和gotos', A进栈actions,a=其中，s是状态，a是读入的终结符（单词）或$; k是j号产生式A右部()的长度；s'是出栈k项后新的栈顶元素

21、中的状态。352015年春季学期编译技术课程信息科学技术学院表达式文法的SLR分析表2015年春季学期编译技术课程信息科学技术学院1. EE+T2. E T3. TT*F4. TF5. F(E)6. F id状态ACTIONGOTOid+*()$ETF01234567891011S5S4S6accr2S7r2r2r4r4r4r4 S5S4r6r6r6r6S5S4S5S4S6S11r1S7r1r1r3r3r3r3r5r5r5r51238239310 龙书图4-37使用图4-31的LR(0)自36LR分析器的驱动程序o 把状态 0 和符号 $ 压入初始为空的栈里。o 设栈顶元素中的状态为 s，当前

22、读入的符号为 a。o 反复执行以下各动作，直到分析成功或发现语法错 误为止：1（移进）若actions, a=Si, 则把a和状态i压进栈， 读下一个输入符号到a中。2（归约）若actions, a=rj(j: A®xm-k+1xm-k+2xm), 则出栈k项，把A和snew=gotos', A 进栈。其中s'是出栈k项后新的栈顶元素中的状态。3（接受）若actions,$=accept,则分析成功，结束。4（出错）若actions,a=error, 则转出错处理程序。372015年春季学期编译技术课程信息科学技术学院LR分析过程示例 使用龙书图4.37的分析表 38

23、2015年春季学期编译技术课程信息科学技术学院栈输入动作$0id+id*id$S5$0id5+id*id$r6 F®id$0F3+id*id$r4 T®F$0T2+ id*id$r2 E®T$0E1+id *id$S6$0E1+6id *id$S5$0E1+6id5*id$r6 F®id$0E1+6F3*id$r4 T®F$0E1+6T9*id$S7LR分析过程示例(续) 使用龙书图4.37的分析表 LR分析的关键是构造LR(k)分析表。 392015年春季学期编译技术课程信息科学技术学院栈输入动作$0E1+6T9*7id $S5$0E1 +6

24、T9*7 id5$r6 F®id$0E 1+6T9*7 F10$r3 T®T*F$0E1+6T9$r1E®E+T$0E1$acceptLR 分析表的种类o LR(0) 分析表n 过于简单，只能用于最简单的文法，不实用o SLR分析表 (Simple LR)n 构造简单, 最易实现, 大多数上下文无关文法都可以构造出SLR分析表, 具有较高的实用价值o LR(1)分析表 (Canonical LR)n 适用文法类最大, 几乎所有上下文无关文法都能构造出LR分析表,但其分析表体积太大, 实用价值不大o LALR(1)分析表 (LookAhead LR)n 这种表适用的

25、文法类及其实现上难易在上面两种之 间, 较为实用402015年春季学期编译技术课程信息科学技术学院构造LR(0)分析表o根据DFA构造LR(0)分析表M：DFA中的每个状态对应分析表中的一行对于DFA中的每一个从状态 i 到状态j的转移nn如果转移符号为终结符a：在相应的表项 Mi, a 中填写移进动作 Sj如果转移符号为非终结符A：在相应的表项 Mi, A 中填写要转移到的状态 joo对于包含归约项A ®a 的状态 in对于所有终结符 a，在相应的表项 Mi, a 中填写归约动作（rk）, 其中 k 是产生式A ®a的编号。o如果按照上面的步骤填写的分析表中没有（即每个单

26、元格中只包含一个动作），那么得到的就是合法 的LR(0)分析表412015年春季学期编译技术课程信息科学技术学院例：LR(0)分析表的构造I4I0S®SS ®aSb S ®abS® aSb bS® aSbSIS´® SS ®aSb S ®aSb S ®ab S ®ab1SI3aaI5bS® abI2422015年春季学期编译技术课程信息科学技术学院例： (0) S´®S(1) S ®aSb(2) S ®abI4例：LR(0)分析表I1S

27、® aSb bSS´® SS®SS ®aSb S ®abI3SS® aSbS ®aSb S ®aSb S ®ab S ®abaaI0I5bS® abI2432015年春季学期编译技术课程信息科学技术学院ab$S0S211acc2S2S533S44r1r1r15r2r2r2文法: (0) S´®S(1) S ®aSb(2) S ®abLR(0)分析表中的o假设我们为 S ® a | aBB ®b 构造 LR(0)项集。

28、(0) S ® S(1) S ® a(2) S ® aB。(3) B ®boI2状态中出现了移进-归约I0S®S S ®a S ®aBSIS® S1I3BS ® a S ® aB B ® bS ® aBabI4B ® bI2442015年春季学期编译技术课程信息科学技术学院解决办法：SLR分析表o根据Follow集来选择是否要进行归约。o如果 I=X ®a b b,A ®a ,B ®a 若b, Follow(A), Follow(B)两

29、两不交，则面对当前读入符号a，状态I的解决方法：1. 若a=b, 则移进。2. 若aÎ Follow(A), 则用A ®a 进行归约。3. 若aÎ Follow(B), 则用B ®a进行归约。4.此外，报错。o这种解决方法比较简单，因此称作SLR分析， 由此构造的分析表，称作SLR分析表。452015年春季学期编译技术课程信息科学技术学院构造SLR分析表o根据LR(0)的DFA构造SLR分析表M：为所有非终结符计算相应的Follow集合对于包含归约项A ®a 的状态 inn为所有终结符 aÎ Follow(A), 在相应的表项oMi,

30、 a 中填写归约动作A ®a的编号。ri , 其中 i 是产生式所有其他表项都按照与LR(0)分析表相同的方式n如果按照上面的步骤填写的分析表中没有冲突（即每个单元格中只包含一个动作），那么得到的就是合法的SLR分析表462015年春季学期编译技术课程信息科学技术学院I1TI6+I9FidI8*I7(I3IIEI045E(+I6FidI)3(I11I5F是否可以构造I3LR(0)分析表I？idI5idTI10F(I7*I4472015年春季学期编译技术课程信息科学技术学院T ®T* F2E ®TT ®T*FT ®T* F F ® (E

31、) F ®idF ®idT ®FF ® (E)F ® (E) E ®E+TE´®EE ®E+T E ®TT ®T*F T ®FF ® (E) F ®idF ® (E) E ®E+T E ®TT ®T*F T ®FF ® (E) F ®idTI2E´®EE ®E+TE ®E+T T ®T*FE ®E+T T ®T*F T

32、 ®FF ® (E) F ®id计算Follow集文法的Follow集：存在的项集： 该文法的SLR分析表参见龙书图4.37。482015年春季学期编译技术课程信息科学技术学院I1: E´®E E®E+T I2:E®T T ®T*F I9:E ®E+T T ®T *F E´ E TF$)+$)+*$)+*SLR的原理：活前缀（1）oLR(0)自刻画了可能出现在语法分析栈中的文法符号串。n 直接把项当作状态，可以构造得到一个NFA。n 然后确定化得到DFA就是LR(0)自o 活前缀 (Viable Prefix, 也译作可行前缀)：n 可以出现在移进-归约语法分析器栈中的右句型前缀n 定义：某个右句型的前缀，且没有越过该句型的句 柄的右端。o 有效项：n 如果存在S=>Aw=>12w，那么我们说项Aà1 2 对1有效。492015年春季学期编译技术课程信息科学技术学院SLR的原理：活前缀（2）o 如果我们知道Aà1 2对1有效，n 当2不等于空，表示句柄尚未出现在栈中，应该移 进或者等待归约；n 如果2等于空，表示句柄出现在栈中，应该归约。o 如果某个时刻存在两个有效项要求执行不同的动作，那么就应该设法解