第三四章习题课编译原理讲课讲稿

第三(dìsān)、四章习题P64：7,8,9,12,14,15,20,补充(bǔchōng)题P81：1,2,3,4,5第一页，共65页。词法(cífǎ)分析正规(zhèngguī)式自动机正规(zhèngguī)文法①②③④⑤⑥正规式正规文法NFADFA状态最小

DFA词法

分析器分裂法转换规则子集法分划法2第二页，共65页。正规(zhèngguī)式与正规(zhèngguī)文法的转化②:令VT=∑对任意正规(zhèngguī)式R选择一个非终结符Z生成规则ZR，并令S＝Z；若a和b都是正规(zhèngguī)式，对形如Aab的规则转换成AaB和Bb；在已转换的文法中，将形如Aa*b的规则进一步转换成AaA|b；不断利用上上面后两条规则进行转换，直到每条规则最多含有一个终结符为止。①:将每个非终结符表示成关于它的正规式方程，获得一个联立方程组。依照求解(qiújiě)规则：若x=x|(或x=x+)，则解为x=*若x=x|(或x=x+)，则解为x=*以及正规式的分配率、交换率和结合率求关于文法开始符号的正规式方程组的解。3第三页，共65页。正规(zhèngguī)式转化为NFA(1/2)(1)引进初始结点X和终止(zhōngzhǐ)结点Y，把R表示成拓广转换图。如图XYR(2)分析R的语法结构，用如下规则对R中的每个基本符号(fúhào)构造NFA。R＝，构造NFA如图：R＝，构造NFA如图：XYXYR＝a(a)，构造NFA如图：XYa4第四页，共65页。正规(zhèngguī)式转化为NFA(2/2)若R是复合正规式，则按下图的转换规则对R进行分裂(fēnliè)和加进新结，直至每个边上只留下一个符号（或）为止。ABr1r2ABr1Cr2代换为ABr1|r2ABr1r2代换为ABr1*ABC代换为r1整个分裂过程中，所有(suǒyǒu)新结点均采用不同的名字，保留X，Y为全图唯一初态结点和终态结点5第五页，共65页。NFA确定(quèdìng)化为DFA首先将从初态S出发经过任意条弧所能到达的状态(zhuàngtài)所组成的集合作为M的初态S’，然后从S’出发，经过对输入符号a的状态(zhuàngtài)转移所能到达的状态(zhuàngtài)(包括读输入符号之前或之后所有可能的转移所能到达的状态(zhuàngtài))所组成的集合作为M的新状态(zhuàngtài)，如此重复，直到不再有新的状态(zhuàngtài)出现为止。从NFAN=(Q,,F,S,Z)构造(gòuzào)等价的DFAM=(Q’,,F’,S’,Z’)的方法6第六页，共65页。DFA的化简将DFAM的状态集Q分成两个子集：终态集F和非终态集F，形成初始分划。对建立新的分划new。对的每个状态子集G进行如下变换：把G分划成新的子集，使得G的两个状态s和t属于同一子集，当且仅当对任何输入符号(fúhào)a，状态s和t转换到的状态都属于的同一子集。用G分划出的所有新子集替换G，形成新的分划new。如果new＝，则执行第（4）步；否则令＝new，重复第（2）步。分划结束，对分划中的每个状态子集，选出一个状态作代表，而删去其它一切等价的状态，并把射向其余状态的箭弧都改为射向作为“代表”的状态。7第七页，共65页。增加新初态X，与所有原初(yuánchū)态用ε相连，

增加新终态Y，与所有原终态用ε相连，

从而构成一个新的FAM’，

它只有一个初态X和一个终态Y。在X与Y之间进行弧合并：ACBr1r2ABr1r2r2ACBr1r3ABr1r2ABr1|r2ABr1r2*r3在X和Y之间的表达式即为所求的正规(zhèngguī)式R。代之以代之以代之以自动机转化(zhuǎnhuà)为正规式8第八页，共65页。正规(zhèngguī)文法转化为自动机(1/2)设给定一个右线性正规文法G=(VN,VT,P,S)，则相应的有穷自动机M=(Q,,f,q0,Z)（1）将VN中的每一个非终结符视作M中的一个状态， 并增加(zēngjiā)一个新终态D，且DVN，

令Q=VN{D},Z={D},=VT,q0=S（2）对AaB（A,BVN,aVT{}），令f(A,a)=B。

构造弧（3）对Aa（AVN,aVT{}），令f(A,a)=D。

