《编译原理》经典课后习题答案精选（含龙书及陈火旺版）.docxVIP

《编译原理》经典课后习题答案精选（含龙书及陈火旺版）

说明

本套习题答案涵盖编译原理核心模块，精选龙书（第2版）和陈火旺《编译原理》（第3版）中的典型习题，包含题目、答案、考点定位及解析思路，适用于课程学习、习题演练及考前复习场景。

第一部分词法分析（LexicalAnalysis）

1.习题（龙书2.2.1）

给出正则表达式(a|b)*abb对应的确定有限自动机（DFA）。

答案：

状态定义：设状态S0（初始态）、S1（匹配a或b后）、S2（匹配ab后）、S3（匹配abb后，接受态）。

转移函数：

S0输入a→S1，输入b→S0

S1输入a→S1，输入b→S2

S2输入a→S1，输入b→S3

S3输入a→S1，输入b→S0

状态图：

S0--a→S1S0--b→S0

S1--a→S1S1--b→S2

S2--a→S1S2--b→S3（接受态）

S3--a→S1S3--b→S0

考点：正则表达式到DFA的转换

解析：采用“子集构造法”，先由正则表达式构建非确定有限自动机（NFA），再将NFA确定化为DFA。核心是追踪输入字符后可达的状态集合，逐步合并等价状态，最终得到最小DFA。

2.习题（陈火旺版3.2）

已知文法G：

S→aS|bS|ε

（1）构造该文法的最小DFA；（2）说明该文法识别的语言。

答案：

（1）最小DFA构造：

状态：S0（初始态，也是接受态，对应ε）

转移：S0输入a→S0，输入b→S0

说明：因所有输入均回到自身，且初始态为接受态，故最小DFA仅含1个状态S0。

（2）识别的语言：由a和b组成的所有字符串（包括空串），即L(G)={a,b}。

考点：正规文法与有限自动机的对应关系

解析：该文法为正规文法（右线性文法），其产生的语言是正规集。通过分析推导过程，发现任意a、b组合及空串均可由S推导得出，故对应正则表达式{a,b}，最小DFA仅需1个接受态即可表示。

第二部分语法分析（SyntaxAnalysis）

3.习题（龙书4.2.2）

判断文法G是否为LL(1)文法：

S→AB

A→a|ε

B→b|ε

答案：

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

计算FIRST集：

FIRST(A)={a,ε}，FIRST(B)={b,ε}

FIRST(AB)=FIRST(A)∪FIRST(B)（因A可推导出ε）={a,b,ε}

计算FOLLOW集：

FOLLOW(S)={$}

FOLLOW(A)=FIRST(B)∪FOLLOW(S)={b,ε,}（去掉ε后为{b,}）

FOLLOW(B)=FOLLOW(S)={$}

LL(1)条件检查：

对A→a|ε，FIRST(a)∩(FIRST(ε)∪FOLLOW(A))={a}∩{b,}=?；对B→b|ε，FIRST(b)∩(FIRST(ε)∪FOLLOW(B))={b}∩{}=?；

但FIRST(AB)中存在交集（如A推ε后B推b，与A推a无冲突），核心冲突在于：当输入为b时，A可推ε后由B处理，也可由A不推ε但无对应产生式，实际因FIRST(A)与FOLLOW(A)无冲突，此处判断有误，正确结论应为是LL(1)文法（修正：经严格计算，所有产生式均满足LL(1)条件，原判断错误）。

考点：LL(1)文法的判定条件

解析：LL(1)文法需满足：对任一非终结符A的任意两个产生式A→α|β，（1）FIRST(α)∩FIRST(β)=?；（2）若β→ε，则FIRST(α)∩FOLLOW(A)=?。本题中两产生式均满足条件，故为LL(1)文法。

4.习题（陈火旺版4.3）

对文法G：

E→E+T|T

T→T*F|F

F→(E)|i

（1）构造其递归下降分析程序的伪代码；（2）给出输入串i+i*i的分析过程。

答案：

（1）递归下降分析程序伪代码：

//全局变量：token（当前输入符号）

voidE(){

T();

while(token==+){

match(+);//匹配+并读取下一个token

T();

}

}

voidT(){

F();

while(token==*){