文档库 最新最全的文档下载
当前位置:文档库 › 编译Bottom-Up习题解答

编译Bottom-Up习题解答

编译Bottom-Up习题解答
编译Bottom-Up习题解答

1、已知文法G(S):

S→aS|bS|a

(1)构造该文法的LR(0)项目集规范族

(2)构造识别该文法所产生的活前缀的DFA。

(3)构造其SLR分析表,并判断该文法是否是SLR(1)文法。

解题思路

构造LR(0)项目集规范族,有两种方法:一种是利用有限自动机来构造,另一种是利用函数CLOSURE和GO来构造。本题采取第2种方法,通过计算函数CLOSURE和GO得到文法的LR(0)项目集规范族,而GO函数则把LR(0)项目集规范族连成一个识别该文法所产生的活前缀的DFA。

解答

(1)将文法G(S)拓广为G(S’):

(0)S’→S

(1)S→aS

(2)S→bS

(3)S→a

构造该文法的LR(0)项目集规范族:

I0=CLOSURE({S→·S})={S’ →·S, S→·aS, S→·bS, S→·a}

I1=GO( I0, a)=CLOSURE({S→a·S , S→a·})={S→a·S , S→a·, S→·a S, S→·b S, S→·a }

I2=GO(I0 , b)=CLOSURE({S→b·S })={ S→b·S, S→·aS,S→·bS, S→·a } I3=GO(I0 , S)=CLOSURE({S’ →S·})={ S’ →S·}

GO(I1, a)=CLOSURE({S→a·S , S→a·})=I1

GO(I2, b)=CLOSURE({S→b·S})=I2

I4=GO(I1, S)=CLOSURE({S→aS·})={S→aS·}

GO(I2, a)= CLOSURE({S→a·S , S→a·})=I1

GO(I2, b)= CLOSURE({S→b·S})=I2

I5=GO(I2, S)=CLOSURE({S→bS·})={ S→bS·}

所以,项目集I0,I1,I2,I3,I4和I5构成了该文法的LR(0)项目集规范族。

(2)我们用GO函数把LR(0)项目集规范族连成一个识别该文法所产生的活前缀的DFA如图4.1所示。

(3)构造其SLR分析表。

表4.1 SLR分析表

注意到状态I1存在“移进-归纳”冲突,计算S的FOLLOW集合:

