LL分析方法自顶向下分析 ●LL(1)是L(k)的特例,其中的k则表示向前看k 个符号。 ●LL(1)方法和递归下降法属于同一级别的自顶 向下分析法,但有一些区别 递归下降法对每个非终极符产生子程序,而L()方 法则产生L分析表; 递归下降法能判断每个产生式的结束,而L(1)方法 则不能; 递归下降法分析法不用符号栈,而L(1)方法则用符 号栈
LL分析方法—自顶向下分析 ⚫ LL(1)是LL(k)的特例,其中的k则表示向前看k 个符号。 ⚫ LL(1)方法和递归下降法属于同一级别的自顶 向下分析法，但有一些区别. ▪ 递归下降法对每个非终极符产生子程序，而LL(1)方 法则产生LL分析表； ▪ 递归下降法能判断每个产生式的结束，而LL(1)方法 则不能； ▪ 递归下降法分析法不用符号栈，而LL(1)方法则用符 号栈
LL(1)分析方法的条件 对于任一非终极符A,其任意两个产生式 A→α和A→β,都要满足下面条件: Predict(A→a)∩ Predict(A→β)= 满足这一条件的文法称为LL(1)文法
LL(1)分析方法的条件 对于任一非终极符A，其任意两个产生式 A→和A→，都要满足下面条件： Predict(A→) Predict(A→)= 满足这一条件的文法称为LL(1)文法
LL(1)分析例 文法G[A]:A→aBc[1 B→>d[2]|bB[3] 输入串: abbdc ●分析过程: ●(A, abbdc)→1(cBa,abbd)→(cB,bbdc) →3(cBb,bbd)→(cB,bdc)→3(cBb,bdc) →(cB,d)→2(cd,dc)→(c,o)→(,)
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)分析的动作 替换:当米1∈V时选相应候选式β去替换X1 匹配:当X1∈时它与Y进行匹配,其结果可 能成功,也可能失败,如果成功则去掉X和 Y1,否则报错。 ●接受:当格局为(空,空)时报分析成功。 ●报错:出错后,停止分析
LL(1)分析的动作 ⚫ 替换：当X1VN时选相应候选式去替换X1。 ⚫ 匹配：当X1VT时它与Y1进行匹配，其结果可 能成功，也可能失败，如果成功则去掉X1和 Y1，否则报错。 ⚫ 接受：当格局为（空，空）时报分析成功。 ⚫ 报错：出错后，停止分析
LL(1)分析表 T:V×V→P∪[ Error NX T(A,t)=A→a若t∈ Predict(A→a) T(A, t=Error 否则 其中P表示所有产生式的集合
LL(1)分析表 ⚫ T：VN VT → P { Error } T(A,t)=A→ 若tPredict( A→ ) T(A,t)=Error 否则 其中P表示所有产生式的集合