《编译原理考试要点.docx》由会员分享，可在线阅读，更多相关《编译原理考试要点.docx（40页珍藏版）》请在三一文库上搜索。
1、编译程序是对高级语言程序进行翻译在规范规约中，用句柄来刻画可规约串动态存储分配是指在运行阶段为源程序的数据对象分配存储空间 词法分析的输出结果是单词的种别编码和自身值正规式等价是指所识别的语言集相等优化可生成运行时间短且占内存少的代码程序【一】文法和语言编译程序和翻译程序的区别编译程序是整体编译完了，生成目标代码，再一次性执行。解释程序是一边解释，一边执行，并不形成目标程序。文法。文法G:定义为四元组(VN,VT,P,S)P为产生式的集合，S为开始符号，文法是描述语言的语法结构的形式规则(即语法规则)VN为非终结符号的集合，VT为终结符号的集合，是一个非终结符，至少要在一条规则中作为左部出现。
2、一个文法，S是它的开始符号。如果 阳*(表示从S出发，经0步或若干步可 a是一个句型。文法分类0型文法1型文法2型文法3型文法 句型假定G是 推出a),则称 句子短语文法上下文有关文法上下文无关文法 正规文法递归可枚举语言 上下文有关语言 上下文无关语言 正规语言仅含终结符号的句型是一个句子。语言由文法G生成的语言记为L(G),它是文法G的一切句子的集合所有的句子都是规范句型所有的句型不一定是规范句型推导直接推导规约直接规约直接推导：仅当A 丫是一个产生式，有V = a A 3 , W= ay 3,aA3= a y 3, 称V直接推导到 W,记作V = W,也称W直接归约到V。最左推导又称为规
3、范推导。G: Sf0S1, S一 01 0S1 =00S11 00S11 =000S111 000S111 =00001111 S n 0S1语法树语法树的根结由开始符号所标记。随着推导的展开，当某个非终结符被它的某个候选式所替换时，这个非终结符的相应结就产生了下一代新结。每个新结和其父亲结间都有一条连线。在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结自左至右排列起来就是一个句型。二义文法如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。也就是说，若一个文法存在某个句子，它有两个不同的最左（最右）推导，则这个文法是法是二义的。文法的二义性证明：找出一个句子，它有两
4、个不同的最左推导或最右推导题型：给出上下文无关文法句型，写出最左或最右推导过程E - E+E|E*E|(E)| i ,关于(i*i+i)的推导E =(E) = (E*E) = (i*E) = (i*E+E)=(i*i+E) = (i*i+i)E= (E)= (E+E) = (E*E+E) = (i*E+E)=(i*i+E) = (i*i+i)判断输入串是不是文法的句子例：文法G: S 一 cAdA 一 abA 一 a识别输入串w=cabd是否为该文法的句子规约过程构造的推导:cAd n cabd S = cAd短语语法树中一棵子树的所有叶子从左向右排列起来形成一个相对于子树根的短语。直接短语只
5、有父子两代的短语为直接短语。句柄一个句型的分析树中，最左边的只有父子两代的子树的叶子从左向右排列起来形成构成此句 型的句柄。已知一上下文无关文法，对给定的句型，画出语法树，并求其短语，直接短语以及句柄。 例：对于文法GSSf ( L) | aS |aL 一 L, S | S画出句型(S ,(a)的语法树，求某一句型的短语，直接短语，句柄.S( L短语：(S ,(a); S ,(a) ; (a) ; a; S直接短语：S; a句柄：S已知语后写出描述该语百的文法试构造生成语言 L=a nbnci |n >1, i > 0的文法分析：anbnci可以进行分解让 A生成anbn,B生成c
6、i符号串anbnci是AB连接后的结果。n>1所以A-aAb|ab , i >0所以B->cB| £也 可写成B->Bc| £。解：S-> AB A- > aAb|ab B->cB| £ 已知文法写出该文法所生成的语言.已知文法 GA=(A,a,b,A>bA|a,A)所生成的语言是什么？bna|n>=01、语言和文法的相互转换1)已知文法写出该文法所生成的语言：语言是有穷集：通过从开始符号的推导出所有的句子，所有句子的集合即为所求的语 言语言是无穷集：通过从开始符号的推导出几个的句子，总结句子的特点，将特点描述
7、 出来。例如 G: S - 0S1, S 01S = 01 S= 0S1 = 0011 S = 0S1 = 00S11=>000111 语言为01个数相等，并且0在前，1在后L (G) =0n1n|n>=1 2)已知语言写出描述该语言的文法一般所写的文法是上下文无关文法和正规文法，用集合的形式表示语言若是这一类的题目先记住几个基本的情况，若是复杂的都可以分解成基本的情况。 一般给定集合是无限集，文法都应是递归文法，可以是直接递归也可以是间接递归。 基本的有：i an若生成多个a,用递归文法表示则为：A->aA,递归有结束的时候，结束的写法看 n的值：若n为0,即有0个a,即为
8、£ , A-> £若n为1,即有1个a,即为a, A-> a若n为2,即有2个a,即为aa, A-> aaiianbn生成n个a, n个b且a在b之前，则每一次推导都要产生一个a和一个b,才能保证ab的个数相等，若用A作为非终结符，右部A不能在ab之前A->Aab,或在ab之后A->abA, 这样生成的符号串就是 abab，所以只能在ab之间。所以为：A->aAb,然后看n的值：若n 为0,即有0个ab,即为e , A-> e若n为1,即有1个a,一个b,即为ab, A-> ab iii rrt若r是a,b* , rt是r的逆
9、，第一位和最后一位相同，第二位和倒数第二位相同，。 所以先生成第一个和最后一个，然后依次生成第二位和倒数第二位。因为第一位和最后一位相同，同为 a或同为b, A->aAa|bAb，这样能保证从后部分是前部分的逆。递归结束看 J和r之间的符号，在这里没有为 £ ,所以为A-> £ ;若改为rar, J和r之间为a,即为 A-> a其余的情况可分解成以上三种情形。例1:试构造生成语言L=a nbnci |n >1, i>0的文法分析：anbnci可以进行分解让 A生成anbn, B生成ci符号串anbnci是AB连接后的结果。nR1 所以 A-&g
10、t; aAb|ab , i R0 所以 B->cB| £ 也可写成 B->Bc| £ 。解：S-> AB A- > aAb|ab B->cB| £例2：已知语言L=anbbn| n > 1,写出产生L的文法。分析：先生成anbn,当n=1符号串为：abb解： S- aSb|abb例3:请给出描述语言=a2m+1 b m+1 | m>=0 Ua2m b m+2 m>=0的文法分析：a2m+1 b m+1可以看成aa2mb mb,而a2m b m可以用A->aaAb生成，a2mb m+2可以看成a2m b mbb,
11、而a2m b m也可以用A->aaAb生成，若m=0, a2m b m为空串所以为A-> e ,aa2m b mb 是 aAb, a 2mb mbb 是 Abb；解:s->aAb|AbbA->aaAb| e例4：已知语言L=x | x C a,b,c*, 且x重复排列是对称的(aabcbaa,aabbaa,等) 写出 该语言的文法。分析：若符号串的长度为偶数，则后半部分是前半部分的逆，所以为 S->aSa|bSb|cSc| £若符号串的长度为奇数， 则除中间的外， 中间字符的后半部分是中间字符前半部分的逆，而中间的字符可以为 a ， b， c 所以文法为
12、： S->aSa|bSb|cSc|a|b|c解：S->aSa|bSb|cSc|a|b|c| £ 用自然语言描述语言这种情况一般常根据经验来构造文法。例：写一个文法，使其语言是奇数集，且每个奇数不以 0 开头。N->A|MAM->B|MDA->1|3|5|7|9B->1|2|3|4|5|6|7|8|9D->0|B1 .已知文法 GA=(A,a,b,A >bA|a,A) 所生成的语言是什么？b na|n>=02 . 写一文法，使其语言是偶正整数的集合。 要求：(1) 允许 0 打头；(2) 不允许 0 打头。答 ： (1) 允许 0
13、开头的偶正整数集合的文法NT|D» NT|DN D|1|3|5|7|9D 0|2|4|6|8(2)不允许0开头的偶正整数集合的文法NT|DTf FT|GN D|1|3|5|7|9D 2|4|6|8Ff N|0G D|0(3) 出生成下述语言的上下文无关文法：(1) a nbnambm| n , m>=0(2) 1 n0m 1 m0n| n , m>=0a 2n+1|n>=0(4) a 2n+1bnci|n>0,i>=0答：(1)SfAAAaAb| e(2) 腔 1S0|AAT 0A1| £(3) S -aaS|a(4) 般 aABaaAb|aa
14、b屋cB| £4.已知语言L=x | x C a,b,c*, 且x重复排列是对称的(aabcbaa,aabbaa,等)写出该语 言的文法。般 aSa|bSb|cSc|a|b|c|e1:证明下述文法 GE是二义的。a|(E)|EOEO+| -|*|/答：可为句子a+a*a构造两个不同的最右推导：最右推导 1 E- EOE - EOa - E* a - EOE* a - EOa * a -E+ a * a - a + a * a最右推导 2 E- EOE-EOEOE; EOEO a。EOE * a - EOa * a - E+ a * a - a + a * a2:令文法GE为:T|E+
15、T|E -TT- F|T*F|T/FF- (E)|i1:试构造生成语言L=a nbnci |n >1, i > 0的文法解：S-> AB A- > aAb|ab B->cB| £2：已知语言L=anbbn| n >1,写出产生L的文法。解：S-> aSb|abb3:已知文法 G=(A,B,C,a,b,c,A,P)其中产生式P由以下组成：A 一 abc A 一 aBbcBb 一 bBBc一 CbccbC一 CbaC一 aaBaC 一 aa问：此文法表式的语言是什么？解：该题通过推导到的句子的特点进行总结,语言为：a nbncn|n>=14
16、 请给出描述语言=a2m+1 b m+1 | m>=0 U a2m b m+2 m>=0的文法解:s->aAb|Abb A->aaAb| e5已知文法GS为：S 一 dABA 一 aA|aB - Bb |GS产生的语言是什么？GS能否改写为等价的正则文法？解：语言为:da nbn|m>0,n>=0可改写为正规文法：S->dA A->aB B->aB|bD| £ D->bD| £6:试写一文法，使其描述的语言 L(G)是能被5整除的整数集合。解:S->D|AD|ABDD->0|5A->1|2|3|4
17、|5|6|7|8|9B->0|A|0B|AB7：已知语言L=x | x C a,b,c*, 且x重复排列是对称的(aabcbaa,aabbaa,等) 写出该语言的文法。解：S->aSa|bSb|cSc|a|b|c| £2、已知一上下文无关文法，对给定的句型，画出语法树，并求其所有的短语，直接 短语以及句柄。1)已知一上下文无关文法，构造语法树语法树是对推导过程中的形象描述。若用产生式：A-> “推导，对应的树中， A是双亲结点，a中的符号是孩子结点。 一般根据推导过程可以画出语法树。注意，推导过程有最左推导、最右推导和既不是最左也不是最右推导。注意：语法树的叶子结点
18、不一定是终结符号例：对于文法GSSf ( L) | aS |aL 一 L, S | S画出句型(S ,(a) 的语法树Sz w( L)/I 、L， SSa2)求某一句型的短语，直接短语， 句柄 .短语： ( S ,(a)； S ,(a) ； (a) ； a ； S直接短语： S； a句柄： S用语法树理解某一句型的短语， 直接短语， 句柄语法树中一棵子树的所有叶子从左向右排列起来形成一个相对于子树根的短语。只有父子两代的短语为直接短语。一个句型的分析树中， 最左边的只有父子两代的子树的叶子从左向右排列起来形成构成此句型的句柄。所以短语的求法 ：根据语法树中的非终端结点来查找短语；每一个非终端结
19、点为根的子树上的叶子结点从左往右排列起来即是短语。若某个非终端结点的所有的孩子结点都是叶子结点，该非终端结点为根的子树上的叶子结点从左往右排列起来即是直接短语，也就是所有的孩子结点排列起来即是直接短语。句柄：最左直接短语写出句型 ( S ,(a) 的所有短语， 直接短语， 句柄 .根据该句型的语法树，可以知道有六个非终端结点，对语法树从上到下, 从左往右看非终端结点：以 S 为根的子树上的叶子结点排列起来为： ( S ,(a) ；以 L 为根的子树上的叶子结点排列起来为：S ,(a);以L为根的子树上的叶子结点排列起来为：S;以S为根的子树上的叶子结点排列起来为： (a) ； 以 L 为根的子
20、树上的叶子结点排列起来为： a ；以 S 为根的 子树上的叶子结点排列起来为：a;后两个非终端结点对应相同的叶子结点，所以写成一个短语，所以短语有五个：所有短语： ( S ,(a)； S ,(a) ； (a) ； a； S第三层上的L 和第五层上的S 的所有孩子都是叶子， 所以所对应的叶子排列起来是直接短语直接短语：S； a句柄： S证明E+T*F 的语法树，指出这个句型的所有短语、直接短语和句柄。答E+T*F 的语法树：短语有：E+T*F,T*F直接短语有：T*F句柄为：T*F3:已知文法 G:S->(AS)|(b)A -(SaA)|(a)试画出句型(A(SaA)(b)的语法树，指出该
21、句型的所有短语、直接短语和句柄(8分)(S a A ) ( b )短语：(SaA)、(b )、(SaA)(b)、 (A(SaA)(b)直接短语：(SaA)、 (b )句柄(SaA)【二】词法分析 正规式: 正规文法：任一产生式 & 一 3的形式都为：A - aB或A-a正规集：,1道和中都是工上的正规式,设字母表为工，辅助字母表，缸 它们所表示的正规集分别为 8和小；令1=a, b,工上的正规式和相应的正规集的例子有:正规式正规集aaa I ba,babab(a I b)(a lb) aa,ab,ba,bba * %a,a,任意个a串DFA一个确定的有穷自动机(DFA) M是一个五元组
22、：M= (K, 2 , f, S, Z)其中1.K是一个有穷集，它的每个元素称为一个状态；2N是一个有穷字母表，它的每个元素称为一个输入符号，所以也称2为输入符号表；3.f是状态转换函数，是在 KX 2 -K上的映射.如 f (ki, a) =kj , (ki C K, kj C K)意味着，当前状态为 ki,输入符为a时，将转换为下一个状态kj,我们把kj称作ki的一个后继状态；4.SC K是唯一的一个初态；5.ZU K是一个终态集，终态也称可接受状态或结束状态。NFA一个不确定的有穷自动机( NFA) M是一个五元组：M= (K, 2 , f, S, Z)其中1.K是一个有穷非空集，它的每
23、个元素称为一个状态；2N是一个有穷字母表，它的每个元素称为一个输入符号，所以也称2为输入符号表;3.f是状态转换函数，是在 KX 2*一2K上的映射.4.S K是初始状态集5.Z K 是一一个终态集NFA到DFA的确定化过程子集法1:NFA确定化和DFA最小化确定化：采用的子集法。1) DFA的初态为：NFA的初态集的 closure ,即为£ -closure (S) S为NFA的 初态集2)从£ -closure (S)开始将所有求出的子集均接受2上的符号，求出所到达的集合，直到子集不在增大为止。3)确定终态：若子集中含有NFA的终态，该子集为 DFA的终态从图中可以得
24、到：NFA的初态为i终态为f e -closure (i ) =i , 1, 2状态集合I的e-闭包，表示为e -closure(I),除了包括自身之外，还包括状态集I中的任何状态 S经任意条£弧而能到达的状态的集合。S -closure (i)要包括自身中的状态i ,和i经过任意条£弧到达的状态，可以到 1和2,所以e -closure(i ) =i , 1,21, 2DFA的初态为：NFA的初态集的一闭包，所以为i ,IaIbi,1,2S1,2,3A1,2,4B1,2,3A1,2,3,5,6,f C1,2,4B1,2,4B1,2,3A1,2,4,5,6,f D1,2,3
25、,5,6,f C1,2,3,5,6,f C1,2,4,6,fE1,2,4,5,6,f D1,2,3,6,fF1,2,4,5,6,f D1,2,4,6,f E1,2,3,6,fF1,2,4,5,6,fDi1,2,3,6,fF1,2,3,5,6,f C1,2,4,6,fE确定化的过程从i, 1, 2开始，接受a是：i接受a到达的集合是空集1接受a到达的集合是12接受a到达的集合是3 U1 U 3=1 , 3,然后求1 , 3的 e -闭包，e -closure(1 , 3)=1 , 3, 2 所以i , 1, 2接受a到达的集合是1 , 3, 2。用数学的形式表示为：1,2, 3= &cl
26、osure(move(i,1,2,a)状态集合I的a弧转换，表示为 move(I,a)定义为状态集合 J,其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。i , 1, 2接受b到达的集合是1 , 2, 4。1,2,3和1 , 2, 4是新增加的子集，然后在对 1 , 2, 3和1 , 2 , 4再分别接受a和b,重复做直到所出现的所有集合都接受了a和bo如上表所示。终态的确定：NFA的终态为f,上面所出现的集合只要有f的即为DFA的终态，1 , 2, 3, 5, 6,f1,2,4,5,6,f1,2,4,6,f1,2,3,6,f中者B含有 f 所以是终态。画出DFA的状态转换图
27、：最小化：采用的分割法完成：1 .将M的状态分成非终态和终态集2、寻找子集中不等价状态若一个集合的状态等价，则对于任何输入符号，该集合中的状态接受该符号后到达 的状态属于同一集合。否则不等价，把不在同一个集合的划分出去。例上图：先划分为终态集和非终态集S,A,B C,D,E,F对于集和C,D,E,F中的状态接受a到达的状态属于同一个集合，属于集和C,D,E,F,接受b到达的状态属于同一集合，所以 C,D,E,F是等价的。对于集和S,A,B , S接受a到达的状态为 A,属于S,A,B , A接受a到达的状态为C, 属于C,D,E,F , B接受a到达的状态为 A,属于S,A,B,所以A与S,
28、B是不等价的。将 A划分出去。划分的结果为：AS , B对于集和S, B接受a到达的状态均为 A,属于 A ;S接受b到达的状态为B,属于 S,B,B接受b到达的状态为 D,属于C,D,E,F,S , B接受b到达的状态属于不同集合， 所以S, B是不等价的。最终的划分为：S, ABC , D, E, F将等价的状态合并：ba a 、正规文法、正规式和 FA的等价问题2、FA和正规式、正规文法的转化1)正规文法转化为正规式：采用的是联立方程组：例如：文法 G网为：S->aA, S->a, A-> aA, A->dA, A->a, A->d联立方程组为：S=a
29、A+a(1)A=aA+dA+a+d(2)整理:A=(a+d)A+(a+d)A=(a+d)*(a+d)带入(1) S=a(a|d)*(a|d) |a=a(a|d)*注：产生式左部相同的写到一个方程中，所有的右部用+连接起来作为方程的右部。产生式左部作为方程的左部，S->aA, S->a,对应的方程为：S=aA+a方程的求解：若有方程 A=rA+t ,则该方程的解为：A=r*t2)正规式转化为正规文法：一般用分解法做，记住几个基本的情况：? 若x和y都是正规式，对 A->xy,重写成：A->xB, B->y;对形如A->x|y,重写成：A->x,A->
30、;y;对形如A->x* y,重写成：A->xA|y-不断使用如上规则，直到每个产生式最多含有一个终结符为止。例如：将R=a(a|d) *转换成正规文法分解的情况是：a与(a|d) *做连接，所以为：A->aB,B->(a|d) *(a|d) *相当于：(a|d) * £按第三种情况处理，所以为： B->(a|d)B| £ ,即为： B->aB |dB| £所以文法为：A->aB B->aB |dB| £3)正规文法转化为 FAa)字母表与G的终结符集相同。b)为G的每个非终结符生成 M的一个状态，G的开始符
31、号S是初态。c)增加一个新状态 Z,作为NFA的终态。d)对G中的形如A->tB的产生式，其中t为终结符或 & A和B为非终结符， 构造M的一个转换函数 f(A,t)=B;，即A到B有一条弧，弧上的标记为te) 对G中的形如 A->t的产生式，构造M的一个转换函数 f(A,t)=Z;即A到Z 有一条弧，弧上的标记为 t例如： GS:S->aA S->bB S-> A A-> aB A-> bA B-> aS B->bA B-> 6转化为的FA为：4） FA转化为正规文法：a）有穷自动机的初态对应文法的开始符号。b）有穷自动机的
32、字母表为文法的终结符集。c）对转换函数f（A,t）=B ,即A到B有一条弧，弧上的标记为t即可写一个产生式A->tB。d）对可接受状态 Z,增加一个产生式 Z->名例如：正规文法为：GA:A->aB A->bD B->bC C->aA C->bD C-> ； D->aB D->bDD-> ；5）正规式转化为 FA一般采用分解法完成，直到弧上只有一个输入符号或S为止形如xy,:C x . y <-形如x|y,二 x|y 二形如A->x* yX例：1(0|1)*101X结点，一个为Y结点，从X6) FA转化为正规式：第一
33、步，在 M的状态转换图上加进两个结点，一个为结点用名弧连接到M的所有初态结点，从M的所有终态结点用弧连接到Y结点,形成一个与M等价的M', M'只有一个初态和一个终态第二步，逐步消去 M'中的所有结点，直至只剩下 X和Y结点 其消结规则如下：1.对于Ri11 2)代之为:。智)2 .对于3 .对于代之为:代之为:Ri|R2* .R1R2 R31) Y最后X和Y结点间的弧上的标记则为所求的正规式例：请构造与正规式 R=(a*b) *ba(a|b) *等价的状态最少的DFA (确定有限自动机)根据正规式所构造的 NFA为:确定化ab1q011,21,2q111,2,31,2
34、,3q21,41,2,31,4q31,41,2,41,2, 4q41,41,2,3,41,2,3,4q51,41,2,3,4b b aa,b其中q3,q4,q5是终态最小化：将状态划分为终态集和非终态集q0.q1.q2q3, q4,q5输入 a f(q0,a)=q0 C q0,q1,q2 f(q1 , a) =q0 C q0,q1,q2f(q2,a尸q3C q3,q4,q5 q2 与q0,q1输入a到达的状态属于不同集合 所以进一步划分为：q0,q1q2f(q0,b)=q1 C q0,q1 f(q1 , b) =q2 q2,q0,q1 输入b到达的状态属于不同集合，进 一步划分为：q0q1f(
35、q3,a)=q2 q2 f(q4,a)=q2 q2 f(q5,a)=q2 q2输入 a 到达的状态属于相同集合；f(q3,b)=q4 6 q3,q4,q5f(q4,b尸q56 q3,q4,q5f(q5,b)=q5 6 q3,q4,q5 输入 b 到达的状态属于相同集合；q3,q4,q5是等价状态最终划分为：q0q1q2q3.q4,q5最小化的状态转换矩阵为：例.设字符集汇= a, b ,请写出不以a开头的但以aa结尾的字符串集合的正规表达式,并构造与之等价的状态最少的DFA正规式为：b(a|b)*aa根据正规式所构造的 NFA为：a,babq0q0q1q1q0q2q2q3q2q3q3q3q3是
36、终态确定化abxq011q11,211,2q2i,2,y11,2,yq3i,2,y1状态q3是终态最小化：将状态划分为终态集和非终态集q0.q1.q2q3输入 a f(q0,a尸 f(q1 , a) =q2 c q1,q2,q0f(q2,a)=q3 q3输入 a 到达的状态属于不同集合，所以进一步划分为：q0q1q2q3即abq0q1q1q2q1q2q3q1q3q3q1q0是初态，q3是终将图确定化:解：下表由子集法将 NFA转换为DFAiI 0 = &closure(MoveTo(I,0)I 1 = e-closure(MoveTo(I,1)ASBQ,VCQ,UBQ,VDV,ZCQ,
37、UCQ,UEVFQ,U,ZDV,ZGZGZEVGZFQ,U,ZDV,ZFQ,U,ZGZGZGZ00,1正规式到NFA到DFA构造下列正规式相应的(1) 1(0|1) * 101DFA0,1解：(1)1(0|1)101对应的NFA为0110,1卜表由子集法将NFA转换为DFAII 0 = -closure(MoveTo(I,0)I 1 = &closure(MoveTo(I,1)A0B1B1B1C1,2C1,2D1,3C1,2D1,3B1E1,4E1,4B1B1【三】语法分析语法分类自顶向下分析方法：确定的 递归子程序法 预测分析法不确定的带有回溯的分析方法自底向上分析方法 LR 分析法
38、LL LR(0) LR SLR LALR(1) 分析法第一个L表明自顶向下分析是从左到右扫描输入串第二个L表明分析过程中将用最左推导1表明只需向右看一个字符便可决定如何推导即选择哪个产生式LL(1)文法只有一部分文法属于LL(1)文法判断条件：first(ai) cfirst(aj) =*ai aj具有相同的左部，即 A ai|aj )A e , first(ai) c follw(A) =©First 集计算Follw集计算给定文法，求first 集follow 集构造预测分析表 已知文法GS:MH|a LSo| dML| eHfK|bLM判断G是否是LL (1)文法，如果是，构造
39、 LL (1)分析表。解：首先求各非终结符的FIRST集合：FIRST(S尸a U FIRST(M) U FIRST(H尸a U b,d, £ U e, £ =a,b,d,e,£ ;FIRST(H尸FIRST(L) U £ =e, £ ;FIRST(K)=d, £ ;FIRST(L)=e;FIRST(M尸FIRST(K) U b=b,d, e ;然后求非终结符的FOLLO膘合：FOLLOW(S)=o,#FOLLOW(H尸FOLLOW(S) f=f,o,#FOLLOW(K尸FOLLOW(M尸FIRST(H) FOLLOW(S尸e,o,#
40、;/不包含 £FOLLOW(L尸FIRST(S) U o U FOLLOW(K)J FIRST(M) U FOLLOW(M)=a,b,d,e,o,# U FOLLOW(M)=a,b,d,e,o,#;/ 不包含 £FOLLOW(M)=FIRST(L)U FIRST(H) U FOLLOW(S)=e,o,#/ 不包含 £文法GE的预测分析表如下：aodefb#SaMHMHMHMHMHH£LSo££K£dML££LeHf设有以下文法：GS: S 一eEfGh | gFSG | hF 一 SEc|cG |
41、3;G- Sh | e(1)求出该文法每一个非终结符的FOLLOW!。# h f c he gn r t jt tFolloW(S) Follow(E)FollOw(G) Follow(F) TirSt(S)First(G) First(E)i 1 IIIe g e g c根据关系图：Follow(S)=#,h,e,g,c,fFollow(E)=f,cFollow(G)=f,c,h,e,gFollow(F)=e,g(2)它是LL(1)文法吗?为什么？不是 FfSEc | cG |£ First(SEc)=e,g因为 F- e ,而 Follow(F)=e,gFirst(SEc) n
42、Follow(F)=e,g ,不为空集,所以不是LL(1)文法给出语言L=1na0n1ma0mn>0, m>=0的LL(1)文法GS并说明其理由。文法为：S-> AB A- > 1A0|1a0 B- > 1B0|a 提取公共左因子为：A-1A' A ' ->A0|a0改造后的文法为：S- > ABA- 1A'A ->A0|a08- > 1B0|a判断文法是LL (1)文法的充要条件是：对每一个非终结符的任何两个不同产生式A- > a | 3 ,则下述条件成立： FIRST ( a ) A FIRST ( 3 )
43、=* 若 3 => e ,则 FIRST ( a ) A FOLLOW A)=由于文法不存在形如 A-> £的产生式，所以无需求非终结符的FOLLOW!。FIRST (A) =FIRST (S) =1 FIRST (A' ) = FIRST (B) =1,a对非终结符A'和B有FIRST (A0) n FIRST (a0)=FIRST (1B0) n FIRST (a)=文法是LL(1)文法。该文法为LL(1)文法，因为左部相同，右部的符号串的First集为空集设有文法：GS:S一aBc|bABA一 aAb|bB一 b |e构造其LL(1)分析表，并分析符
44、号串baabbb是否是该文法的句子。First(S尸a,bFirst(A尸a,bFirst(B尸b,£ Follow(S)=#Follow(A尸b+first(B尸b,£ Follow(B尸c+follow(S尸c,#分析表为：abc#S一 aBc一 bABA一 aAb一 bB一 b££分析栈余留符号串产生式#Sbaabbb#S-> bAB#BAbbaabbb#BAaabbb#AaAb#BbAaaabbb#BbAabbb#AaAb#BbbAaabbb#BbbAbbb#A->b#Bbbbbbb#Bbbbb#Bbb#B#B, £#分析成功有文法GS:Sf BAZ BS | dBf a A | bS | cFirst(S尸first(B尸a,b,cFisrt(A尸fist(B)+(d尸