计算first集合和follow集合

编译原理复习题一、选择题1、编译原理是对(C)。

A、机器语言的执行B、汇编语言的翻译C、高级语言的翻译D、高级语言程序的解释执行2、(A)是一种典型的解释型语言。

A．BASIC B．C C．FORTRAN D．PASCAL3、把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。

A. 编译器B. 汇编器C. 解释器D. 预处理器4、用高级语言编写的程序经编译后产生的程序叫(B)A．源程序 B．目标程序C．连接程序D．解释程序5、(C)不是编译程序的组成部分。

A.词法分析程序B.代码生成程序C.设备管理程序D.语法分析程序6、通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。

A．模拟执行器B．解释器 C．表格处理和出错处理D．符号执行器7、编译程序绝大多数时间花在(D)上。

A．出错处理B．词法分析C．目标代码生成D．表格管理8、源程序是句子的集合，(B)可以较好地反映句子的结构。

A. 线性表B. 树C. 完全图D. 堆栈9、词法分析器的输出结果是(D)。

A、单词自身值B、单词在符号表中的位置C、单词的种别编码D、单词的种别编码和自身值10、词法分析器不能(D)A. 识别出数值常量B. 过滤源程序中的注释C. 扫描源程序并识别记号D. 发现括号不匹配11、文法：G：S→xSx | y所识别的语言是(D)。

A、xyxB、(xyx)*C、x*yx*D、x n yx n (n≥0)12、如果文法G是无二义的，则它的任何句子α(A)A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同13、正则文法(A)二义性的。

