北方工业大学编译原理习题集

1、精选优质文档-倾情为你奉上编译原理课后习题（修订版）第二章 高级语言及其语法描述3、何谓“标识符”，何谓“名字”，两者的区别是什么？解：标识符是高级语言中定义的字符串，一般是以英文字母（包括大小写字母）或下划线开头的，由数字、字母和下划线组成的一定长度的字符串，它只是一个标志，没有其他含义。名字是用标识符表示的，但名字不仅仅是一个字符串，它还具有属性和值。4、令 、* 和代表加、乘和乘幂，按如下的非标准优先级和结合性质的约定，计算11*2*12的值：（1）、优先顺序（从高至低）为、* 和，同级优先采用左结合。（2）、优先顺序为、*，同级优先采用右结合。解：（1）、11*2*12 = 2*2*1

2、2 = 4*12 = 42 = （2）、11*2*12 = 6、令文法G6为NDND，D0123456789（1）、G6的语言L(G6)是什么？（2）、给出句子0127、34和568的最左推导和最右推导。分析：根据产生式NDND可以看出，N最终可推导出1个或多个（可以是无穷多个）D，根据产生式D0123456789可以看出，每个D可以推导出0至9中的某一个数字。因此，N最终推导出的是由0到9这10个数字组成的字符串。解：（1）、L(G6)是由0到9这10个数字组成的字符串。（2）、句子0127、34和568的最左推导：N=>ND=>NDD=>NDDD=>DDDD=>

3、;0DDD=>01DD=>012D=>0127N=>ND=>DD=>3D=>34N=>ND=>NDD=>DDD=>5DD=>56D=>568句子0127、34和568的最右推导：N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127N=>ND=>N4=>D4=>34N=>ND=>N8=>ND8=>N68=>D68=>5687、写一个文法，使其语言是奇数集，且每个奇数不以0开头。分

4、析：本题要构造一个文法，由它产生的句子是奇数，且不以0开头。也就是说它的每个句子都以1、3、5、7、9中某数结尾。如果数字只有一位，则满足要求；如果有多位，则要求第一位不能是0；而中间有多少位，每位是什么数字则没有要求。因此我们可以把这个文法分3部分完成，分别用3个非终结符来产生句子的第一位、中间部分和最后一位。引入几个非终结符，其中，一个用作产生句子的开头，可以是1到9中的数，不包括0；一个用来产生句子的结尾，为奇数；另一个则用来产生以非0整数开头后面跟任意多个数字的数字串，进行分解之后，这个文法就很好写了。解：G(S)：A2468D BA0 CCBA D13579 SCDD8、令文法为ET

5、E+ TE-T TFT*FT/F F(E)i（1） 给出i+i*i、i*(i+i)的最左推导和最右推导；（2） 给出i+i+i、i+i*i和i-i-i的语法树。解：（1） 最左推导为：E => E+T => T+T => F+T => i+T => i+T*F => i+F*F => i+i*F => i+i*iE => T => T*F => F*F => i*F => i*(E) => i*(E+ T) => i*(T+ T)=> i*(F+ T) => i*(i+ T) => i*

6、(i+ F) => i*(i+ i)最右推导为：E =>E+T =>E+T*F =>E+T*i =>E+F*i =>E+i*i => T+i*i => F+i*i => i+i*iE => T => T*F => F*F => F*(E) => F*(E+T) => F*(E+ F) => F*(E+ i)=> F*(T+i) => F*(F+i) => F*(i+i) => i*(i+ i)（2） 语法树：FTETE+EFi+TFiiE+TEFi*TFiTFiEE-TEFi

7、TFi-Fi9、证明下面的文法是二义的：SiSeSiSi分析：根据文法二义性定义，如果要证明该文法是二义的，必须找到一个句子，使该句子具有两个不同的最右推导或两个不同的语法树。我们首先分析这个文法，根据我们对程序语言的了解，不难发现这个文法应该是用来表示ifelse结构的（用“i”表示“if”或语句集，用e代表else）。因此我们就要到ifelse结构中去找二义性。我们知道，程序语言一般都规定else部分是和它前面离它最近的没有被匹配的if语句进行匹配。而上面的这个文法体现不出这种限制，因此我们可以找这样一个句子，在else前面有两个if（如句子iiiei），else和不同的if进行匹配时就会

