三章语法分析.ppt

《三章语法分析.ppt》由会员分享，可在线阅读，更多相关《三章语法分析.ppt（294页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、三章语法分析 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望3.1上下文无关文法上下文无关文法3.1.1上下文无关文法的定义上下文无关文法的定义正规式能定义一些简单的语言正规式能定义一些简单的语言，能表示给定结构能表示给定结构的固定次数的重复或者没有指定次数的重复的固定次数的重复或者没有指定次数的重复例：例：a(ba)5,a(ba)*正规式不能用于描述配对或嵌套的结构正规式不能用于描述配对或嵌套的结构例例1：配对括号串的集合配对括号串的集合例例2：wcw|w是是a

2、和和b的串的串 3.1上下文无关文法上下文无关文法上下文无关文法上下文无关文法是四元组（是四元组（VT,VN,S,P）VT:终结符终结符集合集合VN:非非终结符终结符集合集合S:开始符号，非终结符中的一个开始符号，非终结符中的一个P :产生式产生式集合，集合，产生式形式产生式形式:A 例例 (id,+,(,),expr,op,expr,P)exprexpropexpr expr(expr)expr expr expridop+op 3.1上下文无关文法上下文无关文法简化表示简化表示exprexpropexpr|(expr)|expr|idop+|简化表示简化表示E E A E|(E)|E|id

3、A+|3.1上下文无关文法上下文无关文法3.1.2 推导推导 把产生式看成重写规则，把符号串中的非终结符把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替用其产生式右部的串来代替例例 E E+E|E E|(E)|E|id E E (E)(E+E)(id+E)(id+id)概念概念上下文无关语言上下文无关语言、等价的等价的文法、文法、句型句型记号记号S*、S+w 3.1上下文无关文法上下文无关文法例例E E+E|E E|(E)|E|id 最左最左推导推导E lm E lm(E)lm(E+E)lm(id+E)lm (id+id)最右最右推导（规范推导）推导（规范推导）E rm E

4、rm(E)rm(E+E)rm(E+id)rm (id+id)3.1上下文无关文法上下文无关文法3.1.3分析树分析树例例E E+E|E E|(E)|E|idEE()EEE+idid3.1上下文无关文法上下文无关文法3.1.4二义性二义性EE EEE+Eid EE E+Eid E+Eid E+Eid id+Eid id+Eid id+idid id+id两个不同的最左推导两个不同的最左推导3.1上下文无关文法上下文无关文法3.1.4二义性二义性EE EEE+Eid EE E+Eid E+Eid E+Eid id+Eid id+Eid id+idid id+id两棵不同的语法树两棵不同的语法树EE

5、E*+EEidididEEidE*+EEidid3.2 语言和文法语言和文法 文法的优点文法的优点文法给出了精确的，易于理解的语法说明文法给出了精确的，易于理解的语法说明自动产生高效的分析器自动产生高效的分析器可以给语言定义出层次结构可以给语言定义出层次结构以文法为基础的语言的实现以文法为基础的语言的实现便于语言的修改便于语言的修改文法的问题文法的问题文法只能描述编程语言的大部分语法，不能描述文法只能描述编程语言的大部分语法，不能描述语言中上下文有关的语法特征语言中上下文有关的语法特征3.2 语言和文法语言和文法 3.2.1 正规式和上下文无关文法的比较正规式和上下文无关文法的比较正规式正规式

6、(a|b)*ab文法文法A0aA0|b A0|aA1A1bA2A2 12开始开始a0abb3.2 语言和文法语言和文法 3.2.2分离词法分析器理由分离词法分析器理由为什么要用正规式定义词法为什么要用正规式定义词法词法规则非常简单，不必用上下文无关文法词法规则非常简单，不必用上下文无关文法对于词法记号，正规式描述简洁且易于理解对于词法记号，正规式描述简洁且易于理解从正规式构造出的词法分析器效率高从正规式构造出的词法分析器效率高3.2 语言和文法语言和文法 从软件工程角度看，词法分析和语法分析的从软件工程角度看，词法分析和语法分析的分离有如下好处分离有如下好处简化设计简化设计编译器的效率会改进编

