发布时间 : 星期五 文章编译原理-第三版-何炎祥-第二章习题答案更新完毕开始阅读c2e059e3caaedd3383c4d3ed
2.1 写出下列文法所确定的语言：
①、文法G = （{D}，{0,1,2,3,4,5,6,7,8,9}，P，D）其中，P={D→0|1|2|3|4|5|6|7|8|9}； 该文法定义的是0到9这10个数字{0,1,2,3,4,5,6,7,8,9}； ②、文法G = （{B，L，D}，{0,1,2,3,4,5,6,7,8，9}，P，B）；其中，P = {B→D|L，L→1|2|3|4|5|6|7|89，D→0|L}； 该文法定义的是0到9这10个数字{0,1,2,3,4,5,6,7,8,9}；
③、文法G=（{S，A}，{a，b}，P，S）其中，P={S→Aa，A→bA|a}。 该文件定义的是{baa2|n≥0}； 2.2
①因为语言的句子要求由3的整数倍的a组成，所以在构造产生式时，要保证每次产生的a的个数是3，得到文法 G[s]:s→aaa|Saaa
②因为符号串中a、b的个数没有直接关系，所以，将句子分成两部分：aaa和b2m-1，分别进行构造，然后再合并，可由产生式A→a|aA
得到aa,而由产生式B→b|bbB得到b2m-1,由于n≥1，m≥1，所以得到文法G【s】：S→ABA→a|aAB→b|bbB
③因为句子中a和B的个数一样多，且a全部在句子的前半部分，b全部在句子的后半部分，所以在构造产生式时，可让a和b对称出现，得文法 G【s】：s→aSb|ab
④因为句子中a、b、c的个数没有直接关系，所以分别构造生成an。Bmck的产生式，然后再合成，可由产生式a→aA|。得到bm，再有产生式c→cc|、得到ck， ⑤文法为GS：S→（+|-）（ABC|2|4|6|8）|0 C→02468 B→BAB0 A→123456789
⑥能被5整除的整数的末尾数必定是0或5，所以只要保证生成的整数末位数字是0或5即可，据此，构造描述能被5整除集合的文法如下： GS：S→（+|-）A（0|5） A→0123456789
如果还要求整数除0外，均不以0开头，则文法为 GS：S→（+|-）A（0|5）（0|5）
⑦由于文法的句子a∈{a，b}，因此文法的句子可分解为两种情形； 以a打头的符号串 以b打头的符号串
于是只要在构造产生式时保证每次产生相同个数的a和b即可，可以构造文法如下LGS：S→aSbbSaabSbaSSba 2.4
0型文法 2.5
P={S→aD|eE，D→bf，F→dB，A→bc，B→d} 2.6、
①3274的最左推导为： N→ND→NDD→NDDD→DDDD→3DDD→32DD→327D→3274 ① 3274的最右推导为：
N→ND→N4→ND4→N74→ND74→N274→D274→3274 ②65173的最左推导为：
N→ND→NDD→NDDD→DDDDD→6DDDD→65DDD→651DD→65173 65173的最右推导为：
N→ND→N3→ND3→ND73→ND73→ND73→ND173→65173 2.7、
要判断文法是否具有二义性，只要判断文法是否定义有这样的句子，该句子对应着两颗以上的语法树，或者说有两个以上不同的最右推导，或者说在对该句子进行规范规约的过程中，其规范句型的句柄不唯一。
本题文法是二义性，因为对于句子abc，存在两个不同的最左推导序列：： S→AB→abB→abc、S→AB→aB→abc
② 文法是二义性的，因为对于句子123，存在两个不同的最左推导序列， Unsigned integer → dight→dight i dight→1 dight→1 dight i dight 2.8
（1）G[Z]：Z→E+T E→T T→T*i|i
（2）G[S]：S→aFbT|Tcb|Fa|Tb|abF|c|abc|cMb F→tb|abf|c|abc
T→Fa|Tb|abF|c|abc|cMb M→abF|c