A. 可以是B. 一定不是C. 一定是14、(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。

编译原理答案编译原理复习回顾题一、填空题1. 汇编程序将翻译成；编译程序将翻译成。

2. 编译程序工作工程可以划分为、、、和等5个基本阶段，同时还会伴有和。

3. 对编译程序而言，输入数据是，输出数据是。

4. 已知文法G[E]: E—>T|E+T|E-F, T－>F|T*F|T/F,,F—>(E)|I (“,”是间隔符号，不是文法中的符号)。

该文法的开始符号（识别字符）是，终结符号集合V T是，非终结符号结合V N是，句型T+T*F+i的短语有。

该文法消除直接左递归，改写后的文法为E－> ,T－> ,F －> .5. Chomsky定以来寺中形式语言的文法分别为：文法（又称文法）、文法（又称文法）、文法（又称文法）、文法（又称文法）。

6. 编译过程中扫描器所完成的任务是从中识别出一个个具有。

7. 确定的有穷自动机是一个，通常表示为。

8. LL(k)分析中，第一个L的含义是，第二个L的含义是，“k”的含义是。

9. LL(1)分析中，第一个L的含义是，第二个L的含义是，“1”的含义是。

10.LR(0)分析中，“L”的含义是，“R”的含义是，“0”的含义是。

11.SLR(1)分析中，“L”的含义是，“R”的含义是，“1”的含义是。

12.LR(1)分析中，“L”的含义是，“R”的含义是，“1”的含义是。

13.算术表达式：a*(-b+c)的逆波兰式表示为：。

14.算术表达式：a＋b*(c+d/e)的逆波兰式表示为：。

15.在编译程序中安排中间代码生成的目的是和。

16.语法制导的翻译程序能同时进行分析和分析。

17.根据所涉及的程序范围，优化可分为、、三种。

二、简单题1. 有人认为编译程序的词法分析、语法分析、语义分析和中间代码生成、代码优化、目标代码生成五个组成部分是缺一不可的，这种看法正确吗？说明理由。

2. 多边扫描的程序是高质量的编译程序，优于单遍扫描的编译程序”，对吗？为什么？3. LR分析器与优先分析器在识别被归约串时的主要异同时什么？三、给出生成下述语言的上下文无关的文法{1n0m1m0n|n,m>=0}{WaW r|W属于{0|1}*,W r表示W的逆}四、给出生成下列语言的三型文法：{a n|n>=0}{a n b m|n,m>0}{a n b m c k|n,m,k>=0}五、构造正规式1(0|1)*101相应的最小DFA。

编译原理复习题及答案一、选择题1．一个正规语言只能对应(B)A一个正规文法B一个最小有限状态自动机2．文法G[A]：A→εA→aBB→AbB→a是(A)A正规文法B二型文法3．下面说法正确的是(A)A一个SLR（1）文法一定也是LALR（1）文法B一个LR（1）文法一定也是LALR（1）文法4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的(A)A必要条件B充分必要条件5．下面说法正确的是(B)A一个正规式只能对应一个确定的有限状态自动机B一个正规语言可能对应多个正规文法6．算符优先分析与规范归约相比的优点是(A)A归约速度快B对文法限制少7．一个LR（1）文法合并同心集后若不是LALR（1）文法(B)A则可能存在移进/归约冲突B则可能存在归约/归约冲突C则可能存在移进/归约冲突和归约/归约冲突8．下面说法正确的是(A)ALe某是一个词法分析器的生成器BYacc是一个语法分析器9．下面说法正确的是(A)A一个正规文法也一定是二型文法B一个二型文法也一定能有一个等价的正规文法10．编译原理是对(C)。

A、机器语言的执行B、汇编语言的翻译C、高级语言的翻译D、高级语言程序的解释执行C．FORTRAND．PASCAL11．(A)是一种典型的解释型语言。

A．BASICB．C12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。

A.编译器B.汇编器C.解释器D.预处理器13．用高级语言编写的程序经编译后产生的程序叫(B)A．源程序B．目标程序C．连接程序14．(C)不是编译程序的组成部分。

A.词法分析程序B.代码生成程序D．解释程序D.语法分析程序C.设备管理程序15．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。

A．模拟执行器B．解释器C．表格处理和出错处理D．符号执行器16．编译程序绝大多数时间花在(D)上。

6
分析中出现的问题2：回溯问题
从各种可能的选择中随机挑选一种， 并希望它是正确的。 如果以后发现它是错误的，必须退 回去，再试另外的选择这种方式称为回 溯。 回溯代价极高，效率很低。
7
在自上而下的分析方法中如何选择使 用哪个产生式进行推导？ 假定要被替换的最左非终结符号是B， 且有n条规则：B→A1|A2|…|An，那么如何 确定用哪个右部去替代B？ 从文法的开始符号出发，如何根据当前 的输入符号（单词符号）唯一地确定选用哪 个产生式替换相应非终结符往下推导，或构 造一棵相应的语法树。
8
§4.2 FIRST和FOLLOW集合的构造
9
例1:输入串w=pccadd是否是合法的句子？
G：S→pA|qB A→cAd|a B→dB|b
S=>pA=>pcAd=>pccAdd=>pccadd 总结：本题中对于一个非终结符，存在若干 个候选式，即产生式形如：P→α1|α2|……|αn 每个候选式的第一个字符都是终结符， 且都不相同。这时可直接选用与当前输入符 号相同的那个候选式来替换P。
42
3. 若X为一非终结符，则查分析表M。 若M[X，a]中为A—产生式，将A自栈 顶弹出，将产生式右部符号串按逆序逐 一推入栈中；当产生式为A时，则只将 A→ε弹出即可。若M[X，a]中为空,则调 用出错处理程序。
43
算法实现
当前字符匹 配成功。 要对栈顶的 非终结符进 行替换。
44
初始化
注意一 定要逆 序入栈。
48
49
通过表4-9可以看到，每个非终结符对应 产生式的各个候选式的交集如下：
可以验证，此文法是LL(1)文法。
50
递归下降语法分析程序如下：

一、选择1．将编译程序分成若干个“遍”是为了_使程序的结构更加清晰__。

2．正规式 MI 和 M2 等价是指__.M1 和 M2 所识别的语言集相等_。

3．中间代码生成时所依据的是 _语义规则_。

4．后缀式 ab+cd+/可用表达式__(a+b)/(c+d)_来表示。

6．一个编译程序中，不仅包含词法分析，_语法分析 ____，中间代码生成，代码优化，目标代码生成等五个部分。

7．词法分析器用于识别__单词___。

8．语法分析器则可以发现源程序中的___语法错误__。

9．下面关于解释程序的描述正确的是__解释程序的特点是处理程序时不产生目标代码 ___。

10．解释程序处理语言时 , 大多数采用的是__先将源程序转化为中间代码 , 再解释执行___方法。

11．编译过程中 , 语法分析器的任务就是__(2)(3)(4)___。

(1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的(3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构12．编译程序是一种__解释程序__。

13．文法 G 所描述的语言是_由文法的开始符号推出的所有终极符串___的集合。

14．文法分为四种类型，即 0 型、1 型、2 型、3 型。

其中 3 型文法是___正则文法__。

15．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _产生式__。

16．通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括_表格处理和出错处理__。

17．文法 G[N]= （ {b} ， {N ， B} ， N ， {N→b│ bB ， B→bN} ），该文法所描述的语言是L(G[N])={b2i+1│ i ≥0}18．一个句型中的最左_简单短语___称为该句型的句柄。

19．设 G 是一个给定的文法，S 是文法的开始符号，如果 S->x( 其中 x∈V*), 则称 x 是文法 G 的一个__句型__。

6．削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性。(Y )
7．在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。(N )
8．算符优先关系表不一定存在对应的优先函数。( N)
9．数组元素的地址计算与数组的存储方式有关。(N )
10．编译程序与具体的机器有关,与具体的语言无关。(N )
SELECT(F'->*F')={*};
SELECT(F'->ε)=FOLLOW(F')={(,a,b,^,+,),#};
SELECT(P->(E))={(}
SELECT(P->a)={a}
SELECT(P->b)={b}
SELECT(P->^)={^}
可见，相同左部产生式的SELECT集的交集均为空，所以文法G[E]是LL(1)文法。
A．候选式B．句型C．单词D．产生式
5．文法G[E]：
E→T∣E＋T
T→F∣T﹡F
F→a∣（E）
该文法句型E＋F﹡(E＋T)的简单短语是下列符号串中的_____。
①（E＋T）②E＋T③F④F﹡(E＋T)
A．①和③B．②和③C．③和④D．③
6．若一个文法是递归的，则它所产生的语言的句子_____。
A．( )是无穷多个B．( )是有穷多个
参考答案：
解：根据题意有NFA图:
下表由子集法将NFA转换为DFA：
下面将该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}。

编译原理与技术模拟试题一一、填空题（20分，每空2分）1.1编译程序的工作过程可划分为词法分析、语法分析、、中间代码生成、代码优化、等阶段，一般在阶段对表达式中运算对象的类型进行检查。

答案：语义分析、目标代码生成、语义分析解释：要求掌握编译器的工作原理和特点。

编译和解释方式是翻译高级程序设计语言的两种基本方式。

解释程序也称为解释器，它或者直接解释执行源程序，或者将源程序翻译成某种中间表示形式后再加以执行；而编译程序（编译器）则首先将源程序翻译成目标语言程序，然后在计算机上运行目标程序。

编译过程包含词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成，以及符号表管理和出错处理。

表达式的类型信息属于语义信息，所以在语义分析阶段进行类型检查。

1.2 和预测分析法是自上而下的语法分析方法。

答案：递归下降法解释：语法分析的任务是根据语言的语法规则，分析单词串是否构成短语和句子，即表达式、语句和程序等基本语言结构，同时检查和处理程序中的语法错误。

根据语法树（或分析树）的建立方式，语法分析可分为自上而下分析和自下而上分析两类，递归下降分析和预测分析属于自上而下的语法分析方法。

1.3常用的存储分配策略有存储分配和动态存储分配，其中，动态存储分配策略包括分配和分配。

答案：静态、栈、堆解释：编译器怎样对存储空间进行组织和采用什么样的存储分配策略，很大程度上取决于程序设计语言中所采用的机制。

编译器具体实现时，根据语言机制的特性，采用静态分配策略、栈分配策略和堆分配策略三种方式的其中若干种。

静态分配策略是指编译时安排所有数据对象的存储，即绑定是静态确定的；栈分配策略是指按栈的方式管理运行时的存储；堆分配策略是指在运行时根据要求从堆数据区动态地分配和释放存储。

1.4移进、归约是分析中的典型操作。

答案：自下而上或LR解释：自下而上分析的一般思路是从句子ω开始，从左到右扫描ω，反复用产生式的左部替换产生式的右部、谋求对ω的匹配，最终得到文法的开始符号，或者发现一个错误。

• S→ A • A → Ab bBa • B → aAc a aAb
1.首先拓展文法
• • • • • •
S→ A → A → B → B → B →
A Ab bBa aAc a aAb
2.分解LR（0）项目
• • • • • • S → ·A；S → A·； A → ·Ab；A → A·b；A → Ab· ； A →·bBa；A→b·Ba；A→bB·a；A→bBa·； B →·aAc；B→a·Ac；B→aA·c；B→aAc· ； B → · a； B → a · ； B →·aAb；B→a·Ab；B→aA·b；B→aAb· ；
S→ABS B→SBB S→Aa S→ B→b A→a A
S
B
S
a
S
B
B
A
a

b
b
a
短语、句柄
习题解答
7．给文法G[S]： – SaA|bQ – AaA|bB|b – BbD|aQ – QaQ|bD|b – DbB|aA S – EaB|bF – FbD|aE|b 构造相应的最小的DFA。
由于从S出发任何输入串都 不能到达状态E和F，所以， 状态E，F为多余的状态， 不予考虑。
a a b a
A b Z
b
B a
b
D
b
b
b Q a
简化产生式后生成的NFA
I 1[S] 2[A] 3[Q] 4[B,Z] 5[D,Z] 6[D] 7[B]
Ia
= ε -closure(MoveTo(I,a))
4 5 6 7
8 9
{11,14,16,3,6} {8} {5} {7}
{4,19,17} {9}

程序设计语言与编译复习题一、是非题（请在括号内，正确的划√，错误的划×）1．词法分析作为单独的一遍来处理较好。

(× )2．规范归约（最左规约）和规范推导（最右推导）是互逆的两个过程。

(√)3．正规文法产生的语言都可以用上下文无关文法来描述。

(√ )4．编译程序与具体的机器有关,与具体的语言无关。

(× )5．一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。

(× )6．目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。

(× )7．逆波兰法表示的表达式亦称前缀式。

(√)8．如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。

(√ )9．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。

(× )10．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。

(×)11．递归下降分析法是自顶向下分析方法。

(√ )12．产生式是用于定义词法成分的一种书写规则。

(× )13．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。

(√)14．程序语言的语言处理程序是一种应用软件。

(× )15．解释程序适用于COBOL 和FORTRAN 语言。

(×)16．编译程序是对高级语言程序的解释执行。

(× )17．语法分析时必须先消除文法中的左递归。

(×)18．逆波兰表示法表示表达式时无须使用括号。

(√ )19．仅考虑一个基本块，不能确定一个赋值是否真是无用的。

(√)20．数组元素的地址计算与数组的存储方式有关。

(√)21．静态数组的存储空间可以在编译时确定。

(√)22．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。

(√)23．两个正规集相等的必要条件是他们对应的正规式等价。

《编译原理》模拟试题一一、是非题(请在括号内，正确的划错误的划X)(每个2分，共20分)1•计算机高级语言翻译成低级语言只有解释一种方式。

(X)2.在编译中进行语法检查的目的是为了发现程序中所有错误。

(X)3.甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。

(丁 )4.正则文法其产生式为A->a , A->Bb, A.BGVN , a、beVT o (X)5.每个文法都能改写为LL(1)文法。

(V)6.递归下降法允许任一非终极符是直接左递归的。

(V)7.算符优先关系表不一定存在对应的优先函数。

(X)8.自底而上语法分析方法的主要问题是候选式的选择。

(X)9.LR法是自顶向下语法分析方法。

(X)10.简单优先文法允许任意两个产生式具有相同右部。

(X)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分)1.一个编译程序中，不仅包含词法分析，_____ ,中间代码生成，代码优化，目标代码生成等五个部分。

A.()语法分析B.()文法分析C.()语言分析D.()解释分析2.词法分析器用于识别_____ oA.()字符串B.()语句C.()单词D.()标识符3 •语法分析器则可以发现源程序中的______ oA.()语义错误B.()语法和语义错误C.()错误并校正D.()语法错误4.下面关于解释程序的描述正确的是。

(1) 解释程序的特点是处理程序时不产生目标代码(2) 解释程序适用于COBOL 和FORTRAN 语言(3) 解释程序是为打开编译程序技术的僵局而开发的A. ( ) (1) (2)B. () (1)C. () (1)⑵(3)D.()⑵⑶5. _________________________________________ 解释程序处理语言时，大多数采用的是 ___________________________________ 方法。

构造预测分析表
在确定的自顶向下分析方法中，又有递归子程序法和预测分 析方法，我们采用的是预测分析的方法。一个预测分析器 由三部分组成： （1）预测分析程序 （2）先进后出栈 （3）预测分析表 其中，只有预测分析表与文法有关。分析表可用矩阵M 表示。M（A，a）中的下标A表示非终结符，a为终结符 或括号，矩阵元素M（A，a）中的内容是一条关于A的产 生式，表明当用非终结符A往下推导时，面临输入符A时， 所应采取的候选产生式，元素内容无产生式时，则表明出 错。为便于辨认，我们令M数组为 Analyze数组。
算法介绍
1、在对输入序列进行LL(1)文法分析之前，首先要对文法进行判 别，看文法是不是LL(1)文法。这个文法应该满足无二义性，无 左递归，无公因子。具体的判别过程是，求出能推出ε的非终结 符，求出FIRST集，求出FOLLOW集，求出SELLECT集，看相 同左部的产生式的SELLECT集是否有交集，有就不是LL（1）文 法。 2、如果输入文法不是LL(1)文法，可以进行转换，转换一般有两 种方法：提取左公因子法和消除左递归法。 3、构造预测分析表，设二维矩阵M。
4、预测分析。
人员分工
• 负责MFC界面制作，程序总控，各个非终结 符能否推出ε的计算,判断是否LL(1),以及人员 分工。 • 消除左递归的实现 • 提取公因子的实现 • 求FIRST集 • 求FOLLOW集 • 求SELLECT集 • 构造预测分析表，分析输入的句子
程序流程
程序开始 InitAndConvertPt(); //读入文法、消除左递归、提取公因子 InitArray(); //初始化N[ ]数组 VnRefresh(Pt); //构造非终结符集 VtRefresh(Pt);//构造终结符集 Create_N_Table(); //判断哪些非终结符可以推出空,存入N[ ]

1、编译程序：能够把用各种高级语言书写的源程序翻译成某种等价的目标程序的翻译程序。

2、遍：指编译程序对源程序或中间代码程序从头到尾扫描一次。

3、静态分配：在编译时就能够安排好目标程序运行时的全部数据空间。

4、编译程序包括词法分析、语法分析、中间代码生成、优化，目标代码产生五个阶段，上述各阶段中还要进行表格处理和出错处理的工作。

5、编译程序可分为五个阶段：词法分析、语法分析、中间代码生成、优化、目标代码生成。

上述五个阶段之间每个阶段输出为作下一阶段的输入，第一阶段的输入是源程序，最后阶段的输出是目标代码。

6、程序语言是由语法和语义两方面定义的。

语法指可以形成和产生一个合式的程序的一组规则，语义是定义一个程序的意义的一组规则。

7、一个名字的属性包括类型和作用域。

8、目标代码一般有三种形式：能够立即执行的机器语言代码，待装配的机器语言模块和汇编语言代码。

9、2型文法又称为（上下文无关文法），3型文法又为（正规文法）。

10、虽然名字都是用标识符表示的，但名字和标识符有着本质的区别。

11、词法分析器的任务是从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成单词符号串的中间程序。

12、执行词法分析的程序称为词法分析器或扫描器。

13、词法分析器所输出的单词符号常常表示成如下二元关系：（单词种别，单词自身值）。

14、词法分析器：是一种程序，它能将字符串形式的源程序改造成单词符号串形式的中间程序。

15、程序语言的单词符号包括：（标识符）、（运算符）、（常数）、（基本字）、界符等。

16、超前搜索：在词法分析过程中，有时为了确定词性，需要超前扫描若干个字符，这个动作为超前搜索。

17、状态转换图是一张有限方向图，其中结点代表状态，状态之间用箭弧连接，箭弧上的标记代表在射出结点状态下可能出现的输入字符或字符类，状态中有一个初态，至少有一个终态。

18、自上而下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一颗语法树。

《编译原理》课程复习五、计算题：1、考虑下面程序…………V ar a：integer；Procedure S(X)；V ar X：integer；Begina：＝a＋1；X：＝a＋XEnd；Begina：＝5；S(a)；Print(a)End．试问：若参数传递方式分别采取传名和传值时，程序执行后输出a的值是什么？答：传名：a＝12传值：a＝62、写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列。

逆波兰表示：abc*＋ab＋/d－三元式序列：①(*，b，c)②(＋，a，①)③(＋，a，b)④(/，②，③)⑤(－，④，d)3、已知文法G(S)S→a|∧|(T)T→T，S|S写出句子((a，a)，a)的规范归约过程及每一步的句柄。

句型归约规则句柄((a，a)，a)S→a a((S，a)，a)T→S S((T，a)，a)S→a a((T，S)，a)T→T，S T，S((S)，a)T→S S((T)，a)S→S(T)(T)(S，a)T→S S(T，a)S→a a(T，S)T→T，S T，S(T)S→(T)(T)S4、写一个文法，使其语言是奇数集，且每个奇数不以0开头。

解：文法G(N)：N→AB|BA→AC|DB→1|3|5|7|9D→B|2|4|6|8C→0|D5、设文法G(S)：S→(L)|a S|aL→L，S|S(1) 消除左递归和回溯；(2) 计算每个非终结符的FIRST和FOLLOW；(3) 构造预测分析表。

解：S→(L)|aS’S’→S|εL→SL’L’→SL’|εFIRST)S)＝{(，a}FOLLOW(S)＝{#，，，)}FIRST(S’)＝{，a,ε}FOLLOW(S’)＝{#，，，)}FIRST(L)＝{(，a}FOLLOW(L)＝{ )}FIRST(L’)＝{，，ε}FOLLOW(L’)＝{ }}6、While a＞0 ∨b＜0doBeginX：＝X＋1；if a＞0 then a：＝a－1else b：＝b＋1End；翻译成四元式序列。

*编译原理复习题一．简答题：1) 什么是句子？ 什么是语言?解答：句子——设G 是一个给定的文法，S 是文法的开始符号，如果S x （其中x ∈V T *），则称x 是文法的一个句子。

语言——语言是句子的集合。

或——设G[S]是给定文法，则由文法G 所定义的语言L(G)可描述为：L(G)＝{x │Sx,x ∈V T *} 。

2) DFA 与NFA 有何区别 ?解答:DFA 与NFA 的区别表现为两个方面:一是NFA 可以有若干个开始状态，而DFA 仅只有一个开始状态。

另一方面，DFA 的映象M 是从K ×∑到K ，而NFA 的映象M 是从K ×∑到K 的子集，即映象M 将产生一个状态集合（可能为空集），而不是单个状态。

3) 自顶向下的语法分析方法的基本思想是什么?解答:从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。

