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

编译原理课后习题（修订版）

第二章 高级语言及其语法描述

3、何谓“标识符”，何谓“名字”，两者的区别是什么？

解：标识符是高级语言中定义的字符串，一般是以英文字母（包括大小写字母）或下划线开头的，由数字、字母和下划线组成的一定长度的字符串，它只是一个标志，没有其他含义。名字是用标识符表示的，但名字不仅仅是一个字符串，它还具有属性和值。 4、令 ＋、* 和↑代表加、乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1＋1*2↑*1↑2的值： （1）、优先顺序（从高至低）为＋、* 和↑，同级优先采用左结合。 （2）、优先顺序为↑、＋、*，同级优先采用右结合。 解： （1）、1＋1*2↑*1↑2 = 2*2↑*1↑2 = 4↑*1↑2 = 4↑↑2 = （2）、1＋1*2↑*1↑2 =

6、令文法G6为N→D∣ND，D→0∣1∣2∣3∣4∣5∣6∣7∣8∣9 （1）、G6的语言L(G6)是什么？ （2）、给出句子0127、34和568的最左推导和最右推导。

分析：根据产生式N→D∣ND可以看出，N最终可推导出1个或多个（可以是无穷多个）D，根据产生式D→0∣1∣2∣3∣4∣5∣6∣7∣8∣9可以看出，每个D可以推导出0至9中的某一个数字。因此，N最终推导出的是由0到9这10个数字组成的字符串。 解： （1）、L(G6)是由0到9这10个数字组成的字符串。 （2）、句子0127、34和568的最左推导： N=>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=>0127 N=>ND=>N4=>D4=>34 N=>ND=>N8=>ND8=>N68=>D68=>568

7、写一个文法，使其语言是奇数集，且每个奇数不以0开头。

分析：本题要构造一个文法，由它产生的句子是奇数，且不以0开头。也就是说它的每个句子都以1、3、5、7、9中某数结尾。如果数字只有一位，则满足要求；如果有多位，则要求第一位不能是0；而中间有多少位，每位是什么数字则没有要求。因此我们可以把这个文法分3部分完成，分别用3个非终结符来产生句子的第一位、中间部分和最后一位。引入几个非终结符，其中，一个用作产

生句子的开头，可以是1到9中的数，不包括0；一个用来产生句子的结尾，为奇数；另一个则用来产生以非0整数开头后面跟任意多个数字的数字串，进行分解之后，这个文法就很好写了。 解： G(S)：A→2∣4∣6∣8∣D B→A∣0 C→CB∣A D→1∣3∣5∣7∣9 S→CD∣D

8、令文法为E→T∣E+ T∣E-T T→F∣T*F∣T/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*i E => T => T*F => F*F => i*F => 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*(F+i) => F*(i+i) => i*(i+ i) （2） 语法树：

E

E

+

T

E

E

+

T

E

E

E -

T F E + T

F i

T T * F

- T

T F

F i

F i

i F i

F

i

F i

i

i

9、证明下面的文法是二义的：S→iSeS∣iS∣i

分析：根据文法二义性定义，如果要证明该文法是二义的，必须找到一个句子，使该句子具有两个不同的最右推导或两个不同的语法树。我们首先分析这个

文法，根据我们对程序语言的了解，不难发现这个文法应该是用来表示if?else?结构的（用“i”表示“if”或语句集，用e代表else）。因此我们就要到if?else?结构中去找二义性。我们知道，程序语言一般都规定else部分是和它前面离它最近的没有被匹配的if语句进行匹配。而上面的这个文法体现不出这种限制，因此我们可以找这样一个句子，在else前面有两个if（如句子iiiei），else和不同的if进行匹配时就会产生不同的语义。

解：考虑句子iiiei，存在如下两个最右推导： S=>iSeS=>iSei=>iiSei=>iiiei S=>iS=>iiSeS=>iiSei=>iiiei 由此该文法是二义的。

10、把下面文法改为无二义的：S→SS∣(S)∣( )

分析：本题给出的文法是二义的，关键在于S→SS是产生二义性的根源。我们将该产生式改造成等价的递归结构，消除二义性。 解：S→TS∣T，T→(S)∣( )

11、给出下面语言的相应文法： L1={anbnci∣n≥1，i≥0}， L2={aibncn∣n≥1，i≥0} L3={anbnambm∣n，m≥0} L4={1n0m1m0n∣n，m≥0}

分析：语言L1要求a和b的个数一样多，且至少为一个；c的个数为0个以上。因此我们可用一个非终结符去生成anbn串，用另外一个非终结符去生成ci。

