第 2 章 习题2-1 设有字母表 A 1 ={a,b,c, ⋯,z} ，A 2 ={0,1, ⋯,9} ，试回答下 列问题：（1） 字母表 A 1上长度为 2 的符号串有多少个？（2） 集合 A 1A 2 含有多少个元素？（3） 列出集合 A 1（A 1∪A 2） *中的全部长度不大于 3 的符号串。
2- 2 试分别构造产生下列语言的文法：（1）{a n b n |n ≥0}；（2）{a n b m c p |n,m,p ≥0}；（3）{a n #b n |n ≥ 0} ∪{c n #d n |n ≥0}；（ 4）{w#w r # | w ∈{0,1} *,w r 是 w 的逆序排列 } ； （ 5）任何不是以 0 打头的所有奇整数所组成的集合；（6）所有由偶数个 0 和偶数个 1 所组成的符号串的集合。
2- 3 试描述由下列文法所产生的语言的特点： 1） S →10S0 S →aA A →bA A →a 2） S →SS S →1A0 A →1A0 A →ε 3） S →1A S →B0 A →1A A →CB → B0 B →C C →1C0 C →ε（ 4）S →aSS S →a2- 4 试证明文法S →AB|DC A →aA|a B →bBc|bc C → cC|c D →aDb|ab 矚慫润厲钐瘗睞枥庑赖。
为二义性文法。
2- 5 对于下列的文法S→AB|c A → bA|a B →aSb|c试给出句子 bbaacb 的最右推导，并指出各步直接推导所得句型的句柄；指出句子的全部短语。
2- 6 化简下列各个文法(1)S →aABS|bCACd A → bAB|cSA|cCC B →bAB|cSB C → cS|c 聞創沟燴鐺險爱氇谴净。
(2)S → aAB|E A →dDA|e B → bE|fC→cAB|dSD|a D → eA E →fA|g(3)S → ac|bA A →cBC B →SA C → bC|d2-7 消除下列文法中的ε- 产生式(1)S →aAS|b A →cS| ε(2)S →aAA A →bAc|dAe| ε2-8 消除下列文法中的无用产生式和单产生式(1)S →aB|BC A →aA|c|aDb B →DB|C C →b D →B(2)S → SA|SB|A A → B|(S)|( ) B → [S]|[ ](3)E →E+T|T T → T*F|F F →P↑F|P P →(E)|i第 2 章习题答2- 1 答：(1)26*26=676(2)26*10=260(3) {a,b,c,...,z, a0,a1,...,a9, aa,...,az,...,zz,a00,a01,...,zzz}, 共有 26+26*36+26*36*36=34658 个残骛楼諍锩瀨濟溆塹籟。
1.1何谓源程序、目标程序、翻译程序、编译程序和解释程序?它们之间可能有何种关系?1.2一个典型的编译系统通常由哪些部分组成?各部分的主要功能是什么?1.3选择一种你所熟悉的程序设计语言，试列出此语言中的全部关键字，并通过上机使用该语言以判明这些关键字是否为保留字。
1.4选取一种你所熟悉的语言，试对它进行分析，以找出此语言中的括号、关键字END以及逗号有多少种不同的用途。
1.5试用你常用的一种高级语言编写一短小的程序，上机进行编译和运行，记录下操作步骤和输出信息，如果可能，请卸出中间代码和目标代码。
第一章习题解答1.解：源程序是指以某种程序设计语言所编写的程序。
目标程序是指编译程序（或解释程序）将源程序处理加工而得的另一种语言（目标语言）的程序。
翻译程序是将某种语言翻译成另一种语言的程序的统称。
编译程序与解释程序均为翻译程序，但二者工作方法不同。
解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入下一条语句继续进行解释、执行，如此反复。
即边解释边执行，翻译所得的指令序列并不保存。
编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的空间中，在用户需要时再执行之。
即先翻译、后执行。
2.解：一般说来，编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。
3.解：C语言的关键字有：auto break case char const continue default do double else enum externfloat for goto if int long register return short signed sizeof static struct switch typedef union unsigned void volatile while。
编译原理课后习题（修订版）第二章高级语言及其语法描述3、何谓“标识符”，何谓“名字”，两者的区别是什么？解：标识符是高级语言中定义的字符串，一般是以英文字母（包括大小写字母）或下划线开头的，由数字、字母和下划线组成的一定长度的字符串，它只是一个标志，没有其他含义。
名字是用标识符表示的，但名字不仅仅是一个字符串，它还具有属性和值。
4、令＋、* 和↑代表加、乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1＋1*2↑*1↑2的值：（1）、优先顺序（从高至低）为＋、* 和↑，同级优先采用左结合。
（2）、优先顺序为↑、＋、*，同级优先采用右结合。
解：（1）、1＋1*2↑*1↑2 = 2*2↑*1↑2 = 4↑*1↑2 = 4↑↑2 =（2）、1＋1*2↑*1↑2 =6、令文法G6为N→D∣ND，D→0∣1∣2∣3∣4∣5∣6∣7∣8∣9（1）、G6的语言L(G6)是什么？（2）、给出句子0127、34和568的最左推导和最右推导。
分析：根据产生式N→D∣ND可以看出，N最终可推导出1个或多个（可以是无穷多个）D，根据产生式D→0∣1∣2∣3∣4∣5∣6∣7∣8∣9可以看出，每个D可以推导出0至9中的某一个数字。
因此，N最终推导出的是由0到9这10个数字组成的字符串。
解：（1）、L(G6)是由0到9这10个数字组成的字符串。
（2）、句子0127、34和568的最左推导：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127N=>ND=>DD=>3D=>34N=>ND=>NDD=>DDD=>5DD=>56D=>568句子0127、34和568的最右推导：N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127N=>ND=>N4=>D4=>34N=>ND=>N8=>ND8=>N68=>D68=>5687、写一个文法，使其语言是奇数集，且每个奇数不以0开头。
编译原理（清华⼤学-第2版）课后习题答案第三章N=>D=> {0,1,2,3,4,5,6,7,8,9}N=>ND=>NDDL={a |a(0|1|3..|9)n且 n>=1}(0|1|3..|9)n且 n>=1{ab,}a nb n n>=1第6题.(1) <表达式> => <项> => <因⼦> => i(2) <表达式> => <项> => <因⼦> => (<表达式>) => (<项>)=> (<因⼦>)=>(i)(3) <表达式> => <项> => <项>*<因⼦> => <因⼦>*<因⼦> =i*i(4) <表达式> => <表达式> + <项> => <项>+<项> => <项>*<因⼦>+<项>=> <因⼦>*<因⼦>+<项> => <因⼦>*<因⼦>+<因⼦> = i*i+i (5) <表达式> => <表达式>+<项>=><项>+<项> => <因⼦>+<项>=i+<项> => i+<因⼦> => i+(<表达式>) => i+(<表达式>+<项>)=> i+(<因⼦>+<因⼦>)=> i+(i+i)(6) <表达式> => <表达式>+<项> => <项>+<项> => <因⼦>+<项> => i+<项> => i+<项>*<因⼦> => i+<因⼦>*<因⼦> = i+i*i第7题第9题语法树ss s* s s+aa a推导: S=>SS*=>SS+S*=>aa+a*11. 推导:E=>E+T=>E+T*F语法树:E+T*短语: T*F E+T*F直接短语: T*F句柄: T*F12．短语：直接短语：句柄：13.(1)最左推导：S => ABS => aBS =>aSBBS => aBBS=> abBS => abbS => abbAa => abbaa 最右推导：S => ABS => ABAa => ABaa => ASBBaa => ASBbaa => ASbbaa => Abbaa => a1b1b2a2a3 (2) ⽂法：S → ABSS → AaS →εA → aB → b(3) 短语：a1 , b1 , b2, a2 , , bb , aa , abbaa,直接短语： a1 , b1 , b2, a2 , ,句柄：a114 (1)S → ABA → aAb | εB → aBb | ε(2)S → 1S0S → AA → 0A1 |ε第四章1. 1. 构造下列正规式相应的DFA (1)1(0|1)*101NFA(2) 1(1010*|1(010)*1)*0NFA(3)NFA(4)NFA2.解：构造DFA 矩阵表⽰b其中0 表⽰初态，*表⽰终态⽤0，1，2，3，4，5分别代替{X} {Z} {X,Z} {Y} {X,Y} {X,Y,Z} 得DFA状态图为：3．解：构造DFA矩阵表⽰构造DFA的矩阵表⽰其中表⽰初态，*表⽰终态替换后的矩阵4．（1）解构造状态转换矩阵：{2，3} {0，1}{2，3}a={0,3}{2},{3},{0,1}{0,1}a={1,1} {0,1}b={2,2}（2）解：⾸先把M的状态分为两组：终态组{0}，和⾮终态组{1，2，3，4,5} 此时G=( {0},{1,2,3,4,5} ) {1,2,3,4,5}a={1,3,0,5} {1,2,3,4,5}b={4,3,2,5}由于{4}a={0} {1,2,3,5}a={1,3,5}因此应将{1,2,3,4,5}划分为{4},{1,2,3,5}G=({0}{4}{1,2,3,5}){1,2,3,5}a={1,3,5}{1,2,3,5}b={4,3,2}因为{1,5}b={4} {23}b={2,3}所以应将{1,2,3,5}划分为{1,5}{2,3}G=({0}{1,5}{2,3}{4}){1,5}a={1,5} {1,5}b={4} 所以{1,5} 不⽤再划分{2,3}a={1,3} {2,3}b={3,2}因为 {2}a={1} {3}a={3} 所以{2,3}应划分为{2}{3}所以化简后为G＝（ {0},{2},{3},{4},{1,5}）7.去除多余产⽣式后，构造NFA如下G={(0,1,3,4,6),(2,5)} {0,1,3,4,6}a={1,3}{0,1,3,4,6}b={2,3,4,5,6}所以将{0,1,3,4,6}划分为 {0,4,6}{1,3} G={(0,4,6),(1,3),(2,5)}{0,4,6}b={3,6,4} 所以划分为{0},{4,6} G={(0),(4,6),(1,3),(2,5)}不能再划分，分别⽤ 0，4，1，2代表各状态，构造DFA 状态转换图如下；b8．代⼊得S = 0(1S|1)| 1(0S|0) = 01(S|ε) | 10(S|ε) = (01|10)(S|ε)= (01|10)S | (01|10)= (01|10)*(01|10)构造NFA由NFA可得正规式为(01|10)*(01|10)=(01|10)+9.状态转换函数不是全函数,增加死状态8,G={(1,2,3,4,5,8),(6,7)}(1,2,3,4,5,8)a=(3,4,8) (3,4)应分出(1,2,3,4,5,8)b=(2,6,7,8)(1,2,3,4,5,8)c=(3,8)(1,2,3,4,5,8)d=(3,8)所以应将(1,2,3,4,5,8)分为(1,2,5,8), (3,4)G={(1,2,5,8),(3,4),(6,7)}(1,2,5,8)a=(3,4,8) 8应分出(1,2,5,8)b=(2,8)(1,2,5,8)c=(8)(1,2,5,8)d=(8)G={(1,2,5),(8),(3,4),(6,7)}(1,2,5)a=(3,4,8) 5应分出G={(1,2), (3,4),5, (6,7) ,(8) }去掉死状态8,最终结果为 (1,2) (3,4) 5,(6,7) 以1,3,5,6代替,最简DFA为b正规式:b*a(da|c)*bb*第五章1.S->a | ^ |( T )(a,(a,a))S => ( T ) => ( T , S ) => ( S , S ) => ( a , S) => ( a, ( T )) =>(a , ( T , S ) ) => (a , ( S , S )) => (a , ( a , a ) ) S=>(T) => (T,S) => (S,S) => ( ( T ) , S ) => ( ( T , S ) , S ) => ( ( T , S , S ) , S ) => ( ( S , S , S ) , S )=> ( ( ( T ) , S , S ) , S ) => ( ( ( T , S ) , S , S ) , S ) =>( ( ( S , S ) , S , S ) , S ) => ( ( ( a , S ) , S , S ) , S ) => ( ( ( a , a ) , S , S ) , S ) => ( ( ( a , a ) , ^ , S ) , S ) => ( ( ( a , a ) , ^ , ( T ) ) , S )=> ( ( ( a , a ) , ^ , ( S ) ) , S ) => ( ( ( a , a ) , ^ , ( a ) ) , S ) => ( ( ( a , a ) , ^ , ( a ) ) , a )S->a | ^ |( T )T -> T , ST -> S消除直接左递归：S->a | ^ |( T )T -> S T’T’ -> , S T’ | ξSELECT ( S->a) = {a}SELECT ( S->^) = {^}SELECT ( S->( T ) ) = { ( }SELECT ( T -> S T’) = { a , ^ , ( }SELECT ( T’ -> , S T’ ) = { , }SELECT ( T’ ->ξ) = FOLLOW ( T’ ) = FOLLOW ( T ) = { ）}构造预测分析表分析符号串（ a , a ）#分析栈剩余输⼊串所⽤产⽣式#S ( a , a) # S -> ( T )# ) T ( ( a , a) # ( 匹配# ) T a , a ) # T -> S T’# ) T’ S a , a ) # S -> a# ) T’ a a , a ) # a 匹配# ) T’，a) # T’ -> , S T’# ) T’ S , , a ) # , 匹配# ) T’ S a ) # S->a# ) T’ a a ) # a匹配# ) T’) # T’ ->ξ# ) ) # )匹配# # 接受2.E->TE’E’->+E E’->ξT->FT’T’->T T’->ξF->PF’F’->*F’F’->ξP->(E) P->a P->b P->∧SELECT（E－>TE’）=FIRST(TE’)=FIRST(T)= {（，a，b，^）SELECT（E’－>+E）={+}SELECT（E’－>ε）=FOLLOW(E’)= {#，)}SELECT（T－>FT’）=FIRST（F）= {（，a，b，^}SELECT（T’ —>T）=FIRST（T）= {（，a，b，^）SELECT(T’－>ε)=FOLLOW(T’)= {＋，#，)}SELECT(F －>P F’)=FIRST(F)= {（，a，b，^}SELECT(F’－>*F’)={*}SELECT(F’－>ε)=FOLLOW(F’)= {（，a，b，^，＋，#，）}3. S->MH S->a H->Lso H->ξK->dML K->ξL->eHf M->K M->bLM FIRST ( S ) =FIRST(MH)= FIRST ( M ) ∪FIRST ( H ) ∪{ξ}∪{a}= {a, d , b , e ,ξ} FIRST( H ) = FIRST ( L ) ∪{ξ}= { e , ξ}FIRST( K ) = { d , ξ}FIRST( M ) = FIRST ( K ) ∪{ b } = { d , b ,ξ}FOLLOW ( S ) = { # , o }FOLLOW ( H ) = FOLLOW ( S ) ∪{ f } = { f , # , o }FOLLOW ( K ) = FOLLOW ( M ) = { e , # , o }FOLLOW ( L ) ={ FIRST ( S ) –{ξ} } ∪{o} ∪FOLLOW ( K )∪{ FIRST ( M ) –{ξ} } ∪FOLLOW ( M )= {a, d , b , e , # , o }FOLLOW ( M ) ={ FIRST ( H ) –{ξ} } ∪FOLLOW ( S )∪{ FIRST ( L ) –{ξ} } = { e , # , o }SELECT ( S-> M H) = ( FIRST ( M H) –{ξ} ) ∪FOLLOW ( S )= ( FIRST( M ) ∪FIRST ( H ) –{ξ} ) ∪FOLLOW ( S )= { d , b , e , # , o }SELECT ( S-> a ) = { a }SELECT ( H->L S o ) = FIRST(L S o) = { e }SELECT ( H ->ξ) = FOLLOW ( H ) = { f , # , o }SELECT ( K->ξ) = FOLLOW ( K ) = { e , # , o }SELECT ( L-> e H f ) = { e }SELECT ( M->K ) = ( FIRST( K ) –{ξ} ) ∪FOLLOW ( M ) = {d，e , # , o }SELECT ( M -> b L M )= { b }4 . ⽂法含有左公因式，变为S->C $ { b, a }C-> b A { b }C-> a B { a }A -> b A A { b }A-> a A’ { a }A’-> ξ{ $ , a, b }A’-> C { a , b }B->a B B { a }B -> b B’ { b }B’->ξ{ $ , a , b }B’-> C { a, b }5. <程序> --- S <语句表>――A <语句>――B <⽆条件语句>――C <条件语句>――D <如果语句>――E <如果⼦句> --FS->begin A end S->begin A end { begin }A-> B A-> B A’ { a , if }A-> A ; B A’-> ; B A’ { ; }A’->ξ{ end }B-> C B-> C { a } B-> D B-> D { if }C-> a C-> a { a }D-> E D-> E D’ { if }D-> E else B D’-> else B { else }D’->ξ{; , end } E-> FC E-> FC { if }F-> if b then F-> if b then { if }⾮终结符是否为空S－否A－否A’－是B－否C－否D－否D’－是E－否F－否FIRST(S) = { begin }FIRST(A) = FIRST(B) ∪FIRST(A’) ∪{ξ} = {a , if , ; , ξ} FIRST(A’) ={ ; , ξ}FIRST(B) = FIRST(C) ∪FIRST(D) ={ a , if }FIRST(C) = {a}FIRST(D) = FIRST（E）= { if }FIRSR(D’) = {else , ξ}FIRST(E) = FIRST(F) = { if }FIRST(F) = { if }FOLLOW(S) = {# }FOLLOW(A) = {end}FOLLOW(A’) = { end }FOLLOW(B) = {; , end }FOLLOW (C) = {; , end , else }FOLLOW(D) = {; , end }FOLLOW( D’ ) = { ; , end }FOLLOW(E) = { else , ; end }FOLLOW(F) = { a }S A A’ B C D D’ E F if then else begin end a b ;6. 1.(1) S -> A | B(2) A -> aA|a(3)B -> bB |b提取（2），（3）左公因⼦(1) S -> A | B(2) A -> aA’(3) A’-> A|ξ(4) B -> bB’(5) B’-> B |ξ2.(1) S->AB(2) A->Ba|ξ(3) B->Db|D(4) D-> d|ξ提取（3）左公因⼦(1) S->AB(2) A->Ba|ξ(3) B->DB’(4) B’->b|ξ(5) D-> d|ξ3.(1) S->aAaB | bAbB(2) A-> S| db(3) B->bB|a4(1)S->i|(E)(2)E->E+S|E-S|S提取（2）左公因⼦(1)S->i|(E)(2)E->SE’(3)E’->+SE’|-SE’ |ξ5(1)S->SaA | bB(2)A->aB|c(3)B->Bb|d消除（1）(3)直接左递归(1)S->bBS’(2)S’->aAS’|ξ(3)A->aB | c(4) B -> dB’(5)B’->bB’|ξ6.(1) M->MaH | H(2) H->b(M) | (M) |b消除（1）直接左递归，提取（2）左公因⼦(1)M-> HM’(2)M’-> aHM’ |ξ(3)H->bH’ | ( M )(4)H’->(M) |ξ7. (1)1)A->baB4)B->a将1）、2)式代⼊3）式1)A->baB2)A->ξ3)B->baBbb4)B->bb5)B->a提取3）、4）式左公因⼦1)A->baB2)A->ξ3)B->bB’4)B’->aBbb | b5)B->a(3)1)S->Aa2)S->b3)A->SB4)B->ab将3）式代⼊1）式1)S->SBa2)S->b3)A->SB4)B->ab消除1）式直接左递归1)S->bS’2)S’->BaS’ |ξ3)S->b4)A->SB5)B->ab删除多余产⽣式4）1)S->bS’（5）1)S->Ab2)S->Ba3)A->aA4)A->a5)B->a提取3）4）左公因⼦1)S->Ab4)A’-> A |ξ5)B->a将3）代⼊1）5）代⼊21)S->aA’b2)S->aa3)A->aA’4)A’-> A |ξ5)B->a提取1）2）左公因⼦1)S-> aS’2)S’->A’b | a3)A->aA’4)A’-> A |ξ5)B->a删除多余产⽣式5）1)S-> aS’2)S’->A’b | a3)A->aA’4)A’-> A |ξA A’S’S将3）代⼊4）1)S-> aS’2)S’->A’b | a3)A->aA ’4)A’-> aA’ |ξ3)S’->a4)S’->b5)A->aA ’6)A’-> aA’ |ξ对2）3)提取左公因⼦1)S->aS’2)S’->aS’’3)S’’->A’b|ξ4)S’->b5)A->aA ’6)A’-> aA’ |ξ删除多余产⽣式5）1)S->aS’2)S’->aS’’3)S’’->A’b|ξ4)S’->b第六章1S → a | ∧ | ( T )T → T , S | S解：(1) 增加辅助产⽣式 S’→＃S＃求 FIRSTVT集FIRSTVT（S’）＝ {#}FIRSTVT（S）＝ {a ∧ ( }＝ { a ∧ ( } FIRSTVT (T) ＝ {,} ∪ FIRSTVT( S ) = { , a ∧ ( }求 LASTVT集LASTVT（S’）＝ { # }LASTVT（S）＝ { a ∧ )}LASTVT (T) ＝ { , a ∧ )}(2)因为任意两终结符之间⾄多只有⼀种优先关系成⽴，所以是算符优先⽂法(3)a ∧( ) , #F 1 1 1 1 1 1g 1 1 1 1 1 1f 2 2 1 3 2 1g 2 2 2 1 2 1f 3 3 1 3 3 1g 4 4 4 1 2 1f 3 3 1 3 3 1g 4 4 4 1 2 1(4)栈优先关系当前符号剩余输⼊串移进或规约＃<·( a,a)# 移进＃( <· a ,a)# 移进＃(T <·, a)# 移进＃(T，<· a )# 移进＃(T,a ·> ) # 规约＃(T,T ·> ) # 规约＃(T =·) # 移进＃(T) ·> ＃规约＃T =·＃接受4.扩展后的⽂法S’→#S# S→S;G S→G G→G(T) G→H H→a H→(S)T→T+S T→S（1）FIRSTVT(S)={;}∪FIRSTVT(G) = {; , a , ( }FIRSTVT(G)={ ( }∪FIRSTVT(H) = {a , ( }FIRSTCT(H)={a , ( }FIRSTVT(T) = {+} ∪FIRSTVT(S) = {+ , ; , a , ( }LASTVT(S) = {;} ∪LASTVT(G) = { ; , a , )}LASTVT(G) = { )} ∪LASTVT(H) = { a , )}LASTVT(H) = {a, )}LASTVT(T) = {+ } ∪LASTVT(S) = {+ , ; , a , ) }构造算符优先关系表因为任意两终结符之间⾄多只有⼀种优先关系成⽴，所以是算符优先⽂法（2）句型a(T+S);H;(S)的短语有：a(T+S);H;(S) a(T+S);H a(T+S) a T+S (S) H直接短语有: a T+S H (S)句柄： a素短语：a T+S (S)最左素短语：a(3)（4）不能⽤最右推导推导出上⾯的两个句⼦。
