sun编译原理第4章语法分析(第8-18讲) (2).ppt

1、2020/10/12,信息学院 孙丽云,1,语法分析程序的功能是以词法分析器生成的单词符号序列作为输入，根据语言的语法规则（文法），识别出各种语法成分，并在分析过程中进行语法检查，检查所给单词符号序列是否是该语言的文法的一个句子。若是，则以该句子的某种形式的语法树作为输出；若不是，则表明有错误，并指出错误的性质和位置。,4.1语法分析程序的功能,语法分析程序的输入是单词符号序列；输出是语法树。,2020/10/12,信息学院 孙丽云,2,递归下降法 LL(1)分析法,回溯分析方法（不确定的分析法） 预测分析方法 (确定的分析法),LR(0) parsing SLR(1) parsing LR(

2、1) parsing LALR(1) parsing,自顶向下分析方法,从根结点出发构造语法树,自底向上分析方法,从叶结点出发构造语法树,语法分析方法,L:由左向右的处理输入 L:为输入串构造最左推导,L:由左向右的处理输入 R:为输入串构造最右推导,2020/10/12,信息学院 孙丽云,3, 自顶向下的分析,例： 设有文法G：ScAd; Aab; Aa; 识别串w=cabd是否是该文法的句子。, 自底向上的分析,2020/10/12,信息学院 孙丽云,4,例：已知符号串S=cad 文法GZ: ZcAd Aab|a 求解 SL(GZ),分析过程 是设法建立一棵语法树, 使语法树的末端结点与

3、给定符号串相匹配.,2.用Z的右部,符号串去匹配输入串,完成一步推导ZcAd 检查 c-c匹配 A是非终结符,将匹配任务交给A,回溯分析法,4.2 自上而下分析法,2020/10/12,信息学院 孙丽云,5,3. 选用A的右部符号串匹配输入串 A有两个右部,选第一个,完成进一步推导Aab 检查,a-a匹配,b-d不匹配(失败) 但是还不能冒然宣布SL(GZ),4. 回溯 即砍掉A的子树 改选A的第二右部,Aa 检查 a-a匹配 d-d匹配,建立语法树,末端结点为cad与输入cad相匹配, 建立了推导序列 EcAdcad cadL(G(E),S=cad GZ: ZcAd Aab|a,分析工作要部

4、分地或全部地退回去重做叫回溯,回溯分析法分析效率低，代价高，实际不常用。,2020/10/12,信息学院 孙丽云,6, 文法左递归的消除,4.2 自上而下分析法,左递归导致无限递归循环；解决无限递归循环的方法：消除左递归。,（1） 左递归改成右递归简单直接左递归的消除 A A| ,解： exp term exp exp addop term exp | ,例：将文法G： exp exp addop term | term 消除左递归。,左递归的消除不改变语言，但是改变了文法和分析树。,确定的自上而下分析法对文法要求：(1)无左递归；(2)无回溯,2020/10/12,信息学院 孙丽云,7,A

5、A1| A2| | An|1|2|m,A 1 A | 2 A | | m A A 1 A | 2 A | | n A | ,解： exp term exp exp + term exp | - term exp |,(1) 左递归改成右递归普通的直接左递归的消除,练习：对文法G: E T*F | T/F | F T F | T*F | T/F 消除左递归,2020/10/12,信息学院 孙丽云,8,（2）采用扩充BNF表示法改写含直接左递归的规则,使用花括号a表示符号串a的出现可0次或多次，即表示a*。,例：if-stmt if ( exp ) statement | if ( exp ) s

6、tatement else statement,exp exp addop term | term,exp term addop term ,使用方括号a表示a的出现可有可无，它用来表示可供选择的符号串。,使用圆括号可在规则中提取因子。,例：A xa1|xa2|xan,2020/10/12,信息学院 孙丽云,9, 回溯的消除,引起回溯的情况： （1）相同左部的规则，其右部左端第一个符号相同而引起回溯。 例： ZcAd Aab|a （2）相同左部的规则，其中某一右部能推出串。 例：ABxBx |, LL(1)文法,LL(1)中的第一个L表示从左到右扫描输入串，第二个L表明分析过程中使用最左推导，

7、1表示分析时每一步只需向前看一个符号即可决定所选用的规则，而且这种选择是准确无误的。P61,2020/10/12,信息学院 孙丽云,10,First集合和Follow集合, First集合,定义：FIRST() = a | = * a， a T , , (TN)* 若 = * ，则规定 FIRST() 该集合称为的头符号集合,2020/10/12,信息学院 孙丽云,11,1.若X,则FIRST(X)=X 2.若XN,且有产生式Xa，则把a加入到FIRST(X)中;若X也是一条产生式,则把也加到FIRST(X)中. 3.若XY是一个产生式且YN,则把FIRST(Y)中的所有非元素都加到FIRST

8、(X)中;若X Y1Y2YK 是一个产生式,Y1,Y2,Y(i-1)都是非终结符,而且,对于任何j,1j i-1, FIRST(Yj)都含有 (即Y1.Y(i-1) =* ),则把FIRST(Yj)中的所有非元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj , j=1,2,K)均含有,则把加到FRIST(X)中., First集合算法 P67,令X为一个文法符号或，则集合First(X)由终结符组成，此外还可能有，定义如下：, 求First集合综合举例,求下列各种情况下的First(A) (1)AT (2)AN 例：AaB| ABa Bbd|c ABa Bbd|c| ABCa B

