第5章 语法分析-自顶向下分析

1、精选选ppt第5章 语法分析自顶向下分析自顶向下分析 本章介绍编译程序的第二个阶段语法分析的设本章介绍编译程序的第二个阶段语法分析的设计方法和实现原理。计方法和实现原理。 确定的自顶向下分析思想确定的自顶向下分析思想 FIRST、FOLLOW、SELECT LL(1)文法的判别文法的判别 预测分析方法预测分析方法精选精选ppt ppt 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (2 2) ) LL(1) LL(1)分析法。要求理解递归下降分析、分析法。要求理解递归下降分析、LL(1)LL(1)文法的基本概念；文法的基本概念；LL(1)LL(1)分析表的构造与分析方法。分析表

2、的构造与分析方法。 能够对一个给定的文法判断是否是能够对一个给定的文法判断是否是LL(1)LL(1)文法；文法； 能构造预测分析表；能构造预测分析表； 能用预测分析方法判断给定的输入符号串是否是该文能用预测分析方法判断给定的输入符号串是否是该文法的句子；法的句子； 能对某些非能对某些非LL(1)LL(1)文法做等价变换：文法做等价变换： 消除左递归消除左递归 提取左公共因子提取左公共因子可能会变成可能会变成LL(1)LL(1)文法。这样可扩大自顶向下分析方法的应用。文法。这样可扩大自顶向下分析方法的应用。教学目的及要求编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析

3、( (3 3) )精选ppt5.1 确定的自顶向下分析思想确定的自顶向下分析思想 要点：要点： 由根向下构造语法树；由根向下构造语法树； 构造最左推导；构造最左推导； 推导出的终结符是否与当推导出的终结符是否与当前输入符匹配？前输入符匹配？ S aaab A B a A S ABA aA B b bBaaabS AB S AB aAB A aA aaAB A aA aaaAB A aA aaa B A aaab B b编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (4 4) )精选ppt1. 带回溯的自上而下分析带回溯的自上而下分析S ABA aA B b b

4、Ba a a b bS(1) A. S AB(2) aA. A aA(3) aaA. A aA(4) aaaA. A aA(5) aaa B. A (6) aaab B baaabbS (1) A. S AB (2) aA. A aA (3) aaA. A aA (4) aaaA. A aA (5) aaa B A (6) aaa b B B bB (7) aaabb B b 编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (5 5) )精选ppt2. 无回溯的自顶向下分析程序无回溯的自顶向下分析程序 特征特征根据下一个输入符号为当前要处理的非终结符根据下一个输

5、入符号为当前要处理的非终结符选择产生式。选择产生式。 要求要求文法是文法是LL(1)的的 第一个第一个L 从左到右扫描输入串从左到右扫描输入串 第二个第二个L 生成的是最左推导生成的是最左推导 1 向前看一个输入符号向前看一个输入符号(lookahead) 预测分析程序的实现技术预测分析程序的实现技术 (1) 递归下降子程序递归下降子程序 (2) 表驱动分析程序表驱动分析程序编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (6 6) )精选ppt 3. 语法分析的任务语法分析的任务 语法分析是编译过程的核心部分。语法分析是编译过程的核心部分。 检查由扫描器输检查

6、由扫描器输出的单词序列是否符合该语言的文法出的单词序列是否符合该语言的文法句子。句子。 分析器的输入：单词序列分析器的输入：单词序列 分析器的输出、分析树分析器的输出、分析树 出错处理：定位、继续编译出错处理：定位、继续编译 分析方法：分析方法： （1）自顶向下）自顶向下(预测分析预测分析) （2）自底向上）自底向上(算符优先、算符优先、LR分析器分析器)编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (7 7) )精选ppt 编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (8 8) )精选ppt 例例5-1 若有文法若有文法G

7、S： SpA|qB AcAd|a BdB|b 若输入串若输入串W= pccadd，自顶向下的推导过程为：，自顶向下的推导过程为： S pA pcAd pccAdd pccAdd 所示文法的两个特点：所示文法的两个特点： (1)每个产生式的右部都由终结符开始。每个产生式的右部都由终结符开始。 (2)如果两个产生式有相同的左部，那么它们的右部由如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。不同的终结符开始。 因此分析过程是唯一确定的。因此分析过程是唯一确定的。编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (9 9) )精选ppt 例例5-2若有文法