7、译器的效率会改进编译器的可移植性加强编译器的可移植性加强便于编译器前端的模块划分便于编译器前端的模块划分 3.2 语言和文法语言和文法 能否把词法分析并入到语法分析中，直接从能否把词法分析并入到语法分析中，直接从字符流进行语法分析字符流进行语法分析若把词法分析和语法分析合在一起，则必须将语若把词法分析和语法分析合在一起，则必须将语言的注解和空白的规则反映在文法中，文法将大言的注解和空白的规则反映在文法中，文法将大大复杂大复杂注解和空白由自己来处理的分析器，比注解和空注解和空白由自己来处理的分析器，比注解和空格已由词法分析器删除的分析器要复杂得多格已由词法分析器删除的分析器要复杂得多3.2 语言

8、和文法语言和文法 3.2.3 验证文法产生的语言验证文法产生的语言G:S(S)S|L(G)=配对的括号串的集合配对的括号串的集合3.2 语言和文法语言和文法 3.2.3 验证文法产生的语言验证文法产生的语言G:S(S)S|L(G)=配对的括号串的集合配对的括号串的集合按推导步数进行归纳按推导步数进行归纳：推出的是：推出的是配对括号串配对括号串归纳基归纳基础：础：S 归纳假设：归纳假设：少于少于n步的推导都产生配对的括号串步的推导都产生配对的括号串归纳步骤：归纳步骤：n步的最左推导步的最左推导如下：如下：S(S)S*(x)S*(x)y3.2 语言和文法语言和文法 3.2.3 验证文法产生的语言验

9、证文法产生的语言G:S(S)S|L(G)=配对的括号串的集合配对的括号串的集合按串长进行归纳按串长进行归纳：配对括号串可由配对括号串可由S推出推出归纳基归纳基础：础：S 归纳假设：归纳假设：长度小于长度小于2n的都可以从的都可以从S推导出来推导出来归纳步骤：归纳步骤：考虑长度为考虑长度为2n(n 1)的的w=(x)yS(S)S*(x)S*(x)y3.2 语言和文法语言和文法 3.2.4适当的表达式文法适当的表达式文法用一种层次观点看待表达式用一种层次观点看待表达式id id(id+id)+id id+id3.2 语言和文法语言和文法 3.2.4适当的表达式文法适当的表达式文法用一种层次观点看待

10、表达式用一种层次观点看待表达式id id(id+id)+id id+idid id(id+id)文法文法exprexpr+term|termterm term factor|factorfactorid|(expr)3.2 语言和文法语言和文法 exprexpr+term|termtermterm factor|factorfactorid|(expr)expridtermfactorididterm*termfactorfactor*exprexpr+idfactortermididterm*termfactorfactorid+id id分析树分析树 id id id分析树分析树 3.2

11、语言和文法语言和文法 3.2.5消除二义性消除二义性stmtifexprthenstmt|ifexprthenstmtelsestmt|other句型句型：ifexprthenifexprthenstmtelsestmt两个最左推导：两个最左推导：stmt ifexprthenstmt ifexprthenifexprthenstmtelsestmtstmt ifexprthenstmtelsestmt ifexprthenifexprthenstmtelsestmt3.2 语言和文法语言和文法 无二义的文法无二义的文法stmtmatched_stmt|unmatched_stmtmatche

12、d_stmtifexprthenmatched_stmtelsematched_stmt|otherunmatched_stmtif exprthenstmt|ifexprthenmatched_stmtelseunmatched_stmt3.2 语言和文法语言和文法 3.2.6消除左递归消除左递归文法文法左递归左递归A+A 直接左递归直接左递归AA|串的特点串的特点.消除直接左递归消除直接左递归A A A A|3.2 语言和文法语言和文法 例例算术表达文法算术表达文法EE+T|T（T+T.+T）TT F|F（F F.F）F(E)|id消除左递归后文法消除左递归后文法 ETE E+TE|TFT

13、 T F T|F(E)|id3.2 语言和文法语言和文法 非直接左递归非直接左递归SAa|bASd|先变换成直接左递归先变换成直接左递归S Aa|bAAad|bd|再消除左递归再消除左递归S Aa|bA bd A|A A adA|3.2 语言和文法语言和文法 3.2.7 提左因子提左因子有左因子的文法有左因子的文法A1|2提左因子提左因子A A A 1|2 3.2 语言和文法语言和文法 例例 悬空悬空else的文法的文法 stmtifexprthenstmtelsestmt|ifexprthenstmt|other提左因子提左因子stmtifexprthenstmtoptional_else_

14、part|otheroptional_else_part elsestmt|3.2 语言和文法语言和文法 3.2.8 非上下文无关的语言构造非上下文无关的语言构造L1=wcw|w属于属于(a|b)*标识符的声明应先于其引用的抽象标识符的声明应先于其引用的抽象L2=anbmcndm|n 0,m 0形参个数和实参个数应该相同的抽象形参个数和实参个数应该相同的抽象L3=anbncn|n 0早先排版描述的一个现象的抽象早先排版描述的一个现象的抽象begin：5个字母键，个字母键，5个回退键，个回退键，5个下划线键个下划线键3.2 语言和文法语言和文法 L1=wcwR|w(a|b)*S aSa|bSb|

15、c L2=anbmcmdn|n 1,m 1SaSd|aAdA bAc|bcL2=anbncmdm|n 1，m 1S ABA aAb|abB cBd|cd3.2 语言和文法语言和文法 L3=anbn|n 1S aSb|abL3 是不能用正规式描述的语言的一个范例是不能用正规式描述的语言的一个范例 若存在接受若存在接受L3 的的DFAD，状态数为状态数为k个个设设D读完读完,a,aa,ak 分别到达状态分别到达状态s0,s1,sk至少有两个状态相同，例如是至少有两个状态相同，例如是si和和sj，则则ajbi属于属于L3 sifs0标记为标记为ai的路径的路径标记为标记为bi的路径的路径标记为标记为

16、aj i的路径的路径3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G=(VT,VN,S,P)0型文法：型文法：，,(VN VT)*,|13.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G=(VT,VN,S,P)0型文法：型文法：，,(VN VT)*,|1短语文法短语文法3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G=(VT,VN,S,P)0型文法：型文法：，,(VN VT)*,|11型文法：型文法：|，但但S 可以例外可以例外短语文法短语文法3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法

17、文法G=(VT,VN,S,P)0型文法：型文法：，,(VN VT)*,|11型文法：型文法：|，但但S 可以例外可以例外短语文法、上下文有关文法短语文法、上下文有关文法3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G=(VT,VN,S,P)0型文法：型文法：，,(VN VT)*,|11型文法：型文法：|，但但S 可以例外可以例外2型文法：型文法：A，A VN,(VN VT)*短语文法、上下文有关文法短语文法、上下文有关文法3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G=(VT,VN,S,P)0型文法：型文法：，,(VN VT)*,|11

18、型文法：型文法：|，但但S 可以例外可以例外2型文法：型文法：A，A VN,(VN VT)*短语文法、上下文有关文法、上下文无关文短语文法、上下文有关文法、上下文无关文法法3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G=(VT,VN,S,P)0型文法：型文法：，,(VN VT)*,|11型文法：型文法：|，但但S 可以例外可以例外2型文法：型文法：A，A VN,(VN VT)*3型文法：型文法：A aB或或A a，A,B VN,a VT短语文法、上下文有关文法、上下文无关文短语文法、上下文有关文法、上下文无关文法法3.2 语言和文法语言和文法 3.2.9 形式语言