9、bd|c| Cxy| ABCD Bbd|c| Cxy| Dm| ,2020/10/12,信息学院 孙丽云,13,求文法G的 FIRST集合 G: (1) EE aop T (2) ET (3) aop + (4) aop - (5) T T mop F (6) T F (7) mop * (8) mop / (9) F (E) (10) F i, 求First集合举例1,2020/10/12,信息学院 孙丽云,14,1)求文法G的 FIRST集合(Simple integer expression grammar) expr expr addop termterm addop +|- term

10、 term mulop factor factor mulop * factor (expr) number,(1) expr expr addop term (2) expr term (3) addop + (4) addop - (5) term term mulop factor (6) term factor (7) mulop * (8) factor (expr) (9) factor number,First(expr)=(,number First(term)=(,number First(factor)=(,number First(addop)=+,- First(mul

11、op)=*,解：, 练习,同例1，仅符号不一样而已,2020/10/12,信息学院 孙丽云,15,2)求文法G的 FIRST集合(Left factored grammar of if-statement) statement if-stmt | other if-stmt if (exp) statement else-part else-part else statement | exp 0 | 1,(1) statement if-stmt (2) statement other (3) if-stmt if (exp) statement else-part (4) else-part

12、 else statement (5) else-part (6) exp 0 (7) exp 1,First(statement)=if,other First(if-stmt)=if First(else-part)=else, First(exp)=0,1,解：, 练习,2020/10/12,信息学院 孙丽云,16,3)求文法G的 FIRST集合(Grammar for statement sequences) stmt-sequence stmt stmt-seq stmt-seq ; stmt-sequence| stmts,(1) stmt-sequence stmt stmt-s

13、eq (2) stmt-seq ; stmt-sequence (3) stmt-seq (4) stmts,First(stmt-sequence)=s First(stmt-seq)=;, First(stmt)=s,解：, 练习,2020/10/12,信息学院 孙丽云,17, 求First集合举例2,求文法G的 FIRST集合 G: (1) MTB (2) TBa| (3) B Db|eT| (4) D d| ,注意：有产生式时求First集，别漏元素！,First(M)=e,a,d,b, First(T)= e,a,d,b, First(B)= e, d,b, First(D)= d,

14、 ,注意：除了求非终结符的First集外，还可求符号串的First集。例：求First(BaB),2020/10/12,信息学院 孙丽云,18,定义：FOLLOW(A)=a| S= * Aa，aTAN, S开始符号 特殊地：若S = *.A ，则 $FOLLOW(A), Follow集合,1.对于文法的开始符号S,置$于FOLLOW(S) 中; 2.若 B 是一个产生式,则把FIRST()加至FOLLOW(B)中; 3.若 B是一个产生式,或 B是一个产生式而FIRST() ，则把FOLLOW（A）加至FOLLOW（B）中。,算法：,2020/10/12,信息学院 孙丽云,19, 举例1,1)

15、求文法G的 FOLLOW集合(the simple expression grammar) (1) expr expr addop term (2) expr term (3) addop + (4) addop - (5) term term mulop factor (6) term factor (7) mulop * (8) factor (expr) (9) factor number,First(expr)=(,number First(term)=(,number First(factor)=(,number First(addop)=+,- First(mulop)=*,Fol

16、low(expr)=$,+,-, ) Follow(addop)=(,number Follow(term)= $,+,-, *,) Follow(mulop)=(,number Follow(factor)= $,+,-, *,) ,解：,2020/10/12,信息学院 孙丽云,20, 举例2,2)求文法G的 Follow集合(Left factored grammar of if-statement) statement if-stmt | other if-stmt if (exp) statement else-part else-part else statement | exp 0

17、 | 1,First(statement)=if,other First(if-stmt)=if First(else-part)=else, First(exp)=0,1,Follow(statement)=$,else Follow(if-stmt)=$,else Follow(else-part)=$,else Follow(exp)= ) ,解：,2020/10/12,信息学院 孙丽云,21, 举例3,3)求文法G的FOLLOW集合(Grammar for statement sequences) stmt-sequence stmt stmt-seq stmt-seq ; stmt-

