清华大学1997年研究生入学考试 编译原理试题(共50分)

《编译原理》考试试题及答案（附录）一、判断题：1.一个上下文无关文法的开始符，可以是终结符或非终结符。

( X )2.一个句型的直接短语是唯一的。

( X )3.已经证明文法的二义性是可判定的。

（ X ）4.每个基本块可用一个DAG表示。

（√）5.每个过程的活动记录的体积在编译时可静态确定。

（√）6.2型文法一定是3型文法。

（ x ）7.一个句型一定句子。

( X )8.算符优先分析法每次都是对句柄进行归约。

(应是最左素短语) ( X )9.采用三元式实现三地址代码时，不利于对中间代码进行优化。

（√）10.编译过程中，语法分析器的任务是分析单词是怎样构成的。

( x )11.一个优先表一定存在相应的优先函数。

( x )12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。

( )13.递归下降分析法是一种自下而上分析法。

( )14.并不是每个文法都能改写成LL(1)文法。

( )15.每个基本块只有一个入口和一个出口。

( )16.一个LL(1)文法一定是无二义的。

( )17.逆波兰法表示的表达试亦称前缀式。

( )18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。

( )19.正规文法产生的语言都可以用上下文无关文法来描述。

( )20.一个优先表一定存在相应的优先函数。

( )21.3型文法一定是2型文法。

( )22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。

( )二、填空题：1.( 最右推导 )称为规范推导。

2.编译过程可分为（词法分析），（语法分析），（语义分析和中间代码生成），（代码优化）和（目标代码生成）五个阶段。

3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（）。

4.从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。

5.语法分析器的输入是（），其输出是（）。

6.扫描器的任务是从（）中识别出一个个（）。

清华大学1997硕士入学编译原理试题清华大学1997年研究生入学考试编译原理试题（共50分）1．(8分)已知正规式（1）(（a|b）* |aa)*b和正规式（2）（a|b）*b,试用有限自动机的等价性证明正规式（1）和（2）是等价的,给出相应的正规文法。

2．(8分)已知文法G [A ]为：A→aABl|aB→Bb|d① 试给出与G[A]等价的LL（1）文法G[A]② 构造G'[A]的预测分析表给出输入串aade#的分析过程。

3．(8分)有文法G[S]为：S→a|b|（A）A→SdA|S完成下列算符优先关系表，并判断G[S]是否为算符优先文法。

G[S]的算符优先关系表表1 算符优先关系表① 给出句型（sdsds）的短语，简单短语句柄，素短语和最大素短语。

② 给出输入串（adb）＃的分析过程。

4． (8分)已知文法G[S]为：S→aAd|；Bd|aB↑|；A↑A→aB→a① 试判断G[S]是否为LALR（1）文法② 当一个文法是LR（1）而不是LALR（1）时，那么LR（1）项目集的同心集合并后会出现哪几种冲突，请说明理由。

5．(6分)试对下面基本块进行优化① 应用DAG对该基本块进行优化，给出优化后的语句序列。

② 给出当只有L在基本块出口后为活跃时的优化结果。

基本块为：X=B＊CY=B/CZ=X+YW=9＊Z6．(6分)已知文法G[S]为：S→dABA→aA|aB→Bb|ε① 试向G[S]是否为正规文法，为什么？② G[S]新产生的语言是什么？G[S]能否改写为等价的正规文法？7．(6分)某语言允许过程嵌套定义和逆归调用（如PACAL语言），若在栈式动态存分配中采用嵌套层次显示表Display解决对非局部变量的引用问题，试给出下列程序执行到语句“b：=10；”时运行栈及Display 表的示意图。

var x, y;procedurc p;var a;procedure q;var b;begin(q)b : =10;end (q);procedure s;var c,d;procedure r;var e, f;begin (r)call q;edn (r);begin (s)call r;end (s);begin (p)call s;end (p);begin (main)call p;end (main).。

编译原理（清华⼤学-第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）不能⽤最右推导推导出上⾯的两个句⼦。

第1章引论第1题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍答案：（1） 编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。

（2） 源程序：源语言编写的程序称为源程序。

（3） 目标程序：目标语言书写的程序称为目标程序。

（4） 编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。

通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。

（5） 后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。

（6） 遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。

第2题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。

答案：一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。

其各部分的主要功能简述如下。

词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。

语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。

语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。

中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。

目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。

表格管理程序：负责建立、填写和查找等一系列表格工作。

表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。

1997年全国攻读硕士学位研究生入学考试英语试题答案与解析PartⅠCloze Test1.A2.C3.D4.A5.B6.D7.C8.B9.A10.DPartⅡReading ComprehensionPart APassage111.D12.B13.A14.CPassage215.D16.A17.C18.BPassage319.D20.A21.A22.BPassage423.C24.D25.B26.APassage527.C28.B29.A30.DPartⅢEnglish-Chinese Translation31.事实并非如此，因为这种问法是以人们对人的权利有一种共识为基础的，而这种共识并不存在。