构造弧ABaADa9第九页，共65页。正规文法(wénfǎ)转化为自动机(2/2)设给定一个(yīɡè)左线性正规文法G=(VN,VT,P,S)，则相应的有穷自动机M=(Q,,f,q0,Z)（1）将VN中的每一个(yīɡè)非终结符视作M中的一个(yīɡè)状态， 并增加一个(yīɡè)初始状态q0，且q0VN，

令Q=VN{q0},Z={S},=VT

(将文法G的开始符号S看成终态)（2）对ABa（A,BVN,aVT{}）令f(B,a)=A。

构造弧（3）对Aa（AVN,aVT{}），令f(q0,a)=A。

构造弧BAaq0Aa10第十页，共65页。自动机转化(zhuǎnhuà)为正规文法(1/2)设给定有穷自动机M=(Q,,f,q0,Z)，按照下述方法可以从M构造出相应的右线性正规文法(wénfǎ)G=(VN,VT,P,S)，使得L(M)=L(G)(1)令VN=Q,VT=,S=q0(2)若f(A,a)=B且BZ时，

则将规则AaB加到P中。(3)若f(A,a)=B且BZ时，则将规则

AaBa

或AaB,Bε加到P中。(4)若文法(wénfǎ)的开始符号S是一个终态，则将规则

Sε加到P中。ABa注意(zhùyì):若终态无出弧，则去掉该非终结符起点开始，考虑出弧！11第十一页，共65页。自动机转化为正规(zhèngguī)文法(1/2)设给定(ɡěidìnɡ)有穷自动机M=(Q,,f,q0,Z)，按照下述方法可以从M构造出相应的左线性正规文法G=(VN,VT,P,S)，使得L(M)=L(G)(1)令VN=Q,VT=,S=Z(2)若f(S,a)=A,则Aa|Sa(3)若f(A,a)=B,则BAa(A≠S)注意(zhùyì):若初态无入弧，则去掉该非终结符终点开始，考虑入弧！12第十二页，共65页。习题(xítí)7(1/4)7、构造下列正规式的相应的DFA 1(0|1)*101解题步骤(bùzhòu)：1.由正规式R构造NFAN2.构造确定化后的DFA的状态矩阵3.生成确定化后的DFA的状态转换图4.化简DFA13第十三页，共65页。习题(xítí)7(2/4)由正规式构造NFA构造确定(quèdìng)化后的DFA的状态矩阵Y234101X11010Q’10A{X}{0,1,2}B{0,1,2}{0,2,3}{0,2}C{0,2,3}{0,2,3}{0,2,4}D{0,2}{0,2,3}{0,2}E{0,2,4}{0,2,3,Y}{0,2}F{0,2,3,Y}{0,2,3}{0,2,4}14第十四页，共65页。生成确定(quèdìng)化后的DFA的状态转换图BFDE010C1100A101习题(xítí)7(3/4)115第十五页，共65页。化简DFAABlllFEC00l0lBFDE01C11100A10100首先M的状态分成两组：终态组{F}，非终态组{A,B,C,D,E}考察{A,B,C,D,E}，由于{A,B,C,D,E}1属于{B,C,F},

它既不包含在{A,B,C,D,E}中也不包含在{F}之中，因此，应把{A,B,C,D,E}一分为二。因为状态E经1弧到达状态F，而状态A、B,C,D经1弧都到达{B,C}，因此，应把E分出来，形成{A,B,C,D}、{E}、{F}。{A,B,C,D}0属于{D,E},它不含在任何划分(huàfēn)中，因为状态C经0弧到达状态E，而状态{A,B,D}经0弧都到达D，因此，应把C分出来，形成{A,B,D}、{C}、{E}、{F}。由于{A,B,D}1={B,C}，它不包含在任何划分(huàfēn)之中，因此，应把{A,B,D}一分为二。因为状态B、D经1弧都到达{C}，经0弧都到达{D}因此，应把A分出来，形成{A}、{B,D}、{C}、{E}、{F}。{B,D}无法再分。

