编译原理模拟题

《编译原理》

课

程

学

习

指

导

书

作者：柴玉梅

《编译原理》课程指导书

第一章编译概述

（一）本章学习目标

1.正确理解什么是编译程序、编译程序工作的基本过程及其各阶段的基本任务；

2. 熟练掌握编译程序总框；

3.了解编译程序的生成方法和编译技术在软件开发中的应用。

（二）本章重点、要点

编译程序的概念、编译程序各阶段的划分及任务。

（三）本章练习题和思考题

1.1编译程序由哪几部分构成？简述各部分功能。

1.2简述编译程序工作的基本过程，其各阶段的基本任务是什么？

1.3.编译程序的生成方法有哪些？

1.4画出编译程序总框。

1.5描述词法规则、语法规则、语义规则各使用哪些描述工具？

第二章 文法和语言的基本知识

（一）本章学习目标

1.正确理解字母表和符号串的基本概念及其运算

2.熟练掌握上下文无关文法的定义；

3.熟练掌握形式语言的形式化定义方法；

4.直接推导、推导、最左（右）推导、短语、直接短语、句型、句柄、句子及语言等重要概念；

5.能为给定语言构造文法；

6.能利用推导与语法分析树判断文法的二义性，并进行修改；

7.了解文法和语言的分类。

（二）本章重点、要点

1.上下文无关文法的定义；

2.直接推导、推导、句型、短语、直接短语、句柄、句子等重要概念；

3.为给定语言构造文法；

4.二义文法的判定。

（三）本章练习题和思考题

2.1写文法G1,G2, 分别产生语言:

(1) L(G1)={ambn｜m＞0，n.≥0}。

(2)L(G2)={bmabm|m≥0}。

2.2设文法G为：E→（E）｜abc  

(1) 写出文法G所定义的语言L（G）。

(2) 判断abc、（（（abc））是否为L（G）的句子，说明理由。

(3) 画出句型（（E））的语法树，写出其短语、直接短语和句柄。

2.3设有文法G[A]:

   Aa|b|e|A0|A1

（1）试问分别由哪些符号组成？

（2）下列符号串a,a0,a0e01,0a,e111,e0011是否为该文法的句子？

（3）写出文法G1[A]产生的语言

第三章  词法分析与有穷自动机

（一）本章学习目标

1.理解词法分析器的功能及单词符号及输出单词的形式；

2.熟练掌握正规式与有穷自动机的定义形式；

3.熟练掌握有NFA到DFA的转换及DFA的确定化；

3.熟练掌握正规式与有穷自动机的等价性及其相互转换方法；

4.熟练掌握正规文法与有穷自动机的定义形式；

5.熟练掌握正规文法与有穷自动机的等价性及其相互转换方法；

6.能依据状态转换图编写词法分析程序。

（二）本章重点、要点

1.词法分析器的功能

2.正规式、正规文法与有穷自动机的定义形式；

3.NFA到DFA的转换及DFA的确定化；

4.正规式、正规文法与有穷自动机的等价性及其相互转换方法；

5.词法分析程序的编写方法

1.

（三）本章练习题和思考题

3.1设正则表达式ba*，

(1) 所定义的正规集（语言）L 是什么？

(2) 构造识别L的NFA。

(3) 构造定义L的正则文法。

3.2设正则表达式bba*aa，

(1) 所定义的正规集（语言）是什么？

(2) 构造识别L的最小DFA。

(3) 为其构造正则文法。

3.3有文法G(S)：

SaAc

AbA|aA|a

(1)给出文法G(S)所对应的正规式。

(2)构造G(S)对应的NFA

(3)将 G(S)对应的NFA确定化

(4)将 (3)中的DFA最小化

第四章   语法分析

（一）本章学习目标

1.理解语法分析程序的功能；

2.掌握自上而下语法分析原理；

3.熟练掌握确定的自上而下语法分析的前提条件、LL(1)文法的判定及变换；

4.熟练掌握LL(1)分析方法

5.掌握自下而上语法分析原理；

6.熟练掌握算符优先分析方法；

7.熟练掌握算符优先文法的判定。

8.了解优先函数的构造

（二）本章重点、要点

1.自上而下和自下而上语法分析的基本原理；

2.LL(1)分析表的构造及其分析算法

3.算符优先分析表的构造及其分析算法

（三）本章练习题和思考题

4.1考虑下面文法 G1:

S→a|∧|(T)

T→T,S|S

(1)消去G1的左递归，然后对每个非终结符写出不带回溯的递归子程序。

