《编译原理第五章.ppt

写成一般形式为：A→αβ1|αβ2|…|αβn, 提取左公共因子后变为： A→α （β1|β2|…|βn） ， 再引进非终结符A′，变为： A→αA′ A′→β1|β2|…|βn 若βi、βj、 βk仍含有左公共因子，可反复提取，直到再无左公共因子为止。 注意：提取左公共因子后，不一定变为LL（1）文法。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例5.6 若文法G1的产生式为： S →aSb | aS | ε 提取左公共因子后得 S→aS（b |ε）| ε， 引进非终结符A，得：S →aSA |ε A →b |ε 因为SELECT（A→b）={b} SELECT（A→ε）=FOLLOW（A）=FOLLOW（S） ={b，#} SELECT（A→b）∩ SELECT（A→ε）≠φ 提取左公共因子后，仍不是LL（1）文法。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例5.7 若文法G2的产生式为： A→ad | Bc B→aA | bB 左公共因子是隐式， 用替换方法： A→ad A→a（d | Ac）| bBc A→aA′| bBc A→aAc | bBc B→aA | bB A′→d | Ac B→aA | bB B→aA | bB 是LL（1）文法。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 注意：文法中不含左公共因子只是LL（1）文法的必要条件。对文法进行提取左公共因子后，有时会使某些产生式变成无用产生式，在这种情况下，必须先对文法进行化简，然后进行判断。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例5.8 若文法G3的产生式为： S→aSd | Ac A→aS | b 替换A后，文法变为： S→aSd | aSc | bc A→aS | b 提取左公共因子 S→aS（d | c） | bc Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 引进非终结符A′，文法变为： S→aS A′| bc A′→d | c A→aS | b 文法中非终结符A变成不可达的符号， A→aS | b成为无用产生式，应删除。 S→aS（d | c） | bc A→aS | b Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 结论： 1）不一定每个文法的左公共因子都能在有限步骤内替换成无左公共因子的文法。 2) 一个文法提取了左公共因子后，不一定变成LL（1）文法。 存在某些文法，不能在有限步骤内提取完左公共因子。 见p86 例5.9 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 As