8、若有文法GS： SAp|Bq AcA|a BdB|b 若输入串若输入串W= ccap，自顶向下的推导过程为：，自顶向下的推导过程为： S Ap cAp ccAp ccap 所示文法有三个特点所示文法有三个特点 (1)产生式的右部不全是由终结符开始。产生式的右部不全是由终结符开始。 (2)如果两个产生式有相同的左部，它们的右部由不同的终结符如果两个产生式有相同的左部，它们的右部由不同的终结符或非终结符开始。或非终结符开始。 (3)文法中无空产生式。文法中无空产生式。对于产生式中相同左部含有对于产生式中相同左部含有非终结符非终结符开始的产生式时，为了便于正开始的产生式时，为了便于正确考察和选择需要

9、求出相关产生式的首符号集确考察和选择需要求出相关产生式的首符号集FIRST( )。编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (1010) )精选ppt 定义定义 5-1 设设G=(V，T，P，S)是上下文无关文法是上下文无关文法 FIRST( )=a * a , aT, , (VT)* 若若 * 则规定则规定FRIST( )，称称FIRST( )为为 的开的开始符号集或首符号集。始符号集或首符号集。 求例求例5-2的首符号集如下：的首符号集如下： FIRST(Ap)=a,c FIRST(Bq)=b,d 结论：产生式左部相同，而右部都以非终结符开始，结论：产

10、生式左部相同，而右部都以非终结符开始，只要他们只要他们右部的符号串可以推导出的首符号集不相交，右部的符号串可以推导出的首符号集不相交，仍然可以唯一确定所要选择的产生式。仍然可以唯一确定所要选择的产生式。 编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (1111) )精选ppt5.2 LL(1)文法的判别方法文法的判别方法 利用自顶向下的语法分析技术，必须首先判断利用自顶向下的语法分析技术，必须首先判断给定的文法是否为给定的文法是否为LL(1)文法。文法。 分别计算分别计算FIRST、FOLLOW、SELECT集合，集合，进而判断给定的文法是否为进而判断给定的文

11、法是否为LL(1)文法。文法。 分析前面的分析前面的3个例子，找出关键问题，不同的个例子，找出关键问题，不同的问题采用不同的方法。问题采用不同的方法。编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (1212) )精选ppt计算计算FIRST集集 1.若若X T，则，则FIRST(X)=X 2.若若X V，且有产生式，且有产生式Xa，则把，则把a加入到加入到FIRST(X)中；中； 若若X 也是一条产生式，则把也是一条产生式，则把 也加到也加到FIRST(X)中。中。 3.若若XY是一个产生式且是一个产生式且Y V,则把则把FIRST(Y)中的所有非中的所有非

12、元元素都加到素都加到FIRST(X)中；若中；若X Y1Y2YK 是一个产生式，是一个产生式，Y1,Y2,Y(i-1)都是非终结符，而且，对于任何都是非终结符，而且，对于任何j，1ji-1，FIRST(Yj)都含有都含有 (即即Y1.Y(i-1)* )，则把则把FIRST(Yj)中的中的所有非所有非 元素都加到元素都加到FIRST(X)中；特别是，若所有的中；特别是，若所有的FIRST(Yj , j=1,2,K)均含有均含有 ，则把，则把 加到加到FRIST(X)中。中。编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (1313) )精选ppt 例例5-3 若有

13、文法若有文法GS： SaA Sd AbAS A 若输入串若输入串W=abd,则试图推导出则试图推导出abd串的推导过程为串的推导过程为:abdabSabASaASdSAbSAbSAbAaAaAaAaSSSS 编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (1414) )精选ppt 例例5-3 所示文法的特点所示文法的特点 当某一非终结符的产生式中含有空产生式时，它的非空当某一非终结符的产生式中含有空产生式时，它的非空产生式的右部的首符号集两两不相交，并与在推导过程中产生式的右部的首符号集两两不相交，并与在推导过程中紧跟该非终结符右边可能出现的终结符集也不相交，

14、则仍紧跟该非终结符右边可能出现的终结符集也不相交，则仍可以构造确定的自顶向下分析，为此，需要定义一个文法可以构造确定的自顶向下分析，为此，需要定义一个文法符号的后跟符号的集合符号的后跟符号的集合FOLLOW( )。 定义定义 5-2 FOLLOW(A)= aS * A 且且aT, a FRIST( )， (VT)*， (VT) + 若若S * A ，且，且 *，则，则 #FOLLOW(A)。编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (1515) )精选ppt计算计算FOLLOW集集1. 对于文法的开始符号对于文法的开始符号S，置，置 # 于于FOLLOW(