18、sequence| stmts,First(stmt-sequence)=s First(stmt-seq)=;, First(stmt)=s,Follow(stmt-sequence)=$ Follow(stmt)=;, $ Follow(stmt-seq)=$,解：,2020/10/12,信息学院 孙丽云,22, 课堂练习,4)求文法G的FOLLOW集合 ETE E+TE| TFT T*FT| F(E)|i,FIRST(F)= (，i FIRST(T)=*, FIRST(T)= (，i FIRST(E)=+, FIRST(E)= (，i,FOLLOW(E)=$, ) FOLLOW(E)=$

19、, ) FOLLOW(T)=+, ), $ FOLLOW(T)= +,),$ FOLLOW(F)=*, + , ), $,解：,2020/10/12,信息学院 孙丽云,23, First集合和Follow集合的比较,1、First集合中不可能存在$符号，Follow集合中不可能存在； 2、通常Follow集合是为非终结符定义的，而First集合可以为非终结符、终结符和符号串定义； 3、Follow集合通常在产生式的“右边”计算，而First集合通常在“左边”计算。,2020/10/12,信息学院 孙丽云,24, Select集合,Select 集合是针对规则（产生式）的。 设A 是文法的任一条

20、规则，则定义： Select(A)=,First()若=* ,First()- Follow(A) 若=* ,例：求下列文法的每个规则的Select集合： AaB|d BbBA| ,2020/10/12,信息学院 孙丽云,25,一个上下文无关文法G是LL(1)文法，当且仅当对G中每个非终结符A的任何两个不同的规则A 满足： Select(A ) Select(A ) = , LL(1)文法的要求 P61,2020/10/12,信息学院 孙丽云,26, LL(1)文法判断举例,分别判断下列两个文法是否为LL(1)文法： （1）AaB|d BbBA| （2）SaAB AbB|dA| Ba| e,2

21、020/10/12,信息学院 孙丽云,27, 左递归,exp exp addop term | term, 左因子,if-stmt if ( exp ) statement if ( exp ) statement else statement,易出现死循环,易造成回溯, 某些非LL(1)文法到LL(1)文法的改写,2020/10/12,信息学院 孙丽云,28,若文法中含有左递归，即非终结符S + Sa 对这个文法的句子不能用LL(1)文法进行分析,含有左递归的文法使自上而下的分析过程陷入了一个死循环。, 消除左递归,解决办法：消除左递归 P58-P59,例：exp exp addop ter

22、m | term,2020/10/12,信息学院 孙丽云,29,将文法G： A|提取左因子。,解： AA A|, 提取左因子规则,例：将文法G 提取左因子。 stmt-sequencestmt; stmt-sequence | stmt stmts,提取左因子的结果： stmt-sequencestmt stmt-seq stmt-seq; stmt-sequence | stmts,注意：不可以这样提取： Aa(|),文法中括号的含义与正规式中括号的含义不同。,2020/10/12,信息学院 孙丽云,30,1)将文法G 提取左因子。 if-stmt if ( exp ) statement

23、if ( exp ) statement else statement,if-stmt if (exp) statement else-part else-part else statement | ,2)将文法G : exp term+exp |term提取左因子。,exp term exp exp + exp, 练习,2020/10/12,信息学院 孙丽云,31, 4.2自上而下分析法的复习与整合,自上而下语法分析方法,不确定的分析方法（回溯分析法）,确定的分析方法,（要求：无左递归；无回溯）,确定的自上而下的语法分析方法,递归下降分析方法,LL(1)分析法 （也称预测分析法）,都要求文法

24、是LL(1)文法,2020/10/12,信息学院 孙丽云,32, 4.2自上而下分析法的复习与整合,LL(1)文法的要求： 一个上下文无关文法G是LL(1)文法，当且仅当对G中每个非终结符A的任何两个不同的规则A 满足：Select(A ) Select(A ) = ,此处会求First、Follow、Select集合。,例： SaAB AbB|dA| Ba| e | ,2020/10/12,信息学院 孙丽云,33, 求First集合综合举例,求下列各种情况下的First(A) (1)AT (2)AN 例：AaB| ABa Bbd|c ABa Bbd|c| ABCa Bbd|c| Cxy| A

