编译原理复习-2.ppt

q0 q1, q3 a b a,b q2, q4 , q5 , q6 q4 , q5 , q6 a a,b a b S0 S1 a b a,b S2 S3 a a,b a b * 等价状态 定义1 设DFA M 的两个状态q1和q2 , 如果对任意输入的符号串x，从q1和q2出发，总是同时到达接受状态或拒绝状态中，则称q1和q2是等价的。如果q1和q2不等价，则称q1和q2是可区分的。 定义1’ 对DFA中的两个状态q1和q2 ，如果将它们看作是初始状态，所接受的符号串相同，则定义q1和q2是等价的。 注意: DFA的终止状态和非终止状态是不等价的。 * DFA的化简（最小化） 背景知识 无关状态 从有限自动机的初始状态开始，任何输入序列都不能到达的那些状态称为无关状态。 最小的DFA(化简了的DFA) 如果DFA M 没有无关状态，也没有彼此等价的状态，则称DFA M 是最小的（或规约的）。 状态分离法 * 背景知识 状态分离法 状态分离法的目标: SS = SS1∪SS2∪……∪SSn 其中: SSi∩ SSj=Φ (i ≠ j时) 状态集I对a(a∈Σ)是不可区分的: 若I中元素对输入符a都转到相同的状态集中. 状态集I对a(a∈Σ)是可区分的: 若I中元素对输入符a转到不同的状态集中. 状态集I对a(a∈Σ)进行划分: 若I中元素对输入符a转到不同的状态集中,则分别将转到相同集合中的状态组成一个新的状态集. * 背景知识 状态分离法算法 STEP1.求初始划分: SS=非终止状态集∪终止状态集。 STEP2.若SS中的每个子集对每一个a(a∈Σ)都是不可区分的,则转STEP3;否则对可分的子集按相应的a(a∈Σ)进行划分。 转STEP2。 STEP3.每个子集中元素合并为一个状态，只含终态的集合为一个终态，对边作相应的调整。 * 背景知识 S0 S1 a b a,b S2 S3 a a,b a b STEP1.求初始划分: SS={S0, S1}∪{S2, S3} STEP2. {S0, S1}是否是可区分的？ S0 S1 S0 S3 S2 S1 {S0, S1}对a是否是可区分的？ S0 S1 S0 S1 S3 S2 {S0, S1}对b是否是可区分的？ STEP2. {S2, S3}是否是可区分的？ S2 S3 S0 S1 S2 S3 {S2, S3}对a是否是可区分的？ S2 S3 S0 S1 S2 S3 {S2, S3}对b是否是可区分的？ SS={S0}∪{S1}∪{S2, S3} SS={S0}∪{S1}∪{S2, S3} a S0 S1 b a,b a S2 , S3 最终结果： * 四、已知文法G[S]如下： S ? aSAb | a A ? Aa | b 请写出该文法的递归下降语法分析程序（程序中给出必要的注释）。 解：该文法的产生式中存在左公共前缀和左递归，因此不满足递归下降语法分析条件，因此，需要进行文法变换。 * 文法等价变换技术：消除公共前缀 公共前缀:A的不同产生式的右部具有相同的前缀。 这种情形不满足自顶向下的语法分析条件。 可用提取左因子的方法消除产生式的公共前缀。假定关于Ａ的规则是： A???1 | ??2 |…| ??n | ?1| ?2 |…| γm (其中每个?不以?开头) 则将这些规则写成： A??A’ | ?1 |γ2|…|γm A’??1 | ?2 |…|?n 经过反复提取左因子，就能够使每个非终极符的不同产生式的右部具有不同的前缀。 * 2.2.5 文法的等价变换 背景知识 S ? aSAb | a A ? Aa | b （1）去除左公共前缀: S ? aS’ [1] S’? SAb [2] | ? [3] S ? aS’ [1] S’ ? SAb [2] | ?[3] A ? Aa | b * 背景知识 文法等价变换技术:消除直接左递归 文法的递归性： 对文法中的某个非终极符A，若有产生式：A→A…，则称A是直接左递归的。 对文法中的某个非终极符A，若有产生式：A→…A，则称A是直接右递归的。 对文法中的某个非终极符A，若有产生式：A→…A…，则称A是直接递归的。 对文法中的某个非终极符A，若有：A=+A…，则称A是左递归的。 对文法中的某个非终极符A，若有：A=+… A ，则称A是右递归的。 对文法中的某个非终极符A，若有：A=+… A …，则称A是递归的。 * 左递归情形，一定使得自顶向下的语法分析分析条件不成立。 消除直接左递归的简单情形： A ? Aα | β 即