《编译原理》复习题

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α|β，其中α、β是任意的符号串且β不以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，#} 。

语义处理部分： 式A→α|β，有下面的条件成立：（1）

1．文法符号的属性有两种，一种称为 继承属FIRST(α)∩FIRST(β) = ? ；（2）假若???，

性 ，另一种称为 综合属性 。

则有 FIRST(α) ∩ FOLLOW(A) = ? 。 15．对于LL（1）文法中的任何产生式A→α|β，则需要满足__First(_α)∩First(β)= Φ 、

_若_β=>*ε,则_ First(_α) ∩__Follow(A)=_

在语法分析的同时执行它们。

Φ_。

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

结构是 二元式（单词种别， 单词自身的值） 。

17．关于非终结符A的直接左递归产生式：A→

9

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

4．编译过程中，常见的中间语言形式有 逆波兰表示法 、 抽象语法树 、 三元式 、 四元式 。 5．词法分析器的输入是 源程序字符串 ，输出

《编译原理》复习题

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

7．四元式之间的联系是通过 临时变量 实现的。 8．在属性文法中，终结符只有____综合 属性。 9．

10．语法制导翻译的方法就是为每个产生式配上一

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

10．三地址语句类似于汇编语言代码，可以看成中间代码的一种抽象形式。( √ )

11．最左推导也被称为规范推导。（× ） 12．运算对象排列的先后顺序在后缀式和中缀式中

个 翻译子程序（语义动作或语义子程序） ，并在语法分析的同时执行它们。

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

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分析器的总控程序都是一样的，只是分析表各有不同。( √ )

10

不同。（ × ）

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．语法分析器可以检查出程序中的所有错误。（ × ）

37．LR分析法是自上而下的语法分析方法。（ × ）

三、多项选择题

1. 编译器的各个阶段的工作都涉及到（AE ）

A. 表格处理 B. 词法分析

C. 语法分析 D. 语义分析

E. 出错处理 2. 令?＝{a,b}，则?上的符号串的全体可用下面的正规式表示。（ABE ）

A. (a|b)* B. (a*|b*)*

C. (a|b)+ D.

11

(ab)*

E. (a*b*)*

3. 自上而下的分析方法有：（AD ）

A. 递归下降分析法 B. LR（0）分析法

C. LALR（1）分析法 D. LL（1）分析法

E. SLR（1）分析法 4. 文法G：G[S]：S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD 是（ABE ）。

A. 0型文法 B. 1型文法

C. 2型文法 D. 3型文法

E. 上下文有关文法 5. 对LR分析表的构造，有可能存在的动作冲突有：（AD ）

A. 移进/归约冲突 B. 移进/移进冲突

C. 归约冲突 D. 归约/归约冲突

E. 移进冲突

6. 一个编译器可能有的阶段为（ABCDE ）

A. 词法分析 B. 语法分析

C. 语义分析 D. 中间代码生成

E. 目标代码生成

7 令?＝{a,b}，则?上的所有以b开头，后跟若干个（可为0个）ab的符号串的全体可用下面的正规式表示。（AB ）

A.b (ab)* B. (ba)*b C. b(a|b)+ D. (ba)+b

E. b (a|b)*

8. 自下而上的分析方法有：（BCE ）

A. 递归下降分析法 B. LR（0）分析法

C. LALR（1）分析法 D. LL（1）分析法

E. SLR（1）分析法

《编译原理》复习题

9. 一般来说，编译器可分为前端和后端，下列编译阶段可被划分为编译的前端的有：（ABCDE ）

A. 词法分析 B. 语法分析

C. 语义分析 D. 中间代码生成 E. 中间代码优化

10．令?＝{a,b}，则?上的符号串的全体可用下面的正规式表示。（ABE ）

A. (a|b)* B. (a*|b*)*

C. (a|b)+ D. (ab)* E. (a*b*)* 11．下列符号串是符号集?＝{a,b}上的正规式的有：（ ABCDE）

A. ε B. a C. ab D. (ab｜a) (ab｜a) E. ab｜ab

12．正规式服从的代数规律有：（ABDE ）

A. “或”运算服从交换律 B. “或”运算服从结合律

C. “连接”运算服从交换律 D. “连接”运算服从结合律

E. “连接”运算可对“或”运算进行分配

13． 令?＝{a,b}，则?上的所有以b开头，后跟若干个（可为0个）ab的符号串的全体可用下面的正规式表示。（AB ）

A.b (ab)* B. (ba)*b C. b(a|b)+ D. (ba)+b E. b (a|b)* 14． 一个LR分析器包括：（ADE ）

A. 一个总控程序 B. 一个项目集 C. 一个活前缀 D. 一个分析栈 E. 一张分析表

15． LR分析器的核心部分是一张分析表，该表包括（DE ）等子表。

A. LL（1）分析表 B. LR（1）分析表 C. SLR（1）分析表 D. Action表 E. goto表 16． Action表中的每一项Action[S,a]所表示的动作可能为：（ABCD ）

A. 移进 B. 接受 C. 归约 D. 出错 E. 待约 五．简答题

1．构造正规表达式a(aa)*bb(bb)*a(aa)* 的NFA。 解：

2562．构造正规表达式((a|b)*|aa)*b的NFA。 解：

3aX?1?a?2bY?a4b 2．令文法G[N]为 G[N]: N→D|ND D→0|1|2|3|4|5|6|7|8|9

给出句子568的最左、最右推导。 解：最左推导：N ? ND ? NDD ? DDD ? 5DD ? 56D ? 568

最右推导：N ? ND ? N8 ? ND8? N68 ? D68 ? 568 3．给出字母表Σ={a,b}上的同时只有奇数个a和奇数个b的所有串的集合的正规文法； 解： G[S]：S→aA|bB A→aS|bC|b B→bS|aC|a C→bA|aB|ε 4．给定文法：S→(L) | a L→L,S | S

请书写语义规则，求输出句子中每一个a的括号嵌套深度。 解：

用继承属性depth表示嵌套深度，则 S’ → S S.depth = 0 S → (L) L.depth = S.depth + 1 S → a print(S.depth)

(1)

L → L, S L(1).depth = L.depth; S.depth = L.depth L → S S.depth = L.depth

5. 表达式a*b-c-d$e$f-g-h*i中，运算符的优先级由高到低依次为-、*、$，且均为右结合，请写出相应的后缀式。

解： abcd- -*efgh- - i*$$

6．判断文法G[S]: S → BA

12

aXa1ab3bb4baaYa