25、BCD Bbd|c| Cxy| Dm| ,2020/10/12,信息学院 孙丽云,34, 求Follow集合综合举例,求下列各种情况下的Follow(A) (1)A为开始符号时 (2) BAa (3) BaA (4) CaAB,2020/10/12,信息学院 孙丽云,35, 4.2自上而下分析法的复习与整合,某些非LL(1)文法到LL(1)文法的改写： （1）消除左递归； （2）提取左因子。,例如：对下列文法消除左递归并提取左因子： SrD|rd DD,i|i,注意：含有左递归或左因子的文法必定不是LL(1)文法，但不含左递归和左因子的文法不一定是LL(1)文法。如：下页例。,2020/10/

26、12,信息学院 孙丽云,36, LL(1)文法举例,设有文法GS： SaABbcd| A ASd| B SAh|eC| C Sf|Cg| D aBD| （1）检查文法，并消除左递归及提取左因子。 （2）求每一个非终结符号的FIRST集合。 （3）求每一个非终结符号的FOLLOW集合。 （4）该文法是LL(1)文法吗？,注意检查文法,D aBD|可去掉！,不是LL(1)文法。,2020/10/12,信息学院 孙丽云,37, 4.2自上而下分析法的复习与整合,消除左递归与回溯，还可以用EBNF表示法：,使用花括号a表示符号串a的出现可0次或多次，即表示a*。,例：if-stmt if ( exp

27、) statement | if ( exp ) statement else statement,exp exp addop term | term,exp term addop term ,使用方括号a表示a的出现可有可无，它用来表示可供选择的符号串。,使用圆括号可在规则中提取因子。,例：A xa1|xa2|xan,2020/10/12,信息学院 孙丽云,38, 递归下降分析法,递归下降分析法的基本思想： 将一个非终结符A的文法规则看作是“识别A的一个过程”的定义。 A的文法规则的右部指出此过程的代码结构。 由于文法常常是递归定义的，所以相应的函数会出现相互递归调用的过程，所以这种分析方法

28、称为递归下降分析法。,采用此种方法进行语法分析的前提：文法是LL(1)文法。,递归下降分析算法的优点：简单、易实现； 缺点：对文法要求高、时空效率低。,识别过程：P64-P65 自学,通常若采用递归下降分析法，则文法采用EBNF表示法。,2020/10/12,信息学院 孙丽云,39, 预测分析法与预测分析表的构造,预测分析法也称LL(1)分析法。 使用此种方法进行语法分析的前提：文法是LL(1)文法。 一个预测分析器的组成部分： 预测分析表（LL(1)分析表）、一个先进后出分析栈和一个总控程序。,预测分析器的总控程序对于不同的LL(1)文法都是相同的，而预测分析表对于不同的LL(1)文法是不相

29、同的。,2020/10/12,信息学院 孙丽云,40, 预测分析表的构造算法,（1）计算每一非终结符的First集和Follow集； （2）对于First()中的每个记号a，都将A 添加到表项MA, a中； （3）若在First()中，则对于Follow(A)的每个元素a(记号或是$)，都将A 添加到MA, a中; （4）把分析表中没有填入内容的空白格都标上出错标志error。,P67,例：文法：Sa|(T) TT,S|S 试判断该文法是否是LL(1)文法，若不是请转换，并求转换后LL(1)文法的预测分析表。,2020/10/12,信息学院 孙丽云,41, 练习1,Follow(exp)=$,

30、) Follow(exp)=$,) Follow(addop)=(,number Follow(term)= $,+,-,) Follow(term)=$,+,-,) Follow(mulop)=(,number Follow(factor)= $,+,-, *,),(1)First集和Follow集,First(exp)=(,number First(exp)=+,-, First(addop)=+,- First(term)=(,number First(term)=*, First(mulop)=* First(factor)=(,number,文法： exp exp addop ter

31、mterm addop + | - term term mulop factorfactor mulop * factor (exp) number,注意：先消除左递归,2020/10/12,信息学院 孙丽云,42,Follow(exp)=$,) Follow(exp)=$,) Follow(addop)=(,number) Follow(term)= $,+,-,) Follow(term)=$,+,-,) Follow(mulop)=(,number) Follow(factor)= $,+,-, *,),(2)First集和Follow集,First(exp)=(,number) Fir

32、st(exp)=+,-, First(addop)=+,- First(term)=(,number) First(term)=*, First(mulop)=* First(factor)=(,number),11,10,9,7,5,4,1,1,(3)LL(1)分析表,解,(1) 文法 1 exp term exp 2 exp addop term exp 3 exp 4 addop + 5 addop - 6 term factor term 7 term mulop factor term 8 term 9 mulop * 10 factor (exp) 11 factor number