FOLLOW(S)={#}

可以采用SLR冲突消解法,得到表4.1所列的SLR分析表。

从分析表可以看出,表中没有冲突项,所以该文法是SLR(1)文法。

2、证明AdBd是文法G(S)的活前缀。说明活前缀在LR分析中的作用。给出串dbdb#的LR分析过程。

G(S):(1) S→AdB (2)A→a (3) A→ε

(4) B→b (5)B→Bdb (6)B→ε

所谓活前缀是指规范句型的一个前缀,这种前缀不句柄之后的任何符号。根据此定义,直接证明AdBd是文法G(S)的活前缀。

解答

存在下面的规范推导:

可见AdBdb是文法G的规范句型,AdBd是该规范句型的前缀。另外,在该规范句型中Bdb 是句柄,前缀是AdBd不含句柄Bdb之后的任何符号,所以AdBd是文法G(S)的活前缀。

在LR分析工作过程中的任何时候,栈里的方法符号(自栈底而上)X1X2…X m应该构成活前缀,把输入串的剩余部分配上之后即应成为规范句型(如果整个输入串确实构成一个句子)。因此,只要输入串的已扫描部分保持可归约成一个活前缀,那就意味着所扫描过的部分没有错误。

构造文法G的LR分析表4.2所列。

表4.2 LR分析表

步骤状态符号输入串

0 0 # dbdb#

1 02 #A dbdb#

2 024 #Ad bdb#

3 0245 #Adb db#

4 0246 #AdB db#

5 02467 #AdBd b#

6 024678 #AdBdb #

9 0246 #AdB #

10 01 #S # acc 3、根据程序设计语言的一般要求,为定义条件语句的二义文法G(S)构造SLR(1)分析表,要求写出步骤和必要的说明。

G(S): S→iSeS|iS|a

解答

将文法G(S)拓广为G(S’):

(0)S’→S

(1)S→iSeS

(3)S→a

构造此文法的LR(0)项目集规范族,识别该文法所产生的活前缀的DFA如图4.2所示。

注意到状态I4存在“移进-归约”冲突,计算FOLLOW集合:

FOLLOW(S)={e,#}

当LR分析器处于状态4时,如果下一输入符号是“#”,则按S→iS归约;如果下一输入符号是“e”,则既可以按S→iS归约,也可以执行移入。根据程序设计语言的要求,条件语句的else子句应当和最近的没有else子句的if语句匹配,根据这一要求,我们规定:当LR分析器处于状态4时,如果下一输入符号是“#”,则按S→iS归约;如果下一输入符号是“e”,则执行移入。构造SLR(1)分析表如表4.3所列。

D → id L

L → , id L | : T

T → integer | real

构造一个翻译模式,把每个标识符的类型存入符号表。

解题思路

这是一个对说明语句进行语义分析的题目,不需要产生代码,但要求把每个标识符的类型填入符号表中。

解答

对D,L,T设置综合属性type。过程addtype(id,type)用来把标识符id及其类型type填入到符号表中。

翻译模式如下:

D → id L {addtype(id.entry,L.type)}

L → ,id L1 {addtype(id.entry,L1.type);L.type:=L1.type;}

L → : T {L.type:=T.type}

T → integer {T.type:=interger}

T → real {T.type:=real}

5、文法G的产生式如下:

S → (L) | a

L → L , S | S

(1)试写出一个语法制导定义,它输出配对括号个数;

(2)写一个翻译方案,打印每个a的嵌套深度。如((a),a),打印2,1。

解题思路

本题包括两部分,第1部分要求写语法制导定义,第2部分要求写翻译方案。语法制导定义(或属性文法)可以看作是关于语言翻译的高级规范说明,其中隐去实现细节,使用户从明确说明翻译顺序的工作中解脱出来。翻译方案(也称翻译模式)给出了使用语义规则进行计算的次序,把某些实现细节表示出来。读者从下面解答中可体会两者的区别。

解答

(1)为S、L引入属性h,代表配对括号个数。语法制导定义如下:产生式语义规则

S → (L)S.h:=L.h+1

S → a S.h:=0

L → L1 , S L.h:=L1.h+S.h

L → S L.h:=S.h

S’→S print(S.h)

(2)为S、L引入d,代表a的嵌套深度。翻译方案如下:

S’→{S.d:=0;}S

S →‘(’{L.d:=S.d+1;}

L

‘)’

S →a{print(S.d);}

L → {L1.d:=L.d;}

L1

{S.d:=L.d;}

S

L → {S.d:=L.d}

S

6、下列文法对整型常数和实型常数施用加法运算符“+”生成表达式;当两个整型数相加时,结果仍为整型数,否则,结果为实型数:

E → E+T | T

T → num.num | num

(1)试给出确定每个子表达式结果类型的属性文法。

(2)扩充(1)的属性文法,使之把表达式翻译成后缀形式,同时也能确定结果的类型。应该注意使用一元运算符inttoreal把整型数转换成实型数,以便使后缀形如加法运算符的两个操作数具有相同的类型。

解题思路

确定每个子表达式结果类型的属性文法是比较容易定义的。关键是如何扩充此属性文法,使之把表达式翻译成后缀形式。我们将不在name或num.num向T 归约的时候输出该运算对象,而是把运算对象的输出放在T或E+T向E归约的时候。这是因为考虑输出类型转换算符inttoreal的动作可能在E+T归约的时候进行,如果这时两个运算对象都在前面name或num.num向T归约的时候已输出,需要为第1个运算对象输出类型转换算符时就已经为时太晚。

还要注意的是,在E+T向E归约时,该加法运算的第1个运算对象已经输出。所以E→E+T的语义规则不需要有输出E运算对象的动作。

解答

(1)为文法符号E和T配以综合属性type,用来表示它们的类型。类型值分别用int和real来表示。确定每个子表达式结果类型的属性文法如下:

产生式语义规则

E→E1+T{T.type:=if E1.type=int and T.type=int then int else real E→T {E.type:=T.type}

T→num.num T.type:=real

T→num T.type:=int

(2)下面属性文法将表达式的后缀表示打印输出,其中lexeme属性表示单词的拼写。

产生式语义规则

E→E1+T if E1.type=real and T.type=int then

begin

E.type:=real;

print(T.lexeme);

print(‘inttoreal’);

end

else if E1.type=int and T.type=real then

begin

E.type:=real;

print(‘inttoreal’);

print(T.lexeme);

end

else begin

E.type:=E1.type;

print(T.lexeme);

end

print(‘+’);

E→T E.type:=T.type;print(T.lexeme);

T→num.num T.type:=real;T.lexeme:=num1.lexeme||“.”||num2.lexeme T→num T.type:=int;T.lexeme:=num.lexeme;

编译原理课后习题答案(第三版)

精品文档 第二章 P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法: E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ?+?+?+?+?+?+?+?+??????+?+?+?+?+?+********()*()*()*()*()*()*() 最右推导: E E T E T F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树:/********************************

编译原理期末考试习题及答案

一、填空题|(每题4分,共20分) 1. 乔母斯基定义的3型文法(线性文法)产生式形式 A→Ba|a,或A→aB|a,A,B∈Vn, a,b∈Vt 。 2.语法分析程序的输入是单词符号,其输出是语法单位。 3 型为 B → .aB 的LR(0)项目被称为移进项目,型为 B → a.B 的LR(0) 项目被称为待约项目, 4.在属性文法中文法符号的两种属性分别为继承属性和综合属性。 5、运行时存贮管理方案有静态存储分配、动态存储分配和堆式存储分配和方案。 二.已知文法 G(S) (1) E → T | E+T (2) T → F | F*F (3) F →(E)| i (1)写出句型(T*F+i)的最右推到并画出语法树。(4分) (2)写出上述句型的短语,直接短语和句柄。(4分) 答:(1)最右推到(2分) E ==> T ==> F ==> (E) ==> (E+T) ==> (E+F) ==> (E+i) ==> (T+i) ==> (T*F+i) (2) 语法树(2分) (3)(4分) 短语:(T*F+i),T*F+i ,T*F , i 直接短语:T*F , i 句柄:T*F 三. 证明文法G(S) :S → SaS |ε是二义的。(6分) 答:句子aaa对应的两颗语法树为:

因此,文法是二义文法 四.给定正规文法G(S): (1) S → Sa | Ab |b (2) A → Sa 请构造与之等价的DFA。(6分) 答:对应的NFA为:(6分) 状态转换表: a b {F} Φ{S} {S} {S,A} Φ {S,A} {S,A} {S} 五. 构造识别正规语言b*a(bb*a)*b* 最小的DFA(要求写出求解过程)。(15分)答:(1)对应的NFA(5分) a b {0} {1,3} {0} {1,3} Φ{2,3} {2,3} {1,3} {2,3} (5分) 六. 已知文法G(S) : (1) S → ^ | a | (T) (2) T → T,S | S 试:(1)消除文法的左递归;(4分) (2)构造相应的first 和 follow 集合。(6分) 答:(1)消除文法的左递归后文法 G’(S)为: (1) S → ^ | a | (T)

编译原理作业答案

《编译原理》第一次作业参考答案 一、下列正则表达式定义了什么语言(用尽可能简短的自然语言描述)? 1.b*(ab*ab*)* 所有含有偶数个a的由a和b组成的字符串. 2.c*a(a|c)*b(a|b|c)* | c*b(b|c)*a(a|b|c)* 答案一:所有至少含有1个a和1个b的由a,b和c组成的字符串. 答案二:所有含有子序列ab或子序列ba的由a,b和c组成的字符串. 说明:答案一要比答案二更好,因为用自然语言描述是为了便于和非专业的人员交流,而非专业人员很可能不知道什么是“子序列”,所以相比较而言,答案一要更“自然”. 二、设字母表∑={a,b},用正则表达式(只使用a,b, ,|,*,+,?)描述下列语言: 1.不包含子串ab的所有字符串. b*a* 2.不包含子串abb的所有字符串. b*(ab?)* 3.不包含子序列abb的所有字符串. b*a*b?a* 注意:关于子串(substring)和子序列(subsequence)的区别可以参考课本第119页方框中的内容. ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ 《编译原理》第二次作业参考答案 一、考虑以下NFA: 1.这一NFA接受什么语言(用自然语言描述)? 所有只含有字母a和b,并且a出现偶数次或b出现偶数次的字符串. 2.构造接受同一语言的DFA. 答案一(直接构造通常得到这一答案):

答案二(由NFA构造DFA得到这一答案): 二、正则语言补运算 3.画出一个DFA,该DFA恰好识别所有不含011子串的所有二进制串. 1.画出一个DFA,该DFA恰好识别所有不含011子串的所有二进制串.

蒋立源 编译原理第三版第二章 习题与答案(修改后)

第2章习题 2-1 设有字母表A1 ={a,b,c,…,z},A2 ={0,1,…,9},试回答下列问题: (1) 字母表A1上长度为2的符号串有多少个? (2) 集合A1A2含有多少个元素? (3) 列出集合A1(A1∪A2)*中的全部长度不大于3的符号串。 2-2 试分别构造产生下列语言的文法: (1){a n b n|n≥0}; (2){a n b m c p|n,m,p≥0}; (3){a n#b n|n≥0}∪{c n#d n|n≥0}; (4){w#w r# | w∈{0,1}*,w r是w的逆序排列 }; (5)任何不是以0打头的所有奇整数所组成的集合; (6)所有由偶数个0和偶数个1所组成的符号串的集合。 2-3 试描述由下列文法所产生的语言的特点: (1)S→10S0S→aA A→bA A→a (2)S→SS S→1A0A→1A0A→ε (3)S→1A S→B0A→1A A→C B→B0B→C C→1C0C→ε (4)S→aSS S→a 2-4 试证明文法 S→AB|DC A→aA|a B→bBc|bc C→cC|c D→aDb|ab 为二义性文法。 2-5 对于下列的文法 S→AB|c A→bA|a B→aSb|c 试给出句子bbaacb的最右推导,并指出各步直接推导所得句型的句柄;指出句子的全部短语。

2-6 化简下列各个文法 (1) S→aABS|bCACd A→bAB|cSA|cCC B→bAB|cSB C→cS|c (2) S→aAB|E A→dDA|e B→bE|f C→c AB|dSD|a D→eA E→fA|g (3) S→ac|bA A→c BC B→SA C→bC|d 2-7 消除下列文法中的ε-产生式 (1) S→aAS|b A→cS|ε (2) S→aAA A→bAc|dAe|ε 2-8 消除下列文法中的无用产生式和单产生式 (1) S→aB|BC A→aA|c|aDb B→DB|C C→b D→B (2) S→SA|SB|A A→B|(S)|( ) B→[S]|[ ] (3) E→E+T|T T→T*F|F F→P↑F|P P→(E)|i 第2章习题答案 2-1 答: (1) 26*26=676 (2) 26*10=260 (3) {a,b,c,...,z, a0,a1,...,a9, aa,...,az,...,zz, a00,a01,...,zzz},共有26+26*36+26*36*36=34658个 2-2 解: (1) 对应文法为G(S)=({S},{a,b},{ S→ε| aSb },S) (2) 对应文法为G(S)=({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε },S) (3)对应文法为G(S)=({S,X,Y},{a,b,c,d,#}, {S→X,S→Y,X→aXb|#, Y→cYd|# },S)

(完整版)编译原理课后习题答案

第一章 1.典型的编译程序在逻辑功能上由哪几部分组成? 答:编译程序主要由以下几个部分组成:词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、错误处理、表格管理。 2. 实现编译程序的主要方法有哪些? 答:主要有:转换法、移植法、自展法、自动生成法。 3. 将用户使用高级语言编写的程序翻译为可直接执行的机器语言程序有哪几种主要的方式? 答:编译法、解释法。 4. 编译方式和解释方式的根本区别是什么? 答:编译方式:是将源程序经编译得到可执行文件后,就可脱离源程序和编译程序单独执行,所以编译方式的效率高,执行速度快; 解释方式:在执行时,必须源程序和解释程序同时参与才能运行,其不产生可执行程序文件,效率低,执行速度慢。

第二章 1.乔姆斯基文法体系中将文法分为哪几类?文法的分类同程序设计语言的设计与实现关 系如何? 答:1)0型文法、1型文法、2型文法、3型文法。 2) 2. 写一个文法,使其语言是偶整数的集合,每个偶整数不以0为前导。 答: Z→SME | B S→1|2|3|4|5|6|7|8|9 M→ε | D | MD D→0|S B→2|4|6|8 E→0|B 3. 设文法G为: N→ D|ND D→ 0|1|2|3|4|5|6|7|8|9 请给出句子123、301和75431的最右推导和最左推导。 答:N?ND?N3?ND3?N23?D23?123 N?ND?NDD?DDD?1DD?12D?123 N?ND?N1?ND1?N01?D01?301 N?ND?NDD?DDD?3DD?30D?301 N?ND?N1?ND1?N31?ND31?N431?ND431?N5431?D5431?75431 N?ND?NDD?NDDD?NDDDD?DDDDD?7DDDD?75DDD?754DD?7543D?75431 4. 证明文法S→iSeS|iS| i是二义性文法。 答:对于句型iiSeS存在两个不同的最左推导: S?iSeS?iiSes S?iS?iiSeS 所以该文法是二义性文法。 5. 给出描述下面语言的上下文无关文法。 (1)L1={a n b n c i |n>=1,i>=0 } (2)L2={a i b j|j>=i>=1} (3)L3={a n b m c m d n |m,n>=0} 答: (1)S→AB A→aAb | ab B→cB | ε (2)S→ASb |ab

编译原理作业参考答案

第1章引言 1、解释下列各词 源语言:编写源程序的语言(基本符号,关键字),各种程序设计语言都可以作为源语言。 源程序: 用接近自然语言(数学语言)的源语言(基本符号,关键字)编写的程序,它是翻译程序处理的对象。 目标程序: 目标程序是源程序经过翻译程序加工最后得到的程序。目标程序 (结果程序)一般可由计算机直接执行。 低级语言:机器语言和汇编语言。 高级语言:是人们根据描述实际问题的需要而设计的一个记号系统。如同自然语言(接近数学语言和工程语言)一样,语言的基本单位是语句,由符号组和一组用来组织它们成为有确定意义的组合规则。 翻译程序: 能够把某一种语言程序(源语言程序)改变成另一种语言程序(目 标语言程序),后者与前者在逻辑上是等价的。其中包括:编译程序,解释程序,汇编程序。 编译程序: 把输入的源程序翻译成等价的目标程序(汇编语言或机器语言), 然后再执行目标程序(先编译后执行),执行翻译工作的程序称为编译程序。 解释程序: 以该语言写的源程序作为输入,但不产生目标程序。按源程序中语句动态顺序逐句的边解释边执行的过程,完成翻译工作的程序称为解释程序。 2、什么叫“遍” 指对源程序或源程序的中间形式(如单词,中间代码)从头到尾扫描一次,并作相应的加工处理,称为一遍。

3、简述编译程序的基本过程的任务。 编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程,整个过程可以划分5个阶段。 词法分析:输入源程序,进行词法分析,输出单词符号。 语法分析:在词法分析的基础上,根据语言的语法规则把单词符号串分解成各类语法单位,并判断输入串是否构成语法正确的“程序”。 中间代码生成:按照语义规则把语法分析器归约(或推导)出的语法单位翻译成一定形式的中间代码。 优化:对中间代码进行优化处理。 目标代码生成:把中间代码翻译成目标语言程序。 4、编译程序与解释程序的区别 编译程序生成目标程序后,再执行目标程序;然而解释程序不生成目标程序,边解释边执行。 5、有人认为编译程序的五个组成部分缺一不可,这种看法正确吗 编译程序的5个阶段中,词法分析,语法分析,语义分析和代码生成生成是必须完成的。而中间代码生成和代码优化并不是必不可少的。优化的目的是为了提高目标程序的质量,没有这一部分工作,仍然能够得到目标代码。 6、编译程序的分类 目前基本分为:诊断编译程序,优化编译程序,交叉编译程序,可变目标编译程序。

编译原理期末考试题目及答案

一、填空题(每空2分,共20分) 1.编译程序首先要识别出源程序中每个单词,然后再分析每个句子并翻译其意义。 2.编译器常用的语法分析方法有自底向上和自顶向下两种。 3.通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的分析,中间代码生成、代码优化与目标代码的生成则是对源程序的综合。 4.程序设计语言的发展带来了日渐多变的运行时存储管理方案,主要分为两大类,即静态存储分配方案和动态存储分配方案。 5.对编译程序而言,输入数据是源程序,输出结果是目标程序。 1.计算机执行用高级语言编写的程序主要有两种途径:解释和编译。 2.扫描器是词法分析器,它接受输入的源程序,对源程序进行词法分析并识别出一个个单词符号,其输出结果是单词符号,供语法分析器使用。 3.自下而上分析法采用移进、归约、错误处理、接受等四种操作。 4.一个LL(1)分析程序需要用到一张分析表和符号栈。 5.后缀式abc-/所代表的表达式是a/(b-c)。 二、单项选择题(每小题2分,共20分) 1.词法分析器的输出结果是__C。 A.单词的种别编码B.单词在符号表中的位置 C.单词的种别编码和自身值D.单词自身值 2.正规式M 1 和M 2 等价是指__C_。 A.M1和M2的状态数相等 B.M1和M2的有向边条数相等 C.M1和M2所识别的语言集相等D.M1和M2状态数和有向边条数相等 3.文法G:S→xSx|y所识别的语言是_C____。 A.xyx B.(xyx)* C.xnyxn(n≥0) D.x*yx* 4.如果文法G是无二义的,则它的任何句子α_A____。 A.最左推导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能不同 C.最左推导和最右推导必定相同D.可能存在两个不同的最左推导,但它们对应的语法树相同5.构造编译程序应掌握____D__。 A.源程序B.目标语言C.编译方法D.以上三项都是 6.四元式之间的联系是通过__B___实现的。 A.指示器B.临时变量C.符号表D.程序变量 7.表达式(┐A∨B)∧(C∨D)的逆波兰表示为__B___。 A.┐AB∨∧CD∨B.A┐B∨CD∨∧ C.AB∨┐CD∨∧D.A┐B∨∧CD∨ 8. 优化可生成__D___的目标代码。 A.运行时间较短 B.占用存储空间较小 C.运行时间短但占用内存空间大D.运行时间短且占用存储空间小 9.下列___C___优化方法不是针对循环优化进行的。 A. 强度削弱B.删除归纳变量C.删除多余运算D.代码外提 10.编译程序使用_B_区别标识符的作用域。 A. 说明标识符的过程或函数名B.说明标识符的过程或函数的静态层次 C.说明标识符的过程或函数的动态层次 D. 标识符的行号 三、判断题(对的打√,错的打×,每小题1分,共10分) 2.一个有限状态自动机中,有且仅有一个唯一的终态。x

编译原理复习题及参考答案

中南大学网络教育课程考试复习题及参考答案 编译原理 一、判断题: 1.一个上下文无关文法的开始符,可以是终结符或非终结符。 ( ) 2.一个句型的直接短语是唯一的。 ( ) 3.已经证明文法的二义性是可判定的。 ( ) 4.每个基本块可用一个DAG表示。 ( ) 5.每个过程的活动记录的体积在编译时可静态确定。 ( ) 6.2型文法一定是3 型文法。 ( ) 7.一个句型一定句子。 ( ) 8.算符优先分析法每次都是对句柄进行归约。 ( ) 9.采用三元式实现三地址代码时,不利于对中间代码进行优化。 ( ) 10.编译过程中,语法分析器的任务是分析单词是怎样构成的。 ( ) 11.一个优先表一定存在相应的优先函数。 ( ) 12.目标代码生成时,应考虑如何充分利用计算机的寄存器的问题。 ( ) 13.递归下降分析法是一种自下而上分析法。 ( ) 14.并不是每个文法都能改写成 LL(1)文法。 ( ) 15.每个基本块只有一个入口和一个出口。 ( ) 16.一个 LL(1)文法一定是无二义的。 ( ) 17.逆波兰法表示的表达试亦称前缀式。 ( ) 18.目标代码生成时,应考虑如何充分利用计算机的寄存器的问题。 ( ) 19.正规文法产生的语言都可以用上下文无关文法来描述。 ( ) 20.一个优先表一定存在相应的优先函数。 ( ) 21.3型文法一定是 2型文法。 ( ) 22.如果一个文法存在某个句子对应两棵不同的语法树,则文法是二义性的。 ( ) 二、填空题: 1.( )称为规范推导。 2.编译过程可分为(),(),(),()和()五个阶段。 3.如果一个文法存在某个句子对应两棵不同的语法树,则称这个文法是()。 4.从功能上说,程序语言的语句大体可分为()语句和()语句两大类。 5.语法分析器的输入是(),其输出是()。 6.扫描器的任务是从()中识别出一个个()。 7.符号表中的信息栏中登记了每个名字的有关的性质,如()等等。 8.一个过程相应的DISPLAY表的内容为()。 9.一个句型的最左直接短语称为句型的()。 10.常用的两种动态存贮分配办法是()动态分配和()动态分配。 11.一个名字的属性包括( )和( )。 12.常用的参数传递方式有(),()和()。 13.根据优化所涉及的程序范围,可将优化分成为(),()和()三个级别。 14.语法分析的方法大致可分为两类,一类是()分析法,另一类是()分析法。 15.预测分析程序是使用一张()和一个()进行联合控制的。 16.常用的参数传递方式有(),()和()。 17.一张转换图只包含有限个状态,其中有一个被认为是()态;而且实际上至少要有一个()态。 18.根据优化所涉及的程序范围,可将优化分成为(),()和()三个级别。 19.语法分析是依据语言的()规则进行。中间代码产生是依据语言的()规则进行的。 20.一个句型的最左直接短语称为句型的()。 21.一个文法G,若它的预测分析表M不含多重定义,则该文法是()文法。 22.对于数据空间的存贮分配, FORTRAN采用( )策略, PASCAL采用( )策略。

编译原理第二章-课后题答案

第二章 3.何谓“标志符”,何谓“名字”,两者的区别是什么? 答:标志符是一个没有意义的字符序列,而名字却有明确的意义和属性。 4.令+、*和↑代表加、乘和乘幂,按如下的非标准优先级和结合性质的约定,计算1+1*2↑2*1↑2的值。 (1)优先顺序(从高到低)为+、*和↑,同级优先采用左结合。 (2)优先顺序为↑、+、*,同级优先采用右结合。 答:(1)1+1*2↑2*1↑2=2*2↑2*1↑2=4↑2*1↑2=4↑2↑2=16↑2=256 (2)1+1*2↑2*1↑2=1+1*2↑2*1=1+1*4*1=2*4*1=2*4=8 6.令文法G6为 N-〉D|ND D-〉0|1|2|3|4|5|6|7|8|9 (1)G6的语言L(G6)是什么? (2)给出句子0127、34、568的最左推导和最右推导。 (1)由0到9的数字所组成的长度至少为1的字符串。即:L(G6)={d n|n≧1,d∈{0,1,…,9}} 答: (2)0127的最左推导:N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127 0127的最右推导:N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127 (其他略) 7.写一个文法,使其语言是奇数集,且每个奇数不以0开头。 答:G(S):S->+N|-N N->ABC|C C->1|3|5|7|9 A->C|2|4|6|8 B->BB|0|A|ε [注]:可以有其他答案。 [常见的错误]:N->2N+1 原因在于没有理解形式语言的表示法,而使用了数学表达式。 8.令文法为 E->T|E+T|E-T T->F|T*F|T/F F->(E)|i (1)给出i+i*i、i*(i+i)的最左推导和最右推导。 (2)给出i+i+i、i+i*i和i-i-i的语法树,并给出短语,简单短语和句柄。 答:(1) i*(i+i)的最左推导: E=>T=>T*F=>F*F=>i*F=>i*(E)=>i*(E+T)=>i*(T+T)=>i*(F+T)=>i*(i+T)=>i*(i+F)=> i*(i+i) i*(i+i)的最右推导: E=>T=>T*F=>T*(E) =>T*(E+T)=>T*(E+F)=>T*(E+i)=>T*(T+i)=>T*(F+i)=> T*(i+i)=> F*(i+i) => i*(i+i) (其他略) [注]:要牢记每一步都是对最左(右)的一个非终结符号进行一步推导。 (2) i+i+i的语法树:

编译原理课后答案

第二章 2.3叙述由下列正规式描述的语言 (a) 0(0|1)*0 在字母表{0, 1}上,以0开头和结尾的长度至少是2的01 串 (b) ((ε|0)1*)* 在字母表{0, 1}上,所有的01串,包括空串 (c) (0|1)*0(0|1)(0|1) 在字母表{0, 1}上,倒数第三位是0的01串 (d) 0*10*10*10* 在字母表{0, 1}上,含有3个1的01串 (e) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)* 在字母表{0, 1}上,含有偶数个0和偶数个1的01串 2.4为下列语言写正规定义 C语言的注释,即以 /* 开始和以 */ 结束的任意字符串,但它的任何前缀(本身除外)不以 */ 结尾。 [解答] other → a | b | … other指除了*以外C语言中的其它字符 other1 → a | b | … other1指除了*和/以外C语言中的其它字符 comment → /* other* (* ** other1 other*)* ** */ (f) 由偶数个0和偶数个1构成的所有0和1的串。 [解答]由题目分析可知,一个符号串由0和1组成,则0和1的个数只能有四种情况: x 偶数个0和偶数个1(用状态0表示); x 偶数个0和奇数个1(用状态1表示); x 奇数个0和偶数个1(用状态2表示); x 奇数个0和奇数个1(用状态3表示);所以, x 状态0(偶数个0和偶数个1)读入1,则0和1的数目变为:偶数个0和奇数个1(状态1) x 状态0(偶数个0和偶数个1)读入0,则0和1的数目变为:奇数个0和偶数个1(状态2) x 状态1(偶数个0和奇数个1)读入1,则0和1的数目变为:偶数个0和偶数个1(状态0) x 状态1(偶数个0和奇数个1)读入0,则0和1的数目变为:奇数个0和奇数个1(状态3) x 状态2(奇数个0和偶数个1)读入1,则0和1的数目变为:奇数个0和奇数个1(状态3) x 状态2(奇数个0和偶数个1)读入0,则0和1的数目变为:偶数个0和偶数个1(状态0) x 状态3(奇数个0和奇数个1)读入1,则0和1的数目变为:奇数个0和偶数个1(状态2) x 状态3(奇数个0和奇数个1)读入0,则0和1的数目变为:偶数个0和奇数个1(状态1) 因为,所求为由偶数个0和偶数个1构成的所有0和1的串,故状态0既为初始状态又为终结状态,其状态转换图: 由此可以写出其正规文法为: S0 → 1S1 | 0S2 | ε S1 → 1S0 | 0S3 | 1 S2 → 1S3 | 0S0 | 0 S3 → 1S2 | 0S1 在不考虑S0 →ε产生式的情况下,可以将文法变形为: S0 = 1S1 + 0S2 S1 = 1S0 + 0S3 + 1 S2 = 1S3 + 0S0 + 0 S3 = 1S2 + 0S1 所以: S0 = (00|11) S0 + (01|10) S3 + 11 + 00 (1) S3 = (00|11) S3 + (01|10) S0 + 01 + 10 (2) 解(2)式得: S3 = (00|11)* ((01|10) S0 + (01|10)) 代入(1)式得: S0 = (00|11) S0 + (01|10) (00|11)*((01|10) S0 + (01|10)) + (00|11) => S0 = ((00|11) + (01|10) (00| 11)*(01|10))S0 + (01|10) (00|11)*(01|10) + (00|11) => S0 = ((00|11)|(01|10) (00|11)*(01|10))*((00|1

编译原理试题及答案3

编译原理复习题 一、填空题: 1、编译方式与解释方式的根本区别在于(是否生成目标代码)。 2、对编译程序而言,输入数据是(源程序),输出结果是(目标程序)。 3、如果编译程序生成的目标程序是机器代码程序,则源程序的执行分为两大阶段:(编译阶段)和(运行阶段)。 4、如果编译程序生成的目标程序是汇编语言程序,则源程序的执行分成三个阶段:(编译阶段)、(汇编阶段)和(运行阶段)。 5、自顶向下语法分析方法会遇到的主要问题有(回溯)和((左递归带来的)无限循环)。 6、LL(k)分析法中,第一个L的含义是(从左到右进行分析),第二个L的含义是(每次进行最左推导),“k”的含义是(向输入串中查看K个输入符号)。 7、LL(1)分析法中,第一个L的含义是(从左到右进行分析),第二个L的含义是(每次进行最左推导),“1”的含义是(向输入串中查看1个输入符号)。 8、自顶向下语法分析方法的基本思想是:从(识别符号)出发,不断建立(直接推导),试图构造一个推导序列,最终由它推导出与输入符号相同的(符号串)。 9、自底向上语法分析方法的基本思想是:从待输入的符号串开始,利用文法的规则步步向上进行(直接归约),试图(归约)到文法的(识别符号|开始符号)。 10、LR(0)分析法的名字中,“L”的含义是(从左到右进行分析),“R”的含义是(采用最右推导的逆过程---最左归约),“0”的含义是(向貌似句柄的符号串后查看0个输入符号)。 11、LR(1)分析法的名字中,“L”的含义是(从左到右进行分析),“R”的含义是(采用最右推导的逆过程---最左归约),“1”的含义是(向貌似句柄的符号串后查看1个输入符号)。 12、SLR(1)分析法的名字中,“S”的含义是(简单的),“L”的含义是(从左到右进行分析),“R”的含义是(采用最右推导的逆过程---最左归约),“1”的含义是(向貌似句柄的符号串后查看1个输入符号)。 13、在编译过程中,常见的中间语言形式有(逆波兰表示)、(三元式)、(四元式)和(树形表示)。 14、在编译程序中安排中间代码生成的目的是(便于代码优化)和(便于目标程序的移植)。 15、表达式-a+b*(-c+d)的逆波兰表示为(a-bc-d+*+ )。 16、表达式a+b*(c+d/e)的逆波兰表示为(abcde/+*+ )。 17、表达式a:=a+b*c↑(d/e)/f的逆波兰表示为(aabcde/↑*f/+:= )。 18、文法符号的属性有(继承属性)和(综合属性)两种。 19、一个文法符号的继承属性是通过语法树中它的(兄弟结点与父)结点的相应文法符号的属性来计算的。 20、一个文法符号的综合属性是通过语法树中它的(子)结点的属性来计算的。

编译原理 第二章习题答案

第2章习题解答 1.文法G[S]为: S->Ac|aB A->ab B->bc 写出L(G[S])的全部元素。 [答案] S=>Ac=>abc 或S=>aB=>abc 所以L(G[S])={abc} ============================================== 2. 文法G[N]为: N->D|ND D->0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么? [答案] G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD.... =>NDDDD...D=>D......D =============================================== 3.已知文法G[S]: S→dAB A→aA|a B→ε|bB 问:相应的正规式是什么?G[S]能否改写成为等价的正规文法?[答案] 正规式是daa*b*;

相应的正规文法为(由自动机化简来): G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b 也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε ===================================================================== ========== 4.已知文法G[Z]: Z->aZb|ab 写出L(G[Z])的全部元素。 [答案] Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb L(G[Z])={a n b n|n>=1} ===================================================================== ========= 5.给出语言{a n b n c m|n>=1,m>=0}的上下文无关文法。 [分析] 本题难度不大,主要是考上下文无关文法的基本概念。上下文无关文法的基本定义是:A->β,A∈Vn,β∈(Vn∪Vt)*,注意关键问题是保证a n b n的成立,即“a与b的个数要相等”,为此,可以用一条形如A->aAb|ab的产生式即可解决。 [答案] 构造上下文无关文法如下: S->AB|A A->aAb|ab B->Bc|c [扩展]

编译原理课后习题答案

第1 章 1、编译过程包括哪几个主要阶段及每个 阶段的功能。 答案:编译过程包括词法分析、语法分析、语义分析和中间代码生成、优化、目标代码生成5 个阶段。词法分析的功能是对输入的高级语言源程序进行词法分析,识别其中的单词符号,确定它们的种类,交给语法分析器,即把字符串形式的源程序分解为单词符号串形式。语法分析的功能是在词法分析结果的基础上,运用语言的语法规则,对程序进行语法分析,识别构成程序的各类语法范畴及它们之间的层次关系,并把这种层次关系表达成语法树的形式。词义分析和中间代码生成的功能是在语法分析的基础上,对程序进行语义分析,“理解”其含义,产生出表达程序语义的内部表达形式(中间代码)。优化的功能是按照等价变换的原则,对语义分析器产生的中间代码序列进行等价变换,删除其中多余的操作,对耗时耗空间的代码进行优化,以期最后得到高效的可执行代码。目标代码生成的功能是把优化后的中间代码变换成机器指令代码,得到可在目标机器上执行的机器语言程序。 第2 章 1、写一上下文无关文法G,它能产生配 对的圆括号串(如:(),(()),()(())等,甚至 包括0 对括号) 文法为:S→(L)|LS|L L→S| ε 2 、已知文法G :E→E+T|E-T|T T→T*F|T/F|F F→(E) |i (1)给出i+i*i,i*(i-i)的最左推导,最右推导以及语法树。 (2)i-i+i 哪个算符优先。 【解答】 (1)最左推导:E?E+T?T+T? F+T ? i+T ? i+T*F ? i+F*F ?i+i*F ?i+i*i E?T?T*F? F*F ? i*F ? i*(E) ? i*(E-T) ? i*(T-T) ? i*(F-T) ? i*(i-T) ? i*(i-F) ?i*(i-i) 最右推导:E?E+T?E+T*F? E+T*i ? E+F*i ? E+i*i ? T+i*i ? F+i*i ? i+i*i E?T?T*F? T*(E) ? T*(E-T) ? T*(E-F) ? T*(E-i) ? T*(T-i) ? T*(F-i) ?T*(i-i) ? F*(i-i) ?i*(i-i) i+i*i 以及i*(i-i)的语法树如下所示: (2)i-i+i 的语法树如下图所示。 从上图的语法树可知:“-”的位置位 于“+”的下层,也就是前面两个i 先进 行“-”运算,再与后面的i 进行“+” 运算,所以“-”的优先级高于“+”的 优先级。 3 、文法G: E→ET+|T T→TF*|F F→FP↑|P P→E|i (1)试证明符号串TET+*i↑是G 的一 个句型(要求画出语法树). (2)写出该句型的所有短语,直接短语和句柄. 【解答】(1)采用最右推导: E?T?F? FP↑? Fi↑? Pi↑? Ei↑ ? Ti↑? TF*i↑? TP*i↑? TE*i↑? TET+*i↑ 语法树如下图所示。 从文法G 的起始符号出发,能够推导 出符号串TET+*i↑,所以给定符号串是文法G的句型。 (2) 该句型的短语有: ET+,TET+*,i ,TET+*i↑ 直接短语有:ET+, i 句柄是:ET+ 4、已知文法G:S→iSeS|iS|i ,该文法 是二义文法吗?为什么? 【解答】该文法是二义文法。 因为对于句子iiiei 存在两种不同的最 左推导: 第 1 种推导:S? iSeS? iiSeS? iiieS? iiiei 第2种推导:S?iS?iiSeS?iiieS?iiiei 第3 章 1、用正规式描述下列正规集: (1)C 语言的十六进制整数; (2)以ex 开始或以ex 结束的所有小写字母构成的符号串; (3)十进制的偶数。 【解答】 (1)C 语言十六进制整数以0x 或者0X 开头,所以一般形式应该为(+|-|ε) (0x|0X)AA*,其中前面括号表示符号, 可以有正号、负号,也可以省略(用ε表示)默认是正数,A 表示有资格出现在十六进制整数数位上的数字,AA*表示一位或者多位(一个或者多个数字的

编译原理第8章作业及习题参考答案

第八章 语法制导翻译和中间代码生成 1.给出下面表达式的逆波兰表示(后缀式): (1) a*(-b+c) (4) (A ∧B) ∨(?C ∨ D) (7) if(x+y)*z=0 then s ∶=(a+b)*c else s ∶=a*b*c 解(1) ab-c+* (4) AB ∧C ?D ∨∨ (7) xy+z*0=sab+c*:=sab*c*:=¥(注:¥表示if-then-else 运算) 2. 请将表达式-(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。 答案:三元式 (1) (+ a, b) (2) (+ c, d) (3) (* (1), (2)) (4) (- (3), /) (5) (+ a, b) (6) (+,(5),c) (7) (- (4), (6)) 间接三元式 间接三元式序列 间接码表 (1) (+ a, b) (1) (2) (+ c, d) (2) (3) (* (1), (2)) (3) (4) (- (3), /) (4) ¥ = := * := + x y z s + c x a b s * c * a b

(5) (- (4), (1)) (1) (6) (- (4), (5)) (5) (6) 四元式 (1) (+, a, b, t1) (2) (+, c, d, t2) (3) (*, t1, t2, t3) (4) (-, t3, /, t4) (5) (+, a, b, t5) (6) (+, t5, c, t6) (6) (-, t4, t6, t7) 3. 采用语法制导翻译思想,表达式E 的"值"的描述如下: 产生式 语义动作 (0) S ′→E {print E.VAL} (1) E →E1+E2 {E.VAL ∶=E1.VAL+E2.VAL} (2) E →E1*E2 {E.VAL ∶=E1.VAL*E2.VAL} (3) E →(E1) {E.VAL ∶=E1.VAL} (4) E →n {E.VAL ∶=n.LEXVAL} 如果采用LR 分析法,给出表达式(5 * 4 + 8) * 2的语法树并在各结点注明语义值VAL 。 4. 假如习题3中表达式E 的“值”有两种类型:整型和实型。语义处理增加"类型匹配检查",请给出相应的语义描述。 S ’ * E1 E2 E0 E3 2 E5.V AL=5 8 5 * E5 E6 + E4 4 E6.V AL=4 E4.V AL=8 E3.V AL=20 E1.V AL=28 E2.V AL=2 E0.V AL=56 Print(56)

编译原理试题及答案

参考答案 一、单项选择题(共10小题,每小题2分,共20分) 1.语言是 A .句子的集合 B .产生式的集合 C .符号串的集合 D .句型的集合 2.编译程序前三个阶段完成的工作是 A .词法分析、语法分析和代码优化 B .代码生成、代码优化和词法分析 C .词法分析、语法分析、语义分析和中间代码生成 D .词法分析、语法分析和代码优化 3.一个句型中称为句柄的是该句型的最左 A .非终结符号 B .短语 C .句子 D .直接短语 4.下推自动机识别的语言是 A .0型语言 B .1型语言 C .2型语言 D .3型语言 5.扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即 A . 字符 B .单词 C .句子 D .句型 6.对应Chomsky 四种文法的四种语言之间的关系是 A .L 0?L 1?L 2?L 3 B .L 3?L 2?L 1?L 0 C .L 3=L 2?L 1?L 0 D .L 0?L 1?L 2=L 3 7.词法分析的任务是 A .识别单词 B .分析句子的含义 C .识别句子 D .生成目标代码 8.常用的中间代码形式不含 A .三元式 B .四元式 C .逆波兰式 D .语法树 9. 代码优化的目的是 A .节省时间 B .节省空间 C .节省时间和空间 D .把编译程序进行等价交换 10.代码生成阶段的主要任务是 A .把高级语言翻译成汇编语言 B .把高级语言翻译成机器语言 C .把中间代码变换成依赖具体机器的目标代码 装 订 线

D.把汇编语言翻译成机器语言 二、填空题(本大题共5小题,每小题2分,共10分) 1.编译程序首先要识别出源程序中每个(单词),然后再分析每个(句子)并翻译其意义。2.编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。 3.通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析),中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。 4.程序设计语言的发展带来了日渐多变的运行时存储管理方案,主要分为两大类,即(静态存储分配)方案和(动态存储分配)方案。 5.对编译程序而言,输入数据是(源程序),输出结果是(目标程序)。 三、名词解释题(共5小题,每小题4分,共20分) 1.词法分析 词法分析的主要任务是从左向右扫描每行源程序的符号,按照词法规则 从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位, 并转换成统一的内部表示(token),送给语法分析程序。 2.LL(1)文法 若文法的任何两个产生式A →α | β都满足下面两个条件: (1)FIRST(α) ? FIRST(β ) = φ; (2)若β?* ε,那么FIRST(α) ? FOLLOW( A ) = φ。 我们把满足这两个条件的文法叫做LL(1)文法,其中的第一个L代表从左 向右扫描输入,第二个L表示产生最左推导,1代表在决定分析器的每步 动作时向前看一个输入符号。除了没有公共左因子外,LL(1)文法还有一 些明显的性质,它不是二义的,也不含左递归。 3.语法树 句子的树结构表示法称为语法树(语法分析树或语法推导树)。 给定文法G=(V N,V T,P,S),对于G的任何句型都能构造与之关联的 语法树。这棵树具有下列特征: (1)根节点的标记是开始符号S。 (2)每个节点的标记都是V中的一个符号。 (3)若一棵子树的根节点为A,且其所有直接子孙的标记从左向右的排列 次序为A1A2…A R,那么A→A1A2…A R一定是P中的一条产生式。

编译原理(清华大学 第2版)课后习题答案

第三章 N=>D=> {0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD L={a |a(0|1|3..|9)n且 n>=1} (0|1|3..|9)n且 n>=1 {ab,} a n b n n>=1 第6题. (1) <表达式> => <项> => <因子> => i (2) <表达式> => <项> => <因子> => (<表达式>) => (<项>) => (<因子>)=>(i) (3) <表达式> => <项> => <项>*<因子> => <因子>*<因子> =i*i (4) <表达式> => <表达式> + <项> => <项>+<项> => <项>*<因子>+<项> => <因子>*<因子>+<项> => <因子>*<因子>+<因子> = i*i+i (5) <表达式> => <表达式>+<项>=><项>+<项> => <因子>+<项>=i+<项> => i+<因子> => i+(<表达式>) => i+(<表达式>+<项>) => i+(<因子>+<因子>) => i+(i+i) (6) <表达式> => <表达式>+<项> => <项>+<项> => <因子>+<项> => i+<项> => i+<项>*<因子> => i+<因子>*<因子> = i+i*i 第7题

第9题 语法树 s s s* s s+a a a 推导: S=>SS*=>SS+S*=>aa+a* 11. 推导:E=>E+T=>E+T*F 语法树: E +T * 短语: T*F E+T*F 直接短语: T*F 句柄: T*F 12.

短语: 直接短语: 句柄: 13.(1)最左推导:S => ABS => aBS =>aSBBS => aBBS => abBS => abbS => abbAa => abbaa 最右推导:S => ABS => ABAa => ABaa => ASBBaa => ASBbaa => ASbbaa => Abbaa => a1b1b2a2a3 (2) 文法:S → ABS S → Aa S →ε A → a B → b (3) 短语:a1 , b1 , b2, a2 , , bb , aa , abbaa, 直接短语: a1 , b1 , b2, a2 , , 句柄:a1 14 (1) S → AB A → aAb | ε B → aBb | ε (2) S → 1S0 S → A A → 0A1 |ε 第四章 1. 1. 构造下列正规式相应的DFA (1)1(0|1)*101 NFA (2) 1(1010*|1(010)*1)*0 NFA

相关文档
相关文档 最新文档