编译原理复习.ppt

正规式R转化为NFAM 在这个方法中按正规式的语法结构指引构造过程 将正规式分解为一系列子表达式 然后将子表达式对应的NFA依次连接而成 构造规则如下 1 a 对正规式 对应的NFA为 b 对正规式 对应的NFA为 c 对正规式a 对应的NFA为 2 正规式R 首先表示成拓广状态转换图 首先介绍两个重要运算 1 状态集的 闭包 状态集I中的任何状态s经任意条 弧而能到达的所有状态的集合 定义为状态集I的 闭包 表示为 closure I 2 状态集的a弧转换 状态集I中的任何状态s经过一条a弧而能到达的所有状态的集合 定义为状态集I的a弧转换 表示为move I a 对于任意NFAM K f S F I K a 不妨设I s1 s2 sj 则move I a f s1 a f s2 a f sj a 算法 有了以上所述两个运算 我们就可以构造NFAN的状态集K的子集从而与DFAM的状态对应 即构造若干个状态集T1 T2 Ti 且Ti K 这样就可以构成由若干个状态集组成的子集族C C T1 T2 Ti 具体如下 1 首先 令T closure K0 作为C中的唯一成员 开始以前C中为空 并且它是未标记的 其中K0为NFAN的初态集 2 While C中存在尚未标记的子集T dobegin标记T for每个输入字母adobeginU closure move T a 显然U是一个状态集if U不在C中 then将U作为未标记的子集加入C中 end end 确定的有限自动机的最简化 最小化 对任意一个DFAM构造另一个DFAM 使L M L M 并且M 的状态个数不多于M的状态个数 首先我们介绍几个有关的概念 1 多余状态 对于一个状态Si 若从开始状态出发 不可能到达该状态Si 则Si为多余 无用 状态 S1 S5 S6为多余状态 3 等价状态 若Si为自动机的一个状态 我们把从Si出发能导出的所有符号串集合记为L Si 多余状态和死状态又称为无关状态 设有两个状态Si和Sj 若有L Si L Sj 则称Si和Sj是等价状态 从S1和S2能导出相同的符号串集合 L S1 L S2 b 所以S1和S2等价 4 可区别状态 自动机中两个状态Si和Sj 如果它们不等价 则称它们是可区别的 5 两个状态 Si和Sj 等价的判断条件 分类算法 状态Si和Sj必须同时为终止状态或同时为非终止状态 即终止状态和非终止状态是可区别的 粗分 如 S0 S1 S2肯定与S3不等价 状态Si和Sj对于任意输入符号a 必须转到等价的状态里 否则Si和Sj是可区别的 a为区分依据 可以推广 因f S0 b S2 f S2 b S3 而S2和S3不等价 故S0和S2也不等价 DFA的化简算法 对于DFAM S f S0 Z 1 首先将DFA的状态集进行初始化 分成P Z S Z 3 重复执行 2 直到P中每个状态集不能再划分 Pnew P 为止 4 合并等价状态 在每个G中 取任意状态作为代表 删去其它状态 5 删去无关状态 从其它状态到无关状态的转换都成为无定义 一 首符号集 设有文法G VT VN S P 是上下文无关文法 则符号串x的首符号集合定义为 二 后继符号集 设有文法G VT VN S P 是上下文无关文法 U VN 则非终结符号U的后继符号集定义为 1 两个重要集合 2 求法 以FIRSTVT U 为例说明 在此过程中 要充分利用两条规则 若有产生式U b 或U Vb U V VN 则b FIRSTVT U 若有产生式U V 且b FIRSTVT V 则b FIRSTVT U 2 构造方法 为了算法的实现 建立一个布尔数组F U a 用于存放FIRSTVT U 若终结符a FIRSTVT U 则F U a TRUE 否则F U a FALSE 另外还要建立一个工作栈STACK 初值为空 数组元素初始化为FALSE 用0表示 例2 设有文法G E E E T TT T F FF E i F 从文法中找出形如U b 或U Vb的产生式 并使对应的数组元素F U b TRUE 用1表示 E E T 1 T T F 1 F E 1 F i 1 将F U b 的值为真的符号对压入工作栈 顺序任意 F E T F i 若工作栈不空 将栈顶项弹出 此项记为 若文法中有形如 U V 的产生式 则b FIRSTVT U 此时 若数组中F U b FALSE 则令F U b TRUE 且将压入STACK 此过程重复进行 直到栈空 1 T i 1 E i 1 E 1 T 1 E FIRSTVT E i FIRSTVT T i FIRSTVT F i 用类似的算法可以求出LASTVT U 2 优先关系的确定 P92 1 定义项目 对于文法G 其产生式的右部添加一个特殊符号 就构成文法的一个LR 0 项目 简称项目 2 求项目集规范族 每个项目集对应一个DFA状态 它们的全体称这个文法的项目集规范族 下面给出求各个项目集的方法 以便得到识别文法活前缀的DFA 1 求项目集 设Si是状态Sk输入符号x后到达的状态 Si是Sk关于符号x的后继状态 则有 Si状态中的基本部分为 BASIC Si A x A x Sk 用闭包函数构造项目集CLOSURE Si a BASIC Si CLOSURE Si b 若A B CLOSURE Si B VN B CLOSURE Si 重复 直到CLOSURE Si 不再增加项目为止 2 转换函数 从一个状态出发 到达下一个状态的转换函数定义为 GO I X CLOSURE J I为某个项目集对应的状态 X为输入符号X V J 任何形如A x 的项目 A x I 3 DFA的形成过程 举例说明 对拓广文法G S S EE aA bBA cA dB cB d 有项目 S E肯定包含再S0中 S E 求CLOSURE S0 E aAE bB S1 S E E a A A cAA d E b B B cBB d A c A A cAA d S6 E aA S10 A d B c B B cBB d S7 E bB S11 B d S8 A cA S9 B cB 与P106所示结果一致 我们把First 作为用产生式A 进行归约的搜索符 用于替代SLR 1 分析法中的Follow A 并把搜索符号的集合放在项目的后面 A a a First 这种处理方法称为LR 1 方法 2 LR 1 项目 1 LR 1 项目的构成 在LR 0 项目中放置一个向前搜索的符号a 成为 A a 2 LR 1 项目集的构造 LR 1 分析过程中的每个状态 就是包含若干LR 1 项目的一个LR 1 项目集 特殊的 S S 属于初始项目集中的一个LR 1 项目 即 S S S0 它表示 若文法G S 中有S S产生式 而且要将S归约为S 时 必须面临输入符号 才行 所以文法的所有项目集的获得 就是从初始项目 S S 出发 通过求其闭包再用转换函数逐步求出整个文法的LR 1 项目集 所涉及的算法如下 一般的说 若有x A Si而A Si 1 闭包函数 i Si中任何LR 1 项目都是属于Si的闭包CLOSURE Si ii 设项目 A B a CLOSURE Si B VN V 且B 是文法的产生式 b First a 则 B b CLOSURE Si iii 重复ii 直到CLOSURE Si 不再增大 此外注意 每一个LR 1 项目与其后继项目有相同的向前搜索符 如 若有LR 1 项目为 A x a 则其后继为 A x a 2 转换函数 GO Si x CLOSURE Sj 在LR 1 项目集的构造过程中 仍以 S S 为初态集的基本部分 初始项目 然后对其求闭包 使其增大 再求转换函数得其它项目集的基本部分Sj 再求Sj的闭包 直到项目集不在增大 若 则b First 则b First a a Si是LR 1 的项目集 x是文法符号 表示输入符号 Sj 任何形如 A x a 的项目 A x a Si 3举例 我们仍以G S 为例 看项目集的求法 从而得到DFA S0 S S S aAd S bAc S aec S bed S1 S S S2 S a Ad S a ec A e d S4 S aA d S5 S ae c A e d S8 S aAd S9 S aec S3 S b Ac S b ed A e c S6 S bA c S10 S bAc S7 S be d A e c S11 S bed First First d d First c c 0 S S 1 S aAd 2 S bAc 3 S aec 4 S bed 5 A e 三 LR 1 分析表构造规则 对于文法G S 其LR 1 分析表的构造规则为 1 对于 A x a Si GO Si x Sj 若x VT 则置Action Si x Sj若x VN 则置Goto Si x j