编译原理例题与习题解答PPT课件

1、1回顾 程序语言的定义程序语言的定义 一个程序语言是一个记号系统, ,它主要由以下方面定义： 语法 语义 每个句子构成的规律每个句子构成的规律 研究语言研究语言 每个句子的含义每个句子的含义语法语义第1页/共85页2语法=词法规则+ +语法规则 词法规则：单词符号的形成规则。 单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符等。 描述工具：正规式和有限自动机理论 语法规则：语法单位的形成规则。 语法单位通常包括：表达式、语句、子程序、过程、函数、程序等; ; 描述工具：上下文无关文法回顾第2页/共85页3标识符与名字 标识符：以字母开头的，由字母数字组成的字

2、符串。 标识符与名字两者有本质区别： 标识符是语法概念 名字有确切的意义和属性回顾第3页/共85页4上下文无关文法的定义：一个上下文无关文法G是一个四元式G=(VT，VN，S，P)，其中 VT：终结符集合(非空) VN：非终结符集合(非空)，且VT VN= S：文法的开始符号，S VN P：产生式集合(有限)，每个产生式形式为P， P VN， (VT VN)* 开始符S至少必须在某个产生式的左部出现一次。回顾第4页/共85页5 假定假定G是一个文法，是一个文法，S是它的开始符号。如果是它的开始符号。如果S ，则称，则称 是一个是一个句型句型。仅。仅含终结符号的句型是一个含终结符号的句型是一个句

3、子句子。 文法文法G所产生的句子的全体是一个所产生的句子的全体是一个语言语言，将它记为，将它记为L(G) L(G) = | S & VT* *文法产生语言*+回顾第5页/共85页6 定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。 语言的二义性：一个语言是二义性的，如果对它不存在无二义性的文法。 可能存在G和G，一个为二义的，一个为无二义的。但L(G)=L(G)回顾文法和语言的二义性第6页/共85页7例题例题2.12.1：有一个文法：有一个文法 G=(S,A,B,a,b,P,S),G=(S,A,B,a,b,P,S),其中其中P: P: S S aB|bA aB

4、|bA A A a|aS|bAA a|aS|bAA B B b|bS|aBBb|bS|aBB 采用采用最左推导最左推导产生句子产生句子aabbabaabbab 并画出相应的语法树。并画出相应的语法树。 S S a aB BaaaaB BB B aabaabS SB B aabbaabbA AB BaabbaaabbaB B aabbabaabbab S S a B a B a B B a B Bb Sb Sb b b Ab Aa a第7页/共85页8例题2.2 试构造生成语言L=anbnci|n 1, i 0的文法 分析：要求a和b的个数一样多，并至少为一个，而c的个数为0个以上即可，所以可以

5、用一个终结符去生成anbn串，用另一个非终结符去生成ci 。 G(Z): ZAB A aAb|ab B cB| 第8页/共85页9 例题2.3 请证实文法G(E): E EiT | T T T+F | iF | F F E* | ( 是一个二义文法。第9页/共85页10P36-6. 文法文法G6为为: N D|ND D 0|1|2|3|4|5|6|7|8|9 （1） G6的语言的语言L(G6)是什么是什么? G6的语言是：的语言是： 09的数字组成的任意非空数字串的数字组成的任意非空数字串L(G6)=x|x0,1,2,3,4,5,6,7,8,9+（2）给出句子）给出句子0127、34和和568

6、的最左和最右推导。的最左和最右推导。第10页/共85页 注意：1)1)步骤，和 的区别；2) 2) 不能写为 解：01270127的最左推导：N NNDNDNDDNDDNDDDNDDDDDDDDDDD 0DDD0DDD0101DDDD012012D D01270127 0127 0127的最右推导：N NNDNDN7N7ND7ND7N27N27ND27ND27 N127N127D127D12701270127+第11页/共85页12P36-7 写一文法, 使其语言是奇数集, 但不允 许出现以0打头的奇数。解解: : 将奇数划分为三个部分：将奇数划分为三个部分：最高位最高位允许出现允许出现1 1

