我们喜欢和需要使用是LL(1)文法，但是我们往往遇到的文法不是LL(1)文法这时候需要将它进行转换转换成LL(1)文法。
这里给出两种方法分别是提取左公因子和消除左递归
1提取左公因子
含有左公共因子的文法若文法中含有形如：A→αβ|αr的产生式，称文法含有左公共因子显然,SELECT(A→αβ)∩SELECT(A→αr)≠ф,文法不是LL(1)文法提取左公因子基本思想通过改写产生式来推迟决定，读入足够多的输入，获得足够的信息之后，再做出正确判断。提取左公因子有左因子的文法A→αβ1|αβ2等价于A →A’(β1| β2)提左因子A →αA’ A→ β1| β2一般定义：A→δβ1|δβ2|…|δβn|γ1|γ2|…|γm（每个γ不以δ开头）可改写为A→δA’|γ1|γ2|…|γmA’→β1|β2|…|βn这个左公因子有两种形式：显示和隐式的！！！接下来两个例子会讲述这个问题。例子1：文法G[S] S →aSb | aS | ε请判断该文法是否为LL(1)文法？解：该文法不是LL(1)文法。提左因子S →aS(b| ε)S →ε引入S’转换成S →aSS’S’→b| εS →ε注意：这里只是举例子讲述原理定义不去判断是否是LL(1)文法！！！具体判断可以参考LL(1)文法定义及判别_用编程写诗的博客-CSDN博客例子2：文法 G[A]A →ad | BcB→aA | bB请判断该文法是否为LL(1)文法？解：含有隐含左公因子第一次改写后G[A] A →ad | aAc | bBcB →aA | bB我们发现还是有公因子的接着提公因子后A →aA’| bBcA’→d| AcB →aA | bB这个才是最终的结果！！！消除左公因子小结经过提取左公因子之后，有些文法从非LL(1)文法变为LL(1)文法，有的仍不是LL(1)文法。因此，文法不含左公共因子只是LL(1)文法的必要条件。对于隐含的左公因子，可先等价变换为明确的左公因子之后，再进行提取。经过提取左公因子之后，有时会使某些规则变为多余规则，故必须检查提取左公因子之后的文法，去除多余规则。个别文法不能在有限步之内提取完左公因子。2消除左递归含有左递归的文法若文法中含有形如a)A→Aβ(A∈VN, β∈(V)*)的规则b)A→Bβ B→Aα的规则那么在a)中含有左递归的规则，称为直接左递归在b)中虽然没有含左递归的规则，但A=>Bβ=>Aαβ即A=>+A…,称为间接左递归含有左递归的文法不是一个LL(1)文法证明：以直接左递归为例，若有如下产生式A→A α| A→β其中, α和β为任意语法符号串。不难证明有下面关系式：First( β)⊆First( A α)⊆Select( A→A α)First( β)⊆Select( A→ β)由于A→A α和A→ β的Select集相交，故含有左递归的文法不是LL(1)文法对于产生式P→Pα|β (串的特点βα. . .α)α不为ε，β不以P开头，则可改写规则为：P→βP’ P’→αP’| ε例：S→Sa|b可改写为：S→bS’S’ →aS’| ε消除直接左递归一般定义P →Pα1|Pα2|…|Pαm|β1|β2|…|βn其中每个α均不等于ε，每个β不以P开头，则：P →β1P’|β2P’|…|βnP’P’→α1P’|α2P’|…|αmP’|ε注意：(1)利用这种方法可以把直接左递归都消去，即换成右递归。(2)但是，这种方法并没有消除整个文法的左递归性。间接左递归仍会存在消除间接左递归先将间接左递归等价变换为等价的直接左递归后再消除左递归eg:G[A]A →aB | BbB →Ac | d将规则1,2代入3中先变换成直接左递归A →aB | BbB →aBc | Bbc|d再消除B的直接左递归A →aB | BbB →aBcB’| dB’B’→bcB’|ε消除左递归小结消除左递归之后，有些文法从非LL(1)文法变为LL(1)文法，有的仍不是LL(1)文法。因此，文法不含左公共因子只是LL(1)文法的必要条件。消除左递归之后，有时会使某些规则变为多余规则，故必须检查消除左递归之后的文法，去除多余规则消除左递归的文法在形式上可能不同，但均等价。
如果觉得《非LL(1)文法到LL(1)文法的等价变换》对你有帮助，请点赞、收藏，并留下你的观点哦！