19、鸟瞰形式语言鸟瞰文法文法G=(VT,VN,S,P)0型文法：型文法：，,(VN VT)*,|11型文法：型文法：|，但但S 可以例外可以例外2型文法：型文法：A，A VN,(VN VT)*3型文法：型文法：A aB或或A a，A,B VN,a VT短语文法、上下文有关文法、上下文无关文短语文法、上下文有关文法、上下文无关文法、正规文法法、正规文法3.2 语言和文法语言和文法 例例 L3anbncn|n 1的上下文有关文法的上下文有关文法S aSBC S aBCCBBCaB abbB bbbC bccC ccanbncn的推导过程如下：的推导过程如下：S*an-1S(BC)n 1用用S aSBC

20、 n-1次次S+an(BC)n用用S aBC 1次次S+anBnCn用用CBBC交换相邻的交换相邻的CBS+anbBn 1Cn用用aBab1次次S+anbnCn用用bB bb n-1次次S+anbncCn-1用用bC bc 1次次S+anbncn用用cCcc n-1次次3.3 自上而下分析自上而下分析 3.3.1自上而下分析的一般方法自上而下分析的一般方法例例 文法文法 S aCb C cd|c为输入串为输入串w=acb建立分析树建立分析树SaCbSaCbcdSaCbc不能处理不能处理左递归左递归3.3 自上而下分析自上而下分析不能处理左递归的例子不能处理左递归的例子算术表达文法算术表达文法E

21、E+T|TTT F|FF(E)|idEE+TE+TE+T 3.3 自上而下分析自上而下分析 3.3.1自上而下分析的一般方法自上而下分析的一般方法例例 文法文法 S aCb C cd|c为输入串为输入串w=acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂的回溯技术复杂的回溯技术3.3 自上而下分析自上而下分析 3.3.1自上而下分析的一般方法自上而下分析的一般方法例例 文法文法 S aCb C cd|c为输入串为输入串w=acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂的回溯技术复杂的回溯技术、回溯导回溯导致语

22、义工作推倒重来致语义工作推倒重来3.3 自上而下分析自上而下分析 3.3.1自上而下分析的一般方法自上而下分析的一般方法例例 文法文法 S aCb C cd|c为输入串为输入串w=acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂的回溯技术复杂的回溯技术、回溯导回溯导致语义工作推倒重来致语义工作推倒重来、难以报告出错的确切难以报告出错的确切位置位置3.3 自上而下分析自上而下分析 3.3.1自上而下分析的一般方法自上而下分析的一般方法例例 文法文法 S aCb C cd|c为输入串为输入串w=acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处

23、理不能处理左递归左递归、复杂的回溯技术复杂的回溯技术、回溯导回溯导致语义工作推倒重来致语义工作推倒重来、难以报告出错的确切难以报告出错的确切位置位置、效率低效率低3.3 自上而下分析自上而下分析 3.3.2LL(1)文法文法对文法加什么样的限制可以保证没有对文法加什么样的限制可以保证没有回溯回溯？先定义两个和文法有关的函数先定义两个和文法有关的函数FIRST()=a|*a,a VT特别是，特别是，*时，规定时，规定 FIRST()对对A的任何两个不同选择的任何两个不同选择 i和和 j，希望有希望有FIRST(i)FIRST(j)=若若FIRST(i)或或FIRST(j)含含，还需增加条件，还需

24、增加条件3.3 自上而下分析自上而下分析 3.3.2LL(1)文法文法对文法加什么样的限制可以保证没有对文法加什么样的限制可以保证没有回溯回溯？先定义两个和文法有关的函数先定义两个和文法有关的函数FIRST()=a|*a,a VT特别是，特别是，*时，规定时，规定 FIRST()FOLLOW(A)=a|S*Aa，a VT如如果果A是是某某个个句句型型的的最最右右符符号号，那那么么$属属于于FOLLOW(A)3.3 自上而下分析自上而下分析 LL(1)文法文法任何两个产生式任何两个产生式A|都满足下列条件：都满足下列条件：FIRST()FIRST()=若若 *，那么，那么FIRST()FOLLO