7、9,9,用非终结符用非终结符B B表示表示; ;中间部分中间部分可出现任意多位数字可出现任意多位数字0 09, 9, 每一位用非终结符每一位用非终结符D D表示表示; ;最低位最低位只出现只出现1,3,5,7,9, 1,3,5,7,9, 用用A A表示。表示。 由于中间部分可任意位由于中间部分可任意位, ,故需另引入一故需另引入一 非终结符非终结符M,M,它包括最高位和中间部分。它包括最高位和中间部分。第12页/共85页13MB最高位中间位DDDA最低位第13页/共85页14解: 奇数集文法GN为: G=(0,1,9,N,A,M,B,D,N,) : NA | MA MB | MD A1 | 3

8、 | 5 | 7 | 9 B1|2|3|4|5|6|7|8|9 D0 | B第14页/共85页 8.8. 令文法为 E T|E+T|E-TE T|E+T|E-T T F|T T F|T* *F|T/FF|T/F F (E)|i F (E)|i (1) 给出 i+i*i、i*(i+i)的最左推导和最右推导。解：此处仅以 i*(i+i) 为例给出答案最左推导E E T T T T* *F F F F* *F F i i* *F F i i* *(E) (E) i i* *(E+T)(E+T) i i* *(T+T)(T+T) i i* *(F+T)(F+T) i i* *(i+T)(i+T) i

9、i* *(i+F )(i+F ) i i* *(i+i)(i+i) 最右推导E E T T T T* *F F T T* *(E) (E) T T* *(E+T) (E+T) T T* *(E+F)(E+F) T T* *(E+i) (E+i) T T* *(T+i) (T+i) T T* *(F+i)(F+i) T T* *(i+i)(i+i) F F* *(i+i)(i+i) i i* *(i+i)(i+i) 第15页/共85页 8.8. 令文法为 E T|E+T|E-TE T|E+T|E-T T F|TT F|T* *F|T/FF|T/F F (E)|i F (E)|iEE - TE -

10、 TTF F iF iii-i-i i-i-i 的语法树(2) 给出 i+i+i、i+i*i和i-i-i的语法树。EE + TE + TTF F iF iii+i+i i+i+i 的语法树i+ii+i* *i i 的语法树EE + TTTF F iF ii*n注意：树枝和符号均不可随意增减！第16页/共85页179、证明文法、证明文法: S iSeS | iS | i 是二义的。是二义的。二义性的含义二义性的含义: :如果文法存在如果文法存在某个句子某个句子对应两棵以上对应两棵以上不同的语法树，或者两种以上不同的最不同的语法树，或者两种以上不同的最左左/ /右推导，则称这个文法是二义的。右推导

11、，则称这个文法是二义的。首先：找到此文法对应的一个首先：找到此文法对应的一个句子句子 iiiei其次：构造与之对应的其次：构造与之对应的两棵两棵语法树语法树S i S e S i S i i S i S i S e S i i结论：因为该文法存在句子结论：因为该文法存在句子iiieiiiiei对应两棵对应两棵 不同的语法树，因而该文法是二义的。不同的语法树，因而该文法是二义的。第17页/共85页1810. 把下面文法改写成无二义性的文法 S-SS | (S) | ( ) 解答： S- TS | T T-(S) | ( )第18页/共85页19L2=aibncn| n1,i0G2(S): SAB

12、 AaA| BbBc|bcL3=anbnambm| m,n0G3(S): SAB AaAb| BaBb|11、给出下面语言的相应文法、给出下面语言的相应文法第19页/共85页20L4=1n 0m 1m 0n| n,m0可以看成是两部分：可以看成是两部分：剩下两边的部分就是：剩下两边的部分就是：S 1S0中间部分是中间部分是 0m 1m ：A 0A1 | 所以所以G4S可以写为：可以写为： S 1S0 | A A 0A1 | A第20页/共85页21例题与习题例题与习题解答解答第三章第三章第21页/共85页221. 假定NFA M=，我们对M的状态转换图进行以下改造： 1) 引进新的初态结点X和

