编译原理-陈意云-23963chapter3

第三章语法分析,本章内容上下文无关文法自上而下分析和自下而上分析围绕分析器的自动生成展开,3.1上下文无关文法,3.1.1上下文无关文法的定义正规式能定义一些简单的语言，能表示给定结构的固定次数的重复或者没有指定次数的重复例：a(ba)5,a(ba)*正规式不能用于描述配对或嵌套的结构例1：配对括号串的集合例2：wcw|w是a和b的串,3.1上下文无关文法,上下文无关文法是四元组（VT,VN,S,P）VT:终结符集合VN:非终结符集合S:开始符号P:产生式集合，产生式形式:A例(id,+,(,),expr,op,expr,P)exprexpropexprexpr(expr)exprexprexpridop+op,3.1上下文无关文法,例(id,+,(,),expr,op,expr,P)exprexpropexprexpr(expr)exprexprexpridop+op简化表示EEAE|(E)|E|idA+|,3.1上下文无关文法,3.1.2推导把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替例EE+E|EE|(E)|E|idEE(E)(E+E)(id+E)(id+id)概念上下文无关语言、等价的文法、句型记号S*、S+w,3.1上下文无关文法,EE+E|EE|(E)|E|id最左推导ElmElm(E)lm(E+E)lm(id+E)lm(id+id)最右推导（规范推导）ErmErm(E)rm(E+E)rm(E+id)rm(id+id),3.1上下文无关文法,3.1.3分析树,3.1上下文无关文法,3.1.4二义性EEEEE+EidEEE+EidE+EidE+Eidid+Eidid+Eidid+ididid+id,3.1上下文无关文法,3.1.4二义性EEEEE+EidEEE+EidE+EidE+Eidid+Eidid+Eidid+ididid+id,3.2语言和文法,文法的优点文法给出了精确的，易于理解的语法说明,3.2语言和文法,文法的优点文法给出了精确的，易于理解的语法说明自动产生高效的分析器,3.2语言和文法,文法的优点文法给出了精确的，易于理解的语法说明自动产生高效的分析器可以给语言定义出层次结构,3.2语言和文法,文法的优点文法给出了精确的，易于理解的语法说明自动产生高效的分析器可以给语言定义出层次结构以文法为基础的语言的实现便于语言的修改,3.2语言和文法,文法的优点文法给出了精确的，易于理解的语法说明自动产生高效的分析器可以给语言定义出层次结构以文法为基础的语言的实现便于语言的修改文法的问题文法只能描述编程语言的大部分语法,3.2语言和文法,3.2.1正规式和上下文无关文法的比较正规式(a|b)*ab,3.2语言和文法,3.2.1正规式和上下文无关文法的比较正规式(a|b)*ab,3.2语言和文法,3.2.1正规式和上下文无关文法的比较正规式(a|b)*ab文法A0aA0|bA0|aA1A1bA2A2,3.2语言和文法,3.2.2分离词法分析器理由为什么要用正规式定义词法词法规则非常简单，不必用上下文无关文法,3.2语言和文法,3.2.2分离词法分析器理由为什么要用正规式定义词法词法规则非常简单，不必用上下文无关文法对于词法记号，正规式描述简洁且易于理解,3.2语言和文法,3.2.2分离词法分析器理由为什么要用正规式定义词法词法规则非常简单，不必用上下文无关文法对于词法记号，正规式描述简洁且易于理解从正规式构造出的词法分析器效率高,3.2语言和文法,从软件工程角度看，词法分析和语法分析的分离有如下好处简化设计,3.2语言和文法,从软件工程角度看，词法分析和语法分析的分离有如下好处简化设计编译器的效率会改进,3.2语言和文法,从软件工程角度看，词法分析和语法分析的分离有如下好处简化设计编译器的效率会改进编译器的可移植性加强,3.2语言和文法,从软件工程角度看，词法分析和语法分析的分离有如下好处简化设计编译器的效率会改进编译器的可移植性加强便于编译器前端的模块划分,3.2语言和文法,能否把词法分析并入到语法分析中，直接从字符流进行语法分析若把词法分析和语法分析合在一起，则必须将语言的注解和空白的规则反映在文法中，文法将大大复杂注解和空白由自己来处理的分析器，比注解和空格已由词法分析器删除的分析器要复杂得多,3.2语言和文法,3.2.3验证文法产生的语言G:S(S)S|L(G)=配对的括号串的集合,3.2语言和文法,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)y,3.2语言和文法,3.2.3验证文法产生的语言G:S(S)S|L(G)=配对的括号串的集合按串长进行归纳：配对括号串可由S推出,3.2语言和文法,3.2.3验证文法产生的语言G:S(S)S|L(G)=配对的括号串的集合按串长进行归纳：配对括号串可由S推出归纳基础：S归纳假设：长度小于2n的都可以从S推导出来归纳步骤：考虑长度为2n(n1)的w=(x)yS(S)S*(x)S*(x)y,3.2语言和文法,3.2.4适当的表达式文法用一种层次观点看待表达式idid(id+id)+idid+id,3.2语言和文法,3.2.4适当的表达式文法用一种层次观点看待表达式idid(id+id)+idid+ididid(id+id),3.2语言和文法,3.2.4适当的表达式文法用一种层次观点看待表达式idid(id+id)+idid+ididid(id+id)文法exprexpr+term|term,3.2语言和文法,3.2.4适当的表达式文法用一种层次观点看待表达式idid(id+id)+idid+ididid(id+id)文法exprexpr+term|termtermtermfactor|factor,3.2语言和文法,3.2.4适当的表达式文法用一种层次观点看待表达式idid(id+id)+idid+ididid(id+id)文法exprexpr+term|termtermtermfactor|factorfactorid|(expr),3.2语言和文法,exprexpr+term|termtermtermfactor|factorfactorid|(expr),ididid和id+idid的分析树,3.2语言和文法,3.2.5消除二义性stmtifexprthenstmt|ifexprthenstmtelsestmt|other句型：ifexprthenifexprthenstmtelsestmt,3.2语言和文法,3.2.5消除二义性stmtifexprthenstmt|ifexprthenstmtelsestmt|other句型：ifexprthenifexprthenstmtelsestmt两个最左推导：stmtifexprthenstmtifexprthenifexprthenstmtelsestmt,3.2语言和文法,3.2.5消除二义性stmtifexprthenstmt|ifexprthenstmtelsestmt|other句型：ifexprthenifexprthenstmtelsestmt两个最左推导：stmtifexprthenstmtifexprthenifexprthenstmtelsestmtstmtifexprthenstmtelsestmtifexprthenifexprthenstmtelsestmt,3.2语言和文法,无二义的文法stmtmatched_stmt|unmatched_stmtmatched_stmtifexprthenmatched_stmtelsematched_stmt|otherunmatched_stmtifexprthenstmt|ifexprthenmatched_stmtelseunmatched_stmt,3.2语言和文法,3.2.6消除左递归文法左递归A+Aa,3.2语言和文法,3.2.6消除左递归文法左递归A+Aa直接左递归AAa|b串的特点ba.a,3.2语言和文法,3.2.6消除左递归文法左递归A+Aa直接左递归AAa|b串的特点ba.a消除直接左递归AbAAaA|,3.2语言和文法,例算术表达文法EE+T|T（T+T.+T）TTF|F（FF.F）F(E)|id,3.2语言和文法,例算术表达文法EE+T|T（T+T.+T）TTF|F（FF.F）F(E)|id消除左递归后文法ETEE+TE|TFTTFT|F(E)|id,3.2语言和文法,非直接左递归SAa|bASd|,3.2语言和文法,非直接左递归SAa|bASd|先变换成直接左递归SAa|bAAad|bd|,3.2语言和文法,非直接左递归SAa|bASd|先变换成直接左递归SAa|bAAad|bd|再消除左递归SAa|bAbdA|AAadA|,3.2语言和文法,3.2.7提左因子有左因子的文法A1|2,3.2语言和文法,3.2.7提左因子有左因子的文法A1|2提左因子AAA1|2,3.2语言和文法,例悬空else的文法stmtifexprthenstmtelsestmt|ifexprthenstmt|other,3.2语言和文法,例悬空else的文法stmtifexprthenstmtelsestmt|ifexprthenstmt|other提左因子stmtifexprthenstmtoptional_else_part|otheroptional_else_partelsestmt|,3.2语言和文法,3.2.8非上下文无关的语言结构L1=wcw|w属于(a|b)*标识符的声明应先于其引用的抽象,3.2语言和文法,3.2.8非上下文无关的语言结构L1=wcw|w属于(a|b)*标识符的声明应先于其引用的抽象L2=anbmcndm|n0,m0形参个数和实参个数应该相同的抽象,3.2语言和文法,3.2.8非上下文无关的语言结构L1=wcw|w属于(a|b)*标识符的声明应先于其引用的抽象L2=anbmcndm|n0,m0形参个数和实参个数应该相同的抽象L3=anbncn|n0早先排版描述的一个现象的抽象,3.2语言和文法,L1=wcwR|w(a|b)*SaSa|bSb|c,3.2语言和文法,L1=wcwR|w(a|b)*SaSa|bSb|cL2=anbmcmdn|n1,m1SaSd|aAdAbAc|bc,3.2语言和文法,L1=wcwR|w(a|b)*SaSa|bSb|cL2=anbmcmdn|n1,m1SaSd|aAdAbAc|bcL2=anbncmdm|n1，m1SABAaAb|abBcBd|cd,3.2语言和文法,L3=anbn|n1SaSb|ab,3.2语言和文法,L3=anbn|n1SaSb|abL3是不能用正规式描述的语言的一个范例,3.2语言和文法,L3=anbn|n1SaSb|abL3是不能用正规式描述的语言的一个范例若存在接受L3的DFAD，状态数为k个,3.2语言和文法,L3=anbn|n1SaSb|abL3是不能用正规式描述的语言的一个范例若存在接受L3的DFAD，状态数为k个设D读完,a,aa,ak分别到达状态s0,s1,sk,3.2语言和文法,L3=anbn|n1SaSb|abL3是不能用正规式描述的语言的一个范例若存在接受L3的DFAD，状态数为k个设D读完,a,aa,ak分别到达状态s0,s1,sk至少有两个状态相同，例如是si和sj，则ajbi属于L3,3.2语言和文法,L3=anbn|n1SaSb|abL3是不能用正规式描述的语言的一个范例若存在接受L3的DFAD，状态数为k个设D读完,a,aa,ak分别到达状态s0,s1,sk至少有两个状态相同，例如是si和sj，则ajbi属于L3,3.2语言和文法,3.2.9形式语言鸟瞰文法G=(VT,VN,S,P)0型文法：，,(VNVT)*,|1,3.2语言和文法,3.2.9形式语言鸟瞰文法G=(VT,VN,S,P)0型文法：，,(VNVT)*,|1短语文法,3.2语言和文法,3.2.9形式语言鸟瞰文法G=(VT,VN,S,P)0型文法：，,(VNVT)*,|11型文法：|，但S可以例外短语文法,3.2语言和文法,3.2.9形式语言鸟瞰文法G=(VT,VN,S,P)0型文法：，,(VNVT)*,|11型文法：|，但S可以例外短语文法、上下文有关文法,3.2语言和文法,3.2.9形式语言鸟瞰文法G=(VT,VN,S,P)0型文法：，,(VNVT)*,|11型文法：|，但S可以例外2型文法：A，AVN,(VNVT)*短语文法、上下文有关文法,3.2语言和文法,3.2.9形式语言鸟瞰文法G=(VT,VN,S,P)0型文法：，,(VNVT)*,|11型文法：|，但S可以例外2型文法：A，AVN,(VNVT)*短语文法、上下文有关文法、上下文无关文法,3.2语言和文法,3.2.9形式语言鸟瞰文法G=(VT,VN,S,P)0型文法：，,(VNVT)*,|11型文法：|，但S可以例外2型文法：A，AVN,(VNVT)*3型文法：AaB或Aa，A,BVN,aVT短语文法、上下文有关文法、上下文无关文法,3.2语言和文法,3.2.9形式语言鸟瞰文法G=(VT,VN,S,P)0型文法：，,(VNVT)*,|11型文法：|，但S可以例外2型文法：A，AVN,(VNVT)*3型文法：AaB或Aa，A,BVN,aVT短语文法、上下文有关文法、上下文无关文法、正规文法,3.2语言和文法,例：L3anbncn|n1的上下文有关文法SaSBCSaBCCBBCaBabbBbbbCbccCcc,3.2语言和文法,例：L3anbncn|n1的上下文有关文法SaSBCSaBCCBBCaBabbBbbbCbccCccanbncn的推导过程如下：S*an-1S(BC)n1用SaSBCn-1次,3.2语言和文法,例：L3anbncn|n1的上下文有关文法SaSBCSaBCCBBCaBabbBbbbCbccCccanbncn的推导过程如下：S*an-1S(BC)n1用SaSBCn-1次S+an(BC)n用SaBC1次,3.2语言和文法,例：L3anbncn|n1的上下文有关文法SaSBCSaBCCBBCaBabbBbbbCbccCccanbncn的推导过程如下：S*an-1S(BC)n1用SaSBCn-1次S+an(BC)n用SaBC1次S+anBnCn用CBBC交换相邻的CB,3.2语言和文法,例：L3anbncn|n1的上下文有关文法SaSBCSaBCCBBCaBabbBbbbCbccCccanbncn的推导过程如下：S*an-1S(BC)n1用SaSBCn-1次S+an(BC)n用SaBC1次S+anBnCn用CBBC交换相邻的CBS+anbBn1Cn用aBab1次,3.2语言和文法,例：L3anbncn|n1的上下文有关文法SaSBCSaBCCBBCaBabbBbbbCbccCccanbncn的推导过程如下：S*an-1S(BC)n1用SaSBCn-1次S+an(BC)n用SaBC1次S+anBnCn用CBBC交换相邻的CBS+anbBn1Cn用aBab1次S+anbnCn用bBbbn-1次,3.2语言和文法,例：L3anbncn|n1的上下文有关文法SaSBCSaBCCBBCaBabbBbbbCbccCccanbncn的推导过程如下：S*an-1S(BC)n1用SaSBCn-1次S+an(BC)n用SaBC1次S+anBnCn用CBBC交换相邻的CBS+anbBn1Cn用aBab1次S+anbnCn用bBbbn-1次S+anbncCn-1用bCbc1次,3.2语言和文法,例：L3anbncn|n1的上下文有关文法SaSBCSaBCCBBCaBabbBbbbCbccCccanbncn的推导过程如下：S*an-1S(BC)n1用SaSBCn-1次S+an(BC)n用SaBC1次S+anBnCn用CBBC交换相邻的CBS+anbBn1Cn用aBab1次S+anbnCn用bBbbn-1次S+anbncCn-1用bCbc1次S+anbncn用cCccn-1次,3.3自上而下分析,3.3.1自上而下分析的一般方法例：文法SaCbCcd|c为输入串w=acb建立分析树,3.3自上而下分析,3.3.1自上而下分析的一般方法例：文法SaCbCcd|c为输入串w=acb建立分析树,3.3自上而下分析,3.3.1自上而下分析的一般方法例：文法SaCbCcd|c为输入串w=acb建立分析树,3.3自上而下分析,3.3.1自上而下分析的一般方法例：文法SaCbCcd|c为输入串w=acb建立分析树,3.3自上而下分析,3.3.1自上而下分析的一般方法例：文法SaCbCcd|c为输入串w=acb建立分析树,不能处理左递归,3.3自上而下分析,3.3.1自上而下分析的一般方法例：文法SaCbCcd|c为输入串w=acb建立分析树,不能处理左递归、复杂的回溯技术,3.3自上而下分析,3.3.1自上而下分析的一般方法例：文法SaCbCcd|c为输入串w=acb建立分析树,不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来,3.3自上而下分析,3.3.1自上而下分析的一般方法例：文法SaCbCcd|c为输入串w=acb建立分析树,不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来、难以报告出错的确切位置,3.3自上而下分析,3.3.1自上而下分析的一般方法例：文法SaCbCcd|c为输入串w=acb建立分析树,不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来、难以报告出错的确切位置、效率低,3.3自上而下分析,3.3.2LL(1)文法对文法加什么样的限制可以保证没有回溯？先定义两个和文法有关的函数FIRST()=a|*a,aVT,3.3自上而下分析,3.3.2LL(1)文法对文法加什么样的限制可以保证没有回溯？先定义两个和文法有关的函数FIRST()=a|*a,aVT特别是，*时，规定FIRST(),3.3自上而下分析,3.3.2LL(1)文法对文法加什么样的限制可以保证没有回溯？先定义两个和文法有关的函数FIRST()=a|*a,aVT特别是，*时，规定FIRST()对A的任何两个不同选择i和j，希望有FIRST(i)FIRST(j)=,3.3自上而下分析,3.3.2LL(1)文法对文法加什么样的限制可以保证没有回溯？先定义两个和文法有关的函数FIRST()=a|*a,aVT特别是，*时，规定FIRST()对A的任何两个不同选择i和j，希望有FIRST(i)FIRST(j)=若FIRST(i)或FIRST(j)含，还需增加条件,3.3自上而下分析,3.3.2LL(1)文法对文法加什么样的限制可以保证没有回溯？先定义两个和文法有关的函数FIRST()=a|*a,aVT特别是，*时，规定FIRST()FOLLOW(A)=a|S*Aa，aVT,3.3自上而下分析,3.3.2LL(1)文法对文法加什么样的限制可以保证没有回溯？先定义两个和文法有关的函数FIRST()=a|*a,aVT特别是，*时，规定FIRST()FOLLOW(A)=a|S*Aa，aVT如果A是某个句型的最右符号，那么$属于FOLLOW(A),3.3自上而下分析,LL(1)文法任何两个产生式A|都满足下列条件：FIRST()FIRST()=若*，那么FIRST()FOLLOW(A)=,3.3自上而下分析,LL(1)文法任何两个产生式A|都满足下列条件：FIRST()FIRST()=若*，那么FIRST()FOLLOW(A)=例如,对于下面文法，面临a时不知用什么规则SABAab|aFIRST(ab)FOLLOW(A)BaCC,3.3自上而下分析,LL(1)文法任何两个产生式A|都满足下列条件：FIRST()FIRST()=若*，那么FIRST()FOLLOW(A)=LL(1)文法有一些明显的性质没有公共左因子不是二义的不含左递归,3.3自上而下分析,例ETEE+TE|TFTTFT|F(E)|id,3.3自上而下分析,例ETEE+TE|TFTTFT|F(E)|idFIRST(E)=FIRST(T)=FIRST(F)=(,id,3.3自上而下分析,例ETEE+TE|TFTTFT|F(E)|idFIRST(E)=FIRST(T)=FIRST(F)=(,idFIRST(E)=+,3.3自上而下分析,例ETEE+TE|TFTTFT|F(E)|idFIRST(E)=FIRST(T)=FIRST(F)=(,idFIRST(E)=+,FRIST(T)=,3.3自上而下分析,例ETEE+TE|TFTTFT|F(E)|idFIRST(E)=FIRST(T)=FIRST(F)=(,idFIRST(E)=+,FRIST(T)=,FOLLOW(E)=FOLLOW(E)=),$,3.3自上而下分析,例ETEE+TE|TFTTFT|F(E)|idFIRST(E)=FIRST(T)=FIRST(F)=(,idFIRST(E)=+,FRIST(T)=,FOLLOW(E)=FOLLOW(E)=),$FOLLOW(T)=FOLLOW(T)=+,),$,3.3自上而下分析,例ETEE+TE|TFTTFT|F(E)|idFIRST(E)=FIRST(T)=FIRST(F)=(,idFIRST(E)=+,FRIST(T)=,FOLLOW(E)=FOLLOW(E)=),$FOLLOW(T)=FOLLOW(T)=+,),$FOLLOW(F)=+,),$,3.3自上而下分析,3.3.3递归下降的预测分析为每一个非终结符写一个分析过程这些过程可能是递归的例：typesimple|id|arraysimpleoftypesimpleinteger|char|numdotdotnum,3.3自上而下分析,一个辅助过程voidmatch(terminalt)if(lookahead=t)lookahead=nextToken();elseerror();,3.3自上而下分析,voidtype()if(lookahead=integer)|(lookahead=char)|(lookahead=num)simple();elseif(lookahead=)match();match(id);elseif(lookahead=array)match(array);match();simple();match();match(of);type();elseerror();,typesimple|id|arraysimpleoftype,3.3自上而下分析,voidsimple()if(lookahead=integer)match(integer);elseif(lookahead=char)match(char);elseif(lookahead=num)match(num);match(dotdot);match(num);elseerror();,simpleinteger|char|numdotdotnum,3.3自上而下分析,3.3.4非递归的预测分析,3.3自上而下分析,3.3自上而下分析,预测分析器接受输入id*id+id的动作,3.3自上而下分析,预测分析器接受输入id*id+id的动作,3.3自上而下分析,预测分析器接受输入id*id+id的动作,3.3自上而下分析,预测分析器接受输入id*id+id的动作,3.3自上而下分析,预测分析器接受输入id*id+id的动作,3.3自上而下分析,预测分析器接受输入id*id+id的动作,3.3自上而下分析,预测分析器接受输入id*id+id的动作,3.3自上而下分析,预测分析器接受输入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的其它没有定义的条目都是error,3.3自上而下分析,多重定义的条目,3.3自上而下分析,多重定义的条目,3.3自上而下分析,3.3.6预测分析的错误恢复先对编译器的错误处理做一个概述词法错误，如标识符、关键字或算符的拼写错,3.3自上而下分析,3.3.6预测分析的错误恢复先对编译器的错误处理做一个概述词法错误，如标识符、关键字或算符的拼写错语法错误，如算术表达式的括号不配对,3.3自上而下分析,3.3.6预测分析的错误恢复先对编译器的错误处理做一个概述词法错误，如标识符、关键字或算符的拼写错语法错误，如算术表达式的括号不配对语义错误，如算符作用于不相容的运算对象,3.3自上而下分析,3.3.6预测分析的错误恢复先对编译器的错误处理做一个概述词法错误，如标识符、关键字或算符的拼写错语法错误，如算术表达式的括号不配对语义错误，如算符作用于不相容的运算对象逻辑错误，如无穷的递归调用,3.3自上而下分析,分析器对错误处理的基本目标清楚而准确地报告错误的出现,3.3自上而下分析,分析器对错误处理的基本目标清楚而准确地报告错误的出现迅速地从每个错误中恢复过来，以便诊断后面的错误，并尽量少出现伪错误,3.3自上而下分析,分析器对错误处理的基本目标清楚而准确地报告错误的出现迅速地从每个错误中恢复过来，以便诊断后面的错误，并尽量少出现伪错误它不应该使正确程序的处理速度降低太多,3.3自上而下分析,非递归预测分析在什么场合下发现错误栈顶的终结符和下一个输入符号不匹配栈顶是非终结符A，输入符号是a，而MA,a是空白,3.3自上而下分析,非递归预测分析：采用紧急方式的错误恢复发现错误时，分析器每次抛弃一个输入记号，直到输入记号属于某个指定的同步记号集合为止,3.3自上而下分析,非递归预测分析：采用紧急方式的错误恢复发现错误时，分析器每次抛弃一个输入记号，直到输入记号属于某个指定的同步记号集合为止同步词法分析器当前提供的记号流能构成的语法结构，正是语法分析器所期望的,3.3自上而下分析,同步记号集合的选择把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合,3.3自上而下分析,同步记号集合的选择把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合ifexprthenstmt（then是expr的一个同步记号）,3.3自上而下分析,同步记号集合的选择把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合把高层结构的开始符号加到低层结构的同步记号集合中,3.3自上而下分析,同步记号集合的选择把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合把高层结构的开始符号加到低层结构的同步记号集合中a=expr;if（语句的开始符号作为表达式的同步符号，以免遗漏分号时忽略if语句等一大段程序）,3.3自上而下分析,同步记号集合的选择把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合把高层结构的开始符号加到低层结构的同步记号集合中把FIRST(A)的终结符加入A的同步记号集合a=expr;,if（语句的开始符号作为语句的同步符号，以免多出一个逗号时会把if语句忽略了）,3.3自上而下分析,同步记号集合的选择把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合把高层结构的开始符号加到低层结构的同步记号集合中把FIRST(A)的终结符加入A的同步记号集合如果非终结符可以产生空串，若出错时栈顶是这样的非终结符，则可以使用产生空串的产生式,3.3自上而下分析,栈顶为T，面临id时出错,3.3自上而下分析,T可以产生空串，报错并用T,3.3自上而下分析,同步记号集合的选择把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合把高层结构的开始符号加到低层结构的同步记号集合中把FIRST(A)的终结符加入A的同步记号集合如果非终结符可以产生空串，若出错时栈顶是这样的非终结符，则可以使用产生空串的产生式如果终结符在栈顶而不能匹配，弹出此终结符,3.4自下而上分析,3.4.1归约例SaABeAAbc|bBd,3.4自下而上分析,3.4.1归约例SaABeAAbc|bBdabbcde,3.4自下而上分析,3.4.1归约例SaABeAAbc|bBdabbcdeaAbcde,3.4自下而上分析,3.4.1归约例SaABeAAbc|bBdabbcdeaAbcdeaAde,3.4自下而上分析,3.4.1归约例SaABeAAbc|bBdabbcdeaAbcdeaAdeaABe,3.4自下而上分析,3.4.1归约例SaABeAAbc|bBdabbcdeaAbcdeaAdeaABeS,3.4自下而上分析,3.4.1归约例SaABeAAbc|bBdabbcdeaAbcdeaAdeaABeSSrmaABermaAdermaAbcdermabbcde,3.4自下而上分析,3.4.2句柄句型的句柄是和某产生式右部匹配的子串，并且，把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步,3.4自下而上分析,3.4.2句柄句型的句柄是和某产生式右部匹配的子串，并且，把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步SaABeAAbc|bBdSrmaABermaAdermaAbcdermabbcde,3.4自下而上分析,3.4.2句柄句型的句柄是和某产生式右部匹配的子串，并且，把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步SaABeAAbc|bBdSrmaABermaAdermaAbcdermabbcde句柄的右边仅含终结符,3.4自下而上分析,3.4.2句柄句型的句柄是和某产生式右部匹配的子串，并且，把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步SaABeAAbc|bBdSrmaABermaAdermaAbcdermabbcde句柄的右边仅含终结符如果文法二义，那么句柄可能不唯一,3.4自下而上分析,例EE+E|EE|(E)|id,3.4自下而上分析,例EE+E|EE|(E)|idErmEErmEE+ErmEE+id3rmEid2+id3rmid1id2+id3,3.4自下而上分析,例EE+E|EE|(E)|idErmEEErmE+ErmEE+ErmE+id3rmEE+id3rmEE+id3rmEid2+id3rmEid2+id3rmid1id2+id3rmid1id2+id3在句型EE+id3中，句柄不唯一,3.4自下而上分析,3.4.3用栈实现移进归约分析先通过移进归约分析器在分析输入串id1id2+id3时的动作序列来了解移进归约分析的工作方式,3.4自下而上分析,3.4自下而上分析,3.4自下而上分析,3.4自下而上分析,3.4自下而上分析,3.4自下而上分析,3.4自下而上分析,3.4自下而上分析,3.4自下而上分析,3.4自下而上分析,3.4自下而上分析,3.4自下而上分析,3.4自下而上分析,3.4自下而上分析,3.4自下而上分析,3.4自下而上分析,3.4自下而上分析,3.4自下而上分析,3.4自下而上分析,3.4自下而上分析,3.4自下而上分析,3.4自下而上分析,3.4自下而上分析,要想很好地使用移进归约方式，尚需解决一些问题如何决策选择移进还是归约进行归约时，确定右句型中将要归约的子串进行归约时，如何确定选择哪一个产生式,3.4自下而上分析,3.4.4移进归约分析的冲突移进归约冲突例stmtifexprthenstmt|ifexprthenstmtelsestmt|other如果移进归约分析器处于格局栈输入ifexprthenstmtelse$,3.4自下而上分析,归约归约冲突stmtid(parameter_list)|expr=exprparameter_listparameter_list,parameter|parameterparameteridexprid(expr_list)|idexpr_listexpr_list,expr|expr,3.4自下而上分析,归约归约冲突stmtid(parameter_list)|expr:=exprparameter_listparameter_list,parameter|parameterparameteridexprid(expr_list)|idexpr_listexpr_list,expr|expr由A(I,J)开始的语句栈输入id(id,id),3.4自下而上分析,归约归约冲突stmtid(parameter_list)|expr:=exprparameter_listparameter_list,parameter|parameterparameteridexprid(expr_list)|idexpr_listexpr_list,expr|expr由A(I,J)开始的语句栈输入id(id,id),归约成expr,还是parameter?,3.4自下而上分析,归约归约冲突stmtid(parameter_list)|expr:=exprparameter_listparameter_list,parameter|parameterparameteridexprid(expr_list)|idexpr_listexpr_list,expr|expr由A(I,J)开始的语句(词法分析查符号表,区分首个id)栈输入procid(id,id),3.5LR分析器,本节介绍LR(k)分析技术特点适用于一大类上下文无关文法效率高主要介绍构造LR分析表的三种技术简单的LR方法（简称SLR）规范的LR方法向前看的LR方法（简称LALR）,3.5LR分析器,3.5.1LR分析算法,3.5LR分析器,例EE+T|ETTTF|TEF(E)|Fid,3.5LR分析器,3.5LR分析器,3.5LR分析器,3.5LR分析器,3.5LR分析器,3.5LR分析器,3.5LR分析器,3.5LR分析器,3.5LR分析器,3.5LR分析器,3.5LR分析器,3.5LR分析器,3.5LR分析器,3.5LR分析器,3.5LR分析器,3.5LR分析器,3.5LR分析器,3.5LR分析器,3.5.2LR文法和LR分析方法的特点概念活前缀：右句型的前缀，该前缀不超过最右句柄的右端S*rmAwrmw,3.5LR分析器,3.5.2LR文法和LR分析方法的特点概念活前缀：右句型的前缀，该前缀不超过最右句柄的右端S*rmAwrmw的任何前缀（包括和本身）都是一个活前缀,3.5LR分析器,3.5.2LR文法和LR分析方法的特点概念活前缀：右句型的前缀，该前缀不超过最右句柄的右端定义LR文法：我们能为之构造出所有条目都唯一的LR分析表,3.5LR分析器,LR分析方法的特点栈中的文法符号总是形成一个活前缀,3.5LR分析器,3.5LR分析器,LR分析方法的特点栈中的文法符号总是形成一个活前缀分析表的转移函数本质上是识别活前缀的DFA,3.5LR分析器,例EE+T|ETTTF|TEF(E)|Fid,3.5LR分析器,LR分析方法的特点栈中的文法符号总是形成一个活前缀分析表的转移函数本质上是识别活前缀的DFA栈顶的状态符号包含了确定句柄所需要的一切信息,3.5LR分析器,LR分析方法的特点栈中的文法符号总是形成一个活前缀分析表的转移函数本质上是识别活前缀的DFA栈顶的状态符号包含了确定句柄所需要的一切信息是已知的最一般的无回溯的移进归约方法,3.5LR分析器,LR分析方法的特点栈中的文法符号总是形成一个活前缀分析表的转移函数本质上是识别活前缀的DFA栈顶的状态符号包含了确定句柄所需要的一切信息是已知的最一般的无回溯的移进归约方法能分析的文法类是预测分析法能分析的文法类的真超集,3.5LR分析器,LR分析方法的特点栈中的文法符号总是形成一个活前缀分析表的转移函数本质上是识别活前缀的DFA栈顶的状态符号包含了确定句柄所需要的一切信息是已知的最一般的无回溯的移进归约方法能分析的文法类是预测分析法能分析的文法类的真超集能及时发现语法错误,3.5LR分析器,LR分析方法的特点栈中的文法符号总是形成一个活前缀分析表的转移函数本质上是识别活前缀的DFA栈顶的状态符号包含了确定句柄所需要的一切信息是已知的最一般的无回溯的移进归约方法能分析的文法类是预测分析法能分析的文法类的真超集能及时发现语法错误手工构造分析表的工作量太大,3.5LR分析器,LR分析方法和LL分析方法的比较,3.5LR分析器,LR分析方法和LL分析方法的比较,3.5LR分析器,LR分析方法和LL分析方法的比较在下面的推导中，最后一步用的是AlSrmrmAbwrmlbw,3.5LR分析器,LR分析方法和LL分析方法的比较在下面的推导中，最后一步用的是AlSrmrmAbwrmlbw,LL(1)决定用该产生式的位置,3.5LR分析器,LR分析方法和LL分析方法的比较在下面的推导中，最后一步用的是AlSrmrmAbwrmlbw,LL(1)决定用该产生式的位置,LR(1)决定用该产生式的位置,3.5LR分析器,LR分析方法和LL分析方法的比较,3.5LR分析器,LR分析方法和LL分析方法的比较,3.5LR分析器,LR分析方法和LL分析方法的比较,3.5LR分析器,LR分析方法和LL分析方法的比较,3.5LR分析器,LR分析方法和LL分析方法的比较,3.5LR分析器,LR分析方法和LL分析方法的比较,3.5LR分析器,3.5.3构造SLR分析表LR(0)项目（简称项目）在右部的某个地方加点的产生式,3.5LR分析器,3.5.3构造SLR分析表LR(0)项目（简称项目）加点的目的是用来表示分析过程中的状态,3.5LR分析器,3.5.3构造SLR分析表LR(0)项目（简称项目）加点的目的是用来表示分析过程中的状态,3.5LR分析器,3.5.3构造SLR分析表LR(0)项目（简称项目）加点的目的是用来表示分析过程中的状态,3.5LR分析器,3.5.3构造SLR分析表LR(0)项目（简称项目）加点的目的是用来表示分析过程中的状态,3.5LR分析器,3.5.3构造SLR分析表LR(0)项目（简称项目）在右部的某个地方加点的产生式例：AXYZ对应有四个项目AXYZAXYZAXYZAXYZ,3.5LR分析器,3.5.3构造SLR分析表LR(0)项目（简称项目）在右部的某个地方加点的产生式例：AXYZ对应有四个项目AXYZAXYZAXYZAXYZ例：A只有一个项目和它对应A,3.5LR分析器,构造SLR分析表的两大步骤从文法构造识别活前缀的DFA从上述DFA构造分析表,3.5LR分析器,从文法构造识别活前缀的DFA1.拓广文法EE+T|TTTF|FF(E)|id,3.5LR分析器,从文法构造识别活前缀的DFA1.拓广文法EEEE+T|TTTF|FF(E)|id,3.5LR分析器