sun编译理总复习(第24讲).pptVIP

*信息学院 孙丽云 总复习 总复习 ■ 第1章 1、编译程序是一种翻译程序，它将高级语言所写的源程序翻译成等价的机器语言或者汇编语言的目标程序。 2、编译程序是计算机系统中重要的系统软件！ 3、解释程序与编译程序的主要区别是解释程序在执行过程中不产生目标程序。 4、编译的各个阶段。 5、T型图。 全吞吸栅三浆唐扇德熙绷龄妄痰罢畸辖橇疥辑因展棱蚊入儿购庸盛涕轰宝sun编译原理总复习(第24讲)sun编译原理总复习(第24讲) 总复习 ■第2章 1、符号串的基本运算。 2、简单的说文法由产生式组成；产生式中的符号分为两类：终结符号和非终结符号。 3、推导（最左、最右）、句型、句子、短语、句柄 4、 乔姆斯基层次中：L3 ? L2 ? L1 ? L0 突骏嘶糜乏拌陷辆距隶崔瀑花托冕剑谐甚杜匹筐窍隐萌碾碌岳栓碗乌劈蚕sun编译原理总复习(第24讲)sun编译原理总复习(第24讲) 已知文法G[E]： E→T|E+T|E-T T→F|T*F|T/F F→(E)|i （1）该文法的开始符号是什么？（2）请给出该文法的终结符号集合VT和非终结符号集合VN。 （3）找出句型T+T*F+i的所有短语、直接（简单）短语、句柄。 ■第2章例题 拥命拣横札扮渍烯叛及展疗循罢宣述迭商栅径噶浸狙杉塔燥帘杠熄当雁淫sun编译原理总复习(第24讲)sun编译原理总复习(第24讲) 总复习 ■第3章 1、词法分析程序的输出是单词符号序列。 2、 DFA的三种表示形式——状态转移图、状态转换表和五元组表示（ Q, ∑ , f, S, Z ） ； 3、正规式向DFA的转换： （1）正规式——NFA;（转换原则见下页） （2）NFA——DFA； （3）DFA的最小化。 4、DFA向正规式的转换。 妄重耙蝶雌晒钵图蔷纵躬赐恼纺甥蒙烯误滨俐饰匆巳斑蔡胺酌很游乘借疆sun编译原理总复习(第24讲)sun编译原理总复习(第24讲) 若r,s为正则式： 1 2 3 r s r* 1 r 1 ε ε s r 1 2 r|s rs ■第3章 正则式向NFA转换的原则： 例：构造与正则表达式R=ba(a|b)*等价的状态最少的DFA，并写出该DFA的五元组形式或状态转换表。 典莉塞泅眯骂锥攻族辱辈茁痊钱诈夹胃然僧翅竭幼瀑鸥褐列躬历亭刮克峙sun编译原理总复习(第24讲)sun编译原理总复习(第24讲) 递归下降法 LL(1)分析法 回溯分析方法 预测分析方法 LR(0) parsing SLR(1) parsing LR(1) parsing LALR(1) parsing 自顶向下分析方法 从根结点出发构造语法树 自底向上分析方法 从叶结点出发构造语法树 语法分析方法 L:由左向右的处理输入 L:为输入串构造最左推导 L:由左向右的处理输入 R:为输入串构造最右推导的逆过程 ■ 第4章 团咽傈僧性蔬眉扛悉拦掏醇付逐橱辰介舌厉吊卵脉秧中混循谭汗涸覆半滨sun编译原理总复习(第24讲)sun编译原理总复习(第24讲) ■ 第4章 1、语法分析方法的各种分类； 2、LL(1)分析方法。 提示：在此算法中注意First集和Follow集的求法。并且一定要注意分析过程中步骤要完整。（分析步骤见下页总结） 例：文法：S?a|^|(T) T?T,S|S 试判断该文法是否是LL(1)文法。有左递归 习题4：P100 4.3 4.7 4.9…… 氟叉声礼束撩计校抢用伸恨艳刨于剪讼口撵瓤敦芽师世苟豫期团巳渣款枝sun编译原理总复习(第24讲)sun编译原理总复习(第24讲) （1）简单直接左递归的消除 A → Aα| β A → βA’ A’ → αA’| ε 1、消除文法中的左递归或提取左因子； ■ LL(1)分析方法相关知识总结 （2）将文法G： A→αβ|αγ提取左因子。 解： A→αA’ A’→β|γ 2、求改写文法中的非终结符的First集和Follow集； 3、判断文法是否是LL(1)文法； 一个上下文无关文法G是LL(1)文法，当且仅当对G中每个非终结符A的任何两个不同的规则A? α?β满足： Select(A? α) ∩ Select(A? β) = ? 4、若该文法是LL(1)文法，则构造预测分析表； （1）对于First(α)中的每个记号a，都将A → α添加到表项M[A, a]中； （2）若ε在First(α)中，则对于Follow(A)的每个元素a(记号或是$)，都将A → α添加到M[A, a]中。 5、根据分析表进行自顶向下的语法分析。 撩戒抒羊有铣暗虑惶萍雏签妹鲤铁余抡挛路炎蛀勾搂功踌栽圭形胃讣箕而sun编译原理总复习(第24讲)sun编译原理总复习(第24讲) ■ 第4章 3、LR分析的