第二章 作业（6789B）【编译原理】

前言

以下内容源自《编译原理》
仅供学习交流使用

推荐

无

第二章 作业

6

6.令文法G₆为
N→D|ND
D→0|1|2|3|4|5|6|7|8|9
(1)G₆的语言L(G₆)是什么?
(2)给出句子0127、34和568的最左推导和最右推导。

（1）L(G~6~)={0,1,2,3,4,5,6,7,8,9}^+^
（2）
①0127
左 N=>ND=>NDD=>NDDD=>DDDD=0DDD=>01DD=>012D=>0127
右 N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127.
②34
左 N=>ND=>DD=>3D=>34
右 N=>ND=>N4=>D4=>34
③568
左 N=>ND=>NDD=>DDD=>5DD=>56D=>568
右 N=>ND=>N8=>ND8=>N68=>D68=>568

7

7.写一个文法,使其语言是奇数集,且每个奇数不以0开头。

G~7~(S):S->NZO|ON->1|2|3|4|5|6|7|8|9Z->XZ|εX->0|1|2|3|4|5|6|7|8|9O->1|3|5|7|9

8

8.令文法为
E→T|E+T|E-T
T→F|TFIT/F
F→(E)|i
(1）给出i+ ii、i* (i+i)的最左推导和最右推导;
(2）给出i+i+ i、i+i*i和i-i- i的语法树。

①i+ i*i
左 E=>E+T=>T+T=>F+T=>i+T=>I+T*F=>i+F*F=>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
②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=>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）语法树如图

9

9.证明下面的文法是二义的:
S→iSeS|iS|i

需证明：存在一个句子的语法树是不同的
iiiei的语法树如图
所以S→iSeS|iS|i是二义的

11

11.给出下面语言的相应文法
L₁= {aⁿbⁿcⁱ|n≥1, i≥0}
L₂= {aⁱbⁿcⁿ|n≥1,i≥0}
L₃= {aⁿbⁿa^mb^m|n, m≥0}
L₄= {1ⁿ0^m1^m0ⁿ|n,m≥0}

①G1(S):S->XCX->aXbC->cC|ε
②G2(S):S->AXX->bXCA->aA|ε
③G3(S):S->XYX->aXb|εY->aYb|ε
④G4(S):S->1S0|0S1|ε

最后

祝大家逢考必过
点赞收藏关注哦