13、终态结点Y，X,Y S， 从X到S0中任意状态结点连一条 箭弧， 从F中任意状态结点连一条 箭弧到Y。 2) 对M的状态转换图进一步施行替换，其中k是新引入的状态。非确定有限自动机状态图的改造第22页/共85页23代之为ikABjijAB代之为ijA|BijBA代之为ijA*ik jA按下面的三条规则对V进行分裂:n逐步把这个图转变为每条弧只标记为 上的一个字符或 ，最后得到一个NFA M，显然L(M)=L(M)第23页/共85页24确定有限自动机的确定化采用子集法设I是M的状态集的一个子集，定义I的 -闭包 -closure(I)为: i) 若s I，则s-closure(I)； ii) 若

14、s I，则从s出发经过任意条 弧而能到达的任何状态s都属于 -closure(I) 即： -closure(I)=I s|从某个s I出发经过任意条 弧能到达s第24页/共85页25 设a是 中的一个字符，定义Ia= -closure(J) 其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。n把确定化的过程: : 不失一般性，设字母表只包含两个a a和b b，我们构造一张表: :IIaIb -Closure(X)第25页/共85页26 对一个DFA M最少化的基本思想: 把M的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的。最后，让

15、每个子集选出一个代表，同时消去其他状态。DFA M最少化第26页/共85页27 具体做法: 对M的状态集进行划分 首先，把S划分为终态和非终态两个子集，形成基本划分 。 假定到某个时候， 已含m个子集，记为 =I(1)，I(2)，I(m)，检查 中的每个子集看是否能进一步划分: 对某个I(i)，令I(i)=s1,s2, ,sk，若存在一个输入字符a使得Ia(i) 不会包含在现行 的某个子集I( j)中，则至少应把I(i)分为两个部分。第27页/共85页28 例如，假定状态s1和s2经a弧分别到达t1和t2，而t1和t2属于现行 中的两个不同子集，说明有一个字 ， t1读出 后到达终态，而t2读

16、出 后不能到达终态，或者反之，那么对于字a ， s1读出a 后到达终态，而s2读出a 不能到达终态，或者反之，所以s1和s2不等价。s1t1as2t2a i j第28页/共85页29例题3.1 给出下面描述的正规表达式 以01结尾的二进制数串 能被5正除的十进制整数 包含奇数个1或者奇数个0的二进制数串第29页/共85页30例题3.2 构造下面正规式相应的DFA 1(0|1)*101步骤步骤: :. .根据正规式根据正规式画出画出对应的对应的状态转换图状态转换图; ;. .根据状态转换图画出对应的根据状态转换图画出对应的状态转换矩阵状态转换矩阵; ;. .根据状态转换矩阵得到根据状态转换矩阵得

17、到重命名后的状态转换矩阵重命名后的状态转换矩阵; ;. .根据重命名后的状态转换矩阵得出最后的根据重命名后的状态转换矩阵得出最后的DFA. .第30页/共85页311(0|1)*101.状态转换图状态转换图 abadb1(0|1)*101a1(0|1)*101dcef101101ggg第31页/共85页32.状态转换矩阵状态转换矩阵II0I1ab,c,db,c,dc,dc,d,ec,dc,dc,d,ec,d,ec,d,fc,d,ec,d,fc,dc,d,e,gc,d,e,gc,d,fc,d,e1abdcef10101g第32页/共85页33II0I1ab,c,db,c,dc,dc,d,ec,d

18、c,dc,d,ec,d,ec,d,fc,d,ec,d,fc,dc,d,e,gc,d,e,gc,d,fc,d,e. .重命名后的状态转换矩阵重命名后的状态转换矩阵S01A(始态始态)BBCDCCDDEDECF(终态终态)F(终态终态)EDAB10C1D010E10101F.DFA第33页/共85页34例题3.3 设M=(x,y, a,b, f, x, y)，其中f定义如下： f(x,a)=x, y f(x,b)=y f(y,a)= f(y,b)=x,y 请构造对应的确定有限自动机。第34页/共85页35【解答】 对照自动机的定义，由f的定义可知f(x,a)、f(y,b)均为多值函数，因此M是一非

19、确定有限自动机。 先画出NFA M相应的状态图，第35页/共85页36用子集法构造状态转换矩阵IIaIbxx, yyy-x, yx, yx, yx, y第36页/共85页37重命名后的状态转换矩阵Sab0211-2222第37页/共85页38第38页/共85页391(1010*|1(010)*1)*0abdc10e0101fghi01110jklmn.状态转换图状态转换图 nP64-P64-7. 7. 构造下列正规式相应的DFADFA。 第39页/共85页40.状态转换矩阵状态转换矩阵II 0I 101,2,31,2,345,9,10,115,9,10,116,122,36,122,3,7,8

