编译原理习题及答案1～3

章词法分析章语法分析2021/6/271

第一章绪论

1.1完成下列选择题：

(1)下面叙述中正确的是

。

A．编译程序是将高级语言程序翻译成等价的机器语言程序的程序

B．机器语言因其使用过于困难，所以现在计算机根本不使用机器语言

C．汇编语言是计算机唯一能够直接识别并接受的语言

D．高级语言接近人们的自然语言，但其依赖具体机器的特性是无法改变的2021/6/272

(2)将编译过程分成若干“遍”是为了

。

A．提高程序的执行效率

B．使程序的结构更加清晰

C．利用有限的机器内存并提高机器的执行效率

D．利用有限的机器内存但降低了机器的执行效率

(3)构造编译程序应掌握

。

A．源程序 B．目标语言

C．编译方法 D．A～C项2021/6/273

(4)编译程序绝大多数时间花在

上。

A．出错处理 B．词法分析

B．目标代码生成 D．表格管理

(5)编译程序是对

。

A．汇编程序的翻译B．高级语言程序的解释执行

C．机器语言的执行D．高级语言的翻译2021/6/274

【解答】

(1)编译程序可以将用高级语言编写的源程序转换成与之在逻辑上等价的目标程序，而目标程序可以是汇编语言程序或机器语言程序。故选A。

(2)分多遍完成编译过程可使整个编译程序的逻辑结构更加清晰。故选B。

(3)构造编译程序应掌握源程序、目标语言和编译方法这三方面内容。故选D。2021/6/275

(4)编译各阶段的工作都涉及到构造、查找或更新有关表格，即编译过程的绝大部分时间都用在造表、查表和更新表格的事务上。故选D。

(5)由(1)可知，编译程序实际上实现了对高级语言程序的翻译。故选D。2021/6/276

1.2计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？

【解答】计算机执行用高级语言编写的程序主要有两种途径：解释和编译。

在解释方式下，翻译程序事先并不采用将高级语言程序全部翻译成机器代码程序，然后执行这个机器代码程序的方法，而是每读入一条源程序的语句，就将其解释(翻译)成对应其功能的机器代码语句串并执行，然后再读入下一条源程序语句并解释执行，而所翻译的机器代码语句串在该语句执行后并不保留。这种方法是按源程序中语句的动态执行顺序逐句解释(翻译)执行的，如果一语句处于一循环体中，则每次循环执行到该语句时，都要将其翻译成机器代码后再执行。2021/6/277

在编译方式下，高级语言程序的执行是分两步进行的：第一步首先将高级语言程序全部翻译成机器代码程序，第二步才是执行这个机器代码程序。因此，编译对源程序的处理是先翻译，后执行。

从执行速度上看，编译型的高级语言比解释型的高级语言要快，但解释方式下的人机界面比编译型好，便于程序调试。

这两种途径的主要区别在于：解释方式下不生成目标代码程序，而编译方式下生成目标代码程序。2021/6/278

1.3请画出编译程序的总框图。如果你是一个编译程序的总设计师，设计编译程序时应当考虑哪些问题？

【解答】编译程序总框图如图1-1所示。

作为一个编译程序的总设计师，首先要深刻理解被编译的源语言其语法及语义；其次，要充分掌握目标指令的功能及特点，如果目标语言是机器指令，还要搞清楚机器的硬件结构以及操作系统的功能；第三，对编译的方法及使用的软件工具也必须准确化。总之，总设计师在设计编译程序时必须估量系统功能要求、硬件设备及软件工具等诸因素对编译程序构造的影响。2021/6/279图1-1编译程序总框图2021/6/2710第二章词法分析

2.1完成下列选择题：

(1)词法分析所依据的是

。

A．语义规则 B．构词规则

C．语法规则 D．等价变换规则

(2)词法分析器的输入是

。

A．单词符号串 B．源程序

C．语法单位 D．目标程序2021/6/2711

(3)词法分析器的输出是

。

A．单词的种别编码

B．单词的种别编码和自身的值

C．单词在符号表中的位置

D．单词自身值

(4)状态转换图(见图2-1)接受的字集为_______。

A．以0开头的二进制数组成的集合

B．以0结尾的二进制数组成的集合

C．含奇数个0的二进制数组成的集合

D．含偶数个0的二进制数组成的集合2021/6/2712图2-1习题2.1的DFAM2021/6/2713

(5)对于任一给定的NFAM，

一个DFAM′，使L(M)=L(M′)。

A．一定不存在 B．一定存在

C．可能存在 D．可能不存在

(6) DFA适用于

。

A．定理证明 B．语法分析

C．词法分析 D．语义加工2021/6/2714

(7)下面用正规表达式描述词法的论述中，不正确的是

。

A．词法规则简单，采用正规表达式已足以描述

B．正规表达式的表示比上下文无关文法更加简洁、直观和易于理解

C．正规表达式描述能力强于上下文无关文法

D．有限自动机的构造比下推自动机简单且分析效率高

(8)与(a|b)*(a|b)等价的正规式是

。

A．(a|b)(a|b)* B．a*|b*

C．(ab)*(a|b)* D．(a|b)*2021/6/2715

【解答】

(1)由教材第一章1.3节中的词法分析，可知词法分析所遵循的是语言的构词规则。故选B。

(2)词法分析器的功能是输入源程序，输出单词符号。故选B。

(3)词法分析器输出的单词符号通常表示为二元式：(单词种别，单词自身的值)。故选B。

(4)虽然选项A、B、D都满足题意，但选项D更准确。故选D。2021/6/2716

(5) NFA可以有DFA与之等价，即两者描述能力相同；也即，对于任一给定的NFAM，一定存在一个DFAM'，使L(M)=L(M′)。故选B。