33、,（1）对于First()中的每个记号a，都将A 添加到表项MA, a中； （2）若在First()中，则对于Follow(A)的每个元素a(记号或是$)，都将A 添加到MA, a中。,2020/10/12,信息学院 孙丽云,43, 练习2,2)求文法G的 LL(1)分析表 statement if-stmt | other if-stmt if (exp) statement else-part else-part else statement | exp 0 | 1,(1) 文法 1 statement if-stmt 2 statement other 3 if-stmt if (exp

34、) statement else-part 4 else-part else statement 5 else-part 6 exp 0 7 exp 1,(3)LL(1)分析表,First(statement)=if,other First(if-stmt)=if First(else-part)=else, First(exp)=0,1,Follow(statement)=$,else Follow(if-stmt)=$,else Follow(else-part)=$,else Follow(exp)=),ifother else ( ) 0 1 $,statement if-stmt e

35、lse-part exp,1,2,3,4,6,7,5,5,注意在构造LL(1)分析表之前别忘了先验证文法是否为LL(1)文法！,2020/10/12,信息学院 孙丽云,45,3)求文法G的 LL(1)分析表 stmt-sequence stmt stmt-seq stmt-seq ; stmt-sequence| stmts,课堂练习,(2)First集和Follow集,(3)LL(1)分析表,解,(1) 文法 (1) stmt-sequence stmt stmt-seq (2) stmt-seq ; stmt-sequence (3) stmt-seq (4) stmts,;s$,stmt

36、-sequence stmt-seq stmt,1,2,3,4,First(stmt-sequence)=s First(stmt-seq)=;, First(stmt)=s,Follow(stmt-sequence)=$ Follow(stmt)=;,$ Follow(stmt-seq)=$,2020/10/12,信息学院 孙丽云,47,自上而下语法分析过程,参照P68 表4.2,例：求文法G的 LL(1)分析表 s1 stmt s2 s2 ; s1| stmts 分别分析s;s s;s;是否是该文法定义的语言。,;s$,s1 s2 stmt,1,2,3,4,2020/10/12,信息学院

37、孙丽云,48,课堂练习：文法：Sa|(T) TT,S|S 试判断该文法是否是LL(1)文法，若不是请转换，并求转换后LL(1)文法的预测分析表。 分析：句子(a,)是否为该文法定义的语言。,自上而下语法分析过程,参照P68 表4.2,（1）简单直接左递归的消除 A A| ,1、消除文法中的左递归或提取左因子；, LL(1)分析方法相关知识总结,（2）将文法G： A|提取左因子。,解： AA A|,2、求改写文法中的非终结符的First集和Follow集； 3、判断文法是否是LL(1)文法； 一个上下文无关文法G是LL(1)文法，当且仅当对G中每个非终结符A的任何两个不同的规则A 满足： Sel

38、ect(A ) Select(A ) = 4、若该文法是LL(1)文法，则构造预测分析表； （1）对于First()中的每个记号a，都将A 添加到表项MA, a中； （2）若在First()中，则对于Follow(A)的每个元素a(记号或是$)，都将A 添加到MA, a中。 5、根据分析表进行自顶向下的语法分析。,2020/10/12,信息学院 孙丽云,50, LL(1)分析方法综合举例,已知文法：GS: SSaA|bB AaB|c BBb|d 判断”bdbac”以及”bdbab”是否是所给文法定义的语言。,步骤： （1）消除文法中的左递归或提取左因子； （2）求改写文法中的非终结符的Firs

39、t集和Follow集； （3）判断该文法是否是LL(1)文法，若是，则构造预测分析表； （4）根据分析表进行自顶向下的语法分析。,2020/10/12,信息学院 孙丽云,51,1、有文法G：SAB AaAb| BcBd| 该文法所定义的语言是下边哪个集合（ ） A. anbmcndm|n,m0 B. anbncmdm|n,m0 C. anbmcmdn|n,m0 D. anbncmdm|n,m0, 期中考试,D,2020/10/12,信息学院 孙丽云,52, 期中考试,2、一个文法所描述的语言是（ ）；描述一个语言的文法是（ ）。 A.唯一的 B.不唯一的 C.可能唯一，也可能不唯一,A,B,3

