第2章习题。
1、文法g[s]为:
s->ac|ab
a->ab
b->bc
写出l(g[s])的全部元素。
答案] s=>ac=>abc
或s=>ab=>abc
所以l(g[s])=
2、令文法g为:n → d|nd
d → 0|1|2|3|4|5|6|7|8|9
(1)g的语言l(g)是什么?
(2)给出句子0568的最左推导和最右推导。
3、令文法为 :
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、i*(i+i)的最左推导分别为:
e=>t=>e+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)
i+i*i、i*(i+i)的最右推导分别为:
e=>t=>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)=>t*(e+f)=>t*(e+i)=>t*(t+i)
>t*(f+i)=>t*(i+i)=>f*(i+i)=>i*(i+i)
4、写一个文法,使其语言是奇数集,要求:
1)允许0开头; (2)不允许0开头。
答案] 1)允许0开头的偶正整数集合的文法
e->nt|g|sfm
t->nt|g
n->d|1|3|5|7|9
d->0|g
g->2|4|6|8
s->ns|ε
f->1|3|5|7|9|g
m->m0|0
2)不允许0开头的偶正整数集合的文法
e->nt|d
t->ft|g
n->d|1|3|5|7|9
d->2|4|6|8
f->n|0
g->d|0
5、证明下面的文法是二义的: s→ises|is|i
对于句子iiiei,存在如下两个最右推导:
s=>ises=>isei=>iisei=>iiiei
s=>is=>iises=>iisei=>iiiei
由此,该文法是二义的。
6、给出下面语言的相应上下文无关文法。:
1) l1= (2) l2=
(3) l3= (4) l4=*,wr表示w的逆}
l1的文法: s→ac a→aab|ab c→cc|ε
l2的文法: s→ab a→aab|ε b→abb|ε
l3的文法: s→1s0|a a→0a1|ε
l4的文法:s->0s0|1s1|a
7、给出生成下列语言的三型文法。
l5= l6=
1) 的三型文法为:
s->as|ε
2)的三型文法为:
s->aa
a->aa|bb
b->bb|ε
3)的三型文法为:
a->aa|bb|cc|ε
b->bb|cc|ε
c->cc|ε
编译原理第二章作业
1.pl 0语言允许过程嵌套定义和递归调用,试问它的编译程序如何解决运行时的存储管理。pl 0 语言允许过程嵌套定义和递归调用,它的编译程序在运行时采用了栈式动态存储管理。数组 code 存放的只读目标程序,它在运行时不改变。运行时的数据区 s 是由解释程序定义的一维整型数组,解释执行时对数据空间 ...
编译原理答案第二章
第二章词法分析 2.1 完成下列选择题 1 词法分析器的输出结果是 c a.单词的种别编码 b.单词在符号表中的位置。c.单词的种别编码和自身值 d.单词自身值。2 正规式m1和m2等价是指 c a.m1和m2的状态数相等 b.m1和m2的有向边条数相等。c.m1和m2所识别的语言集相等 d.m1和...
编译原理作业集 第二章
1.程序语言的定义 2.高级程序语言一般结构和主要共同特征 3.正确理解上下文无关文法基本概念,包括 文法的定义 推导 句型 句子 语言 语法树 二义性等 4.chomsky文法分类 掌握和理解程序语言的定义 高级语言的一般特征及程序语言的语法描述。1.语法,词法规则与语法规则 2.语义和语义规则 ...