编译原理-第三版-蒋立源-西北工业大学--第13节第四章.ppt

4.1.5 某些非LL(1)文法的改造 对于LL(1)文法而言，我们总能构造出相应的预测分析表，且表中决不会含有多重定义的元素。 然而对于非LL(1)文法，它们不满足LL(1)文法的条件，尽管仍可为其建立预测分析表，但表中必然会出现多重定义的元素(why?) 例如,文法G[S]: S ? abB A ? SC | BAA | ? B ? AbA C ? B | c FIRST(S)={a} FIRST(A)={a, b, ?} FIRST(B)={a, b} FIRST(C)={a, b, c} FOLLOW(S) = FOLLOW(A) = FOLLOW(B) = FOLLOW(C) = { a,b,c,# } FIRST(SC)={a} FIRST(BAA)={a, b} FOLLOW(A) = { a,b,c,# } 由造表规则,有： M[A, a] = { A?SC , A ? BAA , A?? } 例如,文法G[S]: S ? abB A ? SC | BAA | ? B ? AbA C ? B | c M[A,a] = { A?SC , A ? BAA , A?? } 可见非LL(1)文法所造之分析表中，必有冲突元素。 事实上，是否有冲突元素也是判别一文法是否是LL(1)文法的方法之一。 对于某些非LL(1)文法而言，通过消除左递归、反复提取左因子等方法，有时是可以将其改造成LL(1)文法的。 提取左因子 当文法中含有形如： A ? ??1 | ??2 | … | ??m 的产生式时，可将其改写为: A ? ?A’ A’? ?1 | ?2 | … | ?m 若诸候选式 ?1 ,?2 ,…,?m 中的一部分仍含有左因子，则再进行提取工作，如此等等。这样,就可能得到一个LL(1)文法。 例如： E ? E+T | T T ? (E)| a(E) | a 经改造后可得文法： E ? TE’ E’? +TE’| ? T ? aT’| (E) T’? (E) | ? 这是一个LL(1)文法。 应当指出，并非所有的文法都能改造为LL(1)文法。 例如，文法G[S]: S ? AU | BR A ? aAU | b B ? aBR | b U ? c R ? d 文法中S的两个候选式AU及BR的FIRST 集相交，G是非LL(1)的。为提取左因子，先 将S产生式中的A,B用其右部替换，得： S ? aAUU | bU | aBRR | bR 例如,文法G[S]: S ? AU | BR A ? aAU | b B ? aBR | b U ? c R ? d 先将S产生式中的A,B用其右部替换，得： S ? aAUU | bU | aBRR | bR 经提取左因子，得： S ? aS’| bS” S’? AUU | BRR S”? U|R A ? … 显然它仍不是LL(1)文法。 关于LL(1)的一些结论 能由LL(1)文法产生的语言称为LL(1)语言。它们已被证明具有许多重要特性，主要有： 任何LL(1)文法都是无二义性的； 左递归文法是非LL(1)的； 存在一种算法，它能判定任意文法是否为LL(1)的； 存在一种算法，它能判定任意两个LL(1)文法是否等价; 关于LL(1)的一些结论 （5）CFL是否是LL(1)语言是不可判定的； （6）非LL(1)语言是存在的。 若在分析过程中，每步向前扫描k个符号来确定选用的产生式，此分析方法称为LL(k)分析。 4.2 自底向上的语法分析 自底向上(?)的语法分析是从给定的符号串出发,试图逐步将它们归约为文法的开始符号。 ?的语法分析采用的是最左(规范)归约。 本节中介绍两种?分析方法，即优先分析法和LR分析法。 移进-归约分析