北方工业大学编译原理习题集（精编版）

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

2、 2 =2、11*2 *1 2 =6、令文法 g6 为 ndnd，d 0 1 2 3 4 5 6 7 891、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=

3、>nd=>ndd=>nddd=>dddd=>0ddd=>01dd=>012d=>0127 n=>nd=>dd=>3d=>34 n=>nd=>ndd=>ddd=>5dd=>56d=>568句 子 0127 、 34 和 568 的 最 右 推 导 ： n=>nd=>n7=>nd7=>n27=>nd27=>n127=>d127=>0127n=>nd=>n4=>d4=>34 n=>nd=>n8=>nd8=

4、>n68=>d68=>5687、写一个文法，使其语言是奇数集，且每个奇数不以0 开头。分析：此题要构造一个文法，由它产生的句子是奇数，且不以0 开头。也就是说它的每个句子都以1、3、5、7、9 中某数结尾。如果数字只有一位，那么满足要求；如果有多位，那么要求第一位不能是0；而中间有多少位，每位是什么数字那么没有要求。 因此我们可以把这个文法分3 局部完成， 分别用 3 个非终结符来产生句子的第一位、中间局部和最后一位。引入几个非终结符，其中，一个用作38 / 35产生句子的开头，可以是1 到 9 中的数，不包括 0；一个用来产生句子的结尾， 为奇数；另一个那么用来产生以非0

