单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,0型文法,1型文法,2型文法,3型文法,上下文无关文法,自上而下,自下而上,LL(1)文法,2个函数,任何两个产生式A,|,都满足下列条件：,1、FIRST(,),FIRST(,)=,2、若,*,，那么FIRST(,),FOLLOW(A)=,递归下降预测分析,非递归的预测分析,a,+,b,$,输入,预测分析程序,分析表,M,输出,X,Y,Z,$,栈,3.3,自上而下分析,3.3.6,预测分析的错误恢复,编译器的错误概述,:,词法错误，如标识符、关键字或算符的拼写错,语法错误，如算术表达式的括号不配对,语义错误，如算符作用于不相容的运算对象,逻辑错误，如无穷的递归调用,3.3,自上而下分析,分析器对错误处理的基本目标,清楚而准确地报告错误的出现,迅速地从每个错误中恢复过来，以便诊断后面的错误，并尽量少出现,伪错误,它不应该使正确程序的处理速度降低太多,3.3,自上而下分析,非递归预测分析在什么场合下发现错误,栈顶的终结符和下一个输入符号不匹配,栈顶是非终结符,A,，输入符号是,a,，而,M,A,a,是空白,3.3,自上而下分析,同步记号集合的选择,把,FOLLOW(,A,),的所有终结符放入非终结符,A,的同步记号集合。,if,expr,then,（then是,expr,的一个同步记号）,3.3,自上而下分析,同步记号集合的选择,把,FOLLOW(,A,),的所有终结符放入非终结符,A,的同步记号集合。,把高层结构的开始符号加到低层结构的同步记号集合中。,a,:=,expr,;if,（语句的开始符号作为表达式的同步符号，以免遗漏分号时忽略一大段程序。）,3.3,自上而下分析,同步记号集合的选择,把,FOLLOW(,A,),的所有终结符放入非终结符,A,的同步记号集合。,把高层结构的开始符号加到低层结构的同步记号集合中。,把,FIRST(,A,),的终结符加入,A,的同步记号集合。,3.3,自上而下分析,同步记号集合的选择,把,FOLLOW(,A,),的所有终结符放入非终结符,A,的同步记号集合。,把高层结构的开始符号加到低层结构的同步记号集合中。,把,FIRST(,A,),的终结符加入,A,的同步记号集合。,如果非终结符可以产生空串，若出错时栈顶是这样的非终结符，则可以使用产生空串的产生式。,如果终结符在栈顶而不能匹配，弹出此终结符。,1、DFA，接受,0,和,1,的个数都是偶数的字符串,3,1,2,0,1,1,1,1,0,0,0,0,开始,偶0偶1,奇0奇1,奇0偶1,偶0奇1,巩固与提高,反过来还需要考虑，任何由偶数个0和偶数个1构成的串是否都在这个语言中。这实际上是问，每个这样的串，其结构是否都符合正规式(00|11),(01|10)(00|11),(01|10)(00|11),),所做的刻划。我们可以这样叙述由偶数个0和偶数个1构成的串，从左向右，每两个字符一组地考察，它,1，由若干个（强调一下，可以是零个）00或11开始（这由正规式(00|11),描述）；,2一旦出现一个01或10，那么经过若干个00或11后，一定会出现一个01或10。这第二个01或10的后面可能还有若干个00或11，一直到串的结束，或者到再次出现01或10为止。如果串没有结束的话，就是重复出现这里所描述的结构（所以这由(01|10)(00|11),(01|10)(00|11),),描述）。,因此正规式(00|11),(01|10)(00|11),(01|10)(00|11),),描述的是偶数个0和偶数个1构成的串。,01,0011000011,100110,4、将下图的DFA极小化。,a,a,start,0,1,2,3,a,b,b,b,b,b,4,DFA,0,1,2,3,a,a,b,b,a,b,b,b,start,4,5,a,a,a,b,加入死状态后的DFA,1、加入死状态,2、合并不可区分状态,先把状态集分成非接受状态集,0,1,2,3,5,和接受状态集,4,这两个子集。,1集合,4,不能再分解，我们看集合,0,1,2,3,5。,move,(0,1,2,3,5,a)=1,2,5,move,(0,1,2,3,5,b)=3,4,5,由于,b,转换的结果,3,4,5,不是最初划分的某个集合的子集，因此,0,1,2,3,5,需要再分，由于状态,1,和状态,2,的,b,转换都到状态,4,。因此状态集合的进一步划分是：,1,2，0,3,5和4,2由于,move,(1,2,a)=2,5,move,(1,2,b)=4,move,(0,3,5,a)=1,5,move,(0,3,5,b)=3,5,显然,1,2,和,0,3,5,需要再分，分别分成：,1,和,2,以及,0,3,和,5,3由于,move,(0,3,a)=1,move,(0,3,b)=3,因此不需要再分。这样状态,0,和状态,3,合并成一个状态，我们取,0,为代表，再删去死状态,5,，就得到该题的结果。,正确做法！,最初的划分是,0,1,2,3,和,4。,1状态集合的进一步划分是：,1,2,，,0,3,和,4,2忽略了死状态的影响，会认为它们都不需要再分,错误做法！,1、直接合并不可区分状态,0,1,b,b,a,a,start,a,4,一个不正确的结果,a,a,start,0,1,2,3,a,b,b,b,b,b,4,DFA,procedure match(,t,),if 当前输入符号,t,then 取,下一个符号作为当前输入符号,else 报错。,procedure A,if 当前符号=,a,then match(,a,);调用A;,else return;,procedure B,if 当前符号=,b,then,match(,b,);调用B;,else if当前符号=,c,then,return;,else 报错。,procedure S,switch 当前符号,case,a,:调用 A;,case,b,:调用 B;,S,A|B,AaA|,BbB|,c,aaaaa,bbbbc,aaaaa,aa,bbbc,bbc,当非终结符的产生式有多种选择，即意味着分析过程有不同的展开方式。而我们只能根据当前输入符号来决定采用哪种展开方式（选择），这样就有了 FIRST（）函数。,5、LL(1)文法的自上而下分析及FIRST函数理解,栈,输,入,输,出,$,E,id,*,id$,$,E,T,id,*,id$,E,TE,$,E,T,F,id,*,id$,T,FT,$,E,T,id,id,*,id$,F,id,$,E,T,*,id$,$,E,T,F,*,*,id$,T,*,FT,$,E,T,F,id$,$,E,T,id,id$,F,id,$,E,T,$,$,E,$,T,$,$,E,E,E,$,6、LL(1)文法的自上而下的非递归分析方法理解,深度优先构造分析树,E,TE,E,+,TE,|,T,FT,T,*,FT,|,F,(,E,)|id,输入：id*id,栈,输,入,输,出,$,E,id,*,id$,$,E,T,id,*,id$,E,TE,$,E,T,F,id,*,id$,T,FT,$,E,T,id,id,*,id$,F,id,$,E,T,*,id$,$,E,T,F,*,*,id$,T,*,FT,$,E,T,F,id$,$,E,T,id,id$,F,id,$,E,T,$,$,E,$,T,$,$,E,E,T,E,T,E,$,栈,输,入,输,出,$,E,id,*,id$,$,E,T,id,*,id$,E,TE,$,E,T,F,id,*,id$,T,FT,$,E,T,id,id,*,id$,F,id,$,E,T,*,id$,$,E,T,F,*,*,id$,T,*,FT,$,E,T,F,id$,$,E,T,id,id$,F,id,$,E,T,$,$,E,$,T,$,$,E,E,T,E,F,T,F,T,E,$,栈,输,入,输,出,$,E,id,*,id$,$,E,T,id,*,id$,E,TE,$,E,T,F,id,*,id$,T,FT,$,E,T,id,id,*,id$,F,id,$,E,T,*,id$,$,E,T,F,*,*,id$,T,*,FT,$,E,T,F,id$,$,E,T,id,id$,F,id,$,E,T,$,$,E,$,T,$,$,E,E,T,E,F,T,id,T,E,$,栈,输,入,输,出,$,E,id,*,id$,$,E,T,id,*,id$,E,TE,$,E,T,F,id,*,id$,T,FT,$,E,T,id,id,*,id$,F,id,$,E,T,*,id$,$,E,T,F,*,*,id$,T,*,FT,$,E,T,F,id$,$,E,T,id,id$,F,id,$,E,T,$,$,E,$,T,$,$,E,E,T,E,F,T,id,*,T,F,*,F,T,E,$,栈,输,入,输,出,$,E,id,*,id$,$,E,T,id,*,id$,E,TE,$,E,T,F,id,*,id$,T,FT,$,E,T,id,id,*,id$,F,id,$,E,T,*,id$,$,E,T,F,*,*,id$,T,*,FT,$,E,T,F,id$,$,E,T,id,id$,F,id,$,E,T,$,$,E,$,T,$,$,E,E,T,E,F,T,id,*,T,F,F,T,E,$,栈,输,入,输,出,$,E,id,*,id$,$,E,T,id,*,id$,E,TE,$,E,T,F,id,*,id$,T,FT,$,E,T,id,id,*,id$,F,id,$,E,T,*,id$,$,E,T,F,*,*,id$,T,*,FT,$,E,T,F,id$,$,E,T,id,id$,F,id,$,E,T,$,$,E,$,T,$,$,E,E,T,E,F,T,id,*,T,F,id,T,E,$,栈,输,入,输,出,$,E,id,*,id$,$,E,T,id,*,id$,E,TE,$,E,T,F,id,*,id$,T,FT,$,E,T,id,id,*,id$,F,id,$,E,T,*,id$,$,E,T,F,*,*,id$,T,*,FT,$,E,T,F,id$,$,E,T,id,id$,F,id,$,E,T,$,$,E,$,T,$,$,E,E,T,E,F,T,id,*,T,F,id,E,$,FIRST集合计算方法,若X,a.，则将终结符加入FIRST(X)中,若X,，则将加入FIRST(X)中,若X,Y，且Y属于非终结符，则将FIRST(Y),加入到FIRST(X)中,若XY,1,Y,2,.Y,K,且Y,1,Y,2,.Y,i-1,都是非终结符，且Y,1,Y,2,.Y,i-1,的FIRST集合中均包含,，则将FIRST(Y,j,)的所有非元素加入到FIRST(X)中，（,j,=1,2,.i）.特别地，若Y,1,Y,K,均有产生式，则将加到FIRST(X)中。,7、FIRST集合及FOLLOW集合的计算方法,S,BA,ABS|d,BaA|bS|c,FIRST(B)=a,b,c,FIRST(A)=a,b,c,d,FIRST(S)=a,b,c,FOLLOW集合计算方法,对文法开始符号S,置$于FOLLOW(S)中。,若有A,B，则将FIRST()加入FOLLOW(B)中。,（此处,可以为空,）,若A,B 或A,B,且 ,*,（即 属于FIRST()）,则将,FOLLOW(A)加入FOLLOW(B)中（此处,可以为空,）,。,7、FIRST集合及FOLLOW集合的计算方法,S,BA,ABS|d,BaA|bS|c,FIRST(B)=,a,b,c,FIRST(A)=,a,b,c,d,FIRST(S)=,a,b,c,FOLLOW(S)=?,FOLLOW(A)=?,FOLLOW(B)=?,