编译原理试题及答案(二)ppt课件

5
3.2
• 考虑文法 S -> aSbS|bSaS|ε (a) 为句子abab构造两个不同的最左推导， 以说明此文法二义 (b) 为abab构造对应的最右推导 (c) 为abab构造对应的分析树 (d) 这个文法产生的语言是什么
2019/3/22
luanj@
6
3.2 (续)
luanj@ 9
2019/3/22
3.4 (续)
• 该文法没有体现运算符 |、*、() 、并置的优 先级，因而是二义的。
R=>R|R=> a|R =>a|R*=>a|b* R=>R*=>R|R*=>a|R*=>a|b*
• E -> E’|’T | T T -> TF | F F -> F* | (E) | a | b
• (1) S=>aSbS=>abS=>abaSbS=>ababS=>abab (2) S=>aSbS=>abSaSbS=>abaSbS=>ababS=>abab • S=>aSbS=>aSb=>abSaSb=> abSab =>abab (2)
S a S ε b a S ε (1) 描述的语言是a,b数目相等的串 S b S ε S
S
( L S a L , ( L S a
2019/3/22 luanj@ 3
) S L , ) S a
3.1 (续) - (a,((a,a),(a,a)))
S =>(L) =>(L,S) =>(S,S) =>(a,S) =>(a,(L)) =>(a,(L,S)) =>(a,(S,S)) =>(a,((L),S)) =>(a,((L,S),S)) =>(a,((S,S),S)) =>(a,((a,S),S)) =>(a,((a,a),S)) =>(a,((a,a),(L))) =>(a,((a,a),(L,S))) =>(a,((a,a),(S,S))) =>(a,((a,a),(a,S))) =>(a,((a,a),(a,a))) S =>(L) =>(L,S) =>(L,(L)) =>(L,(L,S)) =>(L,(L,(L))) =>(L,(L,(L,S))) =>(L,(L,(L,a))) =>(L,(L,(S,a))) =>(L,(L,(a,a))) =>(L,(S,(a,a))) =>(L,((L),(a,a))) =>(L,((L,S),(a,a))) =>(L,((L,a),(a,a))) =>(L,((S,a),(a,a))) =>(L,((a,a),(a,a))) =>(S,((a,a),(a,a))) =>(a,((a,a),(a,a)))

27
第27页/共85页
• 例如，假定状态 s 1和s 2经a 弧 分 别 到 达t1和t2，而t1和t 2属于现行 中的两个
不同子集，说明有一个字， t1读出后到达终态，而t2读出后不能到达终 态，或者反之，那么对于字a ， s1读出a后到达终态，而s2读出a不能到 达终态，或者反之，所以s1和s2不等价。
{c,d,e} {c,d,f}
{c,d1,f}
1
{c,d}
{c,d,e,g}
{c,d,f}
③.重命名后的状态转换矩阵
I1 {b,c,d}
1 {c,dF,e}
{c,d,e}
0{c,d,e}
{c,d,e,g}
{c,d,e}
S
0
1
A(始态)
Φ
B
B
C
D
C
C
D
D
E
D
E
C
F(终态)
33
F(终态)
第33页/共E85页
40
{10,11}
{12}
第40页/共85页
I1
{1,2,3} {5,9,10,11}
{2,3} {2,3,7,8,13} {5,9,10,11} {5,9,10,11} {2,3,5,9,10,11} {5,9,10,11,13} {2,3,5,9,10,11} {5,9,10,11}
{2,3} {2,3,7,8,13} {2,3,7,8,13}
• 描述工具：正规式和有限自动机理论
ห้องสมุดไป่ตู้
• 语法规则：语法单位的形成规则。
• 语法单位通常包括：表达式、语句、子程序、 过程、函数、程序等;
2
• 描述工具：上下文无关文法

LowTens | X | XX | XXX
Hundreds LowHundreds | CD | D LowHundreds | CM
LowHundreds | C | CC | CCC Thousands M Thousands |
第三章 词法分析
3.2.2 试描述下列正则体现式定义旳语言：
2）全部由按词典递增序排列旳小写字母构成旳串。
a *b * z *
3）注释，即/*和*/之间旳串，且串中没有不在双引号 （“）中旳*/。
/\* ([^*"] | \*[^/] | \"([^"]*)\")* \*/
8）全部由a和b构成且不含子串abb旳串。
b *(a | ab)*
9）全部由a和b构成且不含子序列abb旳串。
第二章 一种简朴旳语法制导翻译器
2.2.1 考虑下面旳上下文无关文法：
S S S |S S |a
1）试阐明怎样使用该文法生成串 aa a
S S S S S S a S S 最左推导 aa S aa a
2）试为这个串构造一棵语法分析树。
3）该文法生成旳语言是什么？ 以a为变量，+和*为二元操作符旳后缀体现式旳集合
RomanNumeral Thousands Hundreds Tens Ones | RomanNumeral Ones LowOnes | IV |V LowOnes | IX
LowOnes | I | II | III
Tens LowTens | XL | L LowTens | XC
1） a(a | b) * a
以a开头和结尾且至少包括两个字符旳a,b字符串旳集合
2） (( | a)b*) *

A．提高程序的执行效率
B．使程序的结构更加清晰
C．利用有限的机器内存并提高机器的执行效率
D．利用有限的机器内存但降低了机器的执行效
率
(3) 构造编译程序应掌握 。
A．源程序
B．目标语言
C．编译方法
D．A～C项
.
2
严格执行突发事件上报制度、校外活 动报批 制度等 相关规 章制度 。做到 及时发 现、制 止、汇 报并处 理各类 违纪行 为或突 发事件 。
来到达2的弧都导向1，并删除状态2。最后，得到如图2-4
所示的化简了的DF.A M′。
21
严格执行突发事件上报制度、校外活 动报批 制度等 相关规 章制度 。做到 及时发 现、制 止、汇 报并处 理各类 违纪行 为或突 发事件 。
《编译原理教程》习题解析
22
图2-4 图2-3化简后的DFA M′
.
.
4
严格执行突发事件上报制度、校外活 动报批 制度等 相关规 章制度 。做到 及时发 现、制 止、汇 报并处 理各类 违纪行 为或突 发事件 。
《编译原理教程》习题解析
5
(4) 编译各阶段的工作都涉及到构造、查找或更新有 关表格，即编译过程的绝大部分时间都用在造表、查表和 更新表格的事务上。故选D。
《编译原理教程》习题解析
16
(5) NFA可以有DFA与之等价，即两者描述能力相同； 也即，对于任一给定的NFA M，一定存在一个DFA M'，使 L(M)=L(M′)。故选B。
(6) DFA便于识别，易于计算机实现，而NFA便于定 理的证明。故选C。
(7) 本题虽然是第二章的题，但答案参见第三章3.1.3 节。即选C。
.
8
严格执行突发事件上报制度、校外活 动报批 制度等 相关规 章制度 。做到 及时发 现、制 止、汇 报并处 理各类 违纪行 为或突 发事件 。