| 编译原理(第3版 | 您所在的位置：网站首页 › 医学史教材课后答案第二章 › 编译原理(第3版 |
编译原理(第3版
|
1.文法G=({A,B,S},{a,b,c},P,S)其中Р为:S→Ac|aB
A→ab→bc
写出L(GISJ)的全部元素。
答案: L(G[S])={abc} 2.文法G[N]为:N→D|ND D→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} (允许 0 开头的非负整数) 3.为只包含数字、加号和减号的表达式，例如 9-2+5，3-1，7 等构造一个文法答案:G[S]: S→S+DIS-DID D→0|1|2|3|4|5|6|7|8|9 4.证明文法G=({E,O}),{(,),+,*,v,d},P,E)是二义的，其中P为 E->EOE|(E)|v|d O->+|*答案：E=>EOE=>EOEOE E=>EOE=>EOEOE 有两个不同的最左推导（两颗不同的语法树），所以是二义的。 5.已知文法 G[Z]: Z::=a Z b Z::=a b 写出 L(G[Z])的全部元素。答案：L(G[Z])={ 答案： 
7.习题1中的文法G[S]是二义的吗？为什么？
答案：是二义的，对于一个产生式有两个不同的语法树。 8.考虑下面的上下文无关文法: S->SS*|SS+|a (1)表明通过此文法如何生成串 aa+a*，并为该串构造语法树. (2)该文法生成的语言是什么?答案： (1)S=>SS*=>SS+S*=>aS+S*=>aa+S*=>aa+a* 
(2)该文法生成的语言是: *和+的后缀表达式，即逆波兰式。 9.文法 S->S(S)S|ε (1)该文法生成的语言是什么? (2)该文法是二义的吗? 说明理由。答案：(1)生成的语言是：嵌套的括号 (2)是二义的。对于()()可以构造两棵不同的语法树。 10.令文法 G[E]为: E->T|E+TIE-T T->F|T*FIT/E F->(E)|i 证明E+T*F 是它的一个句型，指出这个句型的所有短语、直接短语和句柄。答案：存在推导序列：E=>E+T=>E+T*F，所以E+T*F 是它的一个句型。 短语：T*F、E+T*F 直接短语：T*F 句柄：T*F 
11.一个上下文无关文法生成句子 abbaa 的推导树如下：
(1)给出该句子相应的最左推导和最右推导。
(2)该文法的产生式集合 P 可能有哪些元素?
(3)找出该句子的所有短语、简单短语、句柄
答案： (1)最左推导:S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa->abbaa 最右推导:S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa (2)产生式有:S->ABS|Aa|ε、A->a、B->SBB|b 可能元素有:ε、aa、ab、abbaa、aaabbaa...... (3)短语:a、ε、b、εbb、aa、aεbbaa 简单(直接)短语：a、ε、b 句柄:a 12.构造产生如下语言的上下文无关文法各一个： (1) { }
(2) {
 }
(3) {
 {a,b}*
 |u|=|w|}
(4) {
 }
(5) {
 }
(6) {
 {a,b}*},其中，
 表示w的反向串，其含义是将w中的字母依次反转，首尾字母交换 位置，下同。
(7) {
 {a,b}+
|u|=|w|=1}
(8) {w|w∈{a,b}
w=
}
答案： 
13.构造产生如下语言的上下文无关文法各一个：
(1) {
 }
(2) {
 {a,b}*}
懒得打了......CSDN写公式太麻烦了，找找规律吧。
答案： (1)G[S]：S->AB A->ε|aAbb B->ε|CB (2)G[S]：S->aSa|bSb|c 15.分以下两种情况，各写一个文法，使其语言是十进制非负偶数的集合： （1）允许0打头。 （2）不允许0大头。答案： （1）G[S]：S->D|NT D->0|2|4|6|8 N->1|3|5|7|9|D T->NT|D （2）G[S]：S->D|NT D->2|4|6|8 N->1|3|5|7|9|D T->0|D|FT F->0|N |
|n≥1}【本文地址】