5、整数开头后面跟任意多个数字的数字串，进展分解之后，这个文法就很好写了。解：g(s)：a2 4 6 8 d b a0c cbad 13579 s cdd8、令文法为 e t e+ te-t tft*ft/ff(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*i e => t => t*f => f*f => i*f

6、 => i*(e) => i*(e+ t) => i*(t+ t)=> i*(f+ t) => i*(i+ t) => i*(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*i e => t => t*f => f*f => f*(e) => f*(e+t)=> f*(e+ f) => f*(e+ i)=> f*(t+i) => f*(

7、f+i) => f*(i+i) => i*(i+ i)（2） 语法树：eeee+te+te-te+tftt* tfifffiiife-tfiffiiii9、证明下面的文法是二义的：sisesis i分析：根据文法二义性定义，如果要证明该文法是二义的，必须找到一个句子，使该句子具有两个不同的最右推导或两个不同的语法树。我们首先分析这个文 法，根据我们对程序语言的了解， 不难发现这个文法应该是用来表示ifelse 结构的用“ i 表示“ if 或语句集，用e 代表 else 。因此我们就要到ifelse结构中去找二义性。我们知道，程序语言一般都规定else局部是和它前面离它最近的没有被

8、匹配的if语句进展匹配。而上面的这个文法表达不出这种 限制，因此我们可以找这样一个句子，在else前面有两个 if 如句子 iiiei， else 和不同的 if进展匹配时就会产生不同的语义。解：考虑句子 iiiei，存在如下两个最右推导：s=>ises=>isei=>iisei=>iiiei s=>is=>iises=>iisei=>iiiei 由此该文法是二义的。10、把下面文法改为无二义的：s ss(s) ()分析：此题给出的文法是二义的，关键在于s ss是产生二义性的根源。我们将该产生式改造成等价的递归结构，消除二义性。解： sts t，

9、 t (s) ()111、给出下面语言的相应文法： l =a nbnci n1，i 0 ，lin n2 =a b c n1，i 0n n m ml3 =a b a b n，m0n m m nl4 =1 0 1 0 n，m0n ni分析：语言 l1 要求 a 和 b 的个数一样多，且至少为一个；c 的个数为 0 个以上。因此我们可用一个非终结符去生成a b 串，用另外一个非终结符去生成c 。n ni语言 l2 要求 b 和 c 的个数一样多， 因此可用一个非终结符去生成b c ，而使用另外一个非终结符去生成a 。因此可以模仿 l1 生成 l2。n n m mn nm m对于 l3，可将 a b

10、a b 分两段考虑，即 a b 和 a b ，然后用两个非终结符分别去产生他们。l4 不能采用分段处理的方式，它要求中间的0 和 1 的个数一样，而且一前一后的 0 和 1 的个数一样。对于这种题型我们可以采用从里向外扩展的方式进展， 即先用一个非终结符生成处于中间的m个 0 和 m个 1，然后，使用另外一个非终结符在该串的根底上扩大前后的n 个 0 和 n 个 1。解：l1 的文法： sac； a aabab；ccc l2 的文法： sab； a aa； b bbcbc l3 的文法： sab； a aab； babbl4 的文法： s 1s0a；a0a1；第三章词法分析1、编写一个对于 p

11、ascal 源程序的预处理程序。 该程序的作用是， 每次被调用时都将下一个完整的语句送进扫描缓冲区，去掉注释行，同时要对源程序列表打印。2、请给出以下 c+程序段中的单词符号与其属性值。int cint： nmuldiv int n1，int n2ifn3= =0 return 0；else returnn1*n2 /n3 ；3、用类似 c或 pascal 的语言编写过程getchar， getbc和 concat。4、用某种高级语言编写并调试一个完整的词法分析器。5、6、令 a、b 和 c 是任意正规式，证明以下关系成立： a a=a(a*)*= a* a*= a a* (ab)*a=a(b

12、a)*(a b)*=(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) )*0=l( ) l(a)(l(a)(l(a)12 (l(a)(l(a)12334=l( ) (l(a) (l(a)=(l(a)*=l(a*)(l(a)(l(a)即： l( a a*)=l(a*)，所以有： a*= a a*4、(ab)*a=a(ba)*利用正

13、规式的分配率和结合律直接推导。231(ab)*a=(ab) 0(ab) 1 (ab) 2(ab) 3)a= a (ab)a(ab)a(ab) a1=a a (ba) a (ba)12a (ba) 323=a( (ba) (ba)=a(ba)*(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(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

14、) l(b) 故:l(a)*(l(a) l(b)*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)*故得:(l(a)*l(b)*)*(l(a) l(b)*那么由得 :(l(a)l(b)*=(l(a)*l(b)*)*由于 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)

15、 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*综合上述两种结论，最后得：(a b)*=(a*b*)*=(a*b*)*6、a=baa 当且仅当 a=a*b7、构造以下正规式相应的dfa1(0 1)*1011(1010* 1(010)*1)*00*10*10*10*(00 11)*(0110)(00 11)*(01 10

16、)(00 11)*)*解：(1) 、1(0 1)*101第一步：根据正规式构造nfa，先引入初始状态x 和终止状态 y：x1(0 1)*101y再对该转换图进展分解，得到分解后的nfa如以下图：0x112314051y1第二步：对状态x1 ，2，32 ，32 ，3，42 ，3，52 ，3，4，ynfa进展确定化，获得状态转换矩阵：0?2 ，32 ，32 ，3，52 ，32 ，3，511 ， 2， 32 ， 3， 42 ， 3， 42 ， 3， 42 ， 3， 4，y2 ， 3， 4根据转换矩阵获得相应的dfa：00110210113045011第三步：化简该dfa，获得最简的 dfa即为所求。

17、首先根据是否终止状态将所有状态分为两个集合 0 ， 1，2，3，4 和5 ，这里集合5 已经不可划分，只需考虑集合 0 ，1，2，3， 4 。0 ，1，2，3，4 0 =2 ，4，- ，0 ，1，2，3，4 1=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，3 0=2 ，4

18、，不属于同一个集合，因此要对集合1 ，2，3 进展进一步划分，划分结果为5 个集合： 0 ，1 ，2 ，3 ，4 ，5 。检查集合 1 ， 2 ，1 ，2 0 =2 ，1 ， 2 1=3，不需要进展进一步划分。所以最终划分结果为5 个集合： 0 ，1 ，2 ，3 ，4 ，5 。所以，最终所求dfa如以下图示：001110130450112、1(1010* 1(010)*1)*03、0*10*10*10*4、(00 11)*(0110)(00 11)*(01 10)(00 11)*)*8、给出下面正规表达式：（1） 以 01 结尾的二进制数串；（2） 能被 5 整除的十进制整数；（3） 包含奇数

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

20、 这 10 个数字组成的字符串，并且不能以0 开头整数“ 0除外，要求能被 5 整除，那么该串必须以 0 或者 5 结尾。根据分析，可以把此题分成两种情况考虑：一种情况时该整数只有一位，那么该整数有0 和 5 两种可能；另一种情况是该整数有多位，那么该整数可以分成三局部考虑：一是第一位必须不为0；二是最后一位必须为 0 或 5；三是中间局部可有可无，并且可以由0 到 9 之间任意数字构成，所以所求为 (1 23456789)(0 123456789)*(0 5)(0 5) 。3包含奇数个 1 或奇数个 0 的二进制数串；此题求二进制串，并且要求包含奇数个0 或奇数个 1，由于 0 和 1 都可

21、以在二进制串中任何地方出现，所以此题只需要考虑一种情况，另一种情况也可 以类似求得。考虑包含奇数个0 的字符串：由于只关心0 的个数的奇偶数，我们可以把二进制串分成多段来考虑，第一段为二进制串的开场到第一个0为止，这一段包含一个0，并且 0 的前面有 0 个或多个 1。对于剩下的二进制串按照每段包含两个0 的方式去划分，即以0 开场，以 0 结尾，中间可以有 0 个或多个 1。如果一个二进制串被这样划分完后，剩下的局部如果全部 是全 1 串这些全 1 串在前面划分的串之间或最后 ，那么该二进制串就有奇数个 0，所以该二进制串可以这样描述：以第一段1*0 开场，后面由全1 串1* 以与包含两个0

22、 的串 01*0 组成，所以包含奇数个0 的正规表达式为 1*0101*0* 。所以此题所求为1*0101*0* 0*1010*1 *。4英文字母组成的所有字符串，要求符号串中的字母依照字典序排列；5没有重复出现的数字的数字符号串的全体；6最多有一个重复出现的数字的数字符号串的全体；7不包含子串 abb 的由 a 和 b 组成的符号串的全体。9、对下面情况给出dfa与正规表达式：10 ，1 上的含有子串 010 的所有串；20 ，1 上不含子串 010 的所有串。解：1、2、直接写出满足条件的正规表达式。考虑满足条件的字符串中的 1：在串的开场局部可以有 0 个或多个 1，串的尾部也可以有 0

23、 个或多个 1，但串的中间只要出现 1 那么至少在两个以上，所以满足条件的正规表达式为 1*(0 111*)*1* 。所求的 dfa如以下图所示：100sa11b10、一个人带着狼、山羊和白菜在一条河的左岸。有一条船，大小正好能装下这个人和其他三件东西中的一件。人和他的随行物都要过到河的右岸。人每次只能将一件东西摆渡过河。但假设人将狼和羊留在同一岸而无人照顾的话，狼将把羊吃掉。类似地，假设羊和白菜留下来无人照看，羊将会吃掉白菜。请问是否有可能渡过河去，使得羊和白菜都不被吃掉？如果可能，请用有限自动机写出渡河的方法。解：11、12、将图 3.18 的a和 b分别确定化和最小化。aa， b0a1(

24、a)abba 023baaab145bbaa(b)解：1、图a中为一个 nfa，所以需要先对它进展确定化，得到dfa，然后再对 dfa进展最小化。首先进展确定化，如下两个表所示：状态ab状态ab00 ，110120 ，10 ，1111210?20根据状态转换矩阵得到如以下图所示的dfa：a01abab2化简后的 dfa为：ab02a2、题中所给即为一个dfa，不需要确定化，只对它进展最小化即可。首先将状态划分为两个集合0 ， 1 ，2 ，3， 4， 5 。有0 ，1 a=1 ，0 ， 1 b=2 ，4 和2 ， 3， 4， 5 a=1 ，3，0， 5 ，2 ， 3， 4， 5 b=2 ， 3，

25、 4， 5 ，所以可以进一步划分为 0 ，1 ，2 ，4 ，3 ，5 ，然后有 0 ，1 a=1 ，0 ，1 b=2 ， 4 ，2 ，4 a=1 ，0 ，2 ，4 b=3 ，5 ，3 ，5 a=3 ，5 ，3 ，5 b=2 ，4 。因此， 最后划分结果是 0 ， 1 ，2 ，4 ，3 ，5 。最小化后的 dfa如以下图所示：aabb012ab13、1给出描述 c浮点数的 dfa；14、构造一个 dfa，它承受 =0 ，1 上所有满足如下条件的字符串：每个1都有 0 直接跟在右边。分析：对这类题型的固定解法分4 步进展： 首先根据语言写出正规表达式；然后根据正规表达式构造相应的nfa；然后，对

26、nfa进展确定化得到dfa；最后对 dfa 化简得到最简 dfa。第一步：写出正规表达式。根据题意，该 dfa承受的字符串由 0 和 1 组成， 并且每个 1 的后面都有 0 直接跟在右边，因此，可以将该字符串理解为由 0 和10 构成的串，那么相应的正规表达式就是 (0 10)* 。第二步：构造 nfa。首先得出以下图：x(010)*y然后对上图进展分解后得到如以下图所示的nfa。201x1y0第三步：确定化，得到dfa。确定化结果如表14.1 所列；给状态编号，得到表 14.2 所示的状态转换矩阵：状态01状态01x，1，y1 ，y20121 ，y1 ，y211221 ，y表 14.1状态

27、转换矩阵?2表 14.21新的状态转换矩阵根据状态转换矩阵得到dfa如以下图所示：00101102第四步：对该 dfa进展最小化。其分析过程如下：0 ，1 ，20 ，1 0=1 ，0 ，1 1=20 ，1 ，2最小化后的 dfa如下图，该 dfa即为所求。0101015、给定右线性文法 g： s 0s1s 1a0b a 1c1b 0c0c 0c1c 0 1求出一个与 g等价的左线性文法。分析：根据右线性文法求左线性文法没有直接的方法，但可以通过状态转换 图去转换。可以先求出文法 g的状态转换图， 再根据状态转换图写出相应的左线性文法。文法 g对应的状态转换图如下所示：0， 1s0， 111ac

28、001b00， 1z对状态转换图进展确定化，得到状态转换矩阵：状态s0s，b1s，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如下：000013110102141还可以对上图的dfa进展化简，状态 3 和 4 可以合并，化简后的dfa如以下图所示：0， 10sa0t1101b不难看出，该 dfa承受的语言是 0 ，1 上包含 00 或 11 的字符串。根据化简后的 dfa，我们可以写出相应的左线性文法g：

29、t a0b1 t0t1 a b00b a1116、* 非形式的说明17、* 下面的字集是否为正规集？或写出其正规式，或给出否证。n n（1） l1 =a b n0 ；（2） l2 =x ；（3） l3 = 。18、假定 l 和 m都是正规集：（1） 证明 lm、lm和 m补集也是正规的；（2） l是 l 中每个字的逆转，证明l 也是正规的。19、写出描述 ansi c 的单词符号的 lex程序。20、假定有正规定义式a0ab a1a0 a 0anan-1 a n-1考虑词形 an（1） 把 an 中所有简名都换掉，最终所得的正规式的长度是多少？（2） 字集 an 的元素是什么？把它们非形式的表

30、示成n 的函数；（3） 证明识别 an 的 dfa只需用 2n+1 个状态就足够了。21、把 lex的“动作成分加以充实使得可用它来编写语法制导编辑器。第四章语法分析自上而下分析1、考虑下面的文法g1：s a (t) t t， ss1消去 g1 的左递归。然后对每个非终结符，写出不带回溯的递归子程序。2经改写后的文法是否是ll(1) 的？给出它的预测分析表。解：1按照 t、s的顺序消除左递归，得到文法：g(s)sa (t) tstt， st对于非终结符s,t,t 的递归子程序如下： procedure s;beginif sym = a or sym = then advanceelse if

31、sym = ( then begin advance ;t;ifsym =) then advance elseerrorendelse error ends;procedure t;begins; t ;ends;procedure t beginif sym =, then begin advance ;endsends;s; t 2计算每个非终结符的first集合和 follow集合：firsts=a ， ( firstt=a ， ( firstt= ， follows=) ， #followt=) followt=)从而可见改造后的文法符合ll(1) 文法的充分必要条件，所以是该文法的

32、预测分析表ll(1) 的。as->as->t->s t t->s t (s->(t)t->s t ),#st tt-> t->,st2、对下面的文法 g： e tee +et ftt t f pff *f p (e) a b（1） 计算这个文法的每个非终结符的first和 follo。w（2） 证明这个文法是ll(1) 的。（3） 构造它的预测分析表。（4） 构造它的递归下降分析程序。分析：对于这类题目，我们首先应当检查文法是否符合ll(1) 文法的条件， 根据需要，先通过消除左递归、提取右公因子的方法， 把文法改造成符合ll(1) 文法的条件，

33、在此根底上，我们才能构造出不带回溯的递归下降识别程序。注意，此题在构造子程序时，对于每个产生式候选，在调用第一个非终结符对应的子程序之前，检查了首符集。解：（1） 计算每个非终结符的first集合和 follow集合如下： firste=( ，a，b， firste=+ ，firstt=( ， a， b， firstt=( ，a，b， firstf=( ， a， b， first f =* ， firstp=( ， a， b， followe=# ，)followe=# ， ) followt=+ ，) ，# followt=+ ，) ， #follo wf =( ，a，b， +，) ，# f

34、ollowf=( ， a， b， +，) ，# followp=* ，( ，a，b， +，) ，#（2） 本文法是 ll ( 1 )文法。证明：通过观察可知文法中不含有左递归，满足ll (1)文法定义的第一个条件。考虑以下产生式：e +ett f *f p(e) ab 因为：first+e first =+ = ?firste followe=+ # ，)=?firstt first =( ，a，b， = ?firstt followt=( ， a， b， + ，) ，#= ?first*f first =* = ?firstf followf=* ( ，a， b， +，) ，#=?first

35、 e firsta firstb first =?所以该文法是 ll(1) 文法。（3） 构造其预测分析表： 预测分析表+*()ab#ee+eeettfttftttttttttte et eet eetet ee->fttftttttf fpffpfppffpffff*fffffffpp(e)papbp（4） 构造其递归下降分析程序：proceduree;begint ;eend ;proceduree ; beginifsym = + thenbegin acvance ;eendend ;proceduret ; beginf ; tend ;proceduret ; beginif

36、symfirst ( t ) then telseif sym =* thenerrorend ;proceduref ; beginifsymfirst ( p )p; f;end ;procedurefbeginif sym = * thenbegin advance ;fend end;procedurepbeginif sym = aorsym = b or sym = then acvanceelseif sym = (thenbegin advance ;e ;ifsym = )then advance elseerror endelseerrorend;3、下面文法中，哪些是ll

37、(1) 的，说明理由。1、sabc aa bb2、sab aab bb3、sabbaaa bb4、saseb bbbec ccced分析：判断文法是否是ll(1) 的，要根据ll(1) 文法的条件逐一检查：首先要确定文法不含左递归；随后计算文法的各非终结符x的首符集 firstx和随符集followx。首先要理解这两个集合的计算方法，特别要注意算法终止的条件：直到集合不再变化为止。也就是说，反复检查每一个产生式，直到从头到尾检查了所有产生式，而first集合和 follow集合都没有变化了，这时候计算才能完毕。最后根据ll(1) 文法的充分必要条件即ll(1) 文法定义来判断是否是 ll(1)

38、 文法。解：（1） 该文法不含左递归，计算每个非终结符的first集合和 follow集合如下：firsts=a ，b，c firsta=a ， firstb=b ， follows=#followa=b ， c followb=c可见该文法满足 ll(1) 文法的三个条件，是ll(1) 文法。（2） 该文法不含左递归，计算每个非终结符的first集合和 follow集合如下：first s =a ，b firsta=a ，b， firstb=b ， follo ws =# follo wa =b followb=b考虑 a a b，因为firstb follow a=b ? ，所以该文法不是

39、 ll(1) 文法。（3） 该文法不含左递归，计算每个非终结符的first集合和 follow集合如下：firsts=a ，b， firsta=a ， firstb=b ， follows=#followa=a ， b， #followb=a ， b， #考虑 aa 和 bb，因为firsta followa=a ?firstb followb=b ?所以该文法不是ll(1) 文法。（4） 该文法不含左递归，计算每个非终结符的first集合和 follow集合如下：firsts=a ，b，c，d firstb=b ，c，d first c =c ，d follo ws =e ， # follo

40、 wb =e ， # followc=e ， #可见该文法满足ll(1) 文法的三个条件，是ll(1) 文法。4、对下面文法： expr -expr expr (expr) varexprtail-expr varid vartail vartail (expr) 1、构造 ll(1) 分析表。2、给出对句子 id-id(id)的分析过程。分析：构造文法的预测分析表，通常应当按以下顺序进展：1、消除文法的左递归包括所有直接左递归和间接左递归 ；2、对消除左递归后的文法， 提取左公因子；3、对经过上述改造后的文法，计算它的每个非终结符的first集合和follow集合；4、根据 first集合和

41、 follow集合构造预测分析表。第一步对文法 g的每个产生式 a 执行第一步和第三步； 第二步对每个终结符 afirst() ，把 a 加至 ma，a 中；第三步假设 first() ，那么对任何 bfollow(a把) a 标上“出错标志。解：a 加至 ma，b 中；第四步把所有无定义的ma，1、计算每个非终结符的first集合和 follow集合如下： first(expr)=-，( ，idfirst(exprtail)=-， first(var)=idfirst(vartail)=(，follow(expr)=)， #follow(exprtail)=) ，# follow(var)=

42、-，) ，#follow(vartail)=- ， #构造其预测分析表如下：-id()# exprexpr- exprexpr exprexpr-( expr)exprtailexprtail-exprvarvaridvartailexprtail exprtail vartailvartailvartailvartailvartail(expr)2、句子 id-id(id)的分析过程如下：步骤0符号栈# expr输入串id-id(id)所用产生式#1# exprtail varid-id(id)exprvar exprtail#2# exprtail vartail idid-id(id)#

43、varid vartail3# exprtail vartail-id(id) #4# exprtail-id(id) #vartail 5# expr -id(id) #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) #18#exprtail)exprtailvartail) #19#

44、exprtail ) ) exprtail) #vartail 20# exprtail ) ) #exprtail21# exprtail ) #22# exprtail#23#exprtailsuc121314151617# exprtail ) expr (# exprtail ) expr# exprtail ) ) expr ( # exprtail ) ) expr# exprtail ) ) exprtal var#exprtail)exprtail(id) #(id) #(id) # id) #id) #id) #vartail (expr)exprvar exprtailva

45、rid vartailvartail id5、把下面文法改写为ll(1) 的：declistdeclist；decl decl decl idlist：typeidlistidlist，id idtypescalartype array(scalartypelist) of type scalartype id bound.boundboundsign intliteralid sign +- scalartypelistscalartypelist，scalartype scalartype分析：此题主要考察理解和运用消除文法的左递归、提取公因子等算法的能力，为判断文法是否是ll(1) 文法

46、，还要计算文法的first集合和 follow集合。消除文法的左递归的根本思想是，将文法规那么中的左递归结构变换成等价的右递归结构。 提取左公因子的算法， 是对包含公共左因子的产生式候选，反复提取左因子， 就能够把每个非终结符 包括新引进者 的所有候选首符集变成为两两不相交。 消除文法的左递归、 提取左公共因子后， 再计算文法的各非终结符x的首符集 firstx和随符集follow(x，) 然后根据ll(1) 文法的充分必要条件即 ll(1) 文法的定义来判断文法是否是ll(1) 文法。解：首先消除左递归，得到文法g(declist)：declistdecl declistdeclist； d

47、ecl declistdecl idlist：type idlistid idlistidlist， id listtypescalartype array(scalartypelist) of type scalartype id bound.boundbound sign intliteral id sign +- scalartypelistscalartype scalartypelistscalartypelist， scalartype scalartypelist显然，改造后的文法没有左公共因子，计算每个非终结符的first 集合和follow集合如下：first(declist)=id first(declist )= ；， first(decl)=id first(idlist)=id first(idlist)= ；， first(type)=id，+，- ，intliteral，arrayfi