LL分析方法 — 自顶向下分析
? LL(1)是 LL(k)的特例,其中的 k则表示向前看 k
个符号。
? LL(1)方法和递归下降法属于同一级别的自顶
向下分析法，但有一些区别,
? 递归下降法对每个非终极符产生子程序, 而 LL(1)方
法则产生 LL分析表；
? 递归下降法能判断每个产生式的结束, 而 LL(1)方法
则不能；
? 递归下降法分析法不用符号栈, 而 LL(1)方法则用符
号栈 。
LL(1)分析方法的条件
对于任一非终极符 A,其任意两个产生式
A→ ?和 A→ ?,都要满足下面条件：
Predict(A→ ?) ? Predict(A→ ?)= ?
满足这一条件的文法称为 LL(1)文法。
LL(1)分析例
? 文法 G[A],A ? a B c[1]
? B ? d [2]| b B[3]
? 输入串,abbdc
? 分析过程：
? (A,abbdc)?1(cBa,abbdc) ? (cB,bbdc)
?3(cBb,bbdc) ?(cB,bdc) ?3 (cBb,bdc)
?(cB,dc) ?2 (cd,dc) ?(c,c) ?(,)
LL(1)分析的动作
? 替换,当 X1?VN时选相应候选式 ?去替换 X1。
? 匹配,当 X1?VT时它与 Y1进行匹配，其结果可
能成功，也可能失败，如果成功则去掉 X1和
Y1,否则报错。
? 接受,当格局为（空，空）时报分析成功。
? 报错,出错后，停止分析。
LL(1)分析表
?T,VN ? VT → P ? { Error }
T(A,t)=A→ ? 若 t?Predict( A→ ? )
T(A,t)=Error 否则
其中 P表示所有产生式的集合
LL(1)分析的驱动器
Stack
Input
a
? 栈为空情形的处理
? X? VT情形的处理
? X ? VN情形的处理
X
LL[1]分析
表
LL_Driver
[1]初始化,Stack,=empty； Push(S)；
[2]读下一个输入符,Read(a)；
[3]若当前格局是 ( empty,# ),则成功结束；
否则转下；
[4]设当前格局为 （,...,X,a.....),则
?若 X?VT & X=a
则 {Pop(1)； Read(a)； goto [3] }
?若 X?VT & X?a 则 Error；
?若 X?VN,则：
if T(X,a)=X→Y 1Y2Yn
then {Pop(1)； Push(Yn,.....,Y1)； goto[3]}
else Error
LL分析实例
?文法 G:
E? ? T E’[1]
E’ ? + T E’[2] | ?[3]
T ? F T’[4]
T’? * F T’[5] | ?[6]
F ? id[7] | ( E )[8]
符号串 i + i * i # 的 LL[1]分析过程：
Predict( [1] ) = first(TE’) = { id,( }
Predict( [2] ) = first(+TE’) = { + }
Predict( [3] ) = follow(E’) = { ),# }
Predict( [4] ) = first(FT’) = { id,( }
Predict( [5] ) = first(*FT’) = { * }
Predict( [6] ) = follow(T’) = { +,),# }
Predict( [7] ) = first(id) = { id }
Predict( [8] ) = first((E)) = { ( }
分析栈 S 输入流 T 矩阵元素
# E i + i * i # LL[ E,i ] = [1]
# E’ T i + i * i # LL [ T,i ] = [4]
# E’ T’ F i + i * i # LL [ F,i ] = [7]
# E’ T’ i i + i * i # Match
# E’ T’ + i * i # LL [ T’,+] = [6]
# E’ +i * i # LL [ E’,+ ] = [2]
# E’ T+ +i * i # Match
# E’ T i * i # LL [ T,i ] =[4]
# E’ T’ F i* i # LL [ F,i ] = [7]
# E’ T’ i i * i # Match
# E’ T’ * i # LL [ T’,* ] = [5]
# E’T’F* * i # Match
# E’T’F i # LL[F,i] = [7]
# E’T’i i # Match
# E’T’ # LL[T’,#] = [6]
# E’ # LL[E’,#] = [3]
# # ok
If-then-else语句
? BL语言 { [i ]j | i >=j>=0 }不是 LL文法
? 条件语句的产生式是无法变换成 LL[1]型
产生式的。
? LL(1)是 LL(k)的特例,其中的 k则表示向前看 k
个符号。
? LL(1)方法和递归下降法属于同一级别的自顶
向下分析法，但有一些区别,
? 递归下降法对每个非终极符产生子程序, 而 LL(1)方
法则产生 LL分析表；
? 递归下降法能判断每个产生式的结束, 而 LL(1)方法
则不能；
? 递归下降法分析法不用符号栈, 而 LL(1)方法则用符
号栈 。
LL(1)分析方法的条件
对于任一非终极符 A,其任意两个产生式
A→ ?和 A→ ?,都要满足下面条件：
Predict(A→ ?) ? Predict(A→ ?)= ?
满足这一条件的文法称为 LL(1)文法。
LL(1)分析例
? 文法 G[A],A ? a B c[1]
? B ? d [2]| b B[3]
? 输入串,abbdc
? 分析过程：
? (A,abbdc)?1(cBa,abbdc) ? (cB,bbdc)
?3(cBb,bbdc) ?(cB,bdc) ?3 (cBb,bdc)
?(cB,dc) ?2 (cd,dc) ?(c,c) ?(,)
LL(1)分析的动作
? 替换,当 X1?VN时选相应候选式 ?去替换 X1。
? 匹配,当 X1?VT时它与 Y1进行匹配，其结果可
能成功，也可能失败，如果成功则去掉 X1和
Y1,否则报错。
? 接受,当格局为（空，空）时报分析成功。
? 报错,出错后，停止分析。
LL(1)分析表
?T,VN ? VT → P ? { Error }
T(A,t)=A→ ? 若 t?Predict( A→ ? )
T(A,t)=Error 否则
其中 P表示所有产生式的集合
LL(1)分析的驱动器
Stack
Input
a
? 栈为空情形的处理
? X? VT情形的处理
? X ? VN情形的处理
X
LL[1]分析
表
LL_Driver
[1]初始化,Stack,=empty； Push(S)；
[2]读下一个输入符,Read(a)；
[3]若当前格局是 ( empty,# ),则成功结束；
否则转下；
[4]设当前格局为 （,...,X,a.....),则
?若 X?VT & X=a
则 {Pop(1)； Read(a)； goto [3] }
?若 X?VT & X?a 则 Error；
?若 X?VN,则：
if T(X,a)=X→Y 1Y2Yn
then {Pop(1)； Push(Yn,.....,Y1)； goto[3]}
else Error
LL分析实例
?文法 G:
E? ? T E’[1]
E’ ? + T E’[2] | ?[3]
T ? F T’[4]
T’? * F T’[5] | ?[6]
F ? id[7] | ( E )[8]
符号串 i + i * i # 的 LL[1]分析过程：
Predict( [1] ) = first(TE’) = { id,( }
Predict( [2] ) = first(+TE’) = { + }
Predict( [3] ) = follow(E’) = { ),# }
Predict( [4] ) = first(FT’) = { id,( }
Predict( [5] ) = first(*FT’) = { * }
Predict( [6] ) = follow(T’) = { +,),# }
Predict( [7] ) = first(id) = { id }
Predict( [8] ) = first((E)) = { ( }
分析栈 S 输入流 T 矩阵元素
# E i + i * i # LL[ E,i ] = [1]
# E’ T i + i * i # LL [ T,i ] = [4]
# E’ T’ F i + i * i # LL [ F,i ] = [7]
# E’ T’ i i + i * i # Match
# E’ T’ + i * i # LL [ T’,+] = [6]
# E’ +i * i # LL [ E’,+ ] = [2]
# E’ T+ +i * i # Match
# E’ T i * i # LL [ T,i ] =[4]
# E’ T’ F i* i # LL [ F,i ] = [7]
# E’ T’ i i * i # Match
# E’ T’ * i # LL [ T’,* ] = [5]
# E’T’F* * i # Match
# E’T’F i # LL[F,i] = [7]
# E’T’i i # Match
# E’T’ # LL[T’,#] = [6]
# E’ # LL[E’,#] = [3]
# # ok
If-then-else语句
? BL语言 { [i ]j | i >=j>=0 }不是 LL文法
? 条件语句的产生式是无法变换成 LL[1]型
产生式的。
