LL(1)文法

构造一个不带回溯的自上而下分析的文法条件

  1. 文法不含左递归

  2. 对于文法中每一个非终结符 A 的各个产生式的候选首符集两两不相交。即,若

    Aα1α2...αnA\to \alpha_1|\alpha_2|...|\alpha_n

    FIRST(αi)FIRST(αj)=ϕ(ij)FIRST(\alpha_i)\cap FIRST(\alpha_j)=\phi (i\neq j)

  3. 对文法中的每个非终结符 A,若它存在某个候选首符集包含ε\varepsilon,则

    FIRST(αi)FOLLOW(A)=ϕi=1,2,3,...,nFIRST(\alpha_i)\cap FOLLOW(A) = \phi \newline i = 1,2,3,...,n

如果一个文法 G 满足以上条件,则称该文法 G 为 LL(1)文法。