(6) DFA便于识别，易于计算机实现，而NFA便于定理的证明。故选C。

(7)本题虽然是第二章的题，但答案参见第三章3.1.3节。即选C。

(8)由于正则闭包R+=R*R=RR*，故(a|b)*(a|b)=(a|b)(a|b)*。故选A。2021/6/2717

2.2什么是扫描器？扫描器的功能是什么？

【解答】扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。通常把词法分析器作为一个子程序，每当语法分析器需要一个单词符号时就调用这个子程序。每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。2021/6/2718

2.3设M=({x,y},{a,b},f,x,{y})为一非确定的有限自动机，其中f定义如下：

f(x,a)={x,y} f{x,b}={y}

f(y,a)=Φ f{y,b}={x,y}

试构造相应的确定有限自动机M′。

【解答】对照自动机的定义M=(S,Σ,f, s0, Z)，由f的定义可知f(x,a)、f(y,b)均为多值函数，因此M是一非确定有限自动机。

先画出NFAM相应的状态图，如图2-2所示。2021/6/2719图2-2习题2.3的NFAM

2021/6/2720

用子集法构造状态转换矩阵，如表2-1所示。

表2-1状态转换矩阵

将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到

2021/6/2721

将图2-3所示的DFAM′最小化。首先，将M′的状态分成终态组{1,2}与非终态组{0}。其次，考察{1,2}。由于{1,2}a={1,2}b={2}

{1,2}，因此不再将其划分了，也即整个划分只有两组：{0}和{1,2}。令状态1代表{1,2}，即把原来到达2的弧都导向1，并删除状态2。最后，得到如图2-4所示的化简了的DFAM′。图2-3习题2.3的DFAM′其状态转换图如图2-3所示。2021/6/2722图2-4图2-3化简后的DFAM′

2021/6/2723

2.4正规式(ab)*a与正规式a(ba)*是否等价？请说明理由。

【解答】正规式(ab)*a对应的NFA如图2-5所示，正规式a(ba)*对应的NFA如图2-6所示。

用子集法将图2-5和图2-6分别确定化为如图2-7(a)和(b)所示的状态转换矩阵，它们最终都可以得到最简DFA，如图2-8所示。因此，这两个正规式等价。2021/6/2724图2-5正规式(ab)*a对应的NFA2021/6/2725图2-6正规式a(ba)*对应的NFA2021/6/2726图2-7图2-5和图2-6确定化后的状态转换矩阵

—2021/6/2727图2-8最简DFA

2021/6/2728

实际上，当闭包*取0时，正规式(ab)*a与正规式a(ba)*由初态X到终态Y之间仅存在一条a弧。由于(ab)*在a之前，故描述(ab)*的弧应在初态结点X上；而(ba)*在a之后，故(ba)*对应的弧应在终态结点Y上。因此，(ab)*a和a(ba)*所对应的NFA也可分别描述为如图2-9(a)和(b)所示的形式，它们确定化并化简后仍可得到图2-8所示的最简DFA。2021/6/2729图2-9(ab)*a和a(ba)*分别对应的NFA

2021/6/2730

2.5设有L(G)={a2n+1b2ma2p+1|

n≥0,p≥0,m≥1}。

(1)给出描述该语言的正规表达式；

(2)构造识别该语言的确定有限自动机(可直接用状态图形式给出)。

【解答】该语言对应的正规表达式为a(aa)*bb(bb)*a(aa)*，正规表达式对应的NFA如图2-10所示。

2021/6/2731图2-10习题2.5的NFA2021/6/2732用子集法将图2-10确定化，如图2-11所示。

由图2-11重新命名后的状态转换矩阵可化简为(也可由最小化方法得到)

{0,2}{1}{3,5}{4,6}{7}

图2-11习题2.5的状态转换矩阵

2021/6/2733

按顺序重新命名为0、1、2、3、4后得到最简的DFA，如图2-12所示。图2-12习题2.5的最简DFA

2021/6/2734

2.6有语言L={w | w∈(0,1)+，并且w中至少有两个1，又在任何两个1之间有偶数个0}，试构造接受该语言的确定有限状态自动机(DFA)。

【解答】对于语言L，w中至少有两个1，且任意两个1之间必须有偶数个0；也即在第一个1之前和最后一个1之后，对0的个数没有要求。据此我们求出L的正规式为0*1(00(00)*1)*00(00)*10*，画出与正规式对应的NFA，如图2-13所示。2021/6/2735图2-13习题2.6的NFA2021/6/2736

用子集法将图2-13所示的NFA确定化，如图2-14所示

由图2-14可看出非终态2和4的下一状态相同，终态6和8的下一状态相同，即得到最简状态为

{0}{1}{2,4}{3}{5}{6,8}{7}

2021/6/2737按顺序重新命名为0、1、2、3、4、5、6，则得到最简DFA，如图2-15所示。图2-15习题2.6的最简DFA2021/6/2738

2.7已知正规式((a | b)*| aa)*b和正规式(a | b)*b。

(1)试用有限自动机的等价性证明这两个正规式是等价的；

(2)给出相应的正规文法。

【解答】(1)正规式((a | b)*| aa)*b对应的NFA如图2-16所示。

用子集法将图2-16所示的NFA确定化为DFA，如图2-17所示。2021/6/2739图2-16正规式((a | b)*|aa)*b对应的NFA

2021/6/2740图2-17图2-16确定化后的状态转换矩阵2021/6/2741

由于对非终态的状态1、2来说，它们输入a、b的下一状态是一样的，故状态1和状态2可以合并，将合并后的终态3命名为2，则得到表2-3(注意，终态和非终态即使输入a、b的下一状态相同也不能合并)。