15、S) 中；中；2. 若若 B是一个产生式，则把是一个产生式，则把 FIRST() #加至加至FOLLOW(B)中；中；3. 若若 B是一个产生式，或是一个产生式，或 B是一个产生是一个产生式而式而 * (即即 FIRST()，则把，则把FOLLOW(A)加至加至FOLLOW(B)中。中。编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (1616) )精选ppt 定义定义5-3 给定上下文无关文法的产生式给定上下文无关文法的产生式A AV， (VT)*, 若若 *，则，则SELECT(A )=FIRST( )。如果如果 *，则，则SELECT(A )=(FIRST

16、( )-) FOLLOW(A)。 定义定义5-4 一个上下文无关文法是一个上下文无关文法是LL(1)文法的充分必文法的充分必要条件是，对每个非终结符要条件是，对每个非终结符A的两个不同产生式，的两个不同产生式， A ， A 满足满足 SELECT(A ) SELECT(A )= 其中其中 、 不同时能不同时能 *。编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (1717) )精选ppt LL(1)文法的判别文法的判别 一个文法一个文法G是是LL(1)的，当且仅当对于的，当且仅当对于G的每一个非终结的每一个非终结符的任何两个不同产生式符的任何两个不同产生式 ，下

17、面的条件成立：，下面的条件成立： FIRST()FIRST()= ，也就是也就是 和和推导不出以同推导不出以同一个终结符一个终结符a为首的符号串；它们不应该都能推出空字为首的符号串；它们不应该都能推出空字 。 . 假若假若 * ，那么，那么，FIRST()FOLLOW(A) 。 也就是，若也就是，若 * ，则则所能推出的串的首符号不应在所能推出的串的首符号不应在FOLLOW(A)中。中。编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (1818) )精选ppt 例：例：G E: (1) E TE (2) E+TE (3) E (4) T FT (5) T*FT

18、(6) T (7) F (E) (8) F i非终结符的非终结符的FIRST集合如下：集合如下： FIRST(E)=(，i FIRST(E)=+， FIRST(T)=(，i FIRST(T)=*， FIRST(F)=(，i非终结符的非终结符的FOLLOW集合为：集合为： FOLLOW(E)=)， # FOLLOW(E)=)，# FOLLOW(T)=，)，# FOLLOW(T)=，)，# FOLLOW(F)=*,，)，# 编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (1919) )精选pptG E: (1) E TE (2) E +TE (3) E (4) T

19、 FT (5) T *FT (6) T (7) F (E) (8) F aE+TE FIRST(+TE)=+FOLLOW(E)=)，T*FT FIRST(*FT)=*FOLLOW(T)=+,)，F (E) a FIRST( (E)=(FIRST( a)=a所以所以GE是是LL(1)的的编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (2020) )精选ppt5.3 非非LL(1)文法与文法与LL(1)文法的等价变换文法的等价变换 LL(1)文法的性质文法的性质: LL(1)文法是无二义的文法是无二义的 LL(1)文法不含左递归文法不含左递归 非非LL(1)文法的

20、改造文法的改造 （1）提左公因子）提左公因子 （2）消除左递归）消除左递归编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (2121) )精选ppt 1. 提取左公共因子提取左公共因子 文法文法G的产生式的产生式 A 1 存在左因子存在左因子 ,这导致了对相同左部的产生式其右部的这导致了对相同左部的产生式其右部的FIRST集相集相交，即交，即SELECT(A 1)SELECT(A ) 。 影响分析：遇到影响分析：遇到 时难以判断用哪一个产生式进行匹配若时难以判断用哪一个产生式进行匹配若A 1 改写成改写成: A ( 1 ) 或引入新非终结符或引入新非终结符 A

21、A A 1 一般：一般： A 1 2 n 1 m 改写成改写成:A A 1 m A 1 2 n 若若 1， 2 n仍有公共左因子，可再次提取，直到无公共左因子仍有公共左因子，可再次提取，直到无公共左因子 为止。为止。 编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (2222) )精选ppt 例例5-6 (1)SaSb (2)SaS (3)S 提取提取(1)(2)的左公因子后得：的左公因子后得： SaSA Ab S 例例5-7 SiEtS iEtSeS a Eb 其中，其中，i,t,e分别表示分别表示if,then和和else,E和和S分别表示表达式和分别表示表

22、达式和语句。语句。 提取了公共左因子之后，文法变为提取了公共左因子之后，文法变为 SiEtS a S eS Eb 于是，对于输入于是，对于输入i，可以展开，可以展开S为为iEtSS，直到，直到iEtS分析完分析完毕再去决定把毕再去决定把S展为展为eS或或。 编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (2323) )精选ppt 隐式左公因子：隐式左公因子： 产生式右部以非终结符开始，产生式右部以非终结符开始， 方法：用方法：用该非终结符的右部以终结符开始的产生式去替换它。该非终结符的右部以终结符开始的产生式去替换它。 例例5-8 GS: SaSd Ac Aa

