二义文法的应用

单击编辑母版标题样式,*,单击编辑母版标题样式,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,二义文法的应用,二义文法的应用,二义文法的特点：,二义文法决不是,LR,文法,简洁、自然,例 二义文法,E,E,+,E,|,E,E,|(,E,)|id,非,二义的文法：,E,E,+,T,|,T,T,T,F,|,F,F,(,E,),|id,该文法有单个非终结符为右部的产生式,二义文法的应用,二义文法的特点：,二义文法决不是LR文法,简洁、自然,可以用文法以外的信息来消除二义,语法分析的效率高基于消除二义后得到的分析表,二义文法的应用,.1,使用文法以外信息来解决分析动作冲突,例二义文法,E,E,+,E,|,E,E,|(,E,)|id,规定：,优先级高于,+，,两者都是左结合,二义文法的应用,.1 使用文法以外信息来解决分析动作冲突,例二义文法E E+E|E E|(E)|id,规定：优先级高于+，两者都是左结合,LR(0)工程集I7,E E+E,E E+E,E E E,二义文法的应用,.1 使用文法以外信息来解决分析动作冲突,例二义文法E E+E|E E|(E)|id,规定：优先级高于+，两者都是左结合,LR(0)工程集I7,E E+E,E E+Eid+id+id,E E E,面临+，归约,二义文法的应用,.1 使用文法以外信息来解决分析动作冲突,例二义文法E E+E|E E|(E)|id,规定：优先级高于+，两者都是左结合,LR(0)工程集I7,E E+E,E E+Eid+id+id,E E E id+id id,面临+，归约面临，移进,二义文法的应用,.1 使用文法以外信息来解决分析动作冲突,例二义文法E E+E|E E|(E)|id,规定：优先级高于+，两者都是左结合,LR(0)工程集I7,E E+E,E E+Eid+id+id,E E E id+id id,面临+，归约面临，移进,面临)和$，归约,二义文法的应用,.1 使用文法以外信息来解决分析动作冲突,例二义文法E E+E|E E|(E)|id,规定：优先级高于+，两者都是左结合,LR(0)工程集I8,E E E,E E+E,E E E,二义文法的应用,.1 使用文法以外信息来解决分析动作冲突,例二义文法E E+E|E E|(E)|id,规定：优先级高于+，两者都是左结合,LR(0)工程集I8,E E E,E E+Eid id+id,E E E,面临+，归约,二义文法的应用,.1 使用文法以外信息来解决分析动作冲突,例二义文法E E+E|E E|(E)|id,规定：优先级高于+，两者都是左结合,LR(0)工程集I8,E E E,E E+Eid id+id,E E E id id id,面临+，归约面临，归约,二义文法的应用,.1 使用文法以外信息来解决分析动作冲突,例二义文法E E+E|E E|(E)|id,规定：优先级高于+，两者都是左结合,LR(0)工程集I8,E E E,E E+Eid id+id,E E E id id id,面临+，归约面临，归约,面临)和$，归约,二义文法的应用,.2,特殊情况产生式引起的二义性,E,E,sub,E,sup,E,E,E,sub,E,E,E,sup,E,E,E,E,c,二义文法的应用,.2,特殊情况产生式引起的二义性,E,E,sub,E,sup,E,E,E,sub,E,E,E,sup,E,E,E,E,c,从定义形式语言的角度说，第一个产生式是多余的,二义文法的应用,.2 特殊情况产生式引起的二义性,E E sub E sup E,E E sub E,E E sup E,E E,E c,联络到语义处理，第一个产生式是必要的,二义文法的应用,.2,特殊情况产生式引起的二义性,E,E,sub,E,sup,E,E,E,sub,E,E,E,sup,E,E,E,E,c,对,a,sub,i,sup 2,，需要下面第一种输出,二义文法的应用,.2,特殊情况产生式引起的二义性,E,E,sub,E,sup,EI,11,:,E,E,sub,E E,E,sub,E,sup,E,E,E,sup,E E,E,sup,E,E,E,.,E,c,按前面一个产生式归约,二义文法的应用,.3 LR分析的错误恢复,1、LR分析器在什么情况下发现错误,访问动作表时假设遇到出错条目,访问转移表时它决不会遇到出错条目,决不会把不正确的后继移进栈,标准的LR分析器甚至在报告错误之前决不做任何无效归约,二义文法的应用,2,、紧急方式错误恢复,s,.,.,.,.,.,.,栈,.,.,a.,A,发现错误,s:,C,A,A,b,.,s,1,:,C,A,.,A,A,b,.,b,二义文法的应用,2,、紧急方式错误恢复,(1),退栈，直至出现状态,s,它有预先确定的,A,的转移,s,.,.,.,栈,.,.,a.,A,发现错误,s:,C,A,A,b,.,s,1,:,C,A,.,A,A,b,.,b,二义文法的应用,2、紧急方式错误恢复,(1)退栈，直至出现状态s,它有预先确定的A的转移,(2)抛弃假设干输入符号，直至找到a,它是A的合法后继,s,.,.,.,栈,.,.,a.,A,s:,C,A,A,b,.,s,1,:,C,A,.,A,A,b,.,b,二义文法的应用,2、紧急方式错误恢复,(1)退栈，直至出现状态s,它有预先确定的A的转移,(2)抛弃假设干输入符号，直至找到a,它是A的合法后继,(3)再把A和状态gotos,A压进栈，恢复正常分析,s,s,1,.,.,.,栈,.,.,a.,A,s:,C,A,A,b,.,s,1,:,C,A,.,A,A,b,.,b,本 章 要 点,文法和语言的根本知识,自上而下的分析方法：预测分析，非递归的预测分析，LL(1)文法,自下而上的分析方法：SLR(1)方法，标准LR(1)方法和LALR(1)方法,LR方法如何用于二义文法,语法分析的错误恢复方法,例 题 1,下面的二义文法描绘命题演算公式的语法，,为它写一个等价的非二义文法,S S and S|S or S|not S|p|q|(S),非二义文法的产生式如下：,E E or T|T,T T and F|F,F not F|(E)|p|q,例 题 1,下面的二义文法描绘命题演算公式的语法，,为它写一个等价的非二义文法,S S and S|S or S|not S|p|q|(S),非二义文法的产生式如下：,E E or T|T,T T and F|F,F not E|(E)|p|q?,not p and q有两种不同的最左推导,例 题 1,下面的二义文法描绘命题演算公式的语法，,为它写一个等价的非二义文法,S S and S|S or S|not S|p|q|(S),非二义文法的产生式如下：,E E or T|T not p and q,T T and F|F not p and q,F not E|(E)|p|q?,not p and q有两种不同的最左推导,例 题,2,设计一个文法:字母表,a,b,上,a,和,b,的个数相,等的所有串,的集合,二义文法：,S,a S b S,|,b S a S,|,a,ab,b,abab,a,abba,b,ab,S S S S,例 题,2,设计一个文法:字母表,a,b,上,a,和,b,的个数相,等的所有串,的集合,二义文法：,S,a S b S,|,b S a S,|,a,ab,b,abab,a,abba,b,ab,二义文法：,S,a B,|,b A,|,A,a S,|,b A A,B,b S,|,a B B,a,a,b,babab,a,a,bba,bab,a,a,bbaba,b,B,B,B,B,B,B,例 题,2,设计一个文法:字母表,a,b,上,a,和,b,的个数相,等的所有串,的集合,二义文法：,S,a S b S,|,b S a S,|,a,ab,b,abab,a,abba,b,ab,二义文法：,S,a B,|,b A,|,A,a S,|,b A A,B,b S,|,a B B,a,a,b,babab,a,a,bba,bab,a,a,bbaba,b,非二义文法：,S,a B S,|,b A S,|,A,a,|,b A A,a,a,b,b,abab,B,b,|,a B B,aB,S,例 题,3,试说明下面文法不是,LR(1),的：,L,M L b,|,a,M,M,b,L,L,L,L,a,M,b,M,b,句子,abbb,的分析树,例 题,4,下面的文法不是,LR(1),的，对它略做修改，使之成为,一个等价的,SLR(1),文法,program,begin,declist,;,statement,end,declist,d;,declist,|d,statement,s;,statement,|s,该文法产生的句子的形式是,begin d,;d;,;d,;,s;s,;,;s,end,修改后的文法如下：,program,begin,declist,statement,end,declist,d;,declist,|d;,statement,s;,statement,|s,例 题,5,一个C语言的文件如下，第四行的if误写成fi：,long gcd(p,q),long p,q;,fi(p%q=0),return q;,else,return gcd(q,p%q);,基于LALR1方法的一个编译器的报错情况如下：,parse error before return(line 5).,是否违背了LR分析的活前缀性质？,