8、产生不同的语义。解：考虑句子iiiei，存在如下两个最右推导：S=>iSeS=>iSei=>iiSei=>iiieiS=>iS=>iiSeS=>iiSei=>iiiei由此该文法是二义的。10、把下面文法改为无二义的：SSS(S)( )分析：本题给出的文法是二义的，关键在于SSS是产生二义性的根源。我们将该产生式改造成等价的递归结构，消除二义性。解：STST，T(S)( )11、给出下面语言的相应文法：L1=anbncin1，i0， L2=aibncnn1，i0L3=anbnambmn，m0L4=1n0m1m0nn，m0分析：语言L1要求a和b的

9、个数一样多，且至少为一个；c的个数为0个以上。因此我们可用一个非终结符去生成anbn串，用另外一个非终结符去生成ci。语言L2要求b和c的个数一样多，因此可用一个非终结符去生成bncn，而使用另外一个非终结符去生成ai。因此可以模仿L1生成L2。对于L3，可将anbnambm分两段考虑，即anbn和ambm，然后用两个非终结符分别去产生他们。L4不能采用分段处理的方式，它要求中间的0和1的个数相同，而且一前一后的0和1的个数相同。对于这种题型我们可以采用从里向外扩展的方式进行，即先用一个非终结符生成处于中间的m个0和m个1，然后，使用另外一个非终结符在该串的基础上扩充前后的n个0和n个1。解：

10、L1的文法：SAC；AaAbab；CcCL2的文法：SAB；AaA；BbBcbcL3的文法：SAB；AaAb；BaBbL4的文法： S1S0A； A0A1；第三章 词法分析1、 编写一个对于Pascal源程序的预处理程序。该程序的作用是，每次被调用时都将下一个完整的语句送进扫描缓冲区，去掉注释行，同时要对源程序列表打印。2、 请给出以下C+程序段中的单词符号及其属性值。int CInt：nMulDiv（int n1，int n2）if （n3= =0）return 0；else return（n1*n2）/n3；3、 用类似C或Pascal的语言编写过程GetChar，GetBC和Concat