23、S b 把把A的产生式代入的产生式代入S中：中： SaSd aSc bc 提取左因子：提取左因子： SaSA bc Ad c AaS bA的产生式是多余的，需删除。的产生式是多余的，需删除。 最终：最终： SaSA bc Ad c编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (2424) )精选ppt 例例5-9 (1)SAp Bq (2)AaAp d (3)BaBq e 用用(2)(3)右部替换右部替换(1)中的中的A，B (1)SaApp aBqq dp eq (2)AaAp d (3)BaBq e 替换替换(1) Sa(App Bqq) dp eq Sa

24、S dp eq SApp Bqq 继续，无休止。继续，无休止。 在有限步骤内不能改写成无公共左因子的文法。在有限步骤内不能改写成无公共左因子的文法。说明：说明： 1、有些文法在有限步骤内不能改写成、有些文法在有限步骤内不能改写成无公共左因子的文法。无公共左因子的文法。 2、一个文法提取公共左因子后不一定、一个文法提取公共左因子后不一定为为LL(1)文法。文法。 编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (2525) )精选ppt2. 消除左递归消除左递归 左递归的定义：一个文法左递归的定义：一个文法G， 若存在下列产生式时若存在下列产生式时 AA,其中其中

25、:AV, (VT)*，(直接左递归直接左递归) AB BA A,BV, 、 (VT)* , (间接左递归间接左递归) 则称则称G是左递归的。是左递归的。 左递归文法不适于用来构造自顶向下分析，这种产生式左递归文法不适于用来构造自顶向下分析，这种产生式更简单的代表是：更简单的代表是： SSa b (1)FIRST(Sa)FIRST(b)。 (2)由由S产生的句子是产生的句子是ban n0。 例如例如:对于输入对于输入baaa#,从左到右扫描输入串。从左到右扫描输入串。 编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (2626) )精选ppt 用这样的产生式构造递

26、归预测分析的过程，那用这样的产生式构造递归预测分析的过程，那么，一进入这种过程不匹配任何输入符号，直么，一进入这种过程不匹配任何输入符号，直接执行递归调用，形成自己调用自己的死循环。接执行递归调用，形成自己调用自己的死循环。 编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (2727) )精选ppt 消除直接左递归消除直接左递归 1. 简单左递归简单左递归 AA 消除左递归改写为右递归：消除左递归改写为右递归： AA AA 2. 一般左递归一般左递归 AA1 A2 Am 1 2 n 消除左递归改写为右递归：消除左递归改写为右递归： A1A 2A nA A1A 2

27、A mA 例如：例如： EE+T T TT*F F F(E) id 消除左递归的结果为：消除左递归的结果为：ETE E+TE TFT T*FT F(E) id 编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (2828) )精选ppt 消除间接左递归消除间接左递归 要求无环路要求无环路AA和无和无 -产生式。产生式。 1. 把非终结符按某一顺序排序为把非终结符按某一顺序排序为A1,A2An 。 2. for(i=1;i=n;i+) for(j=1;jx1x2xn按逆序即按逆序即xnx2x1入栈入栈XT?X=#?X=aX=a? MX,a是产生式吗？是产生式吗？出错

28、出错结束结束出错出错 输入输入下下 一一 符号符号YNNNYYNNYY编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (4545) )精选ppt预测分析表构造算法预测分析表构造算法1.对文法对文法G的每个产生式的每个产生式 执行第二步和第三步；执行第二步和第三步；2.对每个终结符对每个终结符a FIRST( )，把，把 加至加至A,a中；中；3.若若 FIRST( )，则对任何，则对任何b FOLLOW(A) 把把 加至加至A,b中，中，4.把所有无定义的把所有无定义的A,a标上标上“出错标志出错标志”。 可以证明，一个文法可以证明，一个文法G的预测分析表不含多

29、重入口，的预测分析表不含多重入口，当且仅当该文法是当且仅当该文法是LL(1)的。的。编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (4646) )精选ppt 对符号串对符号串i+i*i#的分析过程的分析过程 dui对符号串I+I*I#的分析过程编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (4747) )精选ppt编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (4848) )精选ppt5.5 5.5 不确定的自顶向下分析思想不确定的自顶向下分析思想 引起回溯的原因：引起回溯的原因：在文法中当关

