编译原理第二章习题

发布 2022-07-15 15:27:28 阅读 5116

第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.语义和语义规则 ...