没有合适的资源?快使用搜索试试~ 我知道了~
编译原理习题解.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 18 浏览量
2023-06-04
15:41:27
上传
评论
收藏 1.03MB PDF 举报
温馨提示
试读
30页
编译原理习题解.pdf
资源推荐
资源详情
资源评论
第二章:习题 2-4 Table 表
var x,y;
procedure p;
var a;
procedure q;
var b;
begin
b:=10;
end;
procedure s;
var c,d;
procedure r;
var e,f;
begin
call q;
end;
begin
call r;
end;
begin
call s;
end;
begin
call p;
end
依照:Page289,变量 table:array[0..txmax] of record 结构体和 block 函数取得下表,而表中各部份的含义,
见教材 Page18,Page19
Name
x
y
p
a
q
s
c
d
r
Kink
variable
variable
procedur
variable
procedur
procedur
variable
variable
procedur
Val /Level
0
0
0
1
1
1
2
2
2
Adr
3
4
1
3
3
7
3
4
0
Size
0
0
0
0
4
0
0
0
0
第三章 文法和语言
5. 写一文法,使其语言是偶正整数的集合
要求:
(1) 许诺 0 打头
(2) 不许诺 0 打头
解:
(1) G[S]=({S,P,D,N},{0,1,2,…,9},P,S)
P:
SPD|D
P->NP|N
D0|2|4|6|8
N->0|1|2|3|4|5|6|7|8|9
(2) G[S]=({S,P,R,D,N,Q },{0,1,2,…,9},P,S)
P:
SPD|P0|D
P->NR|N
R->QR|Q
D2|4|6|8
N->1|2|3|4|5|6|7|8|9
Q->0|1|2|3|4|5|6|7|8|9
6. 已知文法 G:
<表达式>::=<项>|<表达式>+<项>|<表达式>-<项>
<项>::=<因子>|<项>*<因子>|<项>/<因子>
<因子>::=(<表达式>)|i。
试给出下述表达式的推导及语法树。
(1)i; (2)(i) (3)i*i;
(4)i*i+i; (5)i+(i+i); (6)i+i*i。
解:
(1) v=<表达式>=><项>=><因子>=>i=w
(2) v=<表达式>=><项>=><因子>=>(<表达式>)=>(<项>)=>(<因子>)=>(i)=w
(3) v=<表达式>=><项>=><项>*<因子>=><因子>*<因子>=>i*i=w
(4) v=<表达式>=><表达式>+<项>=><项>+<项>=><项>*<因子>+<项>
=><因子>*<因子>+<因子>=>i*i+i=w
(5) v=<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<因子>=>i+(<表达式>)
=> i+(<表达式>+<项>)=>i+(<项>+<项>)=> i+(<因子>+<因子>)=>i+(i+i)=w
(6) v=<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=>i+<项>
=>i+<项>*<因子>=> i+<因子>*<因子>=> i+i*i=w
语法树见以下图:
(1)i
<表达式>
<项>
<因子>
i
(2)(i)
<表达式>
<项>
<因子>
( <表达式> )
<项>
<因子>
i
(4) i*i+i
<表达式>
(5) i+(i+i)
<表达式>
<表达式> + <项>
<项>
<因子>
i
<因子>
( <表达式> )
<表达式> + <项>
<项>
<因子>
<因子>
i
(3)i*i
<表达式>
<项>
<项> * <因子>
<因子>
i
i
(6) i+i*i
<表达式>
<表达式> + <项>
<项>
<因子>
i
<项> * <因子>
<因子>
i
i
<表达式> + <项>
<项>
<项> * <因子>
<因子>
i
i
<因子>
i
i
7. 为句子 i+i*i 构造两棵语法树,从而证明下述文法 G[<表达式>]是二义的。
<表达式>::=i|(<表达式>)|<表达式><运算符><表达式>
<运算符>::=+|-|*|/
解:为句子 i+i*i 构造的两棵语法树如下:
<表达式> <表达式>
<表达式> + <表达式> <表达式> * <表达式>
i <表达式> * <表达式> <表达式> + <表达式> i
i i i i
因此,该文法是二义的。
8. 习题 1 中的文法 G[S]是二义的吗?什么缘故?
答:是二义的。因为关于句子 abc 能够有两种不同的生成树,即:S=>Ac=>abc 和 S=>aB=>abc
11. 令文法 G[E]为:
ET|E+T|E-T
TF|T*F|T/F
F(E)|i
证明 E+T*F 是它的一个句型,指出那个句型的所有短语、直接短语和句柄。
解:可为 E+T*F 构造一棵语法树(见以下图),因此它是句型。
E
E + T
T * F
从语法树中容易看出,E+T*F 的短语有:
T*F 是句型 E+T*F 的相关于 T 的短语,也是相关于规那么 TT*F 的直接短语。
E+T*F 是句型 E+T*F 的相关于 E 的短语。
句型 E+T*F 的句柄(最左直接短语)是 T*F。
12. 下述文法 G[E]生成的语言是什么?给出该文法的一个句子,该句子至少含五个终结符,构造该句子的
语法树。证明:<E><T><F><MOP><POP>是 G[<E>]的句型,并指出该句型的所有短语、直接短语和句柄。
<E><E><T><POP>|<T>
<T><T><F><MOP>|<F>
<F>a|b|c
<POP>+|-
<MOP>*|/
解:
(1)计算文法 G[E]的语言:
n
由于 L(T)={(a|b|c)((a|b|c)(*|/)) |n>=0}
n
因此 L(E)={L(T)(L(T)(+|-)) |n>=0}
(2)该文法的一个句子是 aab*+,它的语法树是:
<E>
<E> <T> <POP>
<T> <T> <F> <MOP> +
<F> <F> b *
a a
(3) 证明:<E><T><F><MOP><POP>是 G[<E>]的句型,并指出该句型的所有短语、直接短语和句柄。
由于下面的语法树能够生成<E><T><F><MOP><POP>,因此它是 G[<E>]的句型。
<E>
<E> <T> <POP>
<T> <F> <MOP>
由于<E> => <E><T><POP>,且<T> => <T><F><MOP>,因此<T><F><MOP>是句型<E><T><F><MOP><POP>相关
于<T>的短语,也是相关于规那么<T> <T><F><MOP>的直接短语。
由 于 <E> => <E> 且 <E> => <E><T><F><MOP><POP>, 因 此 <E><T><F><MOP><POP> 是 句 型
<E><T><F><MOP><POP>相关于<E>的短语。
显然,句型<E><T><F><MOP><POP>的句柄是<T><F><MOP>。
14. 给诞生成下述语言的上下文无关文法:
n n m m
(1){a b a b |n,m>=0}
n m m n
(2){1 0 1 0 |n,m>=0}
t * t
(3){WaW |W 属于{0|a} ,W 表示 W 的逆}
解:
(1)所求文法为 G[S]=({S,A},{a,b},P,S),其中 P 为:
SAA
AaAb|ε
(2)所求文法为 G[S]=({S,A},{0,1},P,S),其中 P 为:
S1S0|A
A0A1|ε
*
(3)W 属于{0|a} 是指 W 能够的取值为{ε,0,a,00,a0,aa0,00aa,a0a0,…}
t
若是 W=aa0a00,则 W =00a0aa。
所求文法为 G[S]=({S,P,Q},{0,a},P,S),其中 P 为:
S0S0|aSa|a
n m n m
15. 语言{WaW}和{a b c d }是上下文无关的吗?能看出它们反映程序设计语言的什么特性吗?
答:生成语言{WaW}的文法超级简单,如
G[S]: SWaW
WaW|bW|ε
可见 G[S]是上下文无关的。
n m n m
生成语言{a b c d }的文法超级复杂,用上下文无关文法不可能办到,只能用上下文有关文法。这是因
n n m m
为要在 a c 的中间插入 b 而同时要在其后面插入 d 。即 a,c 相关联,b,d 相关联。
这说明对语言的限定越多(专门是语言中的符号前后关联越多),生成它的文法越复杂,乃至于很难
找到一个上下文法无关文法。
16.给诞生成下述语言的三型文法:
n
(1){a |n>=0}
n m
(2){a b |n,m>=1}
n m k
(3){a b c |n,m,k>=0}
解:
(1) 生成的 3 型文法是:
G[S]:SaS|ε
(2) 生成的 2 型文法是:
G[S]: SAB
AaA|a
BbB|b
剩余29页未读,继续阅读
资源评论
hhappy0123456789
- 粉丝: 61
- 资源: 5万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功