20、,132,345,9,10,112,3,7,8,132,3,4,8,10,115,9,10,112,3,4,8,10,112,3,4,8,122,3,5,9,10,112,3,4,8,122,3,4,85,9,10,11,132,3,5,9,10,114,6,122,3,5,9,10,112,3,4,82,3,4,85,9,10,115,9,10,11,136,10,11,122,34,6,122,3,7,8,136,10,11,12122,3,7,8,1312131310,1110,11122,3第40页/共85页41. .重命名后的状态转换矩阵重命名后的状态转换矩阵II 0I 112234

21、456576347848910911121013101111412146137141571516161717156.DFA第41页/共85页428、给出下面正规表达式、给出下面正规表达式（4）英文字母组成的所有符号串，要求符号串中的）英文字母组成的所有符号串，要求符号串中的 字母按字典序排列。字母按字典序排列。(A | a)* (B | b)* (C | c)* (Z | z)*（5）没有重复出现的数字的数字符号串的全体。）没有重复出现的数字的数字符号串的全体。令 ri = i | , i=0,1,2,.,9 R0|R1|R2|.|R9记为 P(0,1,2.,9)表示0,1,2.,9的全排列

22、(01,2,.,9)iiR0190 19.(01,2,.,9).iiii iiPr rr第42页/共85页43（6）最多有一个重复出现的数字的数字符号串全体）最多有一个重复出现的数字的数字符号串全体0190 19(01,2,.,9).(01,2,.,9).iiiiii iiPrr rr(7) 不包含子串abb 的由a和b组成的符号串的全体b*(a|ab)*第43页/共85页4412、将图、将图3.18的的(a)和和(b)分别确定化和最少化。分别确定化和最少化。(a)aaa,b10.状态转换矩阵状态转换矩阵 I Ia Ib 00,1110,10,110. .重命名后的状态转换矩阵重命名后的状态转

23、换矩阵 I Ia Ib 012211200a2baba.DFA.最小化最小化0=(0,1,2)10,1a=10,1b=2因此，不能再分因此，不能再分02baa第44页/共85页45023145aaaabbbbbbaa(b)这道题实质上已经是确定化了的，所以我们只需最小化这道题实质上已经是确定化了的，所以我们只需最小化 ：2，3，4，5 0，1 2，3，4，5a=0，1，3，5 分属两区，所以分为分属两区，所以分为2，4 3，5 0，1a=1 0，1b=2，4 所以所以 0，1等价等价2，4a=0，1 2，4b=3，5 所以所以2，4等价等价 3，5a=3，5 3，5b=2，4 所以所以3，5等

24、价等价所以分为所以分为 0，1 2，4 3，5 023aabbba第45页/共85页46P64-P64-1414. . 构造一个DFADFA，它接受0,10,1上所有满足如下条件的字符串：每个1 1都有0 0直接跟在右边。 思路：先写出满足条件的正规式，由正规式构造NFA，再把NFA确定化和最小化。第46页/共85页47 (1)先写出满足条件的正规式正规式: (10|0)* (2) NFA: 确定化:YX1001201001012 I I0 I1X,1,Y 1,Y2 1,Y1,Y2 21,Y I I0 I1初终0 1 2 终 1 1 2 2 1 DFA:第47页/共85页4801001012D

25、FA:10010DFA:(最简化)第48页/共85页49例题与习题例题与习题解答解答第四章第四章第49页/共85页50源程序单词符号取下一单词.语法分析树词法分析器语法分析器符号表编译程序后续部分语法分析器在编译程序中的地位第50页/共85页51自上而下分析法(Top-down)(Top-down) 基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找 匹配 的推导推导。 递归下降分析法：对每一语法变量( (非终结符) )构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。 预测分析程序F优点：直观、简单和宜于手工实现。第51页/共85