4) 自底向上的语法分析方法的基本思想是什么?解答:从给定的输入串（终结符串）开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。

5) 一个上下文无关文法G 包括哪四个组成部分？解答:一组非终结符号，一组终结符号，一个开始符号，以及一组产生式。

6) 在自底向上的语法分析方法中，分析的关键是什么？解答:关键是寻找句柄。

7)在自顶向下的语法分析方法中，分析的关键是什么？解答:关键是选择候选式。

8）什么是属性文法？答：是在上下文无关文法的基础上，为每个文法符号(含终结符和非终结符)配备若干个属性值，对文法的每个产生式都配备了一组属性计算规则(称为语义规则)。

在语法分析过程中，完成语义规则所描述的动作，从而实现语义处理。

一个属性文法形式的定义为一个三元组AG，AG=（G，V，E）。

其中G为一个上下文无关文法；V为属性的有穷集；E为一组语义规则。

9）语法制导翻译语法制导翻译：定义翻译所必须的语义属性和语义规则，一般不涉及计算顺序。

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

解：本题考查消除左递归的方法。

应用消除文法左递归的算法对文法G[S]消除左递归的过程如下：（1）将非终结符排序为：U1=S，U2=A，U3=B（2）进入算法排序：i=1时，对文法无影响i=2，j=1时：A→Aa有直接左递归，消去该直接左递归，得A→bBA’A’→aA’|εi=3，j=1时：改写文法，有B→ABb|aj=2时：改写文法，有B→bBA’Bb|a无左递归。

