zhouqijie

LL(1)文法

文法G是LL(1)的，当且仅当G的任意两个具有相同左部的产生式A->α|β满足下面条件：

  1. α和β最多有一个能推导出ε。如果α和β均不能推导出ε，则FIRST(α)∩FIRST(β)=Ø。
  2. 如果α可以推导出ε，则FIRST(α)∩FOLLOW(A)=Ø。
  3. 如果α可以推导出ε，则FIRST(α)∩FOLLOW(A)=Ø。

以上是为了保证同一非终结符的各个产生式的可选集互不相交。
由于可选集互不相交，可以为LL(1)文法构造预测分析器。

第一个L表示从左向右扫面输入。
第二个L表示产生最左推导。
“1”表示在每一步中只需要向前看一个输入符号来决定语法分析动作。

自顶向下和自底向上语法分析器的构造可以使用和文法G相关的两个函数FIRST和FOLLOW来实现。在自顶向下语法分析过程中，FIRST和FOLLOW使得我们可以根据下一个输入符号来选择应用哪个产生式。

CRE：FIRST集的计算理解：

  1. 终结符的FIRST集合只有它自身。
  2. 对于非终结符X，其产生式体的符号从左到右遍历。如果能推导出ε，就把符号的FIRST集依次加入非终结符X的FIRST集然后跳到下一个符号，如果不能再推导出ε，把当前符号FIRST集加入X的FIRST集，然后停止遍历。
  3. 如果非终结符X能直接推导出ε，那么把ε加入FIRST(X)中。

CRE：FOLLOW集的计算理解：
不断应用下面的规则，直到再没有新的符号可以被加入到任意的FOLLOW集合中：

  1. 如果将$符号放到FOLLOW(S)中，其中S是开始符号，$是输入右端结束标记。
  2. 如果存在A->αBβ，那么FIRST(β)中除了ε之外所有符号都在FOLLOW(B)中。
  3. 如果存在A->αB或者A->αBβ(FIRST(B)包含ε)，那么FOLLOW(A)中所有的符号都在FOLLOW(B)中



(END)