至此，整个分划含有四组：{A}、{B,D}、{C}、{E}、{F}。每个组都不可再分。习题(xítí)7(4/4)16第十六页，共65页。习题(xítí)8(1/3)8、给出下面正规表达式(1)以01结尾的二进制数串;(2)能被5整除的十进制整数(zhěngshù);(3)包含奇数个1或者奇数个0的二进制数串;(7)不包含子串abb的由a和b组成的符号串的全体。17第十七页，共65页。习题(xítí)8(2/3)解：(1)末两位是01，其他位为0、1组成的任意(rènyì)的字符串。(a|b)*表示a、b组成的任意(rènyì)字符串。所以正规表达式为(0|1)*01。(2)①若是一位数，为0或5②若是多于一位的数，为(1|2|3|…|9)(0|1|2|…|9)*(0|5)所以正规表达式为(1|2|3|…|9)(0|1|2|…|9)*(0|5)|0|518第十八页，共65页。习题(xítí)8(3/3)(3)奇数个1：0*1(0|10*1)*奇数个0：1*0(1|01*0)*所以正则表达式为0*1(0|10*1)*|1*0(1|01*0)*(7)ab后只能跟a,所以可以是ab、a组成的任意(rènyì)符号串，即(a|ab)*。又若以b开始，所以正则表达式为b*(a|ab)*。19第十九页，共65页。习题(xítí)9(1/3)9、对下面的情况给出DFA以及正规表达式。(1){0，1}上的含有子串010的所有串。解：首先(shǒuxiān)必须含有010，然后首尾为0、1组成的任意字符串，所以正规式为(0|1)*010(0|1)*。X15010Y2346001120第二十页，共65页。习题(xítí)9(2/3)Q’01A{X,5,1}{5,1,2}{5,1}B{5,1,2}{5,1,2}{5,1,3}C{5,1}{5,1,2}{5,1}D{5,1,3}{5,1,2,4,6,Y}{5,1}E{5,1,2,4,6,Y}{5,1,2,6,Y}{5,1,3,6,Y}F{5,1,2,6,Y}{5,1,2,6,Y}{5,1,3,6,Y}G{5,1,3,6,Y}{5,1,2,4,6,Y}{5,1,6,Y}H{5,1,6,Y}{5,1,6,Y}{5,1,6,Y}BHC01D1100A001GEF111000,1化简后的DFA：BA0ED0,10011121第二十一页，共65页。习题(xítí)9(3/3)(2){0，1}上不含子串010的所有(suǒyǒu)串。解：1*(0|111*)*1*X13Y425611661011ACBEGDFH10000000111111ABD01110化简后的DFADFANFA22第二十二页，共65页。习题(xítí)12(1/3)12、将图3.18的(a)和(b)分别(fēnbié)确定化和最少化。a,baa015042a3ba1abaaabbbb(b)(a)23第二十三页，共65页。习题(xítí)12(2/3)a,baa01(a)Q’abA{0}{0,1}{1}B{0,1}{0,1}{1}C{1}{0}ababaCBAbaaAB24第二十四页，共65页。5042a3ba1abaaabbbb(b)已经(yǐjing)是确定化，对其最小化。1:{0,1},{2,3,4,5}{0,1}a={0,1}{0,1}b={2,4}{2,3,4,5}a={1,3,0,5}2:{0,1},{2,4},{3,5}{2,4}b={3,5}{3,5}b={2,4}baa02bb3a习题(xítí)12(3/3)25第二十五页，共65页。习题(xítí)14(1/2)14、构造(gòuzào)DFA,接收{0，1}上所有满足每个1都有0直接跟在后面的字符串。解：正规表达式为(10|0)*26第二十六页，共65页。