25、W(A)=例如例如,对于下面文法，面临对于下面文法，面临a时，第时，第2步推导不步推导不知用哪个产生式知用哪个产生式S ABAa b|a FIRST(ab)FOLLOW(A)Ba CC 3.3 自上而下分析自上而下分析 LL(1)文法文法任何两个产生式任何两个产生式A|都满足下列条件：都满足下列条件：FIRST()FIRST()=若若 *，那么，那么FIRST()FOLLOW(A)=LL(1)文法有一些明显的性质文法有一些明显的性质没有公共左因子没有公共左因子不是二义的不是二义的不含左递归不含左递归3.3 自上而下分析自上而下分析 例例 ETE E +TE|TFT T FT|F(E)|idFI

26、RST(E)=FIRST(T)=FIRST(F)=(,idFIRST(E )=+,FRIST(T )=,FOLLOW(E)=FOLLOW(E )=),$FOLLOW(T)=FOLLOW(T )=+,),$FOLLOW(F)=+,),$3.3 自上而下分析自上而下分析 3.3.3递归下降的预测分析递归下降的预测分析为每一个非终结符写一个分析过程为每一个非终结符写一个分析过程这些过程可能是递归的这些过程可能是递归的例例type simple|id|arraysimpleoftypesimple integer|char|numdotdotnum3.3 自上而下分析自上而下分析 一个辅助过程一个辅助

27、过程voidmatch(terminalt)if(lookahead=t)lookahead=nextToken();elseerror();3.3 自上而下分析自上而下分析 voidtype()if(lookahead=integer)|(lookahead=char)|(lookahead=num)simple();else if(lookahead=)match();match(id);elseif(lookahead=array)match(array);match();simple();match();match(of);type();elseerror();type simple|

28、id|arraysimpleoftype3.3 自上而下分析自上而下分析 voidsimple()if(lookahead=integer)match(integer);elseif(lookahead=char)match(char);elseif(lookahead=num)match(num);match(dotdot);match(num);elseerror();simple integer|char|numdotdotnum3.3 自上而下分析自上而下分析3.3.4非递归的预测分析非递归的预测分析a+b$输入输入预测分析程序预测分析程序分析表分析表M输出输出 XYZ$栈栈3.3 自

29、上而下分析自上而下分析非终非终结符结符输输 入入 符符 号号 id+.E E TE E E +TE T T FT T T T FT F F id 分析表的一部分分析表的一部分3.3 自上而下分析自上而下分析栈栈 输输 入入 输输 出出$E id id+id$预测预测分析器接受输入分析器接受输入id*id+id的前一部分动作的前一部分动作 3.3 自上而下分析自上而下分析栈栈 输输 入入 输输 出出$E id id+id$E T id id+id$E TE 预测预测分析器接受输入分析器接受输入id*id+id的前一部分动作的前一部分动作 3.3 自上而下分析自上而下分析栈栈 输输 入入 输输 出

30、出$E id id+id$E T id id+id$E TE$E T F id id+id$T FT 预测预测分析器接受输入分析器接受输入id*id+id的前一部分动作的前一部分动作 3.3 自上而下分析自上而下分析栈栈 输输 入入 输输 出出$E id id+id$E T id id+id$E TE$E T F id id+id$T FT$E T id id id+id$F id 预测预测分析器接受输入分析器接受输入id*id+id的前一部分动作的前一部分动作 3.3 自上而下分析自上而下分析栈栈 输输 入入 输输 出出$E id id+id$E T id id+id$E TE$E T F