(2)经过改写的文法是否是LL（1）的？给出它的预测分析表。

4.2下面文法那些是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

4.3简述算符优先分析过程。

4.4设有表格结构文法G[S]：

(1)给出（a，（a，a））的最左、最右推导，并画出相应的语法树。

(2)计算文法G[S]的FIRSTVT集和LASTVT集。

(3)构造G[S]的优先关系表，并判断G[S]是否为算符优先文法。

样卷

一.(15分)编译程序由哪几部分构成？简述各部分功能。 

二.(15分)写出产生语言L(G1) 的文法G1：

L(G1)={am bm c n｜m，n≥0}。

三.(25分).设语言L是字母表{0，1}上以0开头、以1结尾的所有序列的集合。

 （1）写出其正则表达式。

 （2）构造识别L的NFA。

 （3）构造识别L的DFA。

 （4）给出其最小DFA。  

四.(20分)设有文法G[S]:

S→A   

A→B|AiB

S→C|B+C       

T→A*|(

（1）试画出句型C+Ci(的语法树，并给出该句型的短语、直接短语、句柄和素短语。

（2）判断其是否为算符优先文法。

五.(25分)设有文法G[S]:    

S→a|b|(T)       

T→T,S|S

（1）计算每个非终结符的 FIRSTVT 和 LASTVT。

（2）构造算符优先关系分析表。 

（3）文法G[S] 是算符优先文法吗？如果是，给出优先函数，并给出串 (a,(a,a)) 的算符优先分析过程。

附：各章练习题答案

第一章

1.1编译程序由哪几部分构成？简述各部分功能。

参：

五个部分

词法分析：接收输入源程序串，输出单词序列。

语法分析：接收单词序列，识别出各种语法成分，并做语法检查。

语义分析与中间代码生成：分析每个语法结构的静态语义，生成某种形式的中间代码。

优化：在不改变程序执行结果的前提下，提高中间代码或目标代码的质量。

目标代码生成：将中间代码转换成等价的目标代码。

1.2简述编译程序工作的基本过程，其各阶段的基本任务是什么？

参：

词法分析：接收输入源程序串，输出单词序列。

语法分析：接收单词序列，识别出各种语法成分，并做语法检查。

语义分析与中间代码生成：分析每个语法结构的静态语义，生成某种形式的中间代码。

优化：在不改变程序执行结果的前提下，提高中间代码或目标代码的质量。

目标代码生成：将中间代码转换成等价的目标代码。

1.3编译程序的生成方法有哪些？

参：

(1)手工编写编译程序

(2)自编译

(3)自动生成编译程序

(4)移植

1.4画出编译程序总框。

参见教材第4页图1.5。

1.5描述词法规则、语法规则、语义规则各使用哪些描述工具？

参：

描述词法规则工具：DFA、NFA、正规式、正规文法等。

描述语法规则使用工具：上下文无关文法。

描述语义规则各使用工具：属性文法、操作语义、公理语义、指称语义等。

第二章

2.1写文法G1,G2, 分别产生语言:

(1)L(G1)={ambn｜m＞0，n.≥0}

参：

G1:SAB

Aa|Aa

B|Bb 

(2) L(G2)={bmabm|m≥0}

参：

G2:Sa|bSb

2.2设文法G为：E→（E）｜abc  

(1)写出文法G所定义的语言L（G）。

参：

L(G)={(ma)m|m≥0}

(3)判断abc、（（（abc））是否为L（G）的句子，说明理由。

参：

abc是L(G)的句子。

因为存在推导：Eabc

（（（abc））不是L（G）的句子

因为不存在任何产生（（（abc）串的推导。

(3)画出句型（（E））的语法树，写出其短语、直接短语和句柄。

全部短语为：(E) 、((E))。

直接短语为：(E)。

句柄为(E)。

2.3设有文法G[A]:

   Aa|b|e|A0|A1

(1)试问分别由哪些符号组成？

参：

VT={a,b,e,0,1}

VN={A}

(2)下列符号串a,a0,a0e01,0a,e111,e0011是否为该文法的句子？

参：

a,a0, e111,e0011是该文法的句子。

a0e01,0a不是该文法的句子。

(3)写出文法G1[A]产生的语言

参：

L(G1)是以a,b,e开头后跟若干个0或1的串。

2.4写出产生语言L(G1) 的文法G1：

L(G1)={am bm c n｜m，n≥0}。

参：G1:  S AB

A  |aAb

B  |Bc

第三章

3.1设正则表达式ba*，

(1) 所定义的正规集（语言）L 是什么？

参：

L={bam|m≥0}。

(2) 构造识别L的NFA。

参：

(3) 构造定义L的正则文法。

参：

A b|bB

B a|aB

3.2设正则表达式bba*aa，

(1)所定义的正规集（语言）是什么？

参：

L={bbam aa |m≥0}。

(2)构造识别L的最小DFA。

参：

(3)为其构造正则文法。

参：

A bB

B bC

C aC|aD

D a

3.3有文法G(S)：

SaAc

AbA|aA|a

(1)给出文法G(S)所对应的正规式。

参：

a(a|b)*ac

(2)构造G(S)对应的NFA

参：

(3)将 G(S)对应的NFA确定化

参：

(4)将 (3)中的DFA最小化

参：

第四章

4.1考虑下面文法 G1:

S→a|∧|(T)

T→T,S|S

(3)消去G1的左递归，然后对每个非终结符写出不带回溯的递归子程序。

(4)经过改写的文法是否是LL（1）的？给出它的预测分析表。

参：

（1）消去G1的左递归：S→a|∧|(T)

 T→ST’

T’ →,ST’|ε

递归子程序：

PROCEDURE S;

IF sym=’a’ THEN ADVANCE

ELSE IF sym=’ ∧’ THEN ADVANCE

ELSE IF sym=’ (’ THEN

      BEGIN

        ADVANCE

        T;

        IF sym=’ )’ THEN ADVANCE

        ELSE  ERROR

      END

ELSE  ERROR;

PROCEDURE T;

BEGIN

S;T’

END;

PROCEDURE S;

IF sym=’ ,’ THEN

      BEGIN

        ADVANCE

        S;T’

      END;

（2）是LL（1）文法。

FIRST(S)={ a,∧,( } a,∧,( }  FIRST(T’)={ ,,ε }

FOLLOW(S)={ #, , , ε, )  } ) }  FOLLOW(T’)={ ) }

预测分析表如下：

 （1）S →Abc   A →a|ε   B→b|ε

参：      

      没有左递归且FIRST 候选集不冲突且

 FIRST(A)∩FOLLOW(A)={ a, ε} ∩  { b }=Ф

 FIRST(B)∩FOLLOW(B)={ b, ε} ∩  { c }=Ф

所以该文法为LL（1）文法

（2）S →Ab   A →a|B|ε   B→b|ε

参：

    FIRST(B)＝{ b, ε} ∩ ε) ={ε} ≠Ф

      所以该文法不是LL（1）文法

（3）S →ABBA    A →a |ε   B→b|ε

参：

   没有左递归且FIRST 候选集不冲突

  FIRST(A)∩FOLLOW(A)={ a, ε} ∩{b,#} =Ф

  FIRST(B)∩FOLLOW(B)={ b, ε}∩{b,a,#} ≠Ф

所以该文法不是LL（1）文法

(4) S →aSe|B    B →bBe |C   C→cCe|d

参：

  没有左递归且FIRST 候选集不冲突

  所以该文法为LL（1）文法

4.3简述算符优先分析过程。

参：

算符优先分析法是一种简单、直观、广为使用的自下而上语法分析方法，它是依据算术表达式的四则运算过程而设计的一种方法，也适用于对一般的高级语言程序的分析。算符优先分析法的基本思想是，首先确定运算符（确切地说是终结符）之间的优先关系和结合性质，然后借助这种关系，比较相邻运算符之间的优先级来确定句型的可归约串，并进行归约。

值得注意的是，算符优先分析过程虽然是自下而上归约过程，但它的可归约串未必是句柄，而是素短语。也就是说，算符优先分析过程不是一种规范归约。

4.4设有表格结构文法G[S]：

(1)给出（a，（a，a））的最左、最右推导，并画出相应的语法树。

参：

最左推导：S (T) (T,S) (S,S) (a,S) (a,(T,S)) (a,(S,S)) (a,(a,S)) (a,(a,a))

最右推导：S (T) (T,S) (T,(T,S) (T,(T,a) (T,(S,a)) (T,(a,a)) (S,(a,a)) (a,(a,a))

语法树：

(2)计算文法G[S]的FIRSTVT集和LASTVT集。

参：

FIRSTVT(S)={a, ^,  }

FIRSTVT(T)= {a, ^,  ,,}

LASTVT(S)= {a, ^, }

LASTVT(T)= {a, ^, ,,}              

(3)构造G[S]的优先关系表，并判断G[S]是否为算符优先文法。

参：