26、页52 困难和难点: : 分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。 出错时，不得不“回溯”。 文法左递归问题。一个文法是含有左递归的，如果存在非终结符P P 含有左递归的文法将使自上而下的分析陷入无限循环。PP第52页/共85页53左递归的消除 直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为PP | 其中 不以P开头。 我们可以把P的规则等价地改写为如下的非直接左递归形式：P P P P | 左递归变右递归第53页/共85页54 间接左递归例如文法G(S):SQc|cQRb|bRSa|a虽没有直接左递归，但S、Q、R都是左递归的SQcRbcSabc

27、潜在左递归 即形如：N-N 而 第54页/共85页55消除左递归的算法:1. 把文法G的所有非终结符按任一种顺序排列成P1，P2，Pn；按此顺序执行；2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 将Pj代入Pi的产生式（若可代入的话） 消除关于Pi规则的直接左递归性 END3. 化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。第55页/共85页56消除回溯、提左因子 为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无

28、疑的。第56页/共85页57 令G是一个不含左递归的文法，对G的所有非终结符的每个候选 定义它的终结首符集FIRST( )为：.,|=)(*TVaaaFIRST 特别是，若 ，则规定FIRST( )。*n如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选 i和 jFIRST( i)FIRST( j) 当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含a的 。第57页/共85页58 如何把一个文法改造成任何非终结符的所有侯选式的首符集两两不相交？ 提取公共左因子: 假定关于A的规则是 A 1 | 2 | | n

29、 | 1 | 2 | | m (其中，每个 不以 开头) 那么，可以把这些规则改写成A A | 1 | 2 | | m A 1 | 2 | | n 经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。第58页/共85页59n构造不带回溯的自上而下分析的文法条件1. 文法不含左递归，2. 对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若A 1| 2| n 则 FIRST( i)FIRST( j) (i j)3. 对文法中的每个非终结符A，若它存在某个候选首符集包含 ，则FIRST( i)FOLLOW(A)= i=1,2,.,n如果一个文法

30、G满足以上条件，则称该文法G为LL(1)LL(1)文法文法。LL(1)文法第59页/共85页60 假定S是文法G的开始符号，对于G的任何非终结符A，我们定义.,.|)(*TVaAaSaAFOLLOWAS*特别是，若 ，则规定 FOLLOW(A)FOLLOW提醒：要掌握构造First和Follow集合的方法第60页/共85页61递归下降分析程序构造 在不含左递归和每个非终结符的所有候选式的终结首符集都两两不相交条件下，构造一个不带回溯的自上而下分析程序，该分析程序由一组递归过程组成，每个过程对应文法的一个非终结符。 这样的一个分析程序称为递归下降分析器。第61页/共85页62预测分析程序 使用一

31、张分析表和一个栈同样可实现递归下降分析，用这种方法实现的语法分析程序叫预测分析程序 a 总控程序预测分析表MX#输 出栈输入串第62页/共85页63分析表MA，a的构造q构造FIRST( )和FOLLOW(A)q构造分析表MA，a第63页/共85页64 在对文法G的每个非终结符A及其任意候选 都构造出FIRST( )和FOLLOW(A)之后，现在可以用它们来构造G的分析表MA，a。1. 对文法G的每个产生式A 执行第2步和第3步；2. 对每个终结符a FIRST( )，把A 加至MA，a中；3. 若FIRST( )，则对任何b FOLLOW(A)把A 加至MA，b中。4. 把所有无定义的MA，

32、a标上“出错标志”。第64页/共85页65q总控程序根据现行栈顶符号X和当前输入符号a，执行下列三种动作之一:1. 若Xa，则宣布分析成功，停止分析。2. 若Xa ，则把X从STACK栈顶逐出，让a指向下一个输入符号。第65页/共85页663. 若X是一个非终结符，则查看分析表M。 若MX，a中存放着关于X的一个产生式，把X逐出STACK栈顶，把产生式的右部符号串按反序一一推进STACK栈(若右部符号为 ，则意味不推什么东西进栈)。若MX，a中存放着“出错标志”，则调用出错诊察程序ERROR。如：如：MXMX，a=Xa=XUVWUVW, ,就用就用WVUWVU（U U在顶）在顶）替换栈顶的替换

33、栈顶的X X作为输出；作为输出；如：如：MXMX，a=errora=error，则调用，则调用errorerror程序。程序。第66页/共85页67 1.考虑下面文法G1: Sa|(T) TT，S|S (1) 消去G1的左递归。然后对每个非终结符,写出不带回溯的递归子程序。n解解(1) 消左后的文法消左后的文法G1: Sa|(T) TST T ,ST|练习解答第67页/共85页n解(1) 不带回溯的递归子程序: Sa|(T) Procedure S; Begin if sym=a or sym= then advance else if sym=( then begin advance; T;

34、 if sym=) then advance else error end else error End;第68页/共85页n解(1) 不带回溯的递归子程序: nTST Procedure T; Begin S; T; end; n解(1) 不带回溯的递归子程序: nT,ST| procedure T; begin if sym=, then begin advance; S; T; end End;第69页/共85页(2) 经改写后的文法是否是LL(1)的? 给出它的预测分析表。消左后的文法G1 : Sa|(T) TST T ,ST|因为G1 : 文法不含左递归; 对 Sa|(T) FIRS

35、T(a)=a, FIRST()=, FIRST( (T) )= ( , 集合互不相交且不含; 对 T,ST| FIRST( ,ST )= , , FIRST()=, 其交集为空。 但FIRST(T)=FIRST( ,ST ) FIRST()=，, 然而，FOLLOW(T)= ) FIRST(T)=，, ，两者 不相交。 所以，G1是LL(1)文法。 第70页/共85页71构造G1的预测分析表: 对Sa|(T) 对TST FIRST(a)=a FIRST(ST)=a,( FIRST()= 对 T,ST| FIRST(T)=( FIRST(,ST)=, FOLLOW(T)=) a ( ) , #

36、SSaSS(T) TTSTTSTTST TTT ,ST第71页/共85页722、对下面的文法G：ETEEE TFTTT FPFF*F P(E)ab（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。（2）证明这个文法是LL（1）的。（3）构造它的预测分析表。（4）构造它的递归下降分析程序。第72页/共85页73解：（1）计算FIRST与FOLLOW集FIRST(P)= ( , a , b , FIRST(F)= * , FIRST(F)=FIRST(P) = ( , a , b , FIRST(T)=FIRST(T) = ( , a , b , , FIRST(T)=FIRST(F

37、) = ( , a , b , FIRST(E)= + , FIRST(E)=FIRST(T)= ( , a , b , FOLLOW(E)= ) , # FOLLOW(E)=FOLLOW(E)= ) , # FOLLOW(T)=FIRST(E) FOLLOW(E)=+, ) , # FOLLOW(T)=FOLLOW(T)=+, ) , # FOLLOW(F)=FIRST(T) FOLLOW(T)= (,a,b, , +, ) , # FOLLOW(F)=FOLLOW(F)=(, a , b , , +, ) , # FOLLOW(P)=FIRST(F) FOLLOW(F)=*,( ,a, b

38、 ,+ , ) ,# ETEEE TFTTT FPFF*F P(E)ab第73页/共85页74FIRSTFOLLOWE( , a , b , ) , #E+ , ) , #T( , a , b , +, ) , #T( , a , b , , +, ) , #F( , a , b , (, a , b , , +, ) , #F* , (, a , b , , +, ) , #P) , a , b , *,(, a , b , , +, ) , #第74页/共85页75（2）证明这个文法是）证明这个文法是LL（1）的）的。i.对产生式对产生式P(E)ab，有，有FIRST(E) FISRT(a

39、) FIRST(b) FIRST()= ii. 对产生式对产生式EE FIRST(+E) FOLLOW(E)= + ) , # = 对产生式对产生式TT FIRST(T) FOLLOW(T)= ( , a , b , +, ) , # = 对产生式对产生式F*F FIRST（*F) FOLLOW(F)= * (, a , b , , +, ) , # = iii. 文法不含左递归。文法不含左递归。综上综上 i,ii,iii 可知，文法可知，文法G是是LL（1）的。）的。ETEEE TFTTT FPFF*F P(E)ab第75页/共85页76（3）构造预测分析表。）构造预测分析表。（ab)+*#ETE TE TE TEE+ETFT FT FT