形式语言与编译 九 CFG到CNF再到GNF 左递归消除
2021-05-03 10:27
标签：长度 集合 iba 要求 单位 哪些 多个 递归 替换算法 先找出\(N_A簇，N_B簇，N_C簇\)，先对\(N_A簇\)：是单产生式的 将来会因为替换而消除；不是单产生式的 直接放进新的集合 同理对\(N_B簇,N_C簇\)也是一样(这样一般得到三个"堆") 确实没了单产生式。 建议做的过程： 按这个顺序做 这样化简后的CFG G1 与原来的CFG G相比，有\(L(G_1)=L(G)-\{\epsilon\}\) 本来我们的CFG文法它的形式是 \(A->\alpha,其中\alpha\in(V_N \cup V_T)^*\) 也就是这个串有终结符和非终结符组成的串即可，要求并不严 现在我们进行乔姆斯基范式的正规化。目的就是让我们上面的定义受到一些约束，形成这种\(A->BC,A->a ,a\in V_T\) 类型（\(A->变元变元，A->终结符\)）的。 (这里与我们的正则文法，可以类比，正则文法的形式是：\(A->\alpha , A->\alpha B,\alpha\in (V_T)^*\)，也就是终结符组成的字符串 或者 终结符组成的字符串+变量) 注意：若语言\(\epsilon \in L(G)\) 就会有\(S->\epsilon\)这样一条产生式加入产生式集合 这里很好理解,但是要求\(S\)只能当做开始符号，不能在到别的产生式的产生式体中，要是迫不得已，则就是我们引进$S_1->S与S_1->\epsilon $ 对每一个CFG 都有乔姆斯基范式CNF,也就是都可以化成\(A->BC,A->a ,a\in V_T\) 这种形式 说明： 扫描原来产生式，如果是终结符，就把这个终结符拎出来，形成产生式 【新变量->终结符】 的形式，再把原来产生式中的终结符替换成新变量 如果是非终结符(变量)，把这个长的变量组成的串 想办法缩短成多个小短串(小短串的产生式体只包含不超过2个变量) 为什么要提出Greibach范式？？？ 因为自上而下的推导中会产生回溯，回溯导致分析效率降低 产生回溯的原因： 如何避免回溯？？ 消除左递归！ Greibach范式的定义 ： 把所有产生式定义成：\(A->a\beta,A\in V_N ,a\in V_T,\beta\in (V_N)^*\) 且G不含\(\epsilon\) 产生式 模式：变量——>常量+纯变量串 和CNF范式一样的是：每一个CFG也都有对应的GNF 这里的多步推导 隐含意思（直接+间接）就是文法中几乎可以说 不能含有\(A=>^*A\beta,A=>^*\alpha A \beta, …\) 这种文法。一旦含有则直接被判定为递归文法 步骤： (截止这里，还没有正真的进行消除左递归，只是将所有可能隐含的左递归，通过替换算法给"发掘"出来) 先把不是左递归的部分copy过来；再给这些刚搞过来的产生式后面引入我们的新变量\(A‘\) ；再以新的\(A‘\)引出产生式，这些产生式的产生式体部分要么是原来递归产生式体的非递归部分 ，要么是原来递归产生式体的非递归部分 +\(A‘\) 进行右递归！ 先把刹车部分和新引入的写出来；再由新引入的写出 原来递归中的重复部分，以及递归重复部分连接新引入的 消除左递归的宏观思路： 消除左递归之前，上图中的\(\beta\)是一直到最后，才因替换而出现；消除左递归之后，上图中的\(\beta\) 一开始很早就出现。 替换的过程就是类似于解方程组代入法。通常第一条作为核心方程式，第二条用第一条表示；第三条用第二条和第一条表示。 上面最后一部分 是不完整的，因为只用了\(A_1\)代入，没把\(A_2\)代入 我们代入的目的是形成直接左递归(暴露出原来隐含的左递归，而且是把已经知道的产生式代入(换句话说，序号小的产生式代入序号大的产生式)，比如 上面的 我们先看到\(A_1\) ，单个\(A_1\)形不成左递归； 再看\(A_2\) ,我们的目的就是把\(A_1\) 代入到\(A_2\) 并且还要形成直接左递归的才带入，于是有\(A_2->A_3A_1|A_2A_3b|ab\) 注意到此时有了直接左递归；我们用消除左递归的方式产生右递归：有 \(A_2->A_3A_1|ab|A_3A_1A_2‘|abA_2‘,,, ,,A_2‘->A_3b|A_3bA_2‘\) \(A_3\)发现 我们可能要代入两次(由上面已知的\(A_1,A_2,A_2‘\)) 先将\(A_1\)代入\(A_3\) \(A_3->A_2A_3A_2|aA_2|A_3A_3|a\) 再把\(A_2\)代入\(A_3\) 得到直接左递归形式：\(A_3->A_3A_1A_3A_2|A_3A_1A_2‘A_3A_2|abA_3A_2|abA_2‘A_3A_2|aA_2|A_3A_3|a\) 然后把这个暴露出直接左递归形式的产生式进行消除左递归。得到 \(A_3->abA_3A_2|abA_2‘A_3A_2|aA_2|A_3A_3|abA_3A_2A_3‘|abA_2‘A_3A_2A_3‘|aA_2A_3‘|A_3A_3A_3‘,A_3‘->A_1A_3A_2|A_1A_2‘A_3A_2|A_1A_3A_2A_3‘|A_1A_2‘A_3A_2A_3‘\) 正确的应该是： \(A_3->A_2A_3A_2|aA_2|A_3A_3|a=\) 再把 递归部分产生式 可以替换的(本例是\(A_2\)) 用产生式再次替换,得： \(A_3->A_3A_1A_3A_2|abA_3A_2|A_3A_1A_2‘A_3A_2|abA_2‘A_3A_2|aA_2|A_3A_3|a\) 经过这样，就把所有的隐含左递归产生式 就给显现出来了！ 然后按照正常的 把直接左递归变右递归就行了。 消除\(\epsilon\) 产生式 消除单产生式 消除无用符号 也就是说我们化简完了的CFG G，如果原来的产生式有\(\epsilon\) ,那么那化简完由于没有 \(\epsilon\) 产生式 ，所以得∪上\(\epsilon\) 句子（引入新的开始符号\(S‘\)）；如果原来语言中就不含$\epsilon $ ,那按步骤化简完即可。 判断 变量 是否是可致空的，所谓 消除\(\epsilon\) 产生式 ，就是把 \(\epsilon\) 产生式代入这些变量，每一个变量都有两种可能：是\(\epsilon\) ,不是\(\epsilon\) 。比如$A->aBc，B->\epsilon $ ,我们判断B是可以为\(\epsilon\) 的,那么这两条产生式就可以变为\(A->ac|aBc\) 。 \(A->aBC,B->\epsilon,C->\epsilon\) 就可以变为\(A->aBC|aB|aC|a\) 这就是***消除\(\epsilon\) 产生式 *** [消\(\epsilon\) 产生式] 先识别哪些不是单位产生式，找到它！所谓消除单位产生式就是\(A->B,B->\alpha串\) ,直接替代 入B，B实际上没用，得到\(A->\alpha串\) \(B->A,A->\alpha_1|\alpha_2|\alpha_3\) 变为 \(B->\alpha_1|\alpha_2|\alpha_3\) [消单产生式] 先判定变量是不是可生成的(每一个变量能够推推推到终结符)；再判定变量是可到达的(S变量能够推推推到目前变量) [消无用符号] 化成乔姆斯基形式 我们的目的是把所有的产生式化成 \(A->BC,A->a\) 所以第一步，面对产生式体长度大于等于2的，能化成的，尽可能化成这种形式。比如：\(A->aAS,B->BbB\) 面对这种可以化成的，我们引进\(C->a,D->b\) 这样就可以化成\(A->CAS,B->BDB\) (把常量、变量混杂的换成全部变量形式) 这样换了以后，要么右部全部是变量，要么右部只有一个常量 现在 把变量长度大于等于3的变量串 拆成变量长度是2的。比如：\(S->ASB\) 就可以拆成\(S->AE,E->SB\) ;\(B->SDS\)拆成\(B->SG,G->DS\) 完成！ [化成乔姆斯基范式] 化成乔姆斯基范式CNF 接下来我们拿着CNF将其化为GNF，GNF用处还是相当大的，这由GNF的形式所决定 \(A->a\beta\) ,根据终结符\(a\) 我们可以消除不确定性，可以唯一的替换，避免回溯。 替换的目的是由已知推未知（低序号推高序号） 最终会是\(Z->Z\beta\) 这种形式 然后消除直接左递归算法。 上面搞完后，会有一个符合要求的GNF范式，我们从这个符合要求的GNF要求进行入手，进行回填，会发现一步步都会产生符合要求的\(GNF\) ，直到所有的GNF都完成！ 形式语言与编译 九 CFG到CNF再到GNF 左递归消除 标签：长度 集合 iba 要求 单位 哪些 多个 递归 替换算法 原文地址：https://www.cnblogs.com/fennleo/p/13198948.html
CFG的化简
对上面简化后的CFG进行标准化——Chomsky范式
从上下文无关文发(CFG)到CNF(乔姆斯基范式)的算法
Greibach范式(GNF)
CFG的化简注意事项：
文章标题：形式语言与编译 九 CFG到CNF再到GNF 左递归消除
文章链接：http://soscw.com/index.php/essay/81748.html