11、。4、 用某种高级语言编写并调试一个完整的词法分析器。5、 证明3.3.1中关于正规式的交换律、结合律等五个关系。6、 令A、B和C是任意正规式，证明以下关系成立：AA=A(A*)*= A*A*=A A*(AB)*A=A(BA)*(AB)*=(A*B*)*=(A*B*)*A=baA当且仅当A=a*b证明：（1）、AA=AL(AA)=L(A)L(A)=L(A)，所以有AA=A。（2）、(A*)*= A*（3）、A*=A A*通过证明两个正规式所表示的语言相同来证明两个正规式相等。L(A A*)=L()L(A)L(A*)= L()L(A)(L(A) )*=L()L(A)(L(A)0(L(A)1(L

12、(A)2(L(A)3)=L()(L(A)1(L(A)2(L(A)3(L(A)4=(L(A)*=L(A*)即：L(A A*)=L(A*)，所以有：A*=A A*（4）、(AB)*A=A(BA)*利用正规式的分配率和结合律直接推导。(AB)*A=(AB)0(AB)1(AB)2(AB)3)A=A(AB)1A(AB)2A(AB)3A=AA (BA)1A (BA)2A (BA)3=A(BA)1(BA)2(BA)3)=A(BA)*即：(AB)*A=A(BA)*（5）、(AB)*=(A*B*)*=(A*B*)*证明:先证(AB)*=(A*B*)*因为L(A)L(A) *L(B) *,L(B) L(A) *L

13、(B) *故:L(A) L(B) L(A) *L(B) *于是由本题第二小题结论可知(L(A)L(B) *(L(A) *L(B)*)* 又L(A)L(A)L(B), L(B) L(A)L(B)故:L(A)*(L(A)L(B)* L(B)*(L(A)L(B)*因此有:L(A)*L(B)* (L(A)L(B)* (L(A)L(B)*=( (L(A)L(B)*) 2故(L(A)*L(B)*)*(L(A)L(B)*)*由本题第二小题得: (L(A)L(B)*)*= (L(A)L(B) * 故得: (L(A)*L(B)*)*(L(A)L(B) * 则由得: (L(A)L(B) *=(L(A)*L(B)*

14、)*由于L(A*B*)*=(L(A*B*)*=(L(A*)L(B*)*=(L(A)*L(B)*)*即有(L(A)L(B)*=L(A*B*)* 而(A|B)*对应的语言为(L(A)L(B)*,且(A*B*)*对应的语言为L(A*B*)*则根据得(A|B)*=(A*B*)*再证:(A*|B*)*=(A*B*)*因为:A,B是任意正规式,由以上结论得: (A*|B*)*=(A*)*(B*)*)*又由本题第二小题目的结论可得：（A*）*=A*，（B*）*=B*因此，（A*|B*）*=（A*B*）*综合上述两种结论，最后得：(AB)*=(A*B*)*=(A*B*)*（6）、A=baA当且仅当A=a*b7

15、、 构造下列正规式相应的DFA1(01)*1011(1010*1(010)*1)*00*10*10*10*(0011)*(0110)(0011)*(0110)(0011)*)*解：(1)、1(01)*101第一步：根据正规式构造NFA，先引入初始状态X和终止状态Y：X1(01)*101Y再对该转换图进行分解，得到分解后的NFA如下图：X12345Y110101第二步：对NFA进行确定化，获得状态转换矩阵：状态01XØ1，2，31，2，32，32，3，42，32，32，3，42，3，42，3，52，3，42，3，52，32，3，4，Y2，3，4，Y2，3，52，3，4根据转换矩阵获得相

16、应的DFA：01234100010111501第三步：化简该DFA，获得最简的DFA即为所求。首先根据是否终止状态将所有状态分为两个集合0，1，2，3，4和5，这里集合5已经不可划分，只需考虑集合0，1，2，3，4。0，1，2，3，40=2，4，-，0，1，2，3，41=1，3，5因为1，3，5和2，4，-不在一个集合里面，所以需要对集合0，1，2，3，4进行进一步的划分，检查其中的所有状态。状态0不能接受字符0，需要把状态0划分出来；另外，只有状态4读入字符1后进入状态5，因此将状态4划分出来，划分的结果为4个集合：0，1，2，3，4，5。检查集合1，2，3，1，2，30=2，4，不属于同一

17、个集合，因此要对集合1，2，3进行进一步划分，划分结果为5个集合：0，1，2，3，4，5。检查集合1，2，1，20=2，1，21=3，不需要进行进一步划分。所以最终划分结果为5个集合：0，1，2，3，4，5。所以，最终所求DFA如下图示：01341001011501（2）、1(1010*1(010)*1)*0（3）、0*10*10*10*（4）、(0011)*(0110)(0011)*(0110)(0011)*)*8、 给出下面正规表达式：（1） 以01结尾的二进制数串；（2） 能被5整除的十进制整数；（3） 包含奇数个1或奇数个0的二进制数串；（4） 英文字母组成的所有字符串，要求符号串中的

18、字母依照字典序排列；（5） 没有重复出现的数字的数字符号串的全体；（6） 最多有一个重复出现的数字的数字符号串的全体；（7） 不包含子串abb的由a和b组成的符号串的全体。解：（1）以01结尾的二进制数串；分析题意，要求的是二进制数串，即由0和1构成的串，并且必须以01结尾，所以本题可以分两步完成：一部分实现由0和1构成的任意串，一部分即01，然后将它们连结在一起就可以了，所以所求为(10)*01。（2）能被5整除的十进制整数；分析题意，本题要求的是十进制整数，也就是由0至9这10个数字组成的字符串，并且不能以0开头（整数“0”除外），要求能被5整除，则该串必须以0或者5结尾。根据分析，可以把

19、本题分成两种情况考虑：一种情况时该整数只有一位，则该整数有0和5两种可能；另一种情况是该整数有多位，则该整数可以分成三部分考虑：一是第一位必须不为0；二是最后一位必须为0或5；三是中间部分可有可无，并且可以由0到9之间任意数字构成，所以所求为(123456789) (0123456789)*(05)(05)。（3）包含奇数个1或奇数个0的二进制数串；本题求二进制串，并且要求包含奇数个0或奇数个1，由于0和1都可以在二进制串中任何地方出现，所以本题只需要考虑一种情况，另一种情况也可以类似求得。考虑包含奇数个0的字符串：由于只关心0的个数的奇偶数，我们可以把二进制串分成多段来考虑，第一段为二进制串

20、的开始到第一个0为止，这一段包含一个0，并且0的前面有0个或多个1。对于剩下的二进制串按照每段包含两个0的方式去划分，即以0开始，以0结尾，中间可以有0个或多个1。如果一个二进制串被这样划分完后，剩下的部分如果全部是全1串（这些全1串在前面划分的串之间或最后），则该二进制串就有奇数个0，所以该二进制串可以这样描述：以第一段（1*0）开始，后面由全1串（1*）以及包含两个0的串（01*0）组成，所以包含奇数个0的正规表达式为1*0（101*0）*。所以本题所求为1*0（101*0）*0*1（010*1）*。（4）英文字母组成的所有字符串，要求符号串中的字母依照字典序排列；（5）没有重复出现的数字

21、的数字符号串的全体；（6）最多有一个重复出现的数字的数字符号串的全体；（7）不包含子串abb的由a和b组成的符号串的全体。9、 对下面情况给出DFA及正规表达式： （1）0，1上的含有子串010的所有串；（2）0，1上不含子串010的所有串。解：（1）、（2）、直接写出满足条件的正规表达式。考虑满足条件的字符串中的1：在串的开始部分可以有0个或多个1，串的尾部也可以有0个或多个1，但串的中间只要出现1则至少在两个以上，所以满足条件的正规表达式为1*(0111*)*1*。所求的DFA如下图所示：AS10a11B010、 一个人带着狼、山羊和白菜在一条河的左岸。有一条船，大小正好能装下这个人和其他

22、三件东西中的一件。人和他的随行物都要过到河的右岸。人每次只能将一件东西摆渡过河。但若人将狼和羊留在同一岸而无人照顾的话，狼将把羊吃掉。类似地，若羊和白菜留下来无人照看，羊将会吃掉白菜。请问是否有可能渡过河去，使得羊和白菜都不被吃掉？如果可能，请用有限自动机写出渡河的方法。解：11、12、 将图3.18的（a）和（b）分别确定化和最小化。10a，baa(a)20baa(b)1543bbbbbaaaaa解：（1）、图（a）中为一个NFA，所以需要先对它进行确定化，得到DFA，然后再对DFA进行最小化。首先进行确定化，如下两个表所示：专心-专注-专业状态ab00，110，10，1110Ø

23、状态ab01211220根据状态转换矩阵得到如下图所示的DFA：210bbaaa化简后的DFA为：20baa（2）、题中所给即为一个DFA，不需要确定化，只对它进行最小化即可。首先将状态划分为两个集合0，1，2，3，4，5。有0，1a=1，0，1b=2，4和2，3，4，5a=1，3，0，5，2，3，4，5b=2，3，4，5，所以可以进一步划分为0，1，2，4，3，5，然后有0，1a=1，0，1b=2，4，2，4a=1，0，2，4b=3，5，3，5a=3，5，3，5b=2，4。因此，最后划分结果是0，1，2，4，3，5。最小化后的DFA如下图所示：10b aa2b ba13、 （1）给出描述C浮

24、点数的DFA；14、 构造一个DFA，它接受=0，1上所有满足如下条件的字符串：每个1都有0直接跟在右边。分析：对这类题型的固定解法分4步进行：首先根据语言写出正规表达式；然后根据正规表达式构造相应的NFA；然后，对NFA进行确定化得到DFA；最后对DFA化简得到最简DFA。第一步：写出正规表达式。根据题意，该DFA接受的字符串由0和1组成，并且每个1的后面都有0直接跟在右边，因此，可以将该字符串理解为由0和10构成的串，则相应的正规表达式就是(010)*。第二步：构造NFA。首先得出下图：(010)*XY然后对上图进行分解后得到如下图所示的NFA。XY12010第三步：确定化，得到DFA。确

25、定化结果如表14.1所列；给状态编号，得到表14.2所示的状态转换矩阵：状态01X，1，Y1，Y21，Y1，Y221，YØ表14.1 状态转换矩阵状态0101211221表14.2 新的状态转换矩阵根据状态转换矩阵得到DFA如下图所示：21011000第四步：对该DFA进行最小化。其分析过程如下：0，1，20，10=1，0，11=20，1，2最小化后的DFA如图所示，该DFA即为所求。1010015、 给定右线性文法G：S0S1S1A0BA1C1B0C0C0C1C01求出一个与G等价的左线性文法。分析：根据右线性文法求左线性文法没有直接的方法，但可以通过状态转换图去转换。可以先求出文

26、法G的状态转换图，再根据状态转换图写出相应的左线性文法。文法G对应的状态转换图如下所示：SZ100，1BCA10，10，1001对状态转换图进行确定化，得到状态转换矩阵：状态01SS，BS，AS，BS，B，C，ZS，AS，AS，BS，A，C，ZS，B，C，ZS，B，C，ZS，A，C，ZS，A，C，ZS，B，C，ZS，A，C，Z给状态编号，得到新的状态转换矩阵：状态01012132214334434根据状态转换矩阵获得DFA如下：040123100101101还可以对上图的DFA进行化简，状态3和4可以合并，化简后的DFA如下图所示：0，1ST01BA0101不难看出，该DFA接受的语言是0，1

27、上包含00或11的字符串。根据化简后的DFA，我们可以写出相应的左线性文法G：TA0B1T0T1AB00BA1116、 *非形式的说明17、 *下面的字集是否为正规集？或写出其正规式，或给出否证。（1） L1=anbnn0；（2） L2=x；（3） L3=。18、 假定L和M都是正规集：（1） 证明LM、LM和M（补集）也是正规的；（2） L是L中每个字的逆转，证明L也是正规的。19、 写出描述ANSI C的单词符号的LEX程序。20、 假定有正规定义式A0abA1A0 A0AnAn-1 An-1考虑词形An（1） 把An中所有简名都换掉，最终所得的正规式的长度是多少？（2） 字集An的元素是

28、什么？把它们非形式的表示成n的函数；（3） 证明识别An的DFA只需用2n+1个状态就足够了。21、 把LEX的“动作”成分加以充实使得可用它来编写语法制导编辑器。第四章 语法分析自上而下分析1、考虑下面的文法G1： Sa(T)TT，SS（1）消去G1的左递归。然后对每个非终结符，写出不带回溯的递归子程序。（2）经改写后的文法是否是LL(1)的？给出它的预测分析表。解：（1）按照T、S的顺序消除左递归，得到文法：G(S)Sa(T)TSTT，ST 对于非终结符S,T, T的递归子程序如下：Procedure S;Begin If sym = a or sym = Then advanceElse

29、 ifsym = (Then begin Advance ; T; If sym = ) Then advance Else errorEndElse errorEnds;Procedure T;Begin S; T;Ends;Procedure TBegin If sym = ,Then begin Advance ;S; T Endsends;（2）计算每个非终结符的FIRST集合和FOLLOW集合：FIRST（S）=a，( FIRST（T）=a，( FIRST（T）=，FOLLOW（S）= )，#FOLLOW（T）= ) FOLLOW（T）= ) 从而可见改造后的文法符合LL(1)文法的

30、充分必要条件，所以是LL(1)的。 该文法的预测分析表a(),#SS->aS->S->(T)TT->S TT->S TT->S TTT->T->,S T2、对下面的文法G：ETEE+ETFTTTFPFF*FP(E)ab（1） 计算这个文法的每个非终结符的FIRST和FOLLOW。（2） 证明这个文法是LL(1)的。（3） 构造它的预测分析表。（4） 构造它的递归下降分析程序。分析：对于这类题目，我们首先应当检查文法是否符合LL(1)文法的条件，根据需要，先通过消除左递归、提取右公因子的方法，把文法改造成符合LL(1)文法的条件，在此基础上，我们才

31、能构造出不带回溯的递归下降识别程序。注意，本题在构造子程序时，对于每个产生式候选，在调用第一个非终结符对应的子程序之前，检查了首符集。解：（1） 计算每个非终结符的FIRST集合和FOLLOW集合如下：FIRST（E）=(，a，b，FIRST（E）=+，FIRST（T）=(，a，b，FIRST（T）=(，a，b，FIRST（F）=(，a，b，FIRST（F）=*，FIRST（P）=(，a，b，FOLLOW（E）=#，)FOLLOW（E）=#，)FOLLOW（T）=+，)，#FOLLOW（T）=+，)，#FOLLOW（F）=(，a，b，+，)，#FOLLOW（F）=(，a，b，+，)，#FOLL

32、OW（P）=*，(，a，b，+，)，#（2） 本文法是LL ( 1 )文法。证明： 通过观察可知文法中不含有左递归，满足LL (1)文法定义的第一个条件。考虑下列产生式：E+ETTF*FP(E)ab因为：FIRST（+E）FIRST（）=+=ØFIRST（E）FOLLOW（E）=+#，)= ØFIRST（T）FIRST（）=(，a，b，=ØFIRST（T）FOLLOW（T）=(，a，b，+，)，#=ØFIRST（*F）FIRST（）=*=ØFIRST（F）FOLLOW（F）=*(，a，b，+，)，#= ØFIRST（E）FIRST（a

33、）FIRST（b）FIRST（）= Ø所以该文法是LL(1)文法。（3） 构造其预测分析表： 预测分析表+ * ( ) a b #EEàT EEàT EEàT EEàT EEEà+EE àE ->TT àFTTàFTTàFTTàFTTTàT à TTàTàTTàTT àTTàFF àPFFàPFPàPFFàPFFF à F à*FF à F&

34、#224;FàFàFàFàPP à(E)PàaPàbPà （4） 构造其递归下降分析程序： Procedure E;Begin T ;EEnd ;Procedure E ;Begin Ifsym = + Then begin Acvance ;E End End ;ProcedureT ;Begin F ; TEnd ;Procedure T ;Begin If sym first ( T ) Then T Else if sym = * then errorEnd ;Procedure F ;Begin If s

35、ym first ( P ) P; F;End ; Procedure F BeginIf sym = * Then begin Advance ; F EndEnd;Procedure P Begin Ifsym = a orsym = b or sym = Then acvance Else if sym = ( Then begin Advance ; E ; If sym = ) Then advance Else errorEndElse error End;3、下面文法中，哪些是LL(1)的，说明理由。（1）、SAbcAaBb（2）、SAbAaBBb（3）、SABBAAaBb（4）

36、、SaSeBBbBeCCcCed分析：判断文法是否是LL(1)的，要根据LL(1)文法的条件逐一检查：首先要确定文法不含左递归；随后计算文法的各非终结符（X）的首符集FIRST（X）和随符集FOLLOW（X）。首先要理解这两个集合的计算方法，特别要注意算法终止的条件：直到集合不再变化为止。也就是说，反复检查每一个产生式，直到从头到尾检查了所有产生式，而FIRST集合和FOLLOW集合都没有变化了，这时候计算才能结束。最后根据LL(1)文法的充分必要条件（即LL(1)文法定义）来判断是否是LL(1)文法。解：（1） 该文法不含左递归，计算每个非终结符的FIRST集合和FOLLOW集合如下：FIR

37、ST（S）=a，b，cFIRST（A）=a，FIRST（B）=b，FOLLOW（S）=#FOLLOW（A）=b，cFOLLOW（B）=c可见该文法满足LL(1)文法的三个条件，是LL(1)文法。（2） 该文法不含左递归，计算每个非终结符的FIRST集合和FOLLOW集合如下：FIRST（S）=a，bFIRST（A）=a，b，FIRST（B）=b，FOLLOW（S）=#FOLLOW（A）=bFOLLOW（B）=b考虑AaB，因为FIRST（B）FOLLOW（A）=bØ，所以该文法不是LL(1)文法。（3） 该文法不含左递归，计算每个非终结符的FIRST集合和FOLLOW集合如下：FIR

38、ST（S）=a，b，FIRST（A）=a，FIRST（B）=b，FOLLOW（S）=#FOLLOW（A）=a，b，#FOLLOW（B）=a，b，#考虑Aa和Bb，因为FIRST（a）FOLLOW（A）=aØFIRST（b）FOLLOW（B）=bØ所以该文法不是LL(1)文法。（4） 该文法不含左递归，计算每个非终结符的FIRST集合和FOLLOW集合如下：FIRST（S）=a，b，c，dFIRST（B）=b，c，dFIRST（C）=c，dFOLLOW（S）=e，#FOLLOW（B）=e，#FOLLOW（C）=e，#可见该文法满足LL(1)文法的三个条件，是LL(1)文法。4

39、、对下面文法：Expr-ExprExpr(Expr)Var ExprTail-ExprVarid VarTailVarTail(Expr)（1）、构造LL(1)分析表。（2）、给出对句子id-id(id)的分析过程。分析：构造文法的预测分析表，通常应当按下列顺序进行：（1）、消除文法的左递归（包括所有直接左递归和间接左递归）；（2）、对消除左递归后的文法，提取左公因子；（3）、对经过上述改造后的文法，计算它的每个非终结符的FIRST集合和FOLLOW集合；（4）、根据FIRST集合和FOLLOW集合构造预测分析表。第一步对文法G的每个产生式A执行第一步和第三步；第二步对每个终结符aFIRST(

40、)，把A加至MA，a中；第三步若FIRST()，则对任何bFOLLOW(A)把A加至MA，b中；第四步把所有无定义的MA，a标上“出错标志”。解：（1）、计算每个非终结符的FIRST集合和FOLLOW集合如下：FIRST(Expr)=-，(，idFIRST(ExprTail)=-，FIRST(Var)=idFIRST(VarTail)=(，FOLLOW(Expr)=)，#FOLLOW(ExprTail)=)，#FOLLOW(Var)=-，)，#FOLLOW(VarTail)=-，#构造其预测分析表如下：-id()#ExprExpr- ExprExpr ExprExpr-( Expr)ExprT

41、ailExprTail-ExprExprTailExprTailVarVarid VarTailVarTailVarTailVarTail(Expr)VarTailVarTail（2）、句子id-id(id)的分析过程如下：步骤符号栈输入串所用产生式0# Exprid-id(id) #1# ExprTail Varid-id(id) #ExprVar ExprTail2# ExprTail VarTail idid-id(id) #Varid VarTail3# ExprTail VarTail-id(id) #4# ExprTail-id(id) #VarTail5# Expr -id(id

42、) #ExprTail-Expr6# Expr-id(id) #7# Expr -id(id) #Expr-Expr8# Exprid(id) #9# ExprTail Varid(id) #ExprVar ExprTail10# ExprTail VarTail idid(id) #Varid VarTail11# ExprTail VarTail(id) #12# ExprTail ) Expr (id) #VarTail(Expr)13# ExprTail ) Expr(id) #14# ExprTail ) ) Expr (id) #15# ExprTail ) ) Exprid) #

43、16# ExprTail ) ) ExprTal Varid) #ExprVar ExprTail17# ExprTail ) ) ExprTail VarTail idid) #Varid VarTail18# ExprTail ) ) ExprTail VarTail) #19# ExprTail ) ) ExprTail) #VarTail20# ExprTail ) ) #ExprTail21# ExprTail ) #22# ExprTail#23#ExprTailsuc5、把下面文法改写为LL(1)的：DeclistDeclist；DeclDeclDeclIdList：TypeId

44、ListIdList，ididTypeScalarTypearray(ScalarTypeList) of TypeScalarTypeidBound.BoundBoundSign IntLiteralidSign+-ScalarTypeListScalarTypeList，ScalarTypeScalarType分析：本题主要考察理解和运用消除文法的左递归、提取公因子等算法的能力，为判断文法是否是LL(1)文法，还要计算文法的FIRST集合和FOLLOW集合。消除文法的左递归的基本思想是，将文法规则中的左递归结构变换成等价的右递归结构。提取左公因子的算法，是对包含公共左因子的产生式候选，反复

45、提取左因子，就能够把每个非终结符（包括新引进者）的所有候选首符集变成为两两不相交。消除文法的左递归、提取左公共因子后，再计算文法的各非终结符（X）的首符集FIRST（X）和随符集FOLLOW(X)，然后根据LL(1)文法的充分必要条件（即LL(1)文法的定义）来判断文法是否是LL(1)文法。解：首先消除左递归，得到文法G(Declist)：DeclistDecl DeclistDeclist；Decl DeclistDeclIdList：TypeIdListid IdListIdList，id ListTypeScalarTypearray(ScalarTypeList) of TypeSca

46、larTypeidBound.BoundBoundSign IntLiteralidSign+-ScalarTypeListScalarType ScalarTypeListScalarTypeList，ScalarType ScalarTypeList显然，改造后的文法没有左公共因子，计算每个非终结符的FIRST集合和FOLLOW集合如下：FIRST(Declist)=idFIRST(Declist)=；，FIRST(Decl)=idFIRST(IdList)=idFIRST(IdList)=；，FIRST(Type)=id，+，-，IntLiteral，arrayFIRST(ScalarT

47、ype)=id，+，-，IntLiteralFIRST(Bound)=id，+，-，InLiteralFIRST(Sign)=+，-，FIRST(ScalarTypeList)=id，+，-，IntLiteral FIRST(ScalarTypeList)=，FOLLOW(Declist)=#FOLLOW(Declist)=#FOLLOW(Decl)=id，；FOLLOW(IdList)=：FOLLOW(IdList)=：FOLLOW(Type)=id，；FOLLOW(ScalarType)=id，；，），FOLLOW(Bound)=id，；，），.FOLLOW(Sign)=IntLiteralFOLLOW(ScalarTypeList)=)FOLLOW