第7讲-语法分析-II.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,*,*,/34,编译原理和技术,本讲纲要,回顾,语法分析方法,自上而下分析,词法分析部分编程题补充规定,Program Assignment 1,要求计算与单词相关的词法属性：单词在整个文本中出现的次数，甚至出现的位置（在文本中的第几行，第几个字符）,Program Assignment 2,DFA,，用表格定义状态（有一般性）,比如，将状态转移关系描述为,State:3,State transfer:,0,a-1,0,b-0,从文件中读入状态迁移文件，建立状态迁移表格,第一次上机作业,为简单的语言T,编写词法分析程序,使用工具,lex,相关文件常见,ftp,我的目录下的,proj1.rar,要求：独立尽早完成；最终提交源码与相关文档到,huyan.ssdut,上机时间核对,周,3,晚上,软,0601-05,，软件室,1+IBM,周,4,晚上,编译原理 软,0606-10,，教学楼五楼,文法、推导与分析树,表达式文法,E,E,+,E,|,E,*,E,|(,E,)|,E,|id,语法分析的目标是：给出一个句子，比如,id+id,*id,，怎么判断该句子是满足文法说描述的语法规则？,判断是不是存在一个推导，使得,E,推导出给定的句子,文法、推导与分析树,推导过程,E=E+E=,id+E,=id+E,*E=,id+id,*E=,id+id,*id,E,E-E+E,E,E,+,E,E,*,id,id,id,E-id,E-E*E,E-id,E-id,二义性,表达式文法,消除二义之后的表达式文法,消除二义的途径,层次化的观点看待表达式,expr,expr,+,term,|,term,term,term,*,factor,|,factor,factor,id|(,expr,),E,E,+,E,|,E,*,E,|(,E,)|,E,|id,本讲纲要,回顾,语法分析方法,自上而下分析,语法分析？,给定一个句子,id+id,*id,语法分析的目标,分析句子的语法结构，明该句子符合表达式文法,怎么做？,E,id+id,*id,？,就是为该句子建立以文法的,开始符号,E,为根的语法树,分析的途径,自上而下,自下而上,E,id+id,*id,？,本讲纲要,回顾,语法分析方法,自上而下分析,自上而下分析方法,从根部开始构建语法树,存在的问题,文法存在左递归怎么办？,自上而下分析中的问题,E=E+E=E+E+E=E+E+E+E=,E,E,E,+,E,E,+,E,E,+,无限递归下去，,没有尽头,自上而下分析方法,从根部开始构建语法树,存在的问题,文法存在左递归怎么办？,文法中一步推导可能存在多个产生式选择时，怎么办？,例：,文法,S,aCb,C,cd,|c,为输入串,w,=,acb,建立分析树,S,a,b,C,S,a,b,C,c,d,S,a,b,C,c,复杂的回溯技术,、,回溯导致语义工作推倒重来,、,难以报告出错的确切位置,、,效率低,一步推导有多个,产生式可供选择,如果要用自上而下的方法进行分析，那么就必须避免例子中出现的问题,每一步推导，不能因为左递归的存在而使得推导过程陷入死循环,每一步推导，可以选择的产生式必须是唯一的,消除左递归,文法中存在左递归时，为了采用自上而下的分析方法，必须采取方法消除左递归,3.2,语言和文法,3.2.6,消除左递归,文法,左递归,A,+,A,a,直接左递归,A,A,a,|,b,串的特点,ba,.a,消除直接左递归,A,b,A,A,a,A,|3.2,语言和文法,例,算术表达文法,E,E,+,T,|,T,（,T,+,T,.+,T,）,T,T,*,F,|,F,（,F,*,F,.,*,F,）,F,(,E,)|id,3.2,语言和文法,例,算术表达文法,E,E,+,T,|,T,（,T,+,T,.+,T,）,T,T,*,F,|,F,（,F,*,F,.,*,F,）,F,(,E,)|id,消除左递归后文法,E,TE,E,+,TE,|,T,FT,T,*,F T,|,F,(,E,)|id,3.2,语言和文法,非直接左递归,S,Aa,|,b,A,Sd,|,先变换成直接左递归,S,Aa,|b,A,Aad,|,bd,|,再消除左递归,S,Aa,|b,Abd,A,|A,A,adA,|,提取左因子,当存在某一步推导可能有多种选择的产生式的时候，可以通过提取左因子的方法修改文法,比如，对于,文法,S,aCb,C,cd,|c,可以将文法改写为,S-,aCb,C-,cC,C-d|,3.2,语言和文法,3.2.7,提左因子,有左因子的文法,A,1,|,2,提左因子,A,A,A,1,|,2,3.2,语言和文法,例,悬空,else,的文法,stmt,if,expr,then,stmt,else,stmt,|if,expr,then,stmt,|other,3.2,语言和文法,例,悬空,else,的文法,stmt,if,expr,then,stmt,else,stmt,|if,expr,then,stmt,|other,提左因子,stmt,if,expr,then,stmt,optional,_,else_part,|other,optional,_,else_part,else,stmt,|,通过左递归与提取左因子，解决了文法中一些形式上的问题，但是，一个文法是不是可以应用自上而下的方法进行分析，还需要进一步的讨论,例,1,文法,S-ACD A-,a|B,B-b C-c D-d,句子,bcd,S=ACD=BCD=,bCD,=,bcD,=,bcd,句子,acd,S=ACD=,aCD,=,acD,=,acd,每一步都可以确定用哪一个产生式来进行下一步推导,用,A-B,用,A-a,这时候先引入一个定义,FIRST(,),，表示一个字串对应的终结符串可能的开始字符,可能的情况,S,A,B,C,D,BCD,bCD,根据,FIRST,集合的定义，计算一下上述,各种情况的,FIRST,集合,S-ACD,A-,a|B,B-b,C-c,D-d,引入一种特殊情况,文法,S-ACD A-a|,C-c D-d,FIRST(S)=a,对于句子,cd,，怎么推导？,S=ACD=?,FIRST(A),中的非字符中没有,c,，,那么这时候就要看一看跟在,A,后面,的非终结符,C,的情况，主要看,FIRST(C),中是否有字符,c,再看一下进一步调整后的例子,文法S-ACD A-a|,C-,D-d,FIRST(S)=a,对于句子,d,，怎么推导？,S=ACD=?,这个例子中，,D,既不在,FIRST(A),中，也不在,FIRST(C),中，,最终可以发现是在,FIRST(D),中,FIRST,集和,FOLLOW,集,FIRST(,)=,a,|,*,a,a,V,T,计算满足,的句子的所有可能开头字符,特殊情况：当,*,时，规定,FIRST(,),FOLLOW(,A,)=,a,|,S,*,Aa,，,a,V,T,计算语言的句型中所有可能跟在,A,后面的字符,特殊情况：如果,A,是某个句型的最右符号，那么,$,属于,FOLLOW(,A,),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,3.3,自上而下分析,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)=?,3.3,自上而下分析,