32.有些哲学家论证说，权利只存在于社会契约中，是责任与权益交换的一部分。

33.这种说法从一开始就将讨论引向两个极端，它使人们认为应该这样对待动物：要么像对人类自身一样关切体谅，要么完全冷漠无情。

34.这类人持极端看法，认为人与动物在各相关方面都不相同，对待动物无须考虑道德问题。

35.这种反应并不是错误，这是人类用道德观念进行推理的本能在起作用。

这种本能应该得到鼓励，而不应该遭到嘲笑。

SectionⅣWriting(15points)36.见分析试题精解PartⅠCloze Test一、文章总体分析本文介绍了美国临时劳动大军日益庞大这一现象及其影响。

文章一、二段介绍了美国临时就业机构雇员数量庞大和美国劳务公司的蓬勃发展。

第三段分析了临时劳动大军迅速发展造成的影响：一是使公司更具竞争性，减轻了负担。

二是使工人失去了各种福利及归属感。

二、试题具体解析1.［精解］本题考核的知识点是：上下文语义+动词词义辨析。

文章首句指出：拥有56万雇员的劳务公司（Manpower Inc）是全球最大的临时就业机构。

紧接着，第二句又提到了每天早晨这些临时工人到美国各公司和工厂上班的情况。

我们可以想象一下：56万工人每天早晨上班的情形一定是非常浩大的。

东 北 大 学秦 皇 岛 分 校课程名称： 编译原理 试卷： (B )答案 考试形式： 闭卷授课专业： 计算机科学与技术 考试日期： 年 月 日 试卷：共 2 页题号 一 二 三 四 总分得分 阅卷人一、填空题（每空2分，共30分）1、编译程序的整个过程可以从逻辑上划分为词法分析、 语法分析 、语义分析、中间代码生成、 代码优化 和目标代码生成等几个阶段，另外还有两个重要的工 作是 理 和出错处理。

表格管2、规范规约中的可归约串是 句柄 ，算符优先分析中的可归约串是 最左素短语 。

3、语法分析方法主要可分为 自顶向下 和 自底向上 两大类。

4、LR （0）文法的项目集中不会出现 移进-归约 冲突和 归约-归约 冲突。

5、数据空间的动态存储分配方式可分为 栈式 和 堆式 两种。

6、编译程序是指能将 源语言 程序翻译成 目标语言 程序的程序。

7、确定有穷自动机DFA 是 NFA 的一个特例。

8、表达式 (a+b)*c 的逆波兰表示为 ab+c* 。

二、选择题（每题2分，共20分）1、LR 语法分析栈中存放的状态是识别 B 的DFA 状态。

A 、前缀B 、可归前缀C 、项目D 、句柄 2、 D 不可能是目标代码。

A 、汇编指令代码B 、可重定位指令代码C 、绝对机器指令代码D 、中间代码 3、一个控制流程图就是具有 C 的有向图A 、唯一入口结点B 、唯一出口结点C 、唯一首结点D 、唯一尾结点 4、设有文法G[S]：S →b|bBB →bS ，则该文法所描述的语言是C 。

A 、L （G ）={b i |i ≥0}B 、L （G ）={b 2i |i ≥0}C 、L （G ）={b 2i+1|i ≥0}D 、L （G ）={b 2i+1|i ≥1}5、把汇编语言程序翻译成机器可执行的目标程序的工作是由 B 完成的。

A 、编译器B 、汇编器C 、解释器D 、预处理器 6、在目标代码生成阶段，符号表用于 D 。

//东南大学一、文法G1： E→ET+|T T→TF*|F F→FP↑|P P→E|i 1、试证明符号串TET+*i↑是G1的一个句型（要求画出语法树）。

2、写出该句型的所有短语，简单短句和句柄。

三、 1、试写出一个上下文无关文法G3，它能产生配对的圆括号串（例如，（），（（）），（）（（））等，甚至包含0对括号）。

2、使用文法G3给出输入串（（））（）#的自上而下分析过程。

四、已知文法G4： S→aAb|Sc|ε A→aAb|ε 1、给出G4文法的LR（0）项目集规范族； 2、构造SLR分析表； 3、G4文法所定义的语言； 4、已知有如下文法及相应的LR分析表，试给出语句01001#的LR分析过程（填写下表）。

S→AAA A→1A A→0五、 1、翻译下面语句成四元式中间代码序列和后缀式（逆波兰式）； while x+y>a do if a<10 then a：=a+1 else x：=x-1； 2、翻译布尔表达式 （a>b） or （c=d） and not （e<f） 成转移四元式序列（即四元式中仅包含（zθ，-，-，-）和（j，-，-，-）两类语句，其中θ为关系运算符。

