编译原理LL(1)文法之提取左公因子,消除左递归 |
您所在的位置:网站首页 › 编译原理实验二LL(1)语法分析程序设计提问题 › 编译原理LL(1)文法之提取左公因子,消除左递归 |
在判断LL(1)文法是否符合的时候,需要判断LL(1)文法是否存在左公因子,和左递归的情况,以下给出相应的判断方法以及通过提取左公因子和消除左递归使非LL(1)文法转换为LL(1)法的方法
第一种情况:存在左公因子 ;解决方法:提取左公因子;
若文法中存在形如: A->ay|ab 两个产生式左部第一个符号相同,则不符合LL(1)文法,指代不明,则表示存在左公因子
解决方法: 转换成 A->aM1,aM2,aM3....的形式: 得: A->aM M->y|b 则成功提取左公因子;
第二种情况:存在左递归;
左递归有两种类型: (1)直接左递归 : A->AB, A∈Vn,B属于V* (2)间接左递归 A->Bb B->Aa A,B∈Vn,a,b属于V*
(这里第二种情况注意,因为是左递归,所以看得就是第一个字符,一定要跟这个类型一样的A->B.... 以及B->A.... 这种才是左递归,如果A->B.... ,B->aA..., 这种就不是左递归了,因为样式不同,请注意) 同样消除左递归的方法: 如果是间接左递归,则先转换成直接左递归:
例子: A->Bb | c B->Aa
将B->Aa代入到另一个式子: A->Aab | c,
转换 A->cM M->abM M->ε
就是得出结论,优先删除右部第一个符号和左部相同的即 A->Aab,就是要删除这个右部的第一个A 然后在所有A相关式子后面补一个新的符号 M 变成A->abM 以及A->cM 然后再补充一个式子: M->ε 就得到自己需要的符合的LL(1)文法啦, 大家可以用博主推荐的判断方法,进行判断~~点击打开链接 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |