编译原理习题.pdf

作业一 1. 已知文法 G[A] ，写出它定义的语言描述 如： G[A]: A → 0B|1C B → 1|1A|0BB C → 0|0A|1CC 2. 给出生成下述语言的上下文无关文法： n n m m （1）{ a b a b | n ，m=0} n m m n (2) { 1 0 1 0 | n ，m=0} 3. 给出生成下述语言的三型文法： n m (1){ a b |n,m=1 } n m k (2){a b c |n,m,k=0 } 4、文法 G[E] 为： E→E+T|T T→T*F|F F→(E)|i 试给出句型 (E+F)*i 的短语，简单 ( 直接 ) 短语 , 句柄。 第 3 章练习题 一、判断题 : 1、 编 译程序中的词法分析程序以字符形式的源程序作为输入，输出的单词符号常 采用二元组的形式。 2、 正规式的运算符“ |”读作“或“。 3、 若两个正规式所表示的正规集相同，则认为二者是等价的。 4、 用 l 代表字母， d 代表数字， Σ={l ，d} ，则正规式 r=dd* 定义了无符号整数单词。 5、 一个确定的有穷自动机 DFA M 的转换函数 f 是一个从 K ⅹΣ到 K 的子集的映像。 * 6、 一个非确定的有穷自动机 NFA N 的转换函数 f 是一个从 K ⅹΣ 到 K 的映像。 7、 一张状态转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。 8、 终态与非终态是可区别的。 9、 对任意一个右线性文法 G，都存在一个 NFA M，满足 L （G）=L （M）。 10、 对任意一个右线性文法 G，都存在一个 DFA M，满足 L （M）=L （R）。 * 二、 构造正规式 1(0|1) 101 相应的 DFA. 练习题 2 一、判断题： 1、 空符号串的集合 { ε} ={}= ф。 0 2、 设 A 是符号串的集合，则 A = ε。 T*, 则称 x 是文法 G[S] 的句型。 3、 设 G是一个文法， S 是开始符号，如果 S = x 且 x ∈V 4、 在形式语言中，最右推导的逆过程也称为规范归约。 5、 一个语言的文法是唯一的。 6、 若一个语言是无穷集合，则定义该语言的文法一定是递归的。 7、 一个句型中出现某个产生式的右部，则此右部一定是此句型的句柄。 8、 每个直接短语都是某规则的右部。 9、 用二义性文法定义的语言也是二义性的。 10、 文法的二义性与语言的二义性是两个不同的概念。 11、 任何正规文法都是上下文无关文法。 12、 正规文法对规则的限制比上下文无关文法对规则的限制要多一些。 二、选择题（从各题的 4 个答案中选出一个或多个正确的答案写在横线上） （1） 一般程序设计语言的描述都涉及（ ）3 个方面。 A 语法 B 语用 C 语义 D 基本符号的确定 （2 ）为了使编译程序能对程序设计语言进行正确的翻译，必须采用（