编译原理复习题 - 给学生(2014)

.. .. ..

1． 语法分析的方法通常分为两类： 自上而下分析方法 和 自下而上分析方法 。 2．文法中的终结符集和非终结符集的交集是 空集 。

3．一个句型的最左直接短语称为该句型的___句柄________________。 4．规范归约是 最右推导 的逆过程。

5．自下而上语法分析中分析器的动作有_移进 、____归约 、__接受_ 、__报错 __。 6．自上而下语法分析中分析器的动作有___匹配终结符____、__展开非终结符_、__分析成功、报错__。 7．常用的自上而下语法分析方法有递归下降子程序方法和预测分析表方法（LL（1）方法）。 8．常用的自下而上语法分析方法有算符优先分析法和LR分析法。

9．一个LL(1)分析器由 一张LL(1)分析表（预测分析表） 、 一个先进后出分析栈 和一个 控制程序（表驱动程序）组成。

10．一个LR分析器由 分析栈 、 分析表 和总控程序三个部分组成。

11．LR(0)分析法的名字中，“L”表示 自左至右分析输入串 ，“R”表示 采用最右推导的逆过程即最左归约 。“0”表示 向右查看0个字符 。

12．LL(1)分析法中，第一个L的含义是 从左到右扫描输入串 ；第二个L的含义是 分析过程中采用最左推导 ；“1”的含义是 只需向右查看一个符号就可以决定如何推导 。

13．LR(1)文法的含义是：L表明_____自左至右扫描输入串__，R表明___采用最右推导的逆过程（最左归约）方法进行分析__。

14．一个上下文无关文法是LL(1)文法的充分必要条件是：对每一个非终结符A的任何两个不同产生式A→α|β，有下面的条件成立：（1） FIRST(α)∩FIRST(β) = ? ；（2）假若???，则有 FIRST(α) ∩ FOLLOW(A) = ? 。

15．对于LL（1）文法中的任何产生式A→α|β，则需要满足__First(_α)∩First(β)= Φ 、 _若_β=>*ε,则_ First(_α) ∩__Follow(A)=_ Φ_。

16．LR分析器的核心部分是一张分析表，该表包括 动作（ACTION）表 和 状态转换（GOTO）表

参考材料

.. .. ..

等两个子表。

17．关于非终结符A的直接左递归产生式：A→Aα|β，其中α、β是任意的符号串且β不以A开头，则可以将A的产生式改写为右递归的形式为： A→βA’ , A’→αA’|ε 。

18．在消除回溯，提取公共左因子时，关于A的产生式A → δβ1 | δβ2 | … | δβi | βi+1 | …| βj，可以改写为： A → δA’ | βi+1 | …| βj ， A’ →β1 | … |βi 。

19．设G[S] 是一文法，如果符号串x是从识别符号推导出来的，即有S?x，则称x是文法G[S]的____句型__，若x仅由终结符号组成，即S?x,x?VT，则称x为文法G[S]的__句子 。 20．已知文法G[S]:

S→eT|RT T→DR|ε R→dR|ε D→a|bd

