编译原理经典算法的可视化实现

图4.2提取左因子算法思想描述

其中A’是一个新的非终结符。反复应用这种变换，直到任一非终结符都没有两个候选式具有公共前缀为止。

4.4 LL(1)文法

4.4.1 LL(1)文法定义

对文法G的句子进行确定的自顶向下语法分析的充分必要条件是，G的任意两个具有相同左部的产生式A→α|β满足下列条件：

（1）如果α、β均不能推导出ε，则 FIRST(α) ∩ FIRST(β) = Φ。

（2）α 和 β 至多有一个能推导出 ε。

（3）如果 β错误！未找到引用源。 ε，则 FIRST(α) ∩ FOLLOW(A) = Φ。 我们就将满足上述条件的文法称为LL(1)文法。 4.4.2 LL(1)文法概要

LL(1)文法中的第一个L表示的是程序输入符号串的扫描是从左向右的，第二个L表示的是最左推导，而1表示的是在分析过程中每一步推导的执行都要向前查看一个输入符号—当前正在处理的输入符号。我们应该注意到LL(1)文法不含左递归也不是二义性的，可以用确定的自顶向下语法分析方法来分析LL(1)文法的所有句子。

另外我们应该注意到，并不是LL(1)文法可以用来描述所有的语言，而且也不能判定某语言是否符合LL(1)文法，因为这样的算法是不存在的。换句话说，确定的自顶向下分析不能完成所有的上下文无关语言的分析，而这些就是LL(1)文法所产生的语言。

21

编译原理经典算法的可视化实现 另外，在上述LL(1)文法的条件中，要求：至多只有ε ∈ FIRST(α1)，ε ∈ FIRST(α2)，…ε ∈ FIRST(αn) 这些条件中的一个成立。

22

编译原理经典算法的可视化实现

5 LL(1)文法可视化的设计与实现

5.1 程序界面的实现

在此程序中，我们需要设置文法的符号集，文法的表达式，然后就可以通过第4章中的算法来计算FIRST集合，FOLLOW集合并构造分析表，然后就可以对句子进行文法分析了。

文法符号集设置页面如图5.1所示：

图5.1 文法符号集设置

在文法符号集设置页面中，我们可以在此页面中输入符号集即终结符和非终结符，也可以直接加载文法的符号集，如果我们输入的符号集以后还要用到，我们也可以保存此符号集，这样以后就方便使用。

接下来我们就将文法的产生式输入，语言设置界面如图5.2所示，在此页面中，我们如果要添加表达式，则我们只要将表达式输入到右侧的文本框中，然后点击页面中的

23

编译原理经典算法的可视化实现 添加按钮，则可以看到表达式会在左侧的表达式列表中显示，当然，如果我们要删除表达式，只需选中表达式列表中的表达式，然后点击删除即可将表达式删除。在这里如果要将以前的列表加载进表达式列表中，单击加载列表然后选中文件即可，如果这些表达式以后还要用到，我们就可以单击保存列表即可保存。

图

5.2 语言设置界面

当我们要对字符串进行分析时，只需在如图5.3所示的字符串分析界面输入字符串,然后点击检测即可，页面的右侧是FIRST，FOLLOW和构造分析表的算法思想。

图5.3 字符串输入界面

24