(10|0)*XY10120Q’01A{X,1,Y}{1,Y}{2}B{1,Y}{1,Y}{2}C{2}{1,Y}01010ABC100AC习题(xítí)14(2/2)27第二十七页，共65页。习题(xítí)15(1/3)15、给定右线性文法G：S→0S|1S|1A|0BA→1C|1B→0C|0C→0C|1C|1|0求出一个(yīɡè)与G等价的左线性文法。28第二十八页，共65页。习题(xítí)15(2/3)解：与文法(wénfǎ)G等价的自动机M=({S,A,B,C,D},{0,1},f,{S},{D})f(S,0)={S,B}f(S,1)={S,A}f(A,1)={C,D}f(B,0)={C,D}f(C,0)={C,D}f(C,1)={C,D}SA10,1B00,1100DC0,1129第二十九页，共65页。习题(xítí)15(3/3)与文法(wénfǎ)G等价的左线性文法(wénfǎ)GL=({S,A,B,C,D},{0,1},f,{D})D→A1|B0|C0|C1C→A1|B0|C0|C1B→0|S0A→1|S1S→0|1|S0|S130第三十页，共65页。习题(xítí)20(1/3)20、假定有正规定义式A0→a|bA1→A0A0…An→An-1An-1考虑词形An(1)把An中所有简名都换掉，最终所得的正规式的长度是多少；(2)字集An的元素是什么？把它们非形式地表示成n的函数；(3)证明识别An的DFA只需要用2n+1个状态(zhuàngtài)就足够了。31第三十一页，共65页。习题(xítí)20(2/3)解:(1)An＝＞An-1An-1＝＞An-2An-2An-2An-2＝＞An-3An-3An-3An-3An-3An-3An-3An-3＝＞…＝＞即，所以(suǒyǐ)长度为2n。(2)f(n)=32第三十二页，共65页。习题(xítí)20(3/3)(3)用归纳法证明。当n=0时，只需要1个状态(zhuàngtài)，即假设当n=k时成立，需要2k+1个状态(zhuàngtài)；Ak+1=(a|b)(a|b)SabSABCaabb...第2k+1个状态(zhuàngtài)DEaabb所以Ak+1需要2(k+1)+1个状态，即n=k+1时成立。综上所述，识别An的DFA只需要用2n+1个状态。33第三十三页，共65页。补充(bǔchōng)题构造{a,b}上的含有偶数(ǒushù)个a且奇数个b的正规文法。解：左线性文法GL=({S,A,B,C},{0,1},f,{S})S识别偶数(ǒushù)个a,偶数(ǒushù)个b;A识别奇数个a,偶数(ǒushù)个b;B识别奇数个a,奇数个b;C识别偶数(ǒushù)个a,奇数个b.SaAabbCBaabbS→aA|bC|εA→aS|bBB→aC|bAC→aB|bS34第三十四页，共65页。语法分析——自上而下(zìshànɡérxià)分析(1/5)自上而下(zìshànɡérxià)分析法确定(quèdìng)的自上而下分析法非确定(quèdìng)的自上而下分析法

(带回溯的自上而下分析法)递归下降分析法

预测分析法35第三十五页，共65页。语法分析——自上而下(zìshànɡérxià)分析(2/5)LL(1)文法要求：（1）文法不含左递归。（2）对文法中的每一个非终极符A，若A→α1|α2|...|αn，则FIRST（αi）FIRST（αj）=（3）对文法中的每一个非终极符A，若它存在某个候选(hòuxuǎn)首符集包含ε，则FIRST（A）FOLLOW（A）=左递归的消除(xiāochú)：P→Pα|β改为：P→βP’P’→αP’|εFIRST集：FIRST()={a|a…,a∈VT}若ε，ε∈FIRST()FOLLOW集：FOLLOW(A)={a|S...Aa...，a∈VT}若S...A，则规定#∈FOLLOW（A）**非LL(1)文法改写为LL(1)文法：消除左递归和反复提取公共左因子。提取公共左因子：

A→α1|α2|...|αn|1|2|...|m修改成：

A→αA’|1|2|...|mA’→1|2|...|n36第三十六页，共65页。语法分析——自上而下(zìshànɡérxià)分析(3/5)递归下降分析程序的构造：当遇到终结符a时，则编写语句

if(当前读到的输入符号==a)读入下一个输入符号。当遇到非终结符A时，则编写语句调用A.当遇到A规则时，则编写语句

if(当前读到的输入符号FOLLOW(A))ERROR。当某个非终结符的规则有多个候选(hòuxuǎn)式时，按LL(1)文法的条件唯一现在一个候选(hòuxuǎn)式进行推导。37第三十七页，共65页。实验二：预测(yùcè)分析算法的设计与实现预测(yùcè)分析器预测(yùcè)分析表分析栈总控程序a1a2…ai…an$X…$T[j]分

析

栈

S[k]总控程序(chéngxù)

预测分析表输出38第三十八页，共65页。预测分析(fēnxī)表的构造1、构造文法G的每一个非终结符的FIRST集和FOLLOW集2、构造分析表M[A，a]