求FIRST(S)={e，d，a，b，ε}______；FOLLOW(D)=_{d，#} 。 语义处理部分：

1．文法符号的属性有两种，一种称为 继承属性 ，另一种称为 综合属性 。

2．编译过程中，常见的中间语言形式有 逆波兰表示法 、 抽象语法树 、 三元式 、 四元式 。 3．语法制导翻译的方法就是为每个产生式配上一个 翻译子程序（语义动作或语义子程序） ，并在语法分析的同时执行它们。

4．编译过程中，常见的中间语言形式有 逆波兰表示法 、 抽象语法树 、 三元式 、 四元式 。 6．文法符号的属性有两种，一种称为 继承属性 ，另一种称为 综合属性 。 7．四元式之间的联系是通过 临时变量 实现的。 8．在属性文法中，终结符只有____综合 属性。

10．语法制导翻译的方法就是为每个产生式配上一个 翻译子程序（语义动作或语义子程序） ，并在语法分析的同时执行它们。

11．目前较常见的语言语义的描述形式是__属性文法______，并使用__语法制导翻译 方法完成对语法成分的翻译。

参考材料

***.. .. ..

（优化、存储、错误管理）

1.代码优化的含义是：对代码进行 等价变换 ，使得变换后的代码具有更高的 时间效率 和 空间效率。

2.按照优化对象所涉及的程序范围，优化分为 局部优化 、 循环优化 和 全局优化 。 3.基本块，是指程序中— 顺序执行的语句序列 ，其中只有一个 入口 和一个 出口 。

4.从编译角度看，分配目标程序数据空间的基本策略有： 静态分配策略 、 栈式动态分配策略 和堆式动态分配策略 。 三、判断题

1．设r和s分别为正规式，则有L(r|s) = L(r) | L(s).。( × ) 2．一个文法的所有句型的集合形成该文法所能接受的语言。( × ) 3．语法分析之所以采用上下文无关文法是因为它的描述能力最强。( × )

4．由于LR(0)分析表构造简单，所以它的描述能力强，适用面宽；LR(1)分析表因构造复杂而描述能力弱，适用面窄。( × )

5．逆波兰表示法表示表达式时无需使用括号。( √ ) 6．自动机M和M’的状态个数不同，则二者必不等价。( × ) 7．LL(1)文法一定不含左递归和二义性。( √ )

8．所有LR分析器的总控程序都是一样的，只是分析表各有不同。( √ )

9．无论是三元式表示还是间接三元式表示的中间代码，其三元式在三元式表中的位置一旦确定就很难改变。( √ )

10．三地址语句类似于汇编语言代码，可以看成中间代码的一种抽象形式。( √ ) 11．最左推导也被称为规范推导。（× ）

12．运算对象排列的先后顺序在后缀式和中缀式中不同。（ × ） 13．出现在移进-归约分析器栈中的内容被称为文法G的活前缀。（ √ ）

参考材料

.. .. ..

14．LR方法可以分析含有左递归的文法。（ √ ）

15．三元式的编号具有双重含义，既代表此三元式，又代表三元式存放的结果。（ √ ） 16．语义规则中的属性有两种：综合属性与继承属性。（ √ ）

17．移进-归约分析器的格局中栈的内容一般是文法符号与状态。（ √ ）

18．由于递归下降子程序方法较LL（1）方法简单，因此它要求文法不必是LL（1）文法。（ × ） 19．四元式的编号具有双重含义，既代表此四元式，又代表四元式存放的结果。（ × ）20．用高级语言编写的源程序必须经过编译，产生目标程序后才能运行。（ × ） 21．源程序到目标程序的变换是等价变换，即两者结构不同，但语义是一致的。（ √ 22．对于任何一个正规式e，都存在一个DFA A，使得L（e）=L（A）。（ √ ）23．最小化的DFA，它的状态数最小。（ √ ） 24．NFA的确定化算法具有消除ε边的功能。（ √ ）

25．每个非终结符产生的终结符号串都是该语言的子集。（ × ） 26．一个语言的文法是不唯一的。（ √ ）

27．语法错误校正的目的是为了把错误改正过来。（ × ） 28．源程序和目标程序是等价关系。（ √ ）

29．编译程序中错误处理的任务是对检查出的错误进行修改。（ × ） 30．使用有限自动机可以实现单词的识别。（ √ ）

31．一个非确定的有限自动机NFA可以通过多条路径识别同一个符号串。（ √ ）32．最小化的DFA所识别接受的正规集最小。（ × ） 33．一个语言（如C语言）的句子是有穷的。（ × ） 34．LL（1）方法又称为预测分析方法。（ √ ） 35．一个LL（1）文法是无二义和无回溯方法。（ √ ） 36．语法分析器可以检查出程序中的所有错误。（ × ）

参考材料

）