《编译原理》课后习题答案第三章第3章文法和语言第1.pdf
《编译原理》课后习题答案第三章
第3章文法和语言
第1题
文法G=({A,B,S},{a,b,c},叫其中P为：
S-*Ac|aB
A-ab
B-be
写出L(G⑸)的全部素。
答案：
L(G[S])={abc}
第2题
文法G[N]为:
N-D|ND
D-0|l|2|3|4|5||7|8|9
G[N]的语言是什么？
答案：
G[N]的语言是V+oV={0,1,2,3,45,7,8,9}
N=ND=NDD=NDDDD...D=D……D
或者：允许0开头的非负整数？
第3题
为只包含数字、加号和减号的表达式，例如9-2+5,3-1,7等构造一个文法。
答案：
G[S]:
S-S+D|S-D|D
D-0|l|2|3|4|5||7|8|9
第4题
已知文法G[Z]:
Z-*aZb|ab
写出L(G[Z])的全部素。
盛威网(www.snwei.com)专业的计算机学习网站1
《编译原理》课后习题答案第三章
答案：
Z=aZb=aaZbb=aaa..Z...bbb=aaa..ab...bbb
L(G[Z])={anbn|n=l}
第5题
写一文法，使其语言是偶正整数的集合。要求：
⑴允许0打头；
⑵不允许0打头。
答案：
⑴允许0开头的偶正整数集合的文法
E-NT|D
T-NT|D
N-*D|1|3|5|7|9
D-0|2|4||8
⑵不允许0开头的偶正整数集合的文法
E—NT|D
T-*FT|G
N-*D|1|3|5|7|9
D-2|4||8
F-*N|O
G-D|O
第题
已知文法G：
（表达式＞：：=＜项＞I＜表达式＞+＜项＞
＜项＞::=＜因子＞I＜项＞*＜因子＞
〈因子〉:（表〈达式＞）Ii
试给出下述表达式的推导及语法树。
（5）i+i（+i）
（）i+i*i
盛威网（www.snwei.com）专业的计算机学习网站2
《编译原理》课后习题答案第三章
答案；
表〈达式〉
表〈达式＞+＜项＞
〈因子＞
表〈达式〉
表〈达式〉+＜项＞
〈因子〉
i
项〈〉
（因子＞
i
〈项〉
〈因子〉
（）
⑸表〈达式〉
=＞＜表达式＞+＜项＞
=＞＜表达式＞+＜因子＞
=＞＜表达式＞+（表〈达式＞）
=＞＜表达式＞+（表〈达式＞+＜项＞）
=＞＜表达式＞+（表〈达式＞+＜因子》）
=＞＜表达式＞+（表〈达式〉+i）
=＞＜表达式＞+（＜项＞+i）
=＞＜表达式＞+（〈因子〉+i）
=＞＜表达式＞+（i+i）
=项+(i+i)
=因子+(i+i)
=＞i+（i+i）
〈表达式〉
〈表达式〉+＜项＞
＜项＞♦（因子〉
〈因子＞i
〈项〉
〈因子〉
⑹〈表达式〉
=＞＜表达式＞+＜项＞
=＞＜表达式＞+＜项＞*＜因子＞
=＞＜表达式＞+＜项＞*i
=＞＜表达式＞+＜因子＞*i
=＞＜表达式＞+i*i
=＞＜项〉+i*i
=＞＜因子〉+i*i
=＞iIi*i
盛威网w（ww.）专业的计算机学习网站3
《编译原理》课后习题答案第三章
第7题
证明下述文法G［表〈达式〉］是二义的。
表〈达式〉：：=a|（表〈达式））|表〈达式〉运〈算符〉表〈达式