文档介绍：该【编译原理第二章习题 】是由【知识无限】上传分享，文档一共【13】页，该文档可以免费在线阅读，需要了解更多关于【编译原理第二章习题 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第2章****题解答
[S]为:
S->Ac|aB
A->ab
B->bc
写出L(G[S])的所有元素。
[答案]
S=>Ac=>abc
或S=>aB=>abc
因此L(G[S])={abc}
==============================================
文法G[N]为:
N->D|NDD->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
===============================================
[S]:
S→dABA→aA|aB→ε|bB
问:相应的正规式是什么G[S]可否改写成为等价的正规文法
[答案]
正规式是daa*b*;
相应的正规文法为(由自动机化简来):
G[S]:S→dAA→a|aBB→aB|a|b|bCC→bC|b
也可为(察看得来):G[S]:S→dAA→a|aA|aBB→bB|ε
=============
[Z]:
Z->aZb|ab
写出L(G[Z])的所有元素。
[答案]
Z=>aZb=>aaZbb=>aaa..Z...bbb=>aaa..ab...bbb
nn
L(G[Z])={ab|n>=1}
============
{anbncm|n>=1,m>=0}的上下文没关文法。
[剖析]
此题难度不大,主假如考上下文没关文法的基本观点。上下文没关文法的基本定义是:A->β,A∈Vn,β∈(Vn∪Vt)*,注意重点问题是保证anbn的建立,即“a与b的个数要相等”,为此,能够用一条形如A->aAb|ab的产生式即可解决。
[答案]
结构上下文没关文法以下:
S->AB|A
A->aAb|ab
B->Bc|c
[扩展]
凡是诸这样类的题都应按此思路进行,此题可做为一个基本代表。基本思路是这样的:
要求切合anbncm,因为a与b要求个数相等,因此把它们应看作一个整体单元进行,而cm做为另一个单位,初步产生式就应写为S->AB,此中A推出anbn,B推
出cm。因为m可为0,故上式进一步改写为S->AB|A。接下来考虑A,凡是要求两
个终结符个数相等的问题,都应写为A->aAb|ab形式,关于B就很简单写成
B->Bc|c了。
============
.写一文法,使其语言是偶正整数会合。要求:
(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
===========
:
E->E+T|E-T|T
T->T*F|T/F|F
F->(E)|i
试给出下述表达式的推导及语法树
(1)i;(2)i*i+i(3)i+i*i(4)i+(i+i)
[答案]
(1)E=>T=>F=>i
(2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i
(3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i
(4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T)
=>i+(i+T)=>i+(i+F)=>i+(i+i)
+i*i结构两棵语法树,进而证明下述文法G[<表达式>]是二义的。
〈表达式〉->〈表达式〉〈运算符〉〈表达式〉|(〈表达式〉)|i
〈运算符〉->+|-|*|/
[答案]
可为句子i+i*i结构两个不一样的最右推导:
最右推导1
〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉
=>〈表达式〉〈运算符〉i
=>〈表达式〉*i
=>〈表达式〉〈运算符〉〈表达式〉*i
=>〈表达式〉〈运算符〉i*i
=>〈表达式〉+i*i
=>i+i*i
最右推导2
〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉
=>〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式>
=>〈表达式〉〈运算符〉〈表达式〉〈运算符〉i
=>〈表达式〉〈运算符〉〈表达式〉*i
=>〈表达式〉〈运算符〉i*i
=>〈表达式〉+i*i
=>i+i*i
因此,该文法是二义的。
====
文法G[S]为:
S->Ac|aBA->ab
B->bc
该文法能否为二义的为何
[答案]
关于串abc
(1)S=>Ac=>abc
(2)S=>aB=>abc
即存在两不一样的最右推导
因此,该文法是二义的。
=========
:
S->SS*|SS+|a
(1)表示经过此文法怎样生成串aa+a*,并为该串结构语法树。
G[S]的语言是什么
[答案]
(1)此文法生成串aa+a*的最右推导以下
S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*
(2)该文法生成的语言是即加法和乘法的逆波兰式,
============
令文法G[E]为:E->E+T|E-TT->T*F|T/F|F
F->(E)|I
证明E+T*F是它的一个句型,指出这个句型的所有短语、直接短语和句柄。
[答案]
此句型对应语法树如右,故为此文法一个句型。
或许:因为存在推导序列:E=>E+T=>E+T*F,因此E+T*F句型
此句型相关于E的短语有:E+T*F;相关于T的短语有T*F,
直接短语为:T*F;。
句柄为:T*F
[E]:
E→ET+|TT→TF*|FF→F^|a
试证:FF^^*是文法的句型,指出该句型的短语、简单短语和句柄.
[答案]
该句型对应的语法树以下:
该句型相关于E的短语有FF^^*;相关于T的短语有FF^^*,F;相关于F的短语有F^;F^^;简单短语有F;F^;句柄为F.
:
(1)给出串abbaa最左推导、最右推导。
(2)该文法的产生式会合P可能有哪些元素
(3)找出该句子的所有短语、直接短语、句柄。
(1)串abbaa最左推导:
S=>ABS=>aBS=>aSBBS=>aεBBS=>aεbBS=>aεbbS=>aεbbAa=>aεbbaa
最右推导:
S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Aεbbaa=>aεbbaa
(2)产生式有:S→ABS|Aa|ε
A→a
B→SBB|b
(3)该句子的短语有a1b1b2a2a3、a1、b1、b2、b1b2、a2a3、a2;
直接短语有a1、b1、b2、a2;
句柄是a1。
===
。
(1){anbnambm|n,m>=0}(2){1n0m1m0n|n,m>=0}
3){WaWr|W属于{0|a}*,Wr表示W的逆}
[答案]
1){anbnambm|n,m>=0}S->AA
A->aAb|ε
{1n0m1m0n|n,m>=0}S->1S0|A
A->0A1|ε
3){WaWr|W属于{0|a}*,Wr表示W的逆}
S->0S0|1S1|ε
=
.给出生成以下语言的三型文法。
(1){an|n>=0}
(2){anbm|n,m>=1}
(3){anbmck|n,m,k>=0}
[答案]
(1){an|n>=0}的三型文法为:
S->aS|ε
(2){anbm|n,m>=1}的三型文法为:
S->aA
A->aA|bB
B->bB|ε
(3){anbmck|n,m,k>=0}的三型文法为:
A->aA|bB|cC|ε