nn

语言L2要求b和c的个数一样多，因此可用一个非终结符去生成bc，而使用另外一个非终结符去生成ai。因此可以模仿L1生成L2。

对于L3，可将anbnambm分两段考虑，即anbn和ambm，然后用两个非终结符分别去产生他们。

L4不能采用分段处理的方式，它要求中间的0和1的个数相同，而且一前一后的0和1的个数相同。对于这种题型我们可以采用从里向外扩展的方式进行，即先用一个非终结符生成处于中间的m个0和m个1，然后，使用另外一个非终结符在该串的基础上扩充前后的n个0和n个1。 解：

L1的文法：S→AC；A→aAb∣ab；C→cC∣ε L2的文法：S→AB；A→aA∣ε；B→bBc∣bc L3的文法：S→AB；A→aAb∣ε；B→aBb∣ε L4的文法： S→1S0∣A； A→0A1∣ε；

第三章 词法分析

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。

4、用某种高级语言编写并调试一个完整的词法分析器。

5、证明3.3.1中关于正规式的交换律、结合律等五个关系。

6、令A、B和C是任意正规式，证明以下关系成立： A∣A=A (A*)*= A*

A*=ε∣A A*

(AB)*A=A(BA)*

(A∣B)*=(A*B*)*=(A*∣B*)* A=b∣aA当且仅当A=a*b 证明： （1）、A∣A=A L(A∣A)=L(A)∪L(A)=L(A)，所以有A∣A=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(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∣? =Aε∣A (BA)1∣A (BA)2∣A (BA)3∣?

=A(ε∣(BA)1∣(BA)2∣(BA)3∣?) =A(BA)* 即：(AB)*A=A(BA)* （5）、(A∣B)*=(A*B*)*=(A*∣B*)* 证明:先证(A∣B)*=(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)∪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)*)*

由于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*）*

综合上述两种结论，最后得：(A∣B)*=(A*B*)*=(A*∣B*)*

（6）、A=b∣aA当且仅当A=a*b

7、构造下列正规式相应的DFA 1(0∣1)*101

1(1010*∣1(010)*1)*0 0*10*10*10*

(00∣11)*((01∣10)(00∣11)*(01∣10)(00∣11)*)* 解：

(1)、1(0∣1)*101

第一步：根据正规式构造NFA，先引入初始状态X和终止状态Y：

1(0∣1)*101 X Y

0 1 ε ε

再对该转换图进行分解，得到分解后的NFA如下图：

X 1 2 3 1 4 0 5 1 Y 1

第二步：对NFA进行确定化，获得状态转换矩阵： 状态 0 1 {X} ? {1，2，3} {1，2，3} {2，3} {2，3，4} {2，3} {2，3} {2，3，4} {2，3，4} {2，3，5} {2，3，4} {2，3，5} {2，3} {2，3，4，Y} {2，3，4，Y} {2，3，5} {2，3，4} 根据转换矩阵获得相应的DFA： 0 1 0 0 1 2 1 3 0 0 1 4 1 0 5 1 1 第三步：化简该DFA，获得最简的DFA即为所求。