30、于某个非终结符的产生在文法中当关于某个非终结符的产生式有多个候选时，而面临当前的输入符号无法确定选用式有多个候选时，而面临当前的输入符号无法确定选用惟一的产生式，从而引起回溯。惟一的产生式，从而引起回溯。1. 由于相同左部产生式的右部由于相同左部产生式的右部FIRST集交集不为空集交集不为空 S xAy A ab a 当前输入串为：当前输入串为：xay 可以通过不确定的语法分析树进行分析！可以通过不确定的语法分析树进行分析！编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (4949) )精选ppt 若输入串为若输入串为xay，则其分析过程如下：，则其分析过程如下

31、： (1) 首先建立根结点首先建立根结点S。 (2) 文法关于文法关于S的产生式只有一个，也即由的产生式只有一个，也即由S生长的语法树如图生长的语法树如图(a)所示，它的第一个终结符所示，它的第一个终结符x与输入串待分析的字符与输入串待分析的字符x匹配。此匹配。此时，下一个待分析的字符为时，下一个待分析的字符为a，期待着与语法树中在，期待着与语法树中在x右侧且右侧且与与x相邻的叶结点相邻的叶结点A匹配。匹配。 (3) 非终结符非终结符A有两个候选式，先选用第一个候选式生长的语法有两个候选式，先选用第一个候选式生长的语法树如图树如图 (b)所示；这时语法树的第二个叶结点所示；这时语法树的第二个叶

32、结点a恰与待分析的恰与待分析的字符字符a匹配。匹配。编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (5050) )精选ppt (4) 输入串中下一个待分析的字符为输入串中下一个待分析的字符为y，它期待与第三个叶，它期待与第三个叶结点结点b匹配，但匹配时发现这两个字符是不同的，即匹配匹配，但匹配时发现这两个字符是不同的，即匹配失败，这是因为生成失败，这是因为生成A的子树时所选用的是其第一个候选的子树时所选用的是其第一个候选式。式。 (5) 因不匹配而将因不匹配而将A所生成的这棵子树注销，即把匹配指针所生成的这棵子树注销，即把匹配指针回退到输入串的第二个字符回退到

33、输入串的第二个字符a，也就是恢复与，也就是恢复与A匹配时的匹配时的现场，即现场，即(3)之前。之前。 (6) 此时此时A选用第二个候选式并生长语法树如图选用第二个候选式并生长语法树如图 (c)所示，这所示，这时第二个叶结点时第二个叶结点a与输入串的第二个叶结点与输入串的第二个叶结点a匹配。匹配。编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (5151) )精选pptyAxSyAxSabyAxSa(a)(b)(c) (7) 此时输入串的下一个待分析字符指向此时输入串的下一个待分析字符指向y，而语法树的下一个，而语法树的下一个未匹配的叶结点也为未匹配的叶结点也为y

34、，两者恰好匹配。因此，图，两者恰好匹配。因此，图 (c)的语法树的语法树即为输入串即为输入串xay的语法树。的语法树。 试探分析对应的语法树试探分析对应的语法树编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (5252) )精选ppt2. 由于相同左部产生式的右部存在能由于相同左部产生式的右部存在能=* 的产生的产生式，且该终结符的式，且该终结符的FOLLOW集中含有其它产生集中含有其它产生式右部式右部FIRST集的元素。集的元素。 S aAS S b A bAS A 对输入串对输入串ab#的试探推导过程可以用不确定的语法树表的试探推导过程可以用不确定的语法树表

35、示！示！编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (5353) )精选ppt3. 由于文法含有左递归由于文法含有左递归 S Sa S b 对输入串对输入串baa#的试探推导过程可以用不确定的的试探推导过程可以用不确定的语法树表示！语法树表示！ 显然，这种带回溯的自上而下分析是一个不断显然，这种带回溯的自上而下分析是一个不断试探的过程；其分析效率极低，在实用的编译试探的过程；其分析效率极低，在实用的编译程序中很少使用。程序中很少使用。编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (5454) )精选ppt典型例题及解答典型例题及解答 例题例题1 已知文法已知文法G(S)：S aH HaMd d M Ab A aM e1. 判断判断G(S)是否为是否为LL(1)文法，若是，构造相应的预文法，若是，构造相应的预测分析表。测分析表。2. 请给出对输入串请给出对输入串aaabd#的预测分析过程，的预测分析过程， aaabd是是否为合法句子。否为合法句子。编译原理编译原理 第第5 5章章 语法分析语法分析自顶向下分析自顶向下分析 ( (5555)