）一、判断下列命题的真假，并简述理由：（20分） 1、文法G的一个句子对应于多个推导，则G是二义的。

2、LL（1）分析必须对原有文法提取左因子和消除左递归。

3、算符优先分析法采用“移近-归约”技术，其归约过程是规范的。

4、文法S→aA；A→Ab；A→b是LR（0）文法（S为文法的开始符号）。

5、一个BASIC解释程序和编译程序的不同在于，解释程序由语法制导翻译成目标代码并立即执行之，而编译程序需产生中间代码及优化。

二、设计一个最小状态有穷自动机，识别由下列子串组成的任意字符串。

（20分） GO，GOTO，TOO，ON 例如：GOTOONGOTOOGOON是合法字符串。

三、构造一个LL（1）文法G，识别语言L：（20分） L={ω|ω为{0，1}上不包括两个相邻的1的非空串} 并证明你的结论。

第三章1、L(G[S])={ abc }2、L(G[N])={ n位整数或空字符串| n>0 }3、G[E]：E—>E+D | E-D | DD—>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 94、L(G[Z])={ a n b n | n>0 }5、(1) 考虑不包括“0”的情况G[S]：S—>0S | ABC | 2 | 4| 6 | 8A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9B—>AB | 0B | εC—>0 | 2 | 4 | 6 | 8考虑包括“0”的情况：G[S]：S—>AB | CB—>AB | CA—>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9C—>0 | 2 | 4 | 6 | 8(2)方法1：G[S]：S—> ABC | 2 | 4 | 6 | 8A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9B—>AB | 0B | εC—>0 | 2 | 4 | 6 | 8方法2：G[S]：S—>AB | CB—> AB | 0B | C | 0A—> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9C—>2 | 4 | 6 | 86、设<表达式>为E，<项>为T，<因子>为F，注：推导过程不能省略，以下均为最左推导(1) E => T => F => i(4) E => E+T => T+T => T*F+T => F*F+T => i*F+T => i*i+T => i*i+F => i*i+i(6) E => E+T => T+T => F+T => i+T => i+T*F => i+F*F => i+i*F => i+i*I7、<表达式><表达式>*<表达式><表达式>+<表达式>i i i<表达式><表达式>+<表达式>i <表达式>*<表达式>i i8、是有二义性的，因为句子abc 有两棵语法树（或称有两个最左推导或有两个最右推导）最左推导1：S => Ac => abc 最左推导2：S => aB => abc 9、(1)(2) 该文法描述了变量a 和运算符+、*组成的逆波兰表达式10、(1) 该文法描述了各种成对圆括号的语法结构(2) 是有二义性的，因为该文法的句子()()存在两种不同的最左推导： 最左推导1：S => S(S)S => (S)S => ()S => ()S(S)S => ()(S)S => ()()S => ()() 最左推导2：S => S(S)S => S(S)S(S)S => (S)S(S)S => ()S(S)S => ()(S)S => ()()S => ()()11、(1) 因为从文法的开始符E 出发可推导出E+T*F ，推导过程如下：E => E+T => E+T*F ，所以E+T*F 是句型。

《编译原理》考试试题及答案（汇总）一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）1.编译程序是对高级语言程序的解释执行。

(× )2.一个有限状态自动机中，有且仅有一个唯一的终态。

(×)3.一个算符优先文法可能不存在算符优先函数与之对应。

(√ )4.语法分析时必须先消除文法中的左递归。

(×)5.LR 分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。

(√)6.逆波兰表示法表示表达式时无须使用括号。

(√ )7.静态数组的存储空间可以在编译时确定。

(×)8.进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。

(×)9.两个正规集相等的必要条件是他们对应的正规式等价。

(× )10.一个语义子程序描述了一个文法所对应的翻译工作。

(×)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4 分，共40 分) 1．词法分析器的输出结果是。

A．( ) 单词的种别编码B．( ) 单词在符号表中的位置C．( ) 单词的种别编码和自身值D．( ) 单词自身值2.正规式M 1 和M 2 等价是指。

A．( ) M1 和M2 的状态数相等B．( ) M1 和M2 的有向边条数相等C．( ) M1 和M2 所识别的语言集相等D．( ) M1 和M2 状态数和有向边条数相等3.文法G：S→xSx|y 所识别的语言是。

A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0)D．( ) x*yx*4．如果文法G 是无二义的，则它的任何句子α。

A．( )最左推导和最右推导对应的语法树必定相同B．( ) 最左推导和最右推导对应的语法树可能不同C．( ) 最左推导和最右推导必定相同D．( )可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握。