（1）对文法G的每个规则A→α，执行第二步和第三步；（2）对每个终极符a∈FIRST(α）,则置M[A,a]=A→α；（3）若ε∈FIRST(α）,则对任何b∈FOLLOW（A）,

则置M[A,b]＝A→α；（4）把所有无定义(dìngyì)的M[A,a]标上“出错标志”

(表中用空格表示)。39第三十九页，共65页。FIRST集的构造(gòuzào)若X∈VT，则FIRST(X)={X}。若X∈VN，且有规则Xa…，a∈VT，则a∈FIRST(X)。若X∈VN，且有规则Xε，则ε∈FIRST(X)中。若有规则X→Y1Y2…Yn，对任意(rènyì)的i(1in)，

当Y1Y2…Yi-1都是非终极符且Y1Y2…Yi-1=>ε

(即对任何j(1ji-1)，FIRST(YJ)都含有ε)，

则把FIRST(Yi)中的所有非ε-元素加到FIRST(X)中；

特别地，若Y1Y2…Yn=>ε(即所有的FIRST(Yj)中均含有ε，1jn)，则ε∈FIRST（X）。反复使用上面的规则，直到每个FIRST集不再增大为止40第四十页，共65页。FOLLOW集的构造(gòuzào)(1)对文法的开始符号S，置‘#’于FOLOOW（S）中；(2)若A→αB是一个规则，则把FIRST()-{ε}加到FOLLOW(B)中；(3)若A→αB是一个规则，

或A→αB是一个规则，而=>ε，即ε∈FIRST(),则把FOLLOW(A)加至FOLLOW(B)中。(4)反复使用上面(shàngmiɑn)的规则，直到每个非终结符的FOLLOW集不再增大为止。41第四十一页，共65页。总控程序(chéngxù)42第四十二页，共65页。预测(yùcè)分析的过程若X=a=‘#’，则宣布分析(fēnxī)成功；若X=a‘#’，则将栈顶符号X（终极符）弹出，让IP指针指向下一个输入符号；若X是一个非终极符，则查看分析(fēnxī)表M。如果分析(fēnxī)表的M[A,a]中是一条产生式，则先将栈顶符号X（非终极符）弹出，然后把该产生式右端符号串按反序（从右到左）压入栈中（ε串不入栈）。43第四十三页，共65页。习题(xítí)1(1/4)1、考虑(kǎolǜ)下面文法G1：S→a|∧|(T)T→T,S|S（1）消去G1的左递归，然后对每个非终结符写出不带回溯的递归子程序。（2）经过改写的文法是否是LL（1）的？给出它的预测分析表。44第四十四页，共65页。习题(xítí)1(2/4)解：（1）消去(xiāoqù)G1的左递归：S→a|∧|(T)T→ST’T’→,ST’|ε递归子程序：PROCEDURES;IFSYM=‘a’THENADVANCEELSEIFSYM=‘∧’THENADVANCEELSEIFSYM=‘(’THENBEGINADVANCET;IFSYM=‘)’THENADVANCEELSEERRORENDELSEERROR;PROCEDURET;BEGINS;T’END;PROCEDURET’;IFSYM=‘,’THENBEGINADVANCES;T’END;ELSEIFSYM<>‘)’THENERROR判断输入(shūrù)符号是否属于FOLLOW集45第四十五页，共65页。习题(xítí)1(3/4)（2）FIRST(a)={a}FIRST(∧)={∧}FIRST((T))={(}FIRST(,ST’)={,}FIRST(ε)={ε}FIRST(S)={a,∧,(}FOLLOW(S)={#,,,ε,)}FIRST(T)={a,∧,(}FOLLOW(T)={)}FIRST(T’)={,,ε}FOLLOW(T’)={)}FIRST(a)∩FIRST(∧)∩FIRST((T))=ФFIRST(,ST’)∩FIRST(ε)=ФFIRST(T’)∩FOLLOW(T’)=Ф所以改写(gǎixiě)后的文法是LL（1）文法。46第四十六页，共65页。习题(xítí)1(4/4)预测分析(fēnxī)表如下：47第四十七页，共65页。习题(xítí)2(1/6)2、对下面(xiàmian)的文法G：E→TE’E’→+E|εT→FT’T’→T|εF→PF’F’→*F’|εP→(E)|a|b|∧(1)计算这个文法的每个非终结符的FIRST和FOLLOW。(2)证明这个文法是LL(1)的。(3)构造它的预测分析表。(4)构造它的递归下降分析程序。48第四十八页，共65页。习题(xítí)2(2/6)解：(1)FIRST和FOLLOW集如下(rúxià)表：49第四十九页，共65页。习题(xítí)2(3/6)(2)FIRST(+E)∩FIRST(ε)={+}∩{ε}=ФFIRST(T)∩FIRST(ε)={(,a,b,∧}∩{ε}=ФFIRST(*F’)∩FIRST(ε)={*}∩{ε}=ФFIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(∧)={(}∩{a}∩{b}∩{∧}=ФFIRST(E’)∩FOLLOW(E’)=ФFIRST(T’)∩FOLLOW(T’)=ФFIRST(F’)∩FOLLOW(F’)=Ф所以(suǒyǐ)该文法是LL(1)文法。50第五十页，共65页。习题(xítí)2(4/6)(3)预测(yùcè)分析表为：51第五十一页，共65页。习题(xítí)2(5/6)(4)递归下降(xiàjiàng)分析程序为：PROCEDUREE;BEGINT;E’END;PROCEDURET;BEGINF;T’END;PROCEDUREE’;IFSYM=‘+’THENBEGINADVANCE;EEND;ELSEIFSYM<>‘)’ANDSYM<>‘#’THENERRORPROCEDUREF;BEGINP;F’END;PROCEDURET’;IFSYM=‘a’ORSYM=‘b’ORSYM=‘∧’ORSYM=‘(’THENBEGINADVANCE;TEND;ELSEIFSYM<>‘)’ANDSYM<>‘+’ANDSYM<>‘#’

THENERROR52第五十二页，共65页。习题(xítí)2(6/6)PROCEDUREP;IFSYM=‘(’THENBEGINADVANCE;E;IFSYM!=‘)’THENADVANCE;ELSEERRORENDELSEIFSYM=‘a’ORSYM=‘b’ORSYM=‘∧’THENADVANCE;ELSEERRORPROCEDUREF’;IFSYM=‘*’THENBEGINADVANCE;F’;ENDELSEIFSYM<>‘(’ANDSYM<>‘a’ANDSYM<>‘b’ANDSYM<>‘∧’ANDSYM<>‘+’SYM<>‘)’ANDSYM<>‘#’THENERROR53第五十三页，共65页。习题(xítí)3(1/3)3、下面(xiàmian)文法那些是LL(1)文法？(1)S→AbcA→a|εB→b|ε(2)S→AbA→a|B|εB→b|ε(3)S→ABBAA→a|εB→b|ε(4)S→aSe|BB→bBe|CC→cCe|d54第五十四页，共65页。习题(xítí)3(2/3)解：(1)文法无左递归FIRST(a)∩FIRST(ε)={a}∩{ε}=ФFIRST(b)∩FIRST(ε)={b}∩{ε}=ФFIRST(A)∩FOLLOW(A)={a,ε}∩{b}=ФFIRST(B)∩FOLLOW(B)={b,ε}∩Ф=Ф所以(suǒyǐ)该文法是LL(1)文法。(2)文法无左递归FIRST(a)∩FIRST(B)∩FIRST(ε)={a}∩{b,ε}∩{ε}≠Ф所以(suǒyǐ)该文法不是LL(1)文法。55第五十五页，共65页。习题(xítí)3(3/3)(3)文法(wénfǎ)无左递归FIRST(a)∩FIRST(ε)={a}∩{ε}=ФFIRST(b)∩FIRST(ε)={b}∩{ε}=ФFIRST(A)∩FOLLOW(A)={a,ε}∩{a,b,#}≠Ф所以该文法(wénfǎ)不是LL(1)文法(wénfǎ)。(4)文法(wénfǎ)无左递归FIRST(aSe)∩FIRST(B)={a}∩{b,ε}=ФFIRST(bBe)∩FIRST(C)={b}∩{c,d}=ФFIRST(cCe)∩FIRST(d)={c}∩{d}=Ф所以该文法(wénfǎ)是LL(1)文法(wénfǎ)。56第五十六页，共65页。习题(xítí)4(1/3)4、对下面(xiàmian)文法：Expr→_ExprExpr→(Expr)|VarExprTailExprTail→_Expr|εVar→idVarTailVarTail→(Expr)|ε(1)构造LL（1）分析表(2)给出对句子id__id((id))的分析过程57第五十七页，共65页。习题(xítí)4(2/3)解：(1)FIRST集和FOLLOW集如下(rúxià)表：LL(1)分析(fēnxī)表为：58第五十八页，共65页。习题(xítí)4(3/3)(2)步骤符号栈输入(shūrù)串所用产生式反序压入栈59第五十九页，共65页。习题(xítí)5(1/5)5、把下面(xiàmian)文法改写为LL(1)的：Declist→Declist；Decl|DeclDecl→IdList:TypeIdList→IdList,id|idType→ScalarType|array(ScalarTypeList)ofTypeScalarType→id|Bound..BoundBound→SignIntLiteral|idSign→+|-|εScalarTypeList→ScalarTypeList