由此得到最简DFA，如图2-18所示。

正规式(a | b)*b对应的NFA如图2-19所示。

用子集法将图2-19所示的NFA确定化为如图2-20所示的状态转换矩阵。2021/6/2742表2-3合并后的状态转换矩阵

2021/6/2743图2-18习题2.7的最简DFA2021/6/2744图2-19正规式(a | b)*b对应的NFA2021/6/2745

比较图2-20与图2-17，重新命名后的转换矩阵是完全一样的，也即正规式(a | b)*b可以同样得到化简后的DFA如图2-18所示。因此，两个自动机完全一样，即两个正规文法等价。图2-20图2-19确定化后的状态转换矩阵

2021/6/27462.8构造一个DFA，它接收Σ

={a,b}上所有不含abb的字符串。

解：Σ

={a,b}上所有不含abb的字符串可表示为b*(a*b)a*。

2021/6/27472.9构造一个DFA，它接收Σ

={a,b}上所有含偶数个a的字符串。

解：Σ

={a,b}上所有含偶数个a的字符串可表示为(b|ab*a)*2021/6/2748

2.10下列程序段以B表示循环体，A表示初始化，I表示增量，T表示测试：

I=1;

while(I<=n)

{

sun=sun+a[I];

I=I+1;

}

请用正规表达式表示这个程序段可能的执行序列。

【解答】用正规表达式表示程序段可能的执行序列为AT(BIT)*。2021/6/2749

2.9将图2-21所示的非确定有限自动机(NFA)变换成等价的确定有限自动机(DFA)。

其中，X为初态，Y为终态。

【解答】用子集法将NFA确定化，如图2-22所示。2021/6/2750图2-21习题2.9的NFA2021/6/2751图2-22习题2.9的状态转换矩阵

{2}{2,Y}{2,4}{2}{2,Y}{2,4}{2,4}{2,4}{2,4,Y}{2,4,Y}{2,4,Y}2021/6/2752

图2-22所对应的DFA如图2-23所示。

对图2-23所示的DFA进行最小化。首先将状态分为非终态集和终态集两部分：{0,1,2,5}和{3,4,6,7}。由终态集可知，对于状态3、6、7，无论输入字符是a还是b的下一状态均为终态集，而状态4在输入字符b的下一状态落入非终态集，故将其划分为

{0,1,2,5}，{4}，{3,6,7}

对于非终态集，在输入字符a、b后按其下一状态落入的状态集不同而最终划分为

{0}，{1}，{2}，{5}，{4}，{3,6,7}

按顺序重新命名为0、1、2、3、4、5，得到最简DFA如图2-24所示。2021/6/2753图2-23习题2.9的DFA2021/6/2754

图2-24习题2.9的最简DFA2021/6/2755

2.10有一台自动售货机，接收1分和2分硬币，出售3分钱一块的硬糖。顾客每次向机器中投放大于等于3分的硬币，便可得到一块糖(注意：只给一块并且不找钱)。

(1)写出售货机售糖的正规表达式；

(2)构造识别上述正规式的最简DFA。

【解答】(1)设a=1，b=2，则售货机售糖的正规表达式为a(b | a(a | b)) | b(a | b)。

(2)画出与正规表达式a(b | a(a | b)) | b(a | b)对应的NFA，如图2-25所示。

用子集法将图2-25所示的NFA确定化，如图2-26所示。2021/6/2756图2-25习题2.10的NFA2021/6/2757

由图2-26可看出，非终态2和非终态3面对输入符号a或b的下一状态相同，故合并为一个状态，即最简状态{0}、{1}、{2，3}、{4}。图2-26习题2.10的状态转换矩阵2021/6/2758

按顺序重新命名为0、1、2、3，则得到最简DFA，如图2-27所示。图2-27习题2.10的最简DFA2021/6/2759第三章语法分析

3.1完成下列选择题：

(1)程序语言的语义需要

用来描述。

A．上下文无关文法B．上下文有关文法

C．正规文法 D．短语文法

(2)2型文法对应

。

A．图灵机 B．有限自动机

C．下推自动机 D．线性界限自动机2021/6/2760

(3)下述结论中，

是正确的。

A．1型语言

0型语言 B．2型语言

1型语言

C．3型语言

2型语言 D．A～C均不成立

(4)有限状态自动机能识别_________。

A．上下文无关文法 B．上下文有关文法

C．正规文法 D．短语文法

(5)文法G[S]：S→xSx|y所识别的语言是

。

A．xyx B．(xyx)*

C．xnyxn(n≥0) D．x*yx*2021/6/2761

(6)只含有单层分枝的子树称为“简单子树”，则句柄的直观解释是

。

A．子树的末端结点(即树叶)组成的符号串

B．简单子树的末端结点组成的符号串

C．最左简单子树的末端结点组成的符号串

D．最左简单子树的末端结点组成的符号串且该符号串必须含有终结符2021/6/2762

(7)下面对语法树错误的描述是

。

A．根结点用文法G[S]的开始符S标记

B．每个结点用G[S]的一个终结符或非终结符标记

C．如果某结点标记为ε，则它必为叶结点

D．内部结点可以是非终结符

(8)由文法开始符S经过零步或多步推导产生的符号序列是

。

A．短语B．句柄 C．句型 D．句子2021/6/2763

(9)设文法G[S]：S→SA|A

A→a|b

则对句子aba的规范推导是

。

A．S

SA

SAA

AAA

aAA

abA

aba

B．S

SA

SAA

AAA

AAa

Aba

aba

C．S

SA

SAA

SAa

Sba

Aba

aba

D．S

SA

Sa