40、、编译程序中的语法分析器接受以（ ）为单位的输入，并产生有关信息供以后阶段使用。 A.表达式 B.产生式 C. 单词符号D.语句,C,2020/10/12,信息学院 孙丽云,53,4、如果文法G是无二义的，则下面说法正确的是（ ） A.文法的一个句子对应两棵不同的语法树 B.文法中某个句子有两个不同的最左推导 C.文法中某个句子有两个不同的最右推导 D.文法中任一句子，它的最左或最右推导对应的语法树相同, 期中考试,D,5、给定文法AbA|cc，则符号串ccbcbcbcbccbccbccbbbcc中，是该文法句子的是（ ） A. B. C. D.,D,2020/10/12,信息学院 孙丽云,5

41、4, 期中考试,6、文法G产生的（ ）的全体是该文法描述的语言 A.句型 B.终结符集 C.非终结符集 D.句子 7、正规式M1和M2等价是指（ ）。 A. M1和M2的状态数相等 B. M1和M2的有向边条数相等 C. M1和M2所识别的正规集相等 D. M1和M2的状态数和有向边条数相等 9、设x是符号串，符号串的幂运算x0=（ ）。 A.1B.0C.空集D. ,D,D,C,2020/10/12,信息学院 孙丽云,55, 期中考试,1、含有优化部分的编译程序的执行效率高。 （ ） 2、对编译程序而言，可以没有代码优化的部分。（ ） 3、编译程序生成的目标程序一定是可执行的程序。 （ ） 4

42、、设A是符号串的集合，则A0=。（ ） 5、任何正规文法都是上下文无关文法。（ ）,2020/10/12,信息学院 孙丽云,56, 期中考试,6、若一个语言是无穷集合，则定义该语言的文法也不一定是递归的。（ ） 7、规范推导是指最左推导。 （ ） 8、递归下降分析法是一种自下而上的语法分析方法。（ ） 9、若两个正规式所表示的正规集相同，则认为二者是等价的。（ ） 10、一个确定的有穷自动机DFA是一个三元组 （VN,VT,P）。（ ）,2020/10/12,信息学院 孙丽云,57, 期中考试,3、（4分）请简述文法的二义性与语言的二义性的不同之处。 4、（4分）请简述正规文法与文法描述的语言

43、，及正规式与正规集4个概念之间的联系和区别。,2020/10/12,信息学院 孙丽云,58, 期中考试,1、（16分）构造与(a|b)a(a|b)*a等价状态最少的DFA，按如下步骤求解。 （1）构造NFA,使得L(N)=L(R)； （2）将该NFA确定化为DFA； （3）将所求DFA最小化； （4）写出所求的DFA的五元组。,2020/10/12,信息学院 孙丽云,59, 期中考试,2、（12分）已知文法G(E)： EET+|T TTF*|F FF Aab; Aa; 识别串w=cabd是否是该文法的句子。, 自底向上的分析,2020/10/12,信息学院 孙丽云,61,G = (T, N,

44、P, S)，S=* a ，a (TN)* 称a为句型。,1）句型,G = (T, N, P, S)，w = xuy (TN)* 为文法的句型, 若S =* xUy ,且 U =+ u, 则u是句型w相对于U 的短语； 若S =* xUy, 且 U =u, 则u是句型w相对于U 的简单短语; 其中UN，u (TN)+ , x, y (TN)*,任一句型的最左简单短语称为该句型的句柄。,2）短语：每棵子树的叶组成短语 简单短语：每棵简单子树的叶组成简单短语,3）句柄：最左简单子树的叶组成句柄, 概念复习,归约的过程就是寻找句柄的过程。 例：见上页。,2020/10/12,信息学院 孙丽云,62,4

45、.5 LR分析法,本节介绍四种LR分析法：LR(0)、SLR(1)、LR(1)、LALR，这四种方法的区别只有分析表不同。,LR分析法是一种自下而上进行规范归约的语法分析方法，这里L是指从左向右扫描输入符号串，R是只构造最右推导的逆过程。 优点：对文法的限制少的多，分析速度快； 缺点：构造LR分析器的工作量大，实现困难。,2020/10/12,信息学院 孙丽云,63,LR分析器的结构和工作过程, LR分析器的工作原理和过程,2020/10/12,信息学院 孙丽云,64, LR(0)分析法,LR(0)分析法就是在分析的每一步，只需根据当前栈顶状态而不必向前查看输入符号就能确定应采取的分析动作。

