单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,复习要点,第,1,章 引论,编译程序、解释程序,编译程序的,5,个阶段,遍,编译前端与后端,复习要点,高级语言极其语法描述（,P2.3,节）,上下文无关文法、最左推导、最右推导、句子、句型、语言、语法分析树、二义性文、形式语言分类,复习要点,词法分析,正规式、正规集、有限自动机（确定的有限自动机、非确定的有限自动机）,三者之间的相互转化,自动机的确定化、化简,复习要点,语法分析,-,自上而下分析,递归下降分析法,LL,（,1,）分析法,消除左递归、提左因子、,FIRST,集、,FOLLOW,集,P73:LL(1),文法的判定条件,LL(1),分析器的构造：,P76-79,复习要点,语法分析,-,自下而上分析,移进,-,归约、规范规约、短语、直接短语、句柄,算符优先分析,算符文法、素短语、最左素短语,LR,分析法,LR(0),、,SLR,LR,分析法考核要点,构造文法,GS,的,LR(0),项目集规范族及相应的,DFA,。
构造文法的,LR(0),或,SLR,分析表,对于输入串,xxxxxxx,，给出,LR(0),或,SLR,分析器所作出的动作复习要点,属性文法和语法制导翻译,属性文法、继承属性、综合属性、,S-,属性文法、,L-,属性文法、翻译模式,S-,属性文法的自下而上计算,复习要点,语义分析和中间代码产生,中间语言形式：后缀式、三地址代码（主要是四元式）,控制语句的翻译,字母表,0,1,2,3,对给定正则表达式,0*,（,1|23,）（,0|12,）,0,（,1|13,）,*,构造与之等价的,NFA M,习题举例,设文法,G(S):SS+aF|aF|+aFF*aF|*a,消除左递归和回溯；,构造非终结符的,FIRST,和,FOLLOW,集合；,构造预测分析表,(4),给出句子,a*a+a*a,的,LL(1),分析过程,（格式：栈，输入缓冲区，动作）,习题举例,解：,SaFS|+aFSS+aFS|F*aFFF|,FIRST(S)=a,+FOLLOW(S)=#FIRST(S)=+,FOLLOW(S)=#FIRST(F)=*FOLLOW(F)=+,#FIRST(F)=*,)FOLLOW(F)=+,#,习题举例,-,a,+,*,#,S,SaFS,S+aFS,-,-,S,-,S+aFS,-,S,F,-,-,F*aF,-,F,-,F,FF,F,习题举例,文法,GS,的产生式为：,S,S+A|A,A,A*S|B,B,a|,（,S,）,给出（,a+a,）,*,a,的最左推导、最右推导及相应的分析树；,列出句型,B+A*B,的所有短语、直接短语和句柄。
习题举例,已知文法,G=(b,e,f,S,S,R,T,S,P),其中,P:,(0)SS (1)SbRST (2)SbR,(3)Re (4)Tf,构造 文法的,LR,（,0,）项目集规范族,构造 识别活前缀的,DFA,这个文法哪类,LR,文法并说明理由,习题举例,S,S,S,bRST,S,bR,I,0,S S,I,1,S,Sb,RST,R,e,Sb,R,I,2,b,Re,I,4,e,SbR,ST,SbR,S,bRST,S,bR,I,3,R,b,S,SbRS,T,T,f,I,5,Tf,I,7,f,SbRST,I,6,T,状态,action,goto,b,e,f,#,S,R,T,0,S,2,1,1,acc,2,S,4,3,3,S,2,r,2,r,2,5,4,r,3,r,3,r,3,5,S,7,6,6,r,1,r,1,7,r,4,r,4,状态栈,符号栈,输入缓冲区,动作,0,#,bebef#,S,2,02,#b,ebef#,S,4,024,#be,bef#,r,3,023,#bR,bef#,S,2,0232,#bRb,ef#,S,4,02324,#bRbe,f#,r,3,02323,#bRbR,f#,r,2,0235,#bRS,f#,S,7,02357,#bRSf,#,r,4,02356,#bRST,#,r,1,01,#S,#,acc,。