31、id id+id$T FT$E T id id id+id$F id$E T id+id$预测预测分析器接受输入分析器接受输入id*id+id的前一部分动作的前一部分动作 3.3 自上而下分析自上而下分析栈栈 输输 入入 输输 出出$E id id+id$E T id id+id$E TE$E T F id id+id$T FT$E T id id id+id$F id$E T id+id$E T F id+id$T FT 预测预测分析器接受输入分析器接受输入id*id+id的前一部分动作的前一部分动作 3.3 自上而下分析自上而下分析栈栈 输输 入入 输输 出出$E id id+id$E T

32、 id id+id$E TE$E T F id id+id$T FT$E T id id id+id$F id$E T id+id$E T F id+id$T FT$E T F id+id$预测预测分析器接受输入分析器接受输入id*id+id的前一部分动作的前一部分动作 3.3 自上而下分析自上而下分析栈栈 输输 入入 输输 出出$E id id+id$E T id id+id$E TE$E T F id id+id$T FT$E T id id id+id$F id$E T id+id$E T F id+id$T FT$E T F id+id$E T id id+id$F id 预测预测分析

33、器接受输入分析器接受输入id*id+id的前一部分动作的前一部分动作 3.3 自上而下分析自上而下分析3.3.5构造预测分析表构造预测分析表（1）对文法的每个产生式对文法的每个产生式A ，执行执行(2)和和(3)（2）对）对FIRST()的每个终结符的每个终结符a，把把A 加入加入MA,a（3）如如果果 在在FIRST()中中，对对FOLLOW(A)的的每每个个终终结符结符b（包括包括$）,把把A 加入加入MA,b（4）M中中其它没有定义的条目都是其它没有定义的条目都是error3.3 自上而下分析自上而下分析非终非终结符结符 输输 入入 符符 号号 other b else.stmt stm

34、t other e_part e_part else stmte_part expr expr b 多重定义的条目多重定义的条目3.3 自上而下分析自上而下分析非终非终结符结符 输输 入入 符符 号号 other b else.stmt stmt other e_part e_part else stmtexpr expr b 消去多重定义消去多重定义3.3 自上而下分析自上而下分析3.3.6 预测分析的错误恢复预测分析的错误恢复1、先对编译器的错误处理做一个概述先对编译器的错误处理做一个概述词词法法错错误误，如如标标识识符符、关关键键字字或或算算符符的的拼拼写写错错语法错误，如算术表达式的括

35、号不配对语法错误，如算术表达式的括号不配对语义错误，如算符作用于不相容的运算对象语义错误，如算符作用于不相容的运算对象逻辑错误，如无穷的递归调用逻辑错误，如无穷的递归调用3.3 自上而下分析自上而下分析2、分析器对错误处理的基本目标、分析器对错误处理的基本目标清清楚楚而而准准确确地地报报告告错错误误的的出出现现，并并尽尽量量少少出出现现伪错误伪错误迅迅速速地地从从每每个个错错误误中中恢恢复复过过来来，以以便便诊诊断断后后面的错误面的错误它不应该使正确程序的处理速度降低太多它不应该使正确程序的处理速度降低太多 3.3 自上而下分析自上而下分析3、非递归预测分析在什么场合下发现错误、非递归预测分析

36、在什么场合下发现错误栈顶的终结符和下一个输入符号不匹配栈顶的终结符和下一个输入符号不匹配a+b$输入输入预测分析程序预测分析程序分析表分析表M输出输出 XYZ$栈栈3.3 自上而下分析自上而下分析3、非递归预测分析在什么场合下发现错误、非递归预测分析在什么场合下发现错误栈顶是非终结符栈顶是非终结符A，输入符号是输入符号是a，而而MA,a是是空白空白a+b$输入输入预测分析程序预测分析程序分析表分析表M输出输出 XYZ$栈栈3.3 自上而下分析自上而下分析4、非递归预测分析：采用、非递归预测分析：采用紧急方式的错误恢复紧急方式的错误恢复发现错误时，分析器每次抛弃一个输入记号，直发现错误时，分析器