46、LR分析器的关键部分是分析表的构造。构造LR分析表的基本思想是从给定的上下文无关文法直接构造识别文法所有规范句型活前缀的DFA，然后再将DFA转换成一张LR分析表。,2020/10/12,信息学院 孙丽云,65,为了刻画在分析过程中，文法的一个规则右部符号串已有多大一部分被识别，可在文法中每个规则右部适当位置上加一个圆点来表示。, LR(0)项,例1：已知G，求其项目。 S S S (S)S|,2020/10/12,信息学院 孙丽云,66, LR(0)项,例2：已知G，求其项目。 EE EE + n | n,2020/10/12,信息学院 孙丽云,67,在文法产生式右部某个位置标有. 的产生式

47、，称为文法的一个LR(0)项目 。,形如 A . 的项目称为初始项目； 形如 A . 的项目称为归约项目； 形如 A . B （ BN ）的项目称为待约项目； 形如 A . a （aT） 的项目称为移进项目； 形如 SS . 的项目称为接受项目，其中S为文法的唯一的开始符号,项目分类,2020/10/12,信息学院 孙丽云,68, 构造识别文法所有规范句型活前缀DFA的方法,构成识别文法规范句型活前缀DFA的每一个状态是由若干个LR(0)项目所组成的集合，称为LR(0)项目集。,为了使“接受”项目唯一，对文法G进行拓广。 增加一个唯一的开始符号S，及产生式SS。 （设S为文法G的开始符号）,2

48、020/10/12,信息学院 孙丽云,69,设I是文法G的一个LR(0)项目集合，I的项目闭包closure(I)定义为： (1) I closure(I)。(2) 若项目A . B closure(I)，且 B 是G的产生式，则项目B . closure(I)。(3) closure(I)仅包含上述两条规则确定的LR(0)项目。,项目闭包：,转移函数：,若I是文法G的一个LR(0)项目集，X是G中的文法符号。 go(I, X) = closure(J) 其中J =AX . | A . XI 称函数go(I, X)为转移函数。 项目A X . 称为项目A . X后继。, 构造识别文法所有规范句

49、型活前缀DFA的方法,2020/10/12,信息学院 孙丽云,70,EE EE EE + n EE + n EE + n EE + n En En,DFA, 构造识别文法所有规范句型活前缀DFA的方法,（1）求closure(S.S)，得到初态项目集； （2）对初态项目集或其他已构造的项目集，应用状态转移函数GO(I,X)求出新的项目集； （3）重复（2）直到不出现新的项目集为止； （4）转移函数GO建立状态之间的连接关系。,2020/10/12,信息学院 孙丽云,71, 构造识别文法所有规范句型活前缀DFA的方法,课堂练习：求文法G:S (S)S|识别文法活前缀的DFA,（1）拓广文法并对每

50、条规则编号； （2）求初始项目的项目闭包； （3）重复用状态转移函数求新的项目集，直到不产生新的项目集。,2020/10/12,信息学院 孙丽云,72,LR(0)分析表的构造,若对于一个文法G的拓广文法G的LR(0)项目集规范族中的每个项目集，不存在移进项目和归约项目同时并存或多个归约项目同时并存，则称G为LR(0)文法。,即LR(0)文法中不能存在移进归约冲突或者归约归约冲突。,根据右图某文法识别活前缀的DFA判断该文法是否为LR(0)文法,2020/10/12,信息学院 孙丽云,73,根据下图某文法识别活前缀的DFA判断该文法是否为LR(0)文法,2020/10/12,信息学院 孙丽云,7

51、4,LR(0)分析表的构造,LR(0)分析表包含两个子表：ACTION表和GOTO表 假定项目集规范族C=I0,I1,In，令每个项目集Ik的下标k作为分析器的状态，两个子表的构造过程如下： （1）若项目A . a 属于Ik且GO(Ik,a)=Ij，a为终结符，则置ACTIONk,a为”sj”； （2）若项目A . 属于Ik，则对任何终结符a（包括终结符$），置ACTIONk,a为”rj”（注：j是产生式A的编号，而不是状态集的状态号）； （3）若项目SS属于Ik(S表示整个句子已输入并归约结束)，则置ACTIONk,$为“acc”，表示接受。 （4）若GOIk,A=Ij，A为非终结符，则置G

52、OTOk,A=j; （5）分析表凡不能用规则(1)-(4)填入的空白格均置为“error”。,例：S(S)|a,分析表格式,2020/10/12,信息学院 孙丽云,75,例x：已知文法GS，求其LR(0)的分析表。 S aA | bB A cA | d B cB | d,2020/10/12,信息学院 孙丽云,76,(1)识别文法活前缀的DFA,0 SS 1 SaA 2 SbB3 AcA 4 Ad 5 BcB 6 Bd,2020/10/12,信息学院 孙丽云,77,输入：一个输入串w和文法G的一张LR分析表M。 输出：若w L(G),输出w的一个自底向上的分析；否则，输出一个出错表示。 方法：

