编译原理期末中复习剖析.ppt

《编译原理》期末总复习 考试题型及分数分布 填空题 单选题 判断题 解析题 第二章???? 文法与形式语言简介 用语法树求句型的短语、简单短语、素短语、句柄； 举例：用语法树求F*F * (T+T*i)的短语 寻找子树求短语 (1)F是句型F*F * (T+T*i)相对于非终结符号T的短语，是简单短语，是句柄； 寻找子树求短语 (2)F*F是句型F*F * (T+T*i)相对于非终结符号T的短语。 寻找子树求短语 (3)T是句型F*F * (T+T*i)相对于非终结符号E的短语，是简单短语。 寻找子树求短语 (4)i是句型F*F * (T+T*i)相对于非终结符号F的短语，是简单短语。 寻找子树求短语 (5)T*i是句型F*F * (T+T*i)相对于非终结符号F的短语. 寻找子树求短语 (6)T+T*i是句型F*F * (T+T*i)相对于非终结符号T的短语. 寻找子树求短语 (7)(T+T*i)是句型F*F * (T+T*i)相对于非终结符号F的短语. 寻找子树求短语 (8) F*F * (T+T*i)是句型F*F * (T+T*i)相对于非终结符号E和T的短语. 第三章 词法分析 1、NFA到DFA转换的子集法及最小化 2、正规式和有限自动机的等价性 子集法的基本思想 NFA 2、子集法 设已给具有ε动作的NFA M=（K,∑,f,S0,Z) 递归描述步骤（1） （1）给出M′的初态 ： 递归描述步骤（2） （2）对于K′中尚未标记的状态 qi ={Si1 ,Si2 ,…,Sim}, Sik ?K做 ： 递归描述步骤（3） （3）重复（2）直到M′中不再有未标记的状态为止。 子集法举例 DFA M=({0,1,2,3,4,5,6,7,8,9,10},{a,b},f,0,{10}) 求与之等价的DFA 子集法求解过程（1） 1、ε-closure(0)={0 子集法求解过程（2） 2、对K′中未标记状态q0做： 子集法求解过程（2） move(q0,b)= 子集法求解过程（3） 3、对K′中未标记状态q1做： 子集法求解过程（4） 4、对K′中未标记状态q2做： 子集法求解过程（5） 5、对K′中未标记状态q3做：(1)标记q3 子集法求解过程（6） 6、对K′中未标记状态q4做：(1)标记q4 等价的DFA M ′如下 K′＝｛ q0 , q1 , q2 ,q3 , q4 ｝ NFA M转换为DFA M ′的过程 DFA M ′的状态图 例：将下列DFA M最小化（化简） 化简步骤1 1、初始划分由两个子集组成，即： 化简步骤2 2、考查子集｛q0,q1,q2,q3｝ 化简步骤2－－（1） （1）｛q0,q1,q2,q3｝a= 化简步骤2－－（2） （2）考查子集｛q0,q1,q2｝ 化简步骤2－－（3） （3）考查子集｛q0,q2｝ 化简步骤3 3、选择q0作为｛q0,q2｝的代表 从正规式R构造NFA M的步骤1 1、把正规式R表示为： 从∑上的正规式R构造NFA M的步骤2 2、把R分裂并加进新的结点 结点分裂规则① 结点分裂规则② 结点分裂规则③ 例:构造与正规式等价的NFA M 正规式R＝（a*b)*ba(a|b)* 步骤1 步骤2 步骤3 步骤4 步骤5 第四章 自顶向下的语法分析 LL(1)分析方法 LL(1)文法举例 A::=A∨B|B B::=B∧C|C C::=?D|D D::=(A)|i (1)试问该文法是否为LL(1)文法?为什么? (2)写出与该文法等价的LL(1)文法G1; (3)构造G1的LL(1)分析表. FIRST集 FOLLOW集 FOLLOW(B)={∧, ), ∨,#} 判断是否为LL(1)文法 该文法不是LL(1)文法。 消除左递归(1) 消除左递归(2) ∧C B′|ε 改写后的文法 A::=B A′ A′::=∨B A′|ε B::=C B′ B′::=∧C B′|ε C::=?D|D D::=(A)|i 考察是否避免回溯(1) 考察是否避免回溯(2) 考察是否避免回溯(3) 改写后的文法是LL(1)文法 构造LL(1)分析表M =FIRST(A) FIRST(B′)={∧, ε} FIRST(A′)={∨, ε} LL(1)分析表M 表达式文法G[S′ ]： (1)S′ ::=#S# (2)S::=D(R) (3) R::=R;P (4)R::=P (5)P::=S (6) P::=i (7)D::=i ①计算文法G中每一个非终结符的FIRSTVT、LASTVT集； ②构造文法G的算符优先关系矩阵。 FIRSTVT集 (1)S′ ::=#S# 所以：FIRSTVT(S′ )={#} (2