SAa

Sba

Aba

aba

2021/6/2764

(10)如果文法G[S]是无二义的，则它的任何句子α其

。

A．最左推导和最右推导对应的语法树必定相同

B．最左推导和最右推导对应的语法树可能不同

C．最左推导和最右推导必定相同

D．可能存在两个不同的最右推导，但它们对应的语法树相同

(11)一个句型的分析树代表了该句型的

。

A．推导过程 B．归约过程

C．生成过程 D．翻译过程2021/6/2765

(12)规范归约中的“可归约串”由

定义。

A．直接短语 B．最右直接短语

C．最左直接短语 D．最左素短语

(13)规范归约是指

。

A．最左推导的逆过程B．最右推导的逆过程

C．规范推导 D．最左归约的逆过程2021/6/2766

(14)文法G[S]：S→aAcB|Bd

A→AaB|c

B→bScA|b

则句型aAcbBdcc的短语是

。

A．Bd B．cc C．a D．b

(15)文法G[E]：E→E+T|T

T→T*P|P

P→(E)|i

则句型P+T+i的句柄和最左素短语是

。

A．P+T和T B．P和P+T

C．i和P+T+i D．P和P

2021/6/2767

(16)采用自顶向下分析，必须

。

A．消除左递归 B．消除右递归

C．消除回朔 D．提取公共左因子

(17)对文法G[E]：E→E+S|S

S→S*F|F

F→(E)|i

则FIRST(S)=

。