53、分别置放s0(初态)到栈中和w$（w为输入串，$为界符）到输入缓冲器中; 置ip指向w$的第一个符号； repeat forever begin 令s是栈顶状态且a是ip所指向的符号 if actions,a = shift s then begin 将a和s先后压入栈内； 使ip指向输入串中的下一个符号； end,else if actions,a = reduce A then begin 从栈顶弹出2*|个符号； 令s是当前栈顶状态； 把A和gotos,A先后入栈； 输出产生式A end else if actions,a = accept then return else error(

54、 ) end, LR(0)分析算法,算法在教材 P79,例：利用LR(0)法分析上页例x中acd是否是文法的句子。,作业：P101 4.10 并用LR(0)方法分析a01是否为该文法的句子。,2020/10/12,信息学院 孙丽云,78,在进行LR语法分析过程中，可以发现当前栈和输入串之间发生了间隔，在每种情况下，分析栈的符号序列被称为右句型的可行前缀（不含句柄之后的任何符号）。, 右句型的可行前缀 viable prefix（活前缀）,例x中， ，a, ac, acA都是右句型acA的活前缀。,2020/10/12,信息学院 孙丽云,79,例：已知文法GA：A ( A ) | d 求其LR(

55、0)的分析表，并判断(d)L(G)?,(3)LR(0)分析表,(2)识别文法活前缀的DFA,解: (1)拓广文法,(4)分析过程, 课堂练习,2020/10/12,信息学院 孙丽云,80,例：已知文法GE，分析i*i+iL(GE) ? EE+T | T TT*F | F F (E) | i,出现问题：由该文法识别活前缀的DFA看的出来，有的有效项目集中存在着移进归约冲突，不能用LR(0)分析方法进行分析。,解决方法：对含有冲突的项目集向前查看一个输入符号，这种分析方法称为SLR(1)分析方法。,复习：LR(0)文法中不能存在移进归约冲突或者归约归约冲突。, 引例,2020/10/12,信息学院

56、 孙丽云,81,解： (1)拓广文法 G的拓广文法GE： (0) E E (4) TF (1) EE+T (5) F (E) (2) ET (6) F i (3) TT*F (2)识别文法的活前缀的 DFA (3)SLR(1)分析表 (4)分析过程,例：已知文法GE，并用SLR(1)方法分析i*i+iL(GE) ? EE+T | T TT*F | F F (E) | i,SLR(1)的分析过程与LR(0)的分析过程完全一样，唯一不同的是分析表！,E E,E E+T,E T,T T*F,T F,F (E),F id,E,EE E E +T,T,E T T T*F,(,F ( E) E E+T E

57、 T T T*F T F F (E) F id,I0,I1,I2,I6,F,T F,I3,F id,id,I5,T,I2,F,I3,id,I5,(,E E+ T T T*F T F F (E) F id,+,*,T T* F F (E) F id,I7,F (E ) E E+T,E,I8,T,E E+ T T T*F,I9,F,I3,id,I5,(,F,T T* F ,I10,id,I4,(,I4,*,I7,),F (E) ,+,I6,I11,G：(0) E E (1) EE+T (2) ET (3) TT*F (4) TF (5) F (E) (6) F id,(2)识别文法的活前缀的 DF

58、A,2020/10/12,信息学院 孙丽云,83,若有效项目集中存在冲突动作: I = X . b, A . , B . ,解决方法：设当前输入符号为x, 1. 若x= b, 则移进; 2. 若xFollow(A), 则用A 进行归约; 3. 若xFollow(B), 则用B 进行归约; 4. 其余情况报错.,要求： 移进项目的符号集FOLLOW(A) FOLLOW(B)=, SLR(1)分析法,2020/10/12,信息学院 孙丽云,84,对于表达式文法的例子，FOLLOW集如下：,G： (0) E E (4) TF (1) EE+T (5) F (E) (2) ET (6) F id (3) TT*F,I2: FOLLOW(E)*= I9: FOLLOW(E)*= 可用SLR(1)方法实现,2020/10/12,信息学院 孙丽云,85, SLR分析表的构造算法,输入：一个拓广文法G 输出：对于G的分析表的action 子表和goto子表 方法： 1. 构造G的LR(0)项目集规范族。 2. 对于状态Ii的分析动作如下： (a) 若A . aB Ii且 go (Ii ,a)= Ij actioni,a = shift j (b) 若A . Ii, 对于所有a Follow(A) actioni,a = reduce A , A