首先根据是否终止状态将所有状态分为两个集合{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}，不属于同一个集合，因此要对集合{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如下图示：

0 1 0 1 1 3 0 0 1 4 1 0 5 1

（2）、1(1010*∣1(010)*1)*0

（3）、0*10*10*10*

（4）、(00∣11)*((01∣10)(00∣11)*(01∣10)(00∣11)*)*

8、给出下面正规表达式：

（1） 以01结尾的二进制数串； （2） 能被5整除的十进制整数；

（3） 包含奇数个1或奇数个0的二进制数串；

（4） 英文字母组成的所有字符串，要求符号串中的字母依照字典序排列； （5） 没有重复出现的数字的数字符号串的全体；

（6） 最多有一个重复出现的数字的数字符号串的全体； （7） 不包含子串abb的由a和b组成的符号串的全体。 解：

（1）以01结尾的二进制数串； 分析题意，要求的是二进制数串，即由0和1构成的串，并且必须以01结尾，所以本题可以分两步完成：一部分实现由0和1构成的任意串，一部分即01，然后将它们连结在一起就可以了，所以所求为(1︱0)*01。 （2）能被5整除的十进制整数； 分析题意，本题要求的是十进制整数，也就是由0至9这10个数字组成的字符串，并且不能以0开头（整数“0”除外），要求能被5整除，则该串必须以0或者5结尾。根据分析，可以把本题分成两种情况考虑：一种情况时该整数只有一位，则该整数有0和5两种可能；另一种情况是该整数有多位，则该整数可以分成三部分考虑：一是第一位必须不为0；二是最后一位必须为0或5；三是中间部分可有可无，并且可以由0到9之间任意数字构成，所以所求为(1︱2︱3︱4︱5︱6︱7︱8︱9) (0︱1︱2︱3︱4︱5︱6︱7︱8︱9)*(0︱5)(0︱5)。

（3）包含奇数个1或奇数个0的二进制数串； 本题求二进制串，并且要求包含奇数个0或奇数个1，由于0和1都可

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

（4）英文字母组成的所有字符串，要求符号串中的字母依照字典序排列；

（5）没有重复出现的数字的数字符号串的全体；

（6）最多有一个重复出现的数字的数字符号串的全体；

（7）不包含子串abb的由a和b组成的符号串的全体。

9、对下面情况给出DFA及正规表达式： （1）{0，1}上的含有子串010的所有串； （2）{0，1}上不含子串010的所有串。 解： （1）、 （2）、直接写出满足条件的正规表达式。考虑满足条件的字符串中的1：在串的开始部分可以有0个或多个1，串的尾部也可以有0个或多个1，但串的中间只要出现1则至少在两个以上，所以满足条件的正规表达式为1*(0∣111*)*1*。 所求的DFA如下图所示：

1 S 0A 1 1 B 0

10、 一个人带着狼、山羊和白菜在一条河的左岸。有一条船，大小正好能装下这个人和其他三件东西中的一件。人和他的随行物都要过到河的右岸。人每次只能将一件东西摆渡过河。但若人将狼和羊留在同一岸而无人照顾的话，狼将把羊吃掉。类似地，若羊和白菜留下来无人照看，羊将会吃掉白菜。请问是否有可能渡过河去，使得羊和白菜都不被吃掉？如果可能，请用有限自

11、

12、

动机写出渡河的方法。 解：

将图3.18的（a）和（b）分别确定化和最小化。

a a，b 0 a (a)

1

a b 0 a a a b b 4 b 5 a

b b a

2 3 1 a (b)

解： （1）、图（a）中为一个NFA，所以需要先对它进行确定化，得到DFA，然后再对DFA进行最小化。

首先进行确定化，如下两个表所示： 状态 a b 状态 a b {0} {0，1} {1} 0 1 2 {0，1} {0，1} {1} 1 1 2 {1} {0} ? 2 0 根据状态转换矩阵得到如下图所示的DFA：

0 b a a 1 b a 2

化简后的DFA为：

a b a 0 2

（2）、题中所给即为一个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，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如下图所示：

a ba bb a 1 2 0

13、 （1）给出描述C浮点数的DFA；

14、 构造一个DFA，它接受∑={0，1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。

分析：对这类题型的固定解法分4步进行：首先根据语言写出正规表达式；然后根据正规表达式构造相应的NFA；然后，对NFA进行确定化得到DFA；最后对DFA化简得到最简DFA。

第一步：写出正规表达式。根据题意，该DFA接受的字符串由0和1组成，并且每个1的后面都有0直接跟在右边，因此，可以将该字符串理解为由0和10构成的串，则相应的正规表达式就是(0︱10)*。 第二步：构造NFA。首先得出下图：

(0︱10)* X Y

然后对上图进行分解后得到如下图所示的NFA。

2 0 1 X ε 1 ε Y 0

第三步：确定化，得到DFA。确定化结果如表14.1所列；给状态编号，得到表14.2所示的状态转换矩阵： 状态 0 1 状态 0 1 {X，1，Y} {1，Y} {2} 0 1 2 {1，Y} {1，Y} {2} 1 1 2 {2} {1，Y} ? 2 1 表14.1 状态转换矩阵 表14.2 新的状态转换矩阵 根据状态转换矩阵得到DFA如下图所示：

0 1 2 0 1 0 1 0

第四步：对该DFA进行最小化。其分析过程如下： {0，1}，{2}

{0，1}0={1}，{0，1}1={2} {0，1}，{2}

最小化后的DFA如图所示，该DFA即为所求。

0 1 0 0 1

15、 给定右线性文法G： S→0S∣1S∣1A∣0B A→1C∣1 B→0C∣0

C→0C∣1C∣0∣1

求出一个与G等价的左线性文法。

分析：根据右线性文法求左线性文法没有直接的方法，但可以通过状态转换图去转换。可以先求出文法G的状态转换图，再根据状态转换图写出相应的左线性文法。文法G对应的状态转换图如下所示：

0，1 S 1 A 0 B 0 1 0，1 C 1 0，1 Z 0

对状态转换图进行确定化，得到状态转换矩阵： 状态 0 1 {S} {S，B} {S，A} {S，B} {S，B，C，Z} {S，A} {S，A} {S，B} {S，A，C，Z} {S，B，C，Z} {S，B，C，Z} {S，A，C，Z} {S，A，C，Z} {S，B，C，Z} {S，A，C，Z} 给状态编号，得到新的状态转换矩阵： 状态 0 1 0 1 2 1 3 2 2 1 4 3 3 4 4 3 4 根据状态转换矩阵获得DFA如下： 0 0 1 2 0 1 0 1 1 0 1 4 1 3 0

还可以对上图的DFA进行化简，状态3和4可以合并，化简后的DFA如下图所示：

0，1 0 0 S A 1 0 B T 1 1

不难看出，该DFA接受的语言是{0，1}上包含00或11的字符串。根据化简后的DFA，我们可以写出相应的左线性文法G’： T→A0∣B1∣T0∣T1 A→B0∣0 B→A1∣1

16、 *非形式的说明

17、 *下面的字集是否为正规集？或写出其正规式，或给出否证。

（1） L1={anbn∣n≥0}； （2） L2={x}； （3） L3={}。

18、 假定L和M都是正规集：

（1） 证明L∪M、L∩M和～M（补集）也是正规的； （2） L′是L中每个字的逆转，证明L也是正规的。

19、 写出描述ANSI C的单词符号的LEX程序。

20、 假定有正规定义式 A0→a∣b A1→A0 A0

??

An→An-1 An-1

考虑词形An

（1） 把An中所有简名都换掉，最终所得的正规式的长度是多少？ （2） 字集An的元素是什么？把它们非形式的表示成n的函数； （3） 证明识别An的DFA只需用2n+1个状态就足够了。

21、 把LEX的“动作”成分加以充实使得可用它来编写语法制导编辑器。

第四章 语法分析——自上而下分析

1、考虑下面的文法G1： S→a∣∧∣(T) T→T，S∣S （1）消去G1的左递归。然后对每个非终结符，写出不带回溯的递归子程序。 （2）经改写后的文法是否是LL(1)的？给出它的预测分析表。 解：

（1）按照T、S的顺序消除左递归，得到文法： G’(S)

S→a∣∧∣(T)

T→ST’

T’→，ST’ ∣ε

对于非终结符S,T, T’的递归子程序如下： Procedure S; Begin If sym = ‘a’ or sym = ‘^’ Then advance Else if sym = ‘(‘ Then begin Advance ; T; If sym = ’)’ Then advance Else error End Else error Ends;

Procedure T; Begin S; T’; Ends;

Procedure T’ Begin

If sym = ‘,’ Then begin Advance ; S; T’ Ends

ends;

? （2）计算每个非终结符的FIRST集合和FOLLOW集合： FIRST（S）={a，∧，( } FIRST（T）={a，∧，( } FIRST（T’）={，，ε} FOLLOW（S）={ )，’，’，#} FOLLOW（T）={ ) } FOLLOW（T’）={ ) }

从而可见改造后的文法符合LL(1)文法的充分必要条件，所以是LL(1)的。 该文法的预测分析表 a ^ ( ) , # S S->a S->^ S->(T) T T->S T’ T->S T’ T->S T’ T’->ξ T’ T->,S T’ 2、对下面的文法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） 构造它的递归下降分析程序。

分析：对于这类题目，我们首先应当检查文法是否符合LL(1)文法的条件，根据需要，先通过消除左递归、提取右公因子的方法，把文法改造成符合LL(1)文法的条件，在此基础上，我们才能构造出不带回溯的递归下降识别程序。注意，本题在构造子程序时，对于每个产生式候选，在调用第一个非终结符对应的子程序之前，检查了首符集。 解：

（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，∧，+，)，#} FOLLOW（P）={*，(，a，b，∧，+，)，#} （2） 本文法是LL ( 1 )文法。

证明： 通过观察可知文法中不含有左递归，满足LL (1)文法定义的第一

个条件。

考虑下列产生式： E’→+E∣ε T’→T∣ε F’→*F’∣ε P→(E)∣a∣b∣∧ 因为： 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）∩FIRST（b）∩FIRST（∧）= ? 所以该文法是LL(1)文法。 （3） 构造其预测分析表：

预测分析表 + * ( ) a b ^ E E?T E’ E?T E’ E?T E’ E?T E’ E’ ?ξ E’ E’?+E T’?FT’ T?FT’ T?FT’ T T ?FT’ T’?ξ T’?ξ T’?T T’ T’ ? T T’?T T’ ?T F?PF’ P?PF’ F?PF’ F F ?PF’ F’ ? ξ F’ ?*F’ F’ ? ξ F’?ξ F’?ξ F’?ξ F’?ξ F’ P P ?(E) P?a P?b P? ^ （4） 构造其递归下降分析程序： Procedure E; Begin T ; E’ End ;

Procedure E’ ; Begin If sym = ‘ + ’

# E’ ->ξ T’?ξ F’?ξ Then begin Acvance ; E End End ;

Procedure T ; Begin F ; T’ End ;

Procedure T’ ; Begin If sym ∈first ( T ) Then T

Else if sym = ‘*’ then error End ;

Procedure F ; Begin

If sym ∈first ( P ) P; F’; End ;

Procedure F’ Begin If sym = ‘ * ’ Then begin Advance ; F’ End End;

Procedure P Begin

If sym = ‘ a ’ or sym = ‘ b ‘ or sym = ‘ ^

Then acvance Else if sym = ‘ ( ‘ Then begin Advance ; E ;

If sym = ‘ ) ‘ Then advance Else error End

Else error

End;

3、下面文法中，哪些是LL(1)的，说明理由。 （1）、 S→Abc A→a∣ε B→b∣ε （2）、 S→Ab A→a∣B∣ε B→b∣ε （3）、 S→ABBA A→a∣ε B→b∣ε

（4）、 S→aSe∣B B→bBe∣C C→cCe∣d

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

（1） 该文法不含左递归，计算每个非终结符的FIRST集合和FOLLOW集

合如下：

FIRST（S）={a，b，c} FIRST（A）={a，ε} FIRST（B）={b，ε} FOLLOW（S）={#} FOLLOW（A）={b，c} FOLLOW（B）={c} 可见该文法满足LL(1)文法的三个条件，是LL(1)文法。

（2） 该文法不含左递归，计算每个非终结符的FIRST集合和FOLLOW集

合如下：

FIRST（S）={a，b} FIRST（A）={a，b，ε}

FIRST（B）={b，ε} FOLLOW（S）={#} FOLLOW（A）={b} FOLLOW（B）={b} 考虑A→a∣B∣ε，因为FIRST（B）∩FOLLOW（A）={b}≠?，所以该文法不是LL(1)文法。

（3） 该文法不含左递归，计算每个非终结符的FIRST集合和FOLLOW集

合如下：

FIRST（S）={a，b，ε} FIRST（A）={a，ε} FIRST（B）={b，ε} FOLLOW（S）={#} FOLLOW（A）={a，b，#} FOLLOW（B）={a，b，#} 考虑A→a∣ε和B→b∣ε，因为 FIRST（a）∩FOLLOW（A）={a}≠? FIRST（b）∩FOLLOW（B）={b}≠?

所以该文法不是LL(1)文法。

（4） 该文法不含左递归，计算每个非终结符的FIRST集合和FOLLOW集

合如下：

FIRST（S）={a，b，c，d} FIRST（B）={b，c，d} FIRST（C）={c，d} FOLLOW（S）={e，#} FOLLOW（B）={e，#} FOLLOW（C）={e，#} 可见该文法满足LL(1)文法的三个条件，是LL(1)文法。

4、对下面文法： Expr→-Expr

Expr→(Expr)∣Var ExprTail→-Expr∣ε Var→id VarTail VarTail→(Expr)∣ε （1）、构造LL(1)分析表。 （2）、给出对句子id--id((id))的分析过程。

分析：构造文法的预测分析表，通常应当按下列顺序进行：（1）、消除文法的左递归（包括所有直接左递归和间接左递归）；（2）、对消除左递归后的文法，提取左公因子；（3）、对经过上述改造后的文法，计算它的每个非终结符的FIRST集合和FOLLOW集合；（4）、根据FIRST集合和FOLLOW集合构造预测分析表。 第一步对文法G的每个产生式A→α执行第一步和第三步；第二步对每个终结符a∈FIRST(α)，把A→α加至M[A，a]中；第三步若ε∈FIRST(α)，则对任何b∈FOLLOW(A)把A→α加至M[A，b]中；第四步把所有无定义的M[A，a]标上“出错标志”。

解： （1）、计算每个非终结符的FIRST集合和FOLLOW集合如下： FIRST(Expr)={-，(，id} FIRST(ExprTail)={-，ε} FIRST(Var)={id}

FIRST(VarTail)={(，ε} FOLLOW(Expr)={)，#} FOLLOW(ExprTail)={)，#} FOLLOW(Var)={-，)，#}

FOLLOW(VarTail)={-，∣，#} 构造其预测分析表如下： - id ( ) # Expr Expr→- Expr Expr Expr Expr→ -( Expr) ExprTail ExprTail→-Expr ExprTail→ε ExprTail→ε Var Var→id VarTail VarTail VarTail→ε VarTail→VarTail→ε VarTail→ε (Expr) （2）、句子id--id((id))的分析过程如下： 步骤 符号栈 输入串 所用产生式 0 # Expr id--id((id)) # 1 # ExprTail Var id--id((id)) # Expr→Var ExprTail 2 # ExprTail VarTail id id--id((id)) # Var→id VarTail 3 # ExprTail VarTail --id((id)) # 4 # ExprTail --id((id)) # VarTail→ε 5 # Expr - --id((id)) # ExprTail→-Expr 6 # Expr -id((id)) # 7 # Expr - -id((id)) # Expr→-Expr 8 # Expr id((id)) # 9 # ExprTail Var id((id)) # Expr→Var ExprTail 10 # ExprTail VarTail id id((id)) # Var→id VarTail 11 # ExprTail VarTail ((id)) # 12 # ExprTail ) Expr ( ((id)) # VarTail→(Expr) 13 # ExprTail ) Expr (id)) # 14 # ExprTail ) ) Expr ( (id)) # 15 # ExprTail ) ) Expr id)) # 16 # ExprTail ) ) ExprTal Var id)) # Expr→Var ExprTail 17 # ExprTail ) ) ExprTail VarTail id id)) # Var→id VarTail 18 # ExprTail ) ) ExprTail VarTail )) # 19 # ExprTail ) ) ExprTail )) # VarTail→ε

20 21 22 23 suc

# ExprTail ) ) # ExprTail ) # ExprTail # )) # ) # # # ExprTail→ε ExprTail→ε

5、把下面文法改写为LL(1)的： Declist→Declist；Decl∣Decl Decl→IdList：Type IdList→IdList，id∣id

Type→ScalarType∣array(ScalarTypeList) of Type ScalarType→id∣Bound..Bound Bound→Sign IntLiteral∣id Sign→+∣-∣ε

ScalarTypeList→ScalarTypeList，ScalarType∣ScalarType

分析：本题主要考察理解和运用消除文法的左递归、提取公因子等算法的能力，为判断文法是否是LL(1)文法，还要计算文法的FIRST集合和FOLLOW集合。

消除文法的左递归的基本思想是，将文法规则中的左递归结构变换成等价的右递归结构。提取左公因子的算法，是对包含公共左因子的产生式候选，反复提取左因子，就能够把每个非终结符（包括新引进者）的所有候选首符集变成为两两不相交。消除文法的左递归、提取左公共因子后，再计算文法的各非终结符（X）的首符集FIRST（X）和随符集FOLLOW(X)，然后根据LL(1)文法的充分必要条件（即LL(1)文法的定义）来判断文法是否是LL(1)文法。 解：

首先消除左递归，得到文法G(Declist)： Declist→Decl Declist’ Declist’→；Decl Declist’∣ε Decl→IdList：Type IdList→id IdList’ IdList’→，id List’∣ε Type→ScalarType∣array(ScalarTypeList) of Type ScalarType→id∣Bound..Bound Bound→Sign IntLiteral∣id Sign→+∣-∣ε ScalarTypeList→ScalarType ScalarTypeList’ ScalarTypeList’→，ScalarType ScalarTypeList’∣ε

显然，改造后的文法没有左公共因子，计算每个非终结符的FIRST集合和FOLLOW集合如下： FIRST(Declist)={id} FIRST(Declist’)={；，ε} FIRST(Decl)={id} FIRST(IdList)={id} FIRST(IdList’)={；，ε}

FIRST(Type)={id，+，-，IntLiteral，array} FIRST(ScalarType)={id，+，-，IntLiteral} FIRST(Bound)={id，+，-，InLiteral} FIRST(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)={IntLiteral} FOLLOW(ScalarTypeList)={)} FOLLOW(ScalarTypeList’)={)} 显然，改造后的文法是LL(1)的。

第五章 语法分析——自下而上分析

1、令文法G1为 E→E+T∣T T→T*F∣F F→(E)∣i

证明E+T*F是它的一个句型，指出这个句型的所有短语，直接短语和句柄。 解：因为E=>E+T=>E+T*F，所以E+T*F是该文法的一个句型。 短语：E+T*F，T*F 直接短语：T*F 句柄：T*F

2、考虑下面的表格结构文法G2： S→a∣∧∣(T) T→T，S∣S

（1） 给出(a，(a，a))和(((a，a)，∧，(a))，a)的最左和最右推导。

（2） 指出(((a，a)，^，(a))，a)的规范归约及每一步的句柄。根据这个规范

归约，给出“移进-归约”的过程，并给出它的语法树自下而上的构造过程。

分析：要理解最左推导和最右推导的含义。所谓最左推导是指任何一步α=>β都是对α中的最左非终结符进行替换的；最右推导是指任何一步α=>β都是对α中的最右非终结符进行替换的。 解：

（1）最左推导： S=>(T)=>(T，S)=>(S，S)=>(a，S)=>(a，(T))=>(a，(T，S))=>(a，(S，S))=>

(a，(a，S))=>(a，(a，a)) S=>(T)=>(T，S)=>(S，S)=>((T)，S)=>((T，S)，S)=>((T，S，S)，S)=>((S，S，S)，S)=>(((T)，S，S)，S)=>(((T，S)，S，S)，S)=>(((S，S)，S，S)，S)=>(((a，S)，S，S)，S)=>(((a，a)，S，S)，S)=>(((a，a)，∧，S)，S)=>(((a，a)，∧，(T))，S)=>(((a，a)，∧，(S))，S)=>(((a，a)，∧，(a))，S)=>(((a，a)，∧，(a))，a) 最右推导： S=>(T)=>(T，S)=>(T，(T))=>(T，(T，S))=>(T，(T，a))=>(T，(S，a))=>(T，(a，a))=>(S，(a，a))=> (a，(a，a)) S=>(T，S)=>(T，a)=>(S，a)=>((T)，a)=>((T，S)，a)=>((T，(T))，a)=>((T，(S))，a)=>((T，(a))，a)=>((T，S，(a))，a)=>((T，∧，(a))，a)=>((S，∧，(a))，a)=>(((T)，∧，(a))，a)=>(((T，S)，∧，(a))，a)=>(((T，a)，∧，(a))，a)=>(((S，a)，∧，(a))，a)=> (((a，a)，∧，(a))，a) （2）(((a，a)，^，(a))，a)的规范归约如下： (((a，a)，∧，(a))，a) (((S，a)，∧，(a))，a) (((T，a)，∧，(a))，a) (((T，S)，∧，(a))，a) (((T)，∧，(a))，a) ((S，∧，(a))，a) ((T，∧，(a))，a) ((T，S，(a))，a) ((T，(a))，a) ((T，(S))，a) ((T，(T))，a) ((T，S)，a) ((T)，a) (S，a) (T，S) (T)

“移进—归约”过程： 步骤 栈 输入串 动作 0 # (((a，a)，∧，(a))，a)# 预备 1 #( ((a，a)，∧，(a))，a)# 进 2 #(( (a，a)，∧，(a))，a)# 进 3 #((( a，a)，∧，(a))，a)# 进 4 #(((a ，a)，∧，(a))，a)# 进 5 #(((S ，a)，∧，(a))，a)# 归 6 #(((T ，a)，∧，(a))，a)# 归 7 #(((T， a)，∧，(a))，a)# 进 8 #(((T，a )，∧，(a))，a)# 进 9 #(((T，S )，∧，(a))，a)# 归 10 #(((T )，∧，(a))，a)# 归 11 #(((T) ，∧，(a))，a)# 进 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #((S #((T #((T， #((T，∧ #((T，S #((T #((T， #((T，( #((T，(a #((T，(S #((T，(T #((T，(T) #((T，S #((T #((T) #(S #(T #(T， #(T，a #(T，S #(T #(T) #S ，∧，(a))，a)# ，∧，(a))，a)# ∧，(a))，a)# ，(a))，a)# ，(a))，a)# ，(a))，a)# (a))，a)# a))，a)# ))，a)# ))，a)# ))，a)# )，a)# )，a)# )，a)# ，a)# ，a)# ，a)# a)# )# )# )# # # 归 归 进 进 归 归 进 进 进 归 归 进 归 归 进 归 归 进 进 归 归 进 归 3、（1）计算练习2文法G2的FIRSTVT和LASTVT。

（2）计算G2的优先关系。G2是一个算符优先文法吗？ （3）计算G2的优先函数。 （4）给出输入串（a，（a，a））的算符优先分析过程。

分析：在计算得到FIRSTVT集合和LASTVT集合，并构造文法的优先关系矩阵之后，可以根据优先关系矩阵判断文法是否是算符优先文法：如果优先关系矩阵不存在冲突，即文法的任何终结符对至多只存在一种优先关系，则该文法是一个算符优先文法，否则，该文法不是算符优先文法。算符优先法是根据算符的优先关系进行分析，在“移进—归约”过程中，总是根据算符之间的有限关系确定栈顶是否出现了可规约串——最左素短语，一旦出现便进行规约（注意规约使用的产生式），否则进行移入操作。 解：

（1）FIRSTVT和LASTVT如下： FIRSTVT(S)={a，∧，(} FIRSTVT(T)={，，a，∧，(} LASTVT(S)={a，∧，)}

LASTVT(T)={，，a，∧，)}

（3） 构造优先关系表如下：

a ∧ ( a ^ ( < < < ) ， < < < # < < < G2是算符文法，且是算符优先文法。 （3）优先函数表如下： A ∧ ( f 4 4 2 g 5 5 5 ) > > = > > ， > > < > > # > > > = ) 4 2 ， 4 3

（4）输入串（a，（a，a））的算符优先分析过程如下： 栈 输入字符串 动作 # (a，(a，a))# 预备 #( a，(a，a))# 进 #(a ，(a，a))# 进 #(s ，(a，a))# 归 #(t ，(a，a))# 归 #(t， (a，a))# 进 #(t，( a，a))# 进 #(t，(a ，a))# 进 #(t，(s ，a))# 归 #(t，(t ，a))# 归 #(t，(t a))# 进 #(t，(t，a ))# 进 #(t，(t，s ))# 归 #(t，(t ))# 归 #(t，(t) )# 进 #(t，s )# 归 #(t )# 归 #(t) # 进 #s # 归 成功

4、存在一种称为简单优先的自下而上分析法，这种分析法不会把错误句子当作为正确句子。一个文法G，如果它不含ε-产生式，也不含任何右部相同的不同产生式，并且它的任何符号对（X，Y）——X和Y为终结符或非终结符——顶多存在下述三种关系=、<、>之一，则称这个文法G是一个简单优先文法。这三种关系的定义是：

A、X=Y当且仅当G中含有形如P→?XY?的产生式；

(1) (2) (3) (4) (5) (6) 间接三元式 (0) (1) (2) (3) (4) (5) Op + uminus + * + + - (0) c (1) a (4) (3) d (2) b c (5) ag1 a (0) c (1) (0) (3) ag2 b d (2) d (4) uminus + * + - 间接代码 (0),(1),(2),(3),(0),(4),(5) 四元式序列 (0) (1) (2) (3) (4) op + uminus + + * ag1 a T1 c T1 T3 ag2 b d c T4 result T1 T2 T3 T4 T5 (5) 4

- T5 T4 T6 产生三地址代码 6

A or （B and not（C or D））： 100：（jnz，A，-，0） 101：（j，-，-，102） 102：（jnz，B，-，104） 103：（j，-，-，0） 104：（jnz，C，-，0） 105：（j，-，-，106） 106：（jnz，D，-，0） 107：（j，-，-，0） 7

100：（j<，A，C，102） 101：（j，-，-，114） 102：（j<，B，D，104） 103：（j，-，-，114）

104：（j=，A，‘1’，106） 105：（j，-，-，109）

106：（+，C，‘1’，T1） 107：（:=，T1，-，C） 108：（j，-，-，100） 109：（j≤，A，D，111） 110：（j，-，-，100）

111：（+，A，‘2’，T2） 112：（:=，T2，-，A） 113：（j，-，-，109） 114：

第十章 代码优化 一 程序流图

Read CA:=0B:=0L1: A:=A+BIf B>=C GOTO L2B:=B+1GOTO L1L2:= write Ahalt 第二题 程序流图

Read A,BF:=1C:=A*AD:=B*BIf C100 goto L2haltL2 F:=F+1Goto L1

第四题 优化

I:=1Read j,KL A:=K*IB:=J*IC:=A*BWrite CI:=I+1If I<100 goto LhaltI:=1Read J,KA:=K*IB:=J*IT1:=100KL C:=A*BWrite CA:=A+KB:=B+JIf A

本文来源：https://www.bwwdw.com/article/g2j3.html