37、每次抛弃一个输入记号，直到输入记号属于某个指定的同步记号集合为止到输入记号属于某个指定的同步记号集合为止5、同步、同步词法分析器当前提供的记号流能够构成的语法构词法分析器当前提供的记号流能够构成的语法构造，正是语法分析器所期望的造，正是语法分析器所期望的不同步的例子不同步的例子语法分析器期望剩余的前缀构成过程调用语句，语法分析器期望剩余的前缀构成过程调用语句，而实际剩余的前缀形成赋值语句而实际剩余的前缀形成赋值语句 3.3 自上而下分析自上而下分析6、同步记号集合的选择、同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合同步记号集合3.3

38、 自上而下分析自上而下分析6、同步记号集合的选择、同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合同步记号集合ifexpr thenstmt（then和分号等记号是和分号等记号是expr的同步记号）的同步记号）3.3 自上而下分析自上而下分析6、同步记号集合的选择、同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合同步记号集合把高层构造的开始符号加到低层构造的同步记号把高层构造的开始符号加到低层构造的同步记号集合中集合中3.3 自上而下分析自上而下分析6、同步记号集合的选择、同步记

39、号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合同步记号集合把高层构造的开始符号加到低层构造的同步记号把高层构造的开始符号加到低层构造的同步记号集合中集合中a=expr;if(语句的开始符号作为表达式的同步记号，以免表语句的开始符号作为表达式的同步记号，以免表达式出错又遗漏分号时忽略达式出错又遗漏分号时忽略if语句等一大段程序语句等一大段程序)3.3 自上而下分析自上而下分析6、同步记号集合的选择、同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合同步记号集合把高层构造的开始符号加到低层

40、构造的同步记号把高层构造的开始符号加到低层构造的同步记号集合中集合中把把FIRST(A)的终结符加入的终结符加入A的同步记号集合的同步记号集合a=expr;,if（语句的开始符号作为语句的同步符号，以免多出语句的开始符号作为语句的同步符号，以免多出一个逗号时会把一个逗号时会把if语句忽略了）语句忽略了）3.3 自上而下分析自上而下分析6、同步记号集合的选择、同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合同步记号集合把高层构造的开始符号加到低层构造的同步记号把高层构造的开始符号加到低层构造的同步记号集合中集合中把把FIRST(A)的终结

41、符加入的终结符加入A的同步记号集合的同步记号集合如果非终结符可以产生空串，若出错时栈顶是这如果非终结符可以产生空串，若出错时栈顶是这样的非终结符，则可以使用推出空串的产生式样的非终结符，则可以使用推出空串的产生式3.3 自上而下分析自上而下分析非终非终结符结符 输输 入入 符符 号号 id+.EETE E E+TE TTFT T 出错出错T T FT .例例 栈顶为栈顶为T ，面临，面临id时出错时出错3.3 自上而下分析自上而下分析非终非终结符结符 输输 入入 符符 号号 id+.EETE E E+TE TTFT T 出错，出错，用用T T T FT .T 可以产生空串，报错并用可以产生空串

42、，报错并用T 3.3 自上而下分析自上而下分析同步记号集合的选择同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合同步记号集合把高层结构的开始符号加到低层结构的同步记号把高层结构的开始符号加到低层结构的同步记号集合中集合中把把FIRST(A)的终结符加入的终结符加入A的同步记号集合的同步记号集合如果非终结符可以产生空串，若出错时栈顶是这如果非终结符可以产生空串，若出错时栈顶是这样的非终结符，则可以使用推出空串的产生式样的非终结符，则可以使用推出空串的产生式如果终结符在栈顶而不能匹配，弹出此终结符如果终结符在栈顶而不能匹配，弹出此终结符 3

