北京航空航天大學數理邏輯與編譯原理試題

北京航空航天大學數理邏輯與編譯原理試題(2000年)一、(4’x2)在謂詞邏輯中將以下命題符號化。1.假如一個人只謊話言，那么他說的話沒一句可信的。2.每一個人都有獨一的身份證號碼。二、(8’)甲、乙、丙三人報考王教授的研究生。考試后王教授談了錄取狀況以下：(1)三人中只錄取一人；(2)假如不錄取甲，就錄取乙；(3)假如不錄取丙，就錄取甲。用命題邏輯確立王教授究竟錄取誰為他的研究生。三、(8’)定義二元連結詞△為p△q(p→q)。證明：{，△}是極小完整集。四、(4’x2)判斷以下邏輯推論關系能否建立，1.xy(P(x)Q(y))|xP(x)xQ(x)2.xP(x)xQ(x)|xy(P(x)Q(y))五、(8’)用歸納法證明：有的職業(yè)是每一個人都喜愛的。所以，每一個人都有自己喜愛的職業(yè)。六、填空題(18’，1-6題每空1’，7題每空1/60.5’)1.文法的形式定義為______________語言的形式定義為______________。2.規(guī)范規(guī)約每次規(guī)約的是句型的_______。3.活動記錄由______、______、______三部分構成。4.表達式x+y×z/(a+b)的后綴式為________。5.錯誤的局部化辦理是指____________________。6.局部優(yōu)化是指；循環(huán)優(yōu)化是指；全局優(yōu)化是指。7.有文法R::=i|(T)，T::=T,R|R達成其算符優(yōu)化關系表。(填寫第一二行)i( ),#i()·>·>·>,<·<·>·>·#<·<·=七、判斷題(1’x4)1.對隨意一個右線性文法G，都存在一個NFAM，知足L(G)=L(M).( )2.對隨意一個右線性文法G，都存在一個DFAM，知足L(G)=L(M).( )3.對任何正則表達式e，都存在一個NFAM，知足L(M)=L(e).( )4.對任何正則表達式e，都存在一個DFAM，知足L(M)=L(e).( )2/6八、選擇題(12’，1-2各2’，3-4各4’)1._____不是NFA的成分。(A)有窮字母表(B)初始狀態(tài)會合(C)停止狀態(tài)會合(D)有限狀態(tài)會合2._____不是編譯程序的構成部分。(A)詞法剖析程序(B)代碼生成程序(C)設施管理程序(D)語法剖析程序3.有文法G[S]：S::=aA|a|bCA::=aS|bBB::=aC|bA|bC::=aB|bS則__為L(G)中的句子。(A)a100b50ab100(B)a1000b500aba040103/6(C)aba(D)abaa4.有文法G=({S}，{a}，{S::=SaS，S::=}，S)，該文法是______。(A)LL(1)文法(B)二義性文法(C)算符優(yōu)先文法(D)SLR(1)文法九、有文法G[S]：(5’x3)S::=BAA::=BS|dB::=aA|bS|c(1)證明文法G是LL(1)文法。(2)結構LL(1)剖析表。(3)寫出句子adccd的剖析過程。4/6十、舉例說明什么是語法制導的翻譯(5’)十一、對以下程序，當編譯程序編譯到箭頭所指地點時，畫出其層次表(份程序xx表)和符號表。(6’)PROGRAMstack(output);VARm,n:integer;r:real;PROCEDUREsetup(ns:integer,check:real);VARk,l:integer;FUNCTIONtotal(VAR:at:integer,nt:integer):integer;VAR5/6i,sum:integer;BEGINFORi:=1TOntDOsum:=sum+at