A．{(} B．{(,i}

C．{i} D．{(,)}2021/6/2768

(18)确定的自顶向下分析要求文法满足

。

A．不含左递归 B．不含二义性

C．无回溯 D．A～C项

(19)递归下降分析器由一组递归函数组成，且每一个函数对应文法的

。

A．一个终结符B．一个非终结符

C．多个终结符D．多个非终结符

(20) LL(1)分析表需要预先定义和构造两族与文法有关的集合

。

A．FIRST和FOLLOWB．FIRSTVT和FOLLOW

C．FIRST和LASTVTD．FIRSTVT和LASTVT2021/6/2769

(21)设a、b、c是文法的终结符且满足优先关系ab和bc,则

。

A．必有ac B．必有ca

C．必有ba D．A～C都不一定成立

(22)算符优先分析法要求

。

A．文法不存在…QR…的句型且任何终结符对(a,b)满足ab、a⋖b和a⋗b三种关系

B．文法不存在…QR…的句型且任何终结符对(a,b)至多满足ab、a⋖b和a⋗b三种关系之一2021/6/2770

C．文法可存在…QR…的句型且任何终结符对(a,b)至多满足ab、a⋖b和a⋗b三种关系之一

D．文法可存在…QR…的句型且任何终结符对(a,b)满足ab、a⋖b和a⋗b三种关系

(23)任何算符优先文法

优先函数。

A．有一个 B．没有

C．有若干个 D．可能有若干个

(24)在算符优先分析中，用

来刻画可归约串。

A．句柄 B．直接短语

C．素短语 D．最左素短语2021/6/2771

(25)下面最左素短语必须具备的条件中有错误的是

。

A．至少包含一个终结符

B．至少包含一个非终结符

C．除自身外不再包含其他素短语

D．在句型中具有最左性

(26)对文法G[S]：S→b|∧|(T)

T→T，S|S

其FIRSTVT(T)为

。

A．{b,∧,(} B．{b,∧,)}

C．{，,b,∧,(} D．{，,b,∧,)}2021/6/2772

(27)对文法G[E]：E→E*T|T

T→T+i|i

句子1+2*8+6归约的值为

。

A．23 B．42 C．30 D．17

(28)下述FOLLOW集构造方法中错误的是

。

A．对文法开始符S有#∈FOLLOW(S)

B．若有A→αBβ，则有FIRST(β)\{ε}FOLLOW(B)

C．若有A→αB，则有FOLLOW(B)FOLLOW(A)

D．若有A→αB，则有FOLLOW(A)FOLLOW(B)2021/6/2773

(29)若文法G[S]的产生式有…AB…出现，则对A求FOLLOW集正确的是

。

A．FOLLOW(B)FOLLOW(A)

B．FIRSTVT(B)FOLLOW(A)

C．FIRST(B)\{ε}FOLLOW(A)

D．LASTVT(B)FOLLOW(A)

(30)下面

是自底向上分析方法。

A．预测分析法 B．递归下降分析法

C．LL(1)分析法 D．算符优先分析法2021/6/2774

(31)下面

是采用句柄进行归约的。

A．算符优先分析法 B．预测分析法

C．SLR(1)分析法 D．LL(1)分析法

(32)一个

指明了在分析过程中某时刻能看到产生式多大一部分。

A．活前缀 B．前缀

C．项目 D．项目集

(33)若B为非终结符，则A→α·Bβ为

项目。

A．接受 B．归约

C．移进 D．待约2021/6/2775

(34)在LR(0)的ACTION子表中，如果某一行中存在标记为“rj”的栏，则

。

A．该行必定填满rj B．该行未填满rj

C．其他行也有rj D．GOTO子表中也有rj

(35) LR分析法解决“移进—归约”冲突时，左结合意味着

。

A．打断联系实行移进 B．打断联系实行归约

C．建立联系实行移进 D．建立联系实行归约2021/6/2776

(36) LR分析法解决“移进—归约”冲突时，右结合意味着

。

A．打断联系实行归约 B．建立联系实行归约

C．建立联系实行移进 D．打断联系实行移进2021/6/2777

【解答】

(1)参见第四章4.1.1节，语义分析不像词法分析和语法分析那样可以分别用正规文法和上下文无关文法描述，由于语义是上下文有关的，因此语义分析须用上下文有关文法描述。即选B。

(2)2型文法对应下推自动机。故选C。

(3)由于不存在：3型语言

2型语言

1型语言

0型语言。故选D。

(4)3型文法即正规文法，它的识别系统是有限状态自动机。故选C。2021/6/2778

(5)由S→xSx|y可知该文法所识别的语言一定是：y左边出现的x与y右边出现的x相等。故选C。

(6)最左简单子树的末端结点组成的符号串为句柄。故选C。

(7)内部结点(指非树叶结点)一定是非终结符。故选D。

(8)由文法开始符S经过零步或多步推导产生的符号序列一定是句型，仅当推导产生的符号序列全部由终结符组成时才是句子，即句子是句型的阵列。故选C。

(9)规范推导即最右推导，也即每一步推导都是对句型中的最右非终结符用相应产生式的右部进行替换。故选D。2021/6/2779

(10)文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导)，或存在两棵不同的语法树，则它的任何句子α其最左推导和最右推导对应的语法树必定相同。故选A。

(11)一个句型的分析树代表了该句型的归约过程。故选B。

(12)规范归约中的“可归约串”即为句柄，也就是最左直接短语。故选C。

(13)规范归约的逆过程是规范推导，而规范推导即为最右推导。故选B。

(14)由图3-1可知应选A。2021/6/2780图3-1句型aAcbBdcc对应的语法树2021/6/2781

(15)由图3-2可知，句柄(最左直接短语)为P，最左素短语为P+T。故选B。

(16)回溯使自顶向下分析效率降低，左递归使得自顶向下的分析无法实现；二者相比消除左递归更为重要。故选A。

(17) FIRST(F)={(,i}，而由S→F可知FIRST(F)\{ε}

FIRST(S)，即FIRST(S)={(,i}。故选B。

(18)左递归和二义性将无法实现自顶向下分析，回溯则使自顶向下分析效率下降。故选D。2021/6/2782图3-2句型P+T+i对应的语法树及优先关系示意2021/6/2783

(19)递归下降分析器由一组递归函数组成，且每一个函数对应文法的一个非终结符。故选B。

(20) LL(1)分析表需要预先定义和构造两族与文法有关的集合FIRST和FOLLOW。故选A。

(21)由于ab和bc并不能使选项A、B、C成立。故选D。

(22)由算法优先文法可知应选B。

(23)有些算符优先文法不存在优先函数；有些算符优先文法存在优先函数，且只要存在一对优先函数，就存在无穷多对优先函数。故选D。

(24)在算符优先分析中是以“最左素短语”来刻画可归约串的。故选D。2021/6/2784

(25)最左素短语必须具备的三个条件是：①至少包含一个终结符；②除自身外不得包含其他素短语；③在句型中具有最左性。故选B。

(26) FIRSTVT(T)={，}，FIRSTVT(S)={b,∧,(}；由T→S可知FIRSTV(S)

FIRSTVT(T)，即FIRSTVT(T)={，,b,∧,(}。故选C。

(27)由图3-3可知应选B。

(28)若有A→αB则有FOLLOW(A)

FOLLOW(B)，即选项C错。故选C。

(29)若文法G[S]的产生式有…AB…出现，则有FIRST(B)\{ε}

FOLLOW(A)。故选C。2021/6/2785图3-3句子1+2*8+6的语法树及值变化示意2021/6/2786

(30)自底向上的分析方法有算符优先分析法和LR分析法。故选D。

(31)自底向上分析采用归约方法，但算符优先分析用“最左素短语”归约，而LR分析用“句柄”归约。SLR(1)是LR分析法的一种，故选C。

(32)在LR分析中，一个项目指明了在分析过程的某个时刻所看到产生式的多大一部分。故选C。

(33)对文法G[S’]，S'→α·称为“接受”项目；形如A→α·aβ的项目(其中a为终结符)称为“移进”项目；形如A→α·Bβ的项目(其中B为非终结符)称为“待约”项目。故选D。2021/6/2787

(34)在LR(0)的ACTION子表中，如果某一行存在标注为“rj”的栏，则该行必定填满rj，而在SLR(1)的ACTION子表中，如果某一行存在标注为“rj”的栏，则该行可能未填满rj。因此选A。

(35) LR分析法解决“移进—归约”冲突时，左结合意味着打断联系而实行归约，右结合意味着维持联系而实行移进。故选B。

(36)由(35)可知应选C。2021/6/2788

3.2令文法G[N]为

G[N]:N→D | ND

D→0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

(1) G[N]的语言L(G)是什么?

(2)给出句子0127、34和568的最左推导和最右推导。2021/6/2789

【解答】

(1) G[N]的语言L(G[N])是非负整数。

(2)最左推导：

最右推导：

2021/6/2790

3.3已知文法G[S]为S→aSb | Sb | b，试证明文法G[S]为二义文法。

【解答】由文法G[S]：S→aSb | Sb | b，对句子aabbbb可对应如图3-4所示的两棵语法树。

因此，文法G[S]为二义文法(对句子abbb也可画出两棵不同的语法树)。2021/6/2791图3-4句子aabbbb对应的两棵不同语法树2021/6/2792

3.4已知文法G[S]为S→SaS | ε，试证明文法G[S]为二义文法。

【解答】由文法G[S]：S→SaS | ε，句子aa的语法树如图3-5所示。

由图3-5可知，文法G[S]为二义文法。2021/6/2793图3-5句子aa对应的两棵不同的语法树2021/6/2794

3.5按指定类型，给出语言的文法。

(1) L={aibj | j＞i≥0}的上下文无关文法；

(2)字母表Σ={a,b}上的同时只有奇数个a和奇数个b的所有串的集合的正规文法；

(3)由相同个数a和b组成句子的无二义文法。

【解答】(1)由L={aibj | j＞i≥0}知，所求该语言对应的上下文无关文法首先应有S→aSb型产生式，以保证b的个数不少于a的个数；其次，还需有S→Sb或S→b型的产生式，用以保证b的个数多于a的个数。因此，所求上下文无关文法G[S]为

G[S]：S→aSb | Sb | b2021/6/2795

(2)为了构造字母表Σ={a,b}上同时只有奇数个a和奇数个b的所有串集合的正规式，我们画出如图3-6所示的DFA，即由开始符S出发，经过奇数个a到达状态A，或经过奇数个b到达状态B；而由状态A出发，经过奇数个b到达状态C(终态)；同样，由状态B出发经过奇数个a到达终态C。

由图3-6可直接得到正规文法G[S]如下：

G[S]：S→aA | bB

A→aS | bC | b

B→bS | aC | a

C→bA | aB | ε2021/6/2796图3-62021/6/2797

(3)我们用一个非终结符A代表一个a(即有A→a)，用一个非终结符B代表一个b(即有B→b)；为了保证a和b的个数相同，则在出现一个a时应相应地出现一个B，出现一个b时则相应出现一个A。假定已推导出bA，如果下一步要推导出连续两个b，则应有bA

bbAA。也即为了保证b和A的个数一致，应有A→bAA；同理有B→aBB。此外，为了保证递归地推出所要求的ab串，应有S→aBS和S→bAS。由此得到无二义文法G[S]为

G[S]：S→aBS | bAS | ε

A→bAA | a

B→aBB | b2021/6/2798

3.6有文法G[S]:S→aAcB | Bd

A→AaB | c

B→bScA | b

(1)试求句型aAaBcbbdcc和aAcbBdcc的句柄；

(2)写出句子acabcbbdcc的最左推导过程。

【解答】(1)分别画出对应句型aAaBcbbdcc和aAcbBdcc的语法树如图3-7的(a)、(b)所示。

对树(a)，直接短语有3个：AaB、b和c，而AaB为最左直接短语(即为句柄)。对树(b)，直接短语有两个：Bd和c，而Bd为最左直接短语。2021/6/2799能否不画出语法树，而直接由定义(即在句型中)寻找满足某个产生式的候选式这样一个最左子串(即句柄)呢？例如，对句型aAaBcbbdcc，我们可以由左至右扫描找到第一个子串AaB，它恰好是满足A→AaB右部的子串；与树(a)对照，AaB的确是该句型的句柄。是否这一方法始终正确呢？我们继续检查句型aAcbBdcc，由左至右找到第一个子串c，这是满足A→c右部的子串，但由树(b)可知，c不是该句型的句柄。由此可知，画出对应句型的语法树然后寻找最左直接短语是确定句柄的好方法。2021/6/27100图3-7习题3.6的语法树(a) aAaBcbbdcc;(b) aAcbBdcc2021/6/27101

(2)句子acabcbbdcc的最左推导如下：2021/6/27102

3.7对于文法G[S]:S→(L) | aS | a

L→L,S | S

(1)画出句型(S,(a))的语法树；

(2)写出上述句型的所有短语、直接短语、句柄、素短语和最左素短语。2021/6/27103

【解答】(1)句型(S,(a))的语法树如图3-8所示。

(2)由图3-8可知：

短语：S、a、(a)、S,(a)、(S,(a))；

直接短语：a、S；

句柄：S；

素短语：素短语可由图3-8中相邻终结符之间的优先关系求得，即：

#⋖(⋖，⋖(⋖a⋗)⋗)⋗#

因此，素短语为a。2021/6/27104图3-8句型(S,(a))的语法树2021/6/27105

3.8下述文法描述了C语言整数变量的声明语句：

G[D]:D→TL

T→int | long | short

L→id | L,id

(1)改造上述文法，使其接受相同的输入序列，但文法是右递归的；

(2)分别以上述文法G[D]和改造后的文法G′[D]为输入序列inta,b,c构造分析树。2021/6/27106

【解答】(1)消除左递归后，文法G′[D]如下：

D→TL

T→int | long | short

L→idL′

L′→,idL′| ε

(2)未消除左递归的文法G(D)和消除左递归的文法G′[D]为输入序列inta,b,c构造的分析树分别如图3-9的(a)、(b)所示。2021/6/27107图3-9两种文法为inta,b,c构造的分析树

(a)文法G(D)；(b)文法G′(D)2021/6/27108

3.9考虑文法G[S]:S→(T)|a+S|a

T→T,S|S

消除文法的左递归及提取公共左因子，然后对每个非终结符写出不带回溯的递归子程序。

【解答】消除文法G[S]的左递归：

S→(T)|a+S|a

T→ST′

T′→,ST′|ε2021/6/27109

提取公共左因子：

S→(T)|aS′

S′→+S|ε

T→ST′

T′→,ST′|ε2021/6/27110

改造后的文法已经是LL(1)文法，不带回溯的递归子程序如下：

voidmatch(tokent)

{

if(lookahead==t)

lookahead=nexttoken;

elseerror();

}

voidS()2021/6/27111

{

if(lookahead==′a′)

{match(′a′);

S′();

}

elseif(lookahead==′(′)

{

match(′(′);

T();

if(lookahead==′)′)

match(′)′);

elseerror();

}2021/6/27112

voidS′()

{

if(lookahead==′+′)

{

match(′+′);

S();

}

}

voidT()

{

S();

T′();

}2021/6/27113

voidT′ ()

{

if(lookahead==′,′)

{

match(′,′);

S();

T′ ();

}

}2021/6/27114

对于文法G[S]中的产生式：T→T,S|S，即将非终结符T由下面的正规表达式定义：

T→S{,S}

然后将其用状态转换图表示为图3-10。

这个状态转换图的作用就如同一个递归过程(函数)，并借助于这种转换图来得到递归过程(函数)下降分析器。因此，前面的递归下降分析器程序可删除函数T( )和T'( )，而将T( )和T'( )改为2021/6/27115图3-10非终结符T的状态转换图2021/6/27116

voidT( )

{

S( );

while(lookahead==‘,’)

{

match(‘,’);

S( );

}

}2021/6/27117

3.10已知文法G[A]:A→aABl | a

B→Bb | d

(1)试给出与G[A]等价的LL(1)文法G′[A]；

(2)构造G[A′]的LL(1)分析表；

(3)给出输入串aadl#的分析过程。

【解答】(1)文法G[A]存在左递归和回溯，故其不是LL(1)文法。要将G[A]改造为LL(1)文法，首先要消除文法的左递归，即将形如P→Pα|β的产生式改造为

P→βP′

P→αP′|ε2021/6/27118来消除左递归。由此，将产生式B→Bb | d改造为

B→dB′

B′→bB′|ε

其次，应通过提取公共左因子的方法来消除G[A]中的回溯，即将产生式A→aABl | a改造为

A→aA′

A′→ABl|ε

最后得到改造后的文法为

G′[A]：  A→aA′

A′→ABl|ε

B→dB′

B′→bB′|ε2021/6/27119

求得：

FIRST(A)={a}FIRST(A′)={a,ε}

FIRST(B)={d}FIRST(B′)={b,ε}

对文法开始符号A，有FOLLOW(A)={#}。

由A′→ABl得FIRST(B)\{ε}

FOLLOW(A)，

即FOLLOW(A)={#,d}；

由A′→ABl得FIRST(′l′)FOLLOW(B)，即FOLLOW(B)={l}；2021/6/27120

由A→aA′得FOLLOW(A)

FOLLOW(A′)，即FOLLOW(A′)={#,d}；

由B→dB′得FOLLOW(B)

FOLLOW(B′)，即FOLLOW(B′)={l}。

对A′→ABl来说，FIRST(A)∩FOLLOW(A′)={a}∩{#,d}=Φ，所以文法G′[A]为所求等价的LL(1)文法。2021/6/27121

(2)构造预测分析表的方法如下：

①对文法G′[A]的每个产生式A→α执行②、③步。

②对每个终结符a∈FIRST(A)，把A→α加入到M[A,a]中，其中α为含有首字符a的候选式或为唯一的候选式。

③若ε∈FIRST(A)，则对任何属于FOLLOW(A)的终结符b，将A→ε加入到M[A,b]中。把所有无定义的M[A,a]标记上“出错”。

由此得到G′[A]的预测分析表，见表3-1。

(3)输入串aadl的分析过程见表3-2。2021/6/27122表3-1预 测 分 析 表

2021/6/27123表3-2输入串aadl的分析过程

2021/6/27124

3.11将下述文法改造为LL(1)文法：

G[V]: V→N|N[E]

E→V|V+E

N→i

【解答】LL(1)文法的基本条件是不含左递归和回溯(公共左因子)，而文法G[V]中含有回溯，所以先消除回溯，得到文法G′[V]：

G′[V]：V→NV′

V′→ε|[E]

E→VE′

E′→ε|+E

N→i2021/6/27125一个LL(1)文法的充要条件是：对每一个终结符A的任何两个不同产生式A→α | β有下面的条件成立：

(1) FIRST(α)∩FIRST(β)=Φ；

(2) 假若β→ε，则有FIRST(α)∩FOLLOW(A)=Φ。

即求出G′[V]的FIRST和FOLLOW集如下：

FIRST(N)=FIRST(V)=FIRST(E)={i}

FIRST(V′)={[,ε}

FIRST(E′)={+,ε}

FOLLOW(V)={#}2021/6/27126

由V′→…E]得FIRST(‘]’)FOLLOW(E)，即FOLLOW(E)={]}；

由V→NV′得FIRST(V′)\{ε}FOLLOW(N)，即FOLLOW(N)={[}；

由E→VE′得FIRST(E′)\{ε}

FOLLOW(V)，即FOLLOW(V)={#,+}；

由V→NV′得FOLLOW(V)FOLLOW(V′)，即FOLLOW(V′)={#,+}；

由V→NV′且V′→ε得FOLLOW(V)FOLLOW(N)，

即FOLLOW(N)={[,#,+}；

由E→VE′得FOLLOW(E)FOLLOW(E′)，即FOLLOW(E′)={]}；2021/6/27127则，对V′→ε|[E]有：FIRST(ε)∩FIRST(′[′)=Φ；

对E′→ε|+E有：FIRST(ε)∩FIRST(′+′)=Φ；

对V′→ε|[E]有：FIRST('[')∩FOLLOW(V′)={[}∩{#,+}=Φ；

对E′→ε|+E有：FIRST('+')∩FOLLOW(E′)={+}∩{]}=Φ。

故文法G′[V]为LL(1)文法。2021/6/27128

3.12对文法G[E]:E→E+T | T

T→T*P | P

P→i

(1)构造该文法的优先关系表(不考虑语句括号#)，并指出此文法是否为算符优先文法；

(2)构造文法G[E]的优先函数。2021/6/27129

【解答】(1) FIRSTVT集构造方法：

①由P→a…或P→Qa…，则a∈FIRSTVT(P)。

②若a∈FIRSTVT(Q)，且P→Q…，则a∈FIRSTVT(P)，也即FIRSTVT(Q)

FIRSTVT(P)。

由①得：由E→E+…得FIRSTVT(E)={+}；

由T→T*…得FIRSTVT(T)={*}；

由P→i得FIRSTVT(P)={i}。

由②得：由T→P得FIRSTVT(P)

FIRSTVT(T)，即FIRSTVT(T)={*，i}；

由E→T得FIRSTVT(T)

FIRSTVT(E)，即FIRSTVT(E)={+，*，i}。2021/6/27130

LASTVT集构造方法：

①由P→…a或P→…aQ,则a∈LASTVT(P)。

②若a∈LASTVT(Q)，且P→…Q，则a∈LASTVT(P)，也即LASTVT(Q)

LASTVT(P)。

由①得：E→…+T，得LASTVT(E)={+}；

T→…*P，得LASTVT(T)={*}；

P→i，得LASTVT(P)={i}。2021/6/27131由②得：由T→P得LASTVT(P)

LASTVT(T)，即LASTVT(T)={*，i}；

由E→T得LASTVT(T)

LASTVT(E)，即LASTVT(E)={+，*，i}。

优先关系表构造方法：

①对P→…ab…或P→…aQb…，有ab；

②对P→…aR…而b∈FIRSTVT(R)，有a⋖b；

③对P→…Rb…而a∈LASTVT(R)，有a⋗b。

解之无①。2021/6/27132由②得：E→…+T，即+⋖FIRSTVT(T)，有+⋖*，+⋖i；

T→…*P，即*⋖FIRSTVT(P)，有*⋖i。

由③得：E→E+…，即LASTVT(E)⋗+，有+⋗+，*⋗+，i⋗+；

T→T*…，即LASTVT(T)⋗*，有*⋗*，i⋗*。

得到优先关系表见表3-3。

由于该文法的任何产生式的右部都不含两个相继并列的非终结符，故属算符文法，且该文法中的任何终结符对(见优先关系表)至多满足、⋖ 和 ⋗三种关系之一，因而是算符优先文法。2021/6/27133表3-3习题3.12的优先关系表

2021/6/27134

(2)用关系图构造优先函数的方法是：对所有终结符a用有下脚标的fa、ga为结点名画出全部终结符所对应的结点。若存在优先关系a⋗b或ab，则画一条从fa到ga的有向弧；若a⋖b或ab，则画一条从gb到fa的有向弧。最后，对每个结点都赋一个数，此数等于从该结点出发所能到达的结点(包括出发结点)的个数，赋给fa的数作为f(a)，赋给gb的数作为g(b)。用关系图法构造本题的优先函数，如图3-11所示。

得到优先函数见表3-4。2021/6/27135图3-11习题3.12021/6/27136表3-4习题3.12的优先函数表2021/6/27137该优先函数表经检查与优先关系表没有矛盾，故为所求优先函数。

也可由定义直接构造优先函数，其方法是：对每个终结符a，令f(a)=g(a)=1；如果a⋗b，而f(a)≤g(b)，则令f(a)=g(b)+1；如果a⋖b，而f(a)≥g(b)，则令g(b)=f(a)+1；如果ab，而f(a)≠g(b)，则令min{f(a),g(b)}=max{f(a),g(b)}。重复上述过程，直到每个终结符的函数值不再变化为止。如果有一个函数值大于2n(n为终结符个数)，则不存在优先函数。

优先函数的计算过程如表3-5所示。2021/6/27138表3-5优先函数的计算过程

2021/6/27139

3.13设有文法G[S]:S→a | b | (A)

A→SdA | S

(1)构造算符优先关系表；

(2)给出句型(SdSdS)的短语、简单短语、句柄、素短语和最左素短语；

(3)给出输入串(adb)#的分析过程。2021/6/27140

【解答】(1)先求文法G[S]的FIRSTVT集和LASTVT集：

由S→a | b | (A)得FIRSTVT(S)={a,b,(}；

由A→Sd…得FIRSTVT(A)={d}，又由A→S…得FIRSTVT(S)

FIRSTVT(A)，即FIRSTVT(A)={d,a,b,(}；

由S→a | b | (A)得LASTVT(S)={a,b,)}；

由A→…dA得LASTVT(A)={d}，又由A→S得LASTVT(S)

LASTVT(A)，即LASTVT(A)={d,a,b,)}。2021/6/27141构造优先关系表方法如下：

①对P→…ab…或P→…aQb…，有ab；

②对P→…aR…而b∈FIRSTVT(R)，有a⋖b；

③对P→…Rb…而a∈FIRSTVT(R)，有a⋗b。

由此得到：

①由S→(A)得()；

②由S→(A…得(⋖FIRSTVT(A)，即(⋖d,(⋖a,(⋖b,(⋖(；

由A→…dA得d⋖FIRSTVT(A)，即d⋖d,d⋖a,d⋖b,d⋖(；2021/6/27142③由S→…A)得LASTVT(A)⋗)，即d⋗),a⋗),b⋗),)⋗)；

由A→Sd…得LASTVT(S)⋗d，即a⋗d,b⋗d,)⋗d；

此外，由 #S#得##；

由#⋖FIRSTVT(S)得#⋖a,#⋖b,#⋖(；

由LASTVT(S)⋗#得a⋗#,b⋗#,)⋗#。

最后得到算符优先关系表，见表3-6。

由表3-6可以看出，任何两个终结符之间至多只满足、⋖、⋗三种优先关系之一，故G[S]为算符优先文法。2021/6/27143表3-6习题3.13的算符优先关系表

2021/6/27144 (2)为求出句型(SdSdS)的短语、简单短语、句柄，我们先画出该句型对应的语法树