43、.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc|bB d 3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc|bB dabbcde（读入（读入ab）ab3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc|bB dabbcdeaAbcde（归约）（归约）abA3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc|bB dabbcdeaAbcde（再读入（再读入bc）abAbc3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc|bB dab

44、bcdeaAbcdeaAde（归约）（归约）abAbAc3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc|bB dabbcdeaAbcdeaAde（再读入（再读入d）abAbdAc3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc|bB dabbcdeaAbcdeaAdeaABe（归约）（归约）abAbdAcB3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc|bB dabbcdeaAbcdeaAdeaABe(再读入再读入e)eabAbdAcB3.4 自下而上分析自下而上分析 3.4.1 归约归约

45、例例 S aABeA Abc|bB dabbcdeaAbcdeaAdeaABeS（归约）（归约）SeabAbdAcB3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc|bB dabbcdeaAbcdeaAdeaABeS S rm aABe rm aAde rm aAbcde rm abbcdeSeabAbdAcB3.4 自下而上分析自下而上分析 3.4.2 句柄句柄句型的句型的句柄句柄是和某产生式右部匹配的子串，是和某产生式右部匹配的子串，并且，把它归约成该产生式左部的非终结符并且，把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步代表了最右推导过

46、程的逆过程的一步S aABeA Abc|bB dS rm aABe rm aAde rm aAbcde rm abbcde句柄的右边仅含终结符句柄的右边仅含终结符如果文法二义，那么句柄可能不唯一如果文法二义，那么句柄可能不唯一3.4 自下而上分析自下而上分析 例例 句柄不唯一句柄不唯一E E+E|E E|(E)|id3.4 自下而上分析自下而上分析 例例 句柄不唯一句柄不唯一E E+E|E E|(E)|idE rm E Erm E E+Erm E E+id3rm E id2+id3 rm id1 id2+id3 3.4 自下而上分析自下而上分析 例例 句柄不唯一句柄不唯一E E+E|E E|(

47、E)|idE rm E E E rm E+Erm E E+Erm E+id3rm E E+id3rm E E+id3rm E id2+id3 rm E id2+id3 rm id1 id2+id3 rm id1 id2+id3 在句型在句型E E+id3中，句柄不唯一中，句柄不唯一3.4 自下而上分析自下而上分析 3.4.3用栈实现移进用栈实现移进 归约分析归约分析先通过先通过移进移进 归约分析器在分析输入串归约分析器在分析输入串id1 id2+id3时时的动作序列的动作序列来了解移进来了解移进 归约分析的工作方式归约分析的工作方式3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作

48、$id1 id2+id3$3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作$id1 id2+id3$移进移进 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作$id1 id2+id3$移进移进$id1 id2+id3$3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作$id1 id2+id3$移进移进$id1 id2+id3$按按E id归约归约 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作$id1 id2+id3$移进移进$id1 id2+id3$按按E id归约归约$E id2+id3$3.4 自下而上分析自下而上分析 栈栈 输输

49、入入 动动 作作$id1 id2+id3$移进移进$id1 id2+id3$按按E id归约归约$E id2+id3$移进移进 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作$id1 id2+id3$移进移进$id1 id2+id3$按按E id归约归约$E id2+id3$移进移进$E id2+id3$3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作$id1 id2+id3$移进移进$id1 id2+id3$按按E id归约归约$E id2+id3$移进移进$E id2+id3$移进移进 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作$id1 i

50、d2+id3$移进移进$id1 id2+id3$按按E id归约归约$E id2+id3$移进移进$E id2+id3$移进移进$E id2 +id3$3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作$id1 id2+id3$移进移进$id1 id2+id3$按按E id归约归约$E id2+id3$移进移进$E id2+id3$移进移进$E id2 +id3$按按E id归约归约 3.4 自下而上分析自下而上分析 栈栈 输输 入入 动动 作作$id1 id2+id3$移进移进$id1 id2+id3$按按E id归约归约$E id2+id3$移进移进$E id2+id3$移进移