《编译原理》第四章试题

编译原理2014—2015学年第二学期第四单元测试试卷（闭卷考试）时间：45分钟满分：100分姓名班级出题人刘兵班级 2一、选择题（5*2分）（每题1分，共10分）1．编译过程中语法分析器的任务就是__________。

(1) 分析单词是怎样构成的（2）分析单词串是如何构成语句和说明的（3）分析语句和说明是如何构成程序的（4)分析程序的结构A （2）（3） B（2）（3）（4） C （1）（2）（3） D（1）（2）（3）（4）2．给定文法G[S]及其非终结符A，FIRST(A)定义为：从A 出发能推导出的终结符号的集合（S 是文法的起始符号，为非终结符）。

对于文法G[S]：S→[L] | aL→L, S| S其中，G[S]包含的四个终结符号分别为：a , [ ]则FIRST(S)的成员包括。

A. aB. a、[C. a、[和]D. a、[、]和，3．若一个文法是递归的，则它产生的句子个数是( )A．无穷个 B．不确定 C．有限个 D.根据具体情况而定4．语法分析器则可以发现源程序中的__D___。

A．语义错误 B．语法和语义错误 C．错误并校正 D．语法错误5．若文法 G 定义的语言是无限集，则文法必然是( ) 。

A．递归的 B．前后文无关的C．二义性的 D．无二义性的二、简答题（2*10分）（每题10分，共20分）1．自上而下分析的前提？2.若有文法A→(A)A|ε，说明该文法是LL(1)的文法。

三、分析题（4题共70分）1．设有文法G[E]:E→Aa|BbA→cA|eBB→bd试按照递归子程序法为该文法构造语法分析程序。

2．设有文法G[S]：S→ABA→bB|AaB→Sb|a试消除该文法的左递归。

3.计算练习4.2.2的文法的FIRST和FOLLOW集合(1)S->S(S)S|ε(2)S->(L)|a, L->L, S|S4. 正规式(ab)*a与正规式a(ba)*是否等价？请说明理由。

第五章习题5-1设有文法G[S] ：S→A/A→aA∣ AS∣/(1)找出部分符号序偶间的简单优先关系。

(2)验证 G[S] 不是简单优先文法。

5-2对于算符文法G[S] ：S→E E→ E-T∣ T T→T*F∣F F→ -P∣P P→ (E)∣i(1)找出部分终结符号序偶间的算符优先关系。

(2)验证 G[S] 不是算符优先文法。

5-3 设有文法G′[E] ：E→E E→E+T |T1T →T T→T*F|F F→(E)|i11111其相应的简单优先矩阵如题图5-3所示，试给出对符号串（i+i ）进行简单优先分析的过程。

题图 5-3 文法 G′ [E] 的简单优先矩阵5-4设有文法G[E]：E→E+T|TT→T*F|FF→(E)|i其相应的算符优先矩阵如题图5-4 所示。

试给出对符号串（i+i ）进行算符优先分析的过程。

(i*+)#(○○○○○＜＜＜＜＝i○○○○＞＞＞＞○○○○○○*＜＜＞＞＞＞○○○○○○+＜＜＜＞＞＞○○○○)＞＞＞＞○○○○#＜＜＜＜题图 5-4文法 G[E] 的算符优先矩阵5-5对于下列的文法，试分别构造识别其全部可归前缀的DFA和 LR(0) 分析表，并判断哪些是LR(0) 文法。

(1)S →aSb∣ aSc∣ ab(2)S →aSSb∣ aSSS∣c(3)S →AA→Ab∣ a5-6下列文法是否是SLR(1)文法？若是，构造相应的SLR(1) 分析表，若不是，则阐明其理由。

(1) S →Sab∣ bR R→S∣a(2) S →aSAB∣ BA A→aA∣ B B→ b(3) S →aA∣bB A→cAd∣εB→cBdd∣ε5-7对如下的文法分别构造LR(0) 及 SLR(1) 分析表，并比较两者的异同。

S→cAd∣ b A→ASc∣a5-8对于文法G[S]:S→A A→BA∣εB→ aB∣ b(1)构造 LR(1) 分析表；(2)给出用LR(1)分析表对输入符号串abab 的分析过程。

编译原理龙书第四章答案编译原理是计算机科学中的一门基础课程，是用于教授计算机程序的设计、构建和优化的学科，常常被用于编写编译器和解释器。

在编译原理课程中，龙书（Compilers: Principles, Techniques, and Tools）是一本经典的教材，其中第四章主要讲述了词法分析器的设计和实现。

以下是第四章的答案，按照列表划分：1. 什么是词法分析器？词法分析器（Lexical Analyzer）是编译器的组成部分之一，它用于将程序中的字符序列转换为一系列单词或词法单元（Lexeme），以便后续的语法分析和语义分析使用。

2. 词法分析器的工作流程是什么？词法分析器的工作流程如下：（1）读入字符序列。

（2）将字符序列划分为一个个词法单元，或者检查字符序列是否合法。

（3）生成一个词法单元序列，并将其传递给语法分析器。

3. 词法单元的定义是什么？词法单元是编程语言中的一个基本单元，它是对代码中的一个单一概念进行编码的基本方式。

例如，在C语言中，词法单元包括关键字（如int，if，while等）、标识符（Identifier，即自定义变量名）、运算符和特殊符号等。

4. 有哪些方法可以实现词法分析器？可以使用正则表达式、自动机等方法实现词法分析器。

其中，正则表达式可以表示字符串的集合，因此可以将其用于识别单词类别；自动机是根据输入字符序列转换状态的一种计算模型，因此可以用于实现有限自动机（Deterministic Finite Automaton）和非确定有限自动机（Nondeterministic Finite Automaton）等。

5. DFA和NFA分别是什么？DFA和NFA都是有限自动机的一种，但在转换动作上有所不同。

DFA 是确定的有限自动机，即在状态转换时只有唯一的一个选择；而NFA 是非确定的有限自动机，即在状态转换时可以有多个选择。

6. DFA和NFA之间有什么关系？DFA和NFA虽然在转换动作上不同，但它们可以互相转化。

第四章 词法分析1．构造下列正规式相应的DFA ：(1) 1(0|1)*101(2) 1(1010*| 1(010)*1)*0 (3) a((a|b)*|ab *a)*b (4) b((ab)*| bb)*ab 解：(1)1(0|1)*101对应的NFA 为下表由子集法将NFA 转换为DFA ：(2)1(1010*| 1(010)*1)*0对应的NFA 为 10,1下表由子集法将NFA转换为DFA：(3)a((a|b)*|ab *a)*b (略) (4)b((ab)*| bb)*ab (略)2．已知NFA=（{x,y,z},{0,1},M,{x},{z}）其中：M(x,0)={z},M(y,0)={x,y},M(z,0)={x,z},M(x,1)={x}, M(y,1)=φ,M(z,1)={y},构造相应的DFA 。

解：根据题意有NFA 图如下下表由子集法将NFA 转换为DFA ：0，1下面将该DFA最小化：(1)首先将它的状态集分成两个子集：P1={A,D,E},P2={B,C,F}(2)区分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等价。

由于F(B,0)=F(C,0)=C,F(B,1)=D,F(C,1)=E,而D，E不等价（见下步），从而B与C，F可以区分。

有P21={C,F},P22={B}。

(3)区分P1:由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有P11={A,E},P12={D}。

(4)由于F(A,0)=B,F(E,0)=F,而B，F不等价，所以A，E可以区分。

(5)综上所述，DFA可以区分为P={{A}，{B}，{D}，{E}，{C，F}}。

所以最小化的DFA如下：3.将图确定化：1101111解：下表由子集法将NFA 转换为DFA ：4.把图的(a)和(b)分别确定化和最小化：(a) (b)解： (a):下表由子集法将NFA 转换为DFA ：0，1a可得图（a1），由于F(A,b)=F(B,b)=C,并且F(A,a)=F(B,a)=B,所以A,B 等价，可将DFA 最小化，即：删除B ，将原来引向B 的引线引向与其等价的状态A ，有图(a2)。

1.1考虑下面文法G1S->a|^|(T)T->T,S|S消去G1的左递归。

然后对每个非终结符，写出不带回溯的递归子程序。

答:：(1)消除左递归:S->a|^|(T)T-> ST’T’->,S T’|ε(2)first(S)={ a , ^ , ( } first(T)= { a , ^ , ( } first(T’)={ , ε}First(a)={a},First(^)={^},First( (T) )={ ( }S的所有候选的首符集不相交First(,ST’)={,} ,First(ε)={ε},T’的所有候选的首符集不相交Follow(T’)=Follow(T)={ )}first(T’)∩Follow(T’)={}所以改造后的文法为LL(1)文法。

不带回溯的递归子程序如下：S( ){if (lookahead=’a’) advance;Else if(lookahead=’^’) advance;Else if(lookahead=’(’){advance;T();if(lookahead=’)’) advance;else error();}Else error();}T( ){S( );T’( ):}T’->,S T’|εT’( ){if (lookahead=’,’){advance;T’();}Else if(lookahead=Follow(T’)) advance;Else error;}有文法G(S):S→S+aF|aF|+aFF→*aF|*a(1)改写文法为等价文法G[S’]，消除文法的左递归和回溯(2)构造G[S’]相应的FIRST和FOLLOW集合；(3)构造G[S’]的预测分析表，以此说明它是否为LL(1)文法。

(4)如果是LL(1)文法，请给出句子a*a+a*a*a的预测分析过程该文法为LL(1)文法，因为它的预测分析表中无冲突项。

========= A卷学号以1，4 ，7结尾的同学做下题=========文法G： D → TL T→ int | floatL → id R R → , id R | ε(1)构造上面文法的LL(1)分析表。

(2) 证明文法是否为LL(1)文法。

(3) 给出分析器接受int id, id的自上而下分析步骤。

========= B卷学号以2，5，8结尾的同学做下题==========文法G：S→a | ∧|(T) T→T,S | S(1) 计算S和T 的firstVT和lastVT。

(2) 获取该文法的优先关系表。

(3) 给出(a, ( a , a)) 的算符优先分析步骤。

========= C卷学号以0，3，6，9 结尾的同学做下题======文法G： E → aTd T → Eb|a(1)画出该文法识别活前缀的DFA，证明G不是LR(0)文法而是SLR(1)文法。

(2)获取SLR分析表。

(3)给出aaadbd的规范归约分析步骤。

文法G： D → TL T→ int | floatL → id R R → , id R | ε(1)构造上面文法的LL(1)分析表。

(2) 证明文法是否为LL(1)文法。

(3) 给出分析器接受int id, id的自上而下分析步骤。

First(D)=First(T)={int,float}First(L)={id}First(R)={, ε} follow(R)={#}Select(D → TL)= First(TL)= {int,float}Select(T→ int)={int}Select(T→ float)={float}Select (L → id R)= First(id R)={id}Select(R → , id R)= First(,id R)={,}Select(R →ε)= (First(ε)-{ε})∪follow(R)= {#}因为Select(T→ int)∩Select(T→ float)=∅Select(R → , id R)∩Select(R →ε)=∅所以该文法为LL（1）文法。