（3）所以文法G[S]消除左递归后变为：G’[S]：S→ABA→bBA’A’→aA’|εB→bBA’Bb|a2.设有文法G[E]:E→Aa|BbA→cA|eBB→bd试按照递归子程序法为该文法构造语法分析程序。

解：本题考查递归子程序的构造方法。

首先判断文法是否满足递归子程序法对文法的要求，然后再构造递归子程序。

因为：（1）该文法无左递归。

（2）文法的产生式E→Aa|Bb和A→cA|eB的右部有若干选项，判断这两条产生式右部各候选式的终结首符号集合是否两两互不相交。

对产生式E→Aa|Bb，有FIRST(Aa)∩FIRST(Bb)={c，e}∩{b}=ø对产生式A→cA|eB，有FIRST(cA)∩FIRST(eB)={c}∩{e}=ø文法中其他产生式都只有一个非空ε的右部。

综合（1）、（2），该文法可以采用自上而下分析方法进行语法分析而不会出现回朔和无限循环。

下面为该文法的每一个非终结符号构造递归子程序。

假设用READAWORD代表读下一个单词。

用P(E)、P(A)、P(B)分别表示非终结符号E、A、B对应的子程序名。

约定输入符号串以“#”作为输入结束符。

P(E)的递归子程序为：PROCEDURE P(E);BEGINIF WORD IN FIRST(Aa)THENBEGINP(A);READAWORD;IF WORD=’a’THEN READAWORDELSE ERRORENDELSE IF WORD IN FIRST(Bb)THENBEGINP(B);READAWORD;IF WORD=’b’THEN READAWORDELSE ERRORENDELSE ERROREND;P(A)的递归子程序为：PROCEDURE P(A);BEGINIF WORDD=’c’THENBEGINREADAWORD;P(A)ENDELSE IF WORD=’e’THENBEGINREADWORD;P(B)ENDELSE ERROREND;P(B)的递归子程序为：PROCEDURE P(B);BEGINIF WORD=’b’THENBEGINREADAWORD;IF WORD=’d’THEN READAWORDELSE ERRORENDELSE ERROREND;主程序中的主要内容为：READAWORD;P(E);IF WORD=”#”THEN WRITE(“RIGHT!”)ELSE WRITE(“ERROR!”)3.已知文法G[E]：G[E]：E→E+T|TT→T*F|FF→i|(E)请按递归子程序法为其构造语法分析程序。

