编译原理复习题-给学生(简) 下载本文

《编译原理》复习题

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