LL(1)语法分析器的构造摘要语法分析的主要任务是接收词法分析程序识别出来的单词符由某种号串，判断它们是否语言的文法产生，即判断被识别的符号串是否为某语法部分。

一般语法分析常用自顶向下方法中的LL分析法，采用种方法时，语法分程序将按自左向右的顺序扫描输入的的符号串，并在此过程中产生一个句子的最左推导，即LL是指自左向右扫描，自左向右分析和匹配输入串。

经过分析，我们使用VC++作为前端开发工具，在分析语法成分时比较方便直观，更便于操作。

运行程序的同时不断修正改进程序，直至的到最优源程序。

关键字语法分析文法自顶向下分析 LL(1)分析最左推导AbstractGrammatical analysis of the main tasks was to receive lexical analysis procedure to identify the words from a website, string, and judge whether they have a grammar of the language, that is, judging by the series of symbols to identify whether a grammar part. General syntax analysis commonly used top-down methods of LL analysis, using methods, Grammar hours will be from the procedures of the order left-to-right scanning input string of symbols, and in the process produced one of the most left the sentence is derived, LL is scanned from left to right, From left to right analysis and matching input strings. After analysis, we use VC + + as a front-end development tool for the analysis of syntax ingredients more convenient visual, more easy to operate. Operational procedures at the same time constantly improving procedures, until the source of optimal .Key WordsGrammatical analysis grammar Top-down analysis LL (1) AnalysisMost left Derivation目录摘要 (1)引言 (3)第一章设计目的 (4)第二章设计的内容和要求 (5)2.1 设计内容 (5)2.2 设计要求 (5)2.3 设计实现的功能 (5)第三章设计任务的组织和分工 (6)3.1 小组的任务分工 (6)3.2 本人主要工作 (6)第四章系统设计 (9)4.1 总体设计 (9)4.2 详细设计 (9)第五章运行与测试结果 (22)5.1 一组测试数据 (22)5.2 界面实现情况 (23)第六章结论 (27)课程设计心得 (28)参考文献 (29)致谢 (30)附录（核心代码清单） (31)引言编译器的构造工具是根据用户输入的语言的文法，编译器的构造工具可以生成程序来处理以用户输入的文法书写的文本。

“编译技术”第四章作业4-1 已知文法G[C]：C→iEtS|iEtSeSE→ a|bS→ a+b|a*b(1)提取左公共因子；(2)计算修改后文法的每个非终结符的FIRST集和FOLLOW集；(3)给出递归下降分析程序。

(3)递归下降分析程序void match(token t){if(lookahead=='t')lookahead = nexttoken;else error;}void C(){if(lookahead=='i'){match('i');E();if(lookahead=='t'){match('t');S();Cprime();}else error;}else error;}void Cprime(){if(lookahead=='e'){match('e');S();}}void E(){if(lookahead=='a')match('a');else if(lookahead=='b')match('b');else error;}void S(){if(lookahead=='a'){match('a');Sprime();}}void Sprime(){if (lookahead=='+'){match('+');if(lookahed=='b'){match('b');}else error();}else if(lookahead=='*'){match('*');if(lookahead=='b'){match('b');}else error();}}4-2 已知文法G[Z]：Z→Az|bA→ Za|a(1)删除左递归；(2)计算修改后文法的每个非终结符的FIRST集和FOLLOW集；(3)给出递归下降分析程序。