華師網(wǎng)絡2014年9月課程考試《編譯原理》練習測試題庫及參考答案

華中師范大學網(wǎng)絡教育學院《編譯原理》練習測試題庫及參考答案一、填空若源程序是用高級語言編寫的目標程序是 則其翻譯程序稱為編譯序。詞法分析和語法分析本質(zhì)上都是對源程序的 進行分析。如果源語言(編寫源程序的語言)是高級語言而目標語言是某計算機的匯編言或機器語言，則這種翻譯程序稱為 。對編譯程序而言，輸入數(shù)據(jù)是 ,輸出結果是 。 ，是構成語言文法的單詞，是語法成分的最小單位。由PL／0的EBNF可知語言可看成是PASCAL語言的子集，它的編譯序是一個 。由于PL／0編譯程序采，所以語法分析過程BLOCK是整個編譯程的核心。用語法圖描述語法規(guī)則的優(yōu)點是 、 。每個非終結符是一個語法成分在書寫語言程序時并不出現(xiàn)它是由 和 、或終結符串定義的。PL／0的目標程序為假想棧式計算機的匯編語言，與具體計算機 。PL／0的編譯程序和目標程序的解釋執(zhí)行程序都是用 書寫的因此PL／0語言可在配備 的任何機器上實現(xiàn)。PL／0編譯程序是用PASCAL語言書寫的，整個編譯程序(包括主程序)是由 個嵌套及并列的過程或函數(shù)組成當源程序編譯正確時，PL／0編譯程序自動調(diào)用 ，對目標代碼行解釋執(zhí)行，并按用戶程序要求輸入數(shù)據(jù)和輸出運行結果。由于對某些非終結符可以遞歸定義，這就使得 可用有窮的文法述。 定的文法規(guī)則。PL／0編譯程序的語法分析采用了 。語法分析程序除總控外主要有兩大部分的功能，即 和 .PL／0的詞法分析程序GETSYM，是一個獨立的過程，其功能是為 提供單詞用的，是 的基礎，它把輸入的字符串形式的源程序分割成一個個單詞符號。每個過程應有過程首部以定義局部于它自己過程的常量變量和過程標識符也稱 。詞法分析程序GETSYM將完成的任務有: ,識別保留字,拼數(shù)拼復合詞,輸出源程序.如果一個PL／0語言的單詞序列在整個語法分析中，都能逐個得到匹配，到 ，這時就說所輸入的程序是正確的。若要構造程序設計語言的編譯程序，則首先要對程序設計語言本身有較為精確的描述而關于程序設計語言的描述將涉及 語義和 三個方面23.凡是具有某種特殊性質(zhì)的客體的聚合，都可稱為 。如果集合中元素個數(shù)為零，即集合中不含有任何元素，這樣的集合稱為 ，記為φ。設有集合A和B，如果A和B有相同的元素，則稱這兩個集合是 .設AB為任意兩個集合由所有屬于集合A或屬于集合B的元素組成的集合叫做集合A與B的 ．設A、B為任意兩個集合，由所有用于集合A且屬于集合B的元素組成的合，稱為集合A與B的 . E。AAAA的 .由兩個按一定次序排列的客體組成的序列，稱為 .ABA個成員是集合B的一個元素，則所有這樣的序偶組成的集合稱為集合A和B的 .在集合X上的關系如對任意均有則稱關系R是 。XR，如果合(x，y)∈R，便必有(y，x)∈R，R是 。在集合X上的關系R，如果合(x，y)∈R且(y，z)∈R，必有(x，z)則稱關系R是 。35P={（1，2（3，4（2，2）}Q={4，7（2，9（3，1）}則P·Q= 符號串與符號組成順序 ，如符號串a(chǎn)b ba，符號申001也 010。假設G是一個文法，S是文法的開始符號，如果S=>*x,則稱x是 。文法G產(chǎn)生的 的全體是該文法描述的語言39.一個文法G[Z]若存在推導序列Z=>+··Z··,則稱G(z)是 文法，這類文法所產(chǎn)生的句子有 個40.喬姆斯基把文法分成 類型.四個文法類的定義是逐漸增加限制的，因此每一種正規(guī)文法都是 .最右推導常被稱為 。由規(guī)范推導所得的句型稱為 。文法的二義性和語言的二義性是兩個 的概念。對于上下文無關文法， 是句型推導過程的幾何表示。直接短語也稱 .每棵語法樹的葉子組成一個 .每棵子樹的葉子組成一個 .每棵簡單子樹的葉子組成一個 .最左邊簡單子樹的葉子組成 .一個句型的最左直接短語稱為該句型的 。關于句型或句子的直接推導"=>"和推導實際上均可視為符號串之間系，而且推導"=>+"為直接推導"=>"的 。 BNF某條規(guī)則U→u中的左部符號U(U不是識別符)，不在所屬文法的任何其規(guī)則右部出現(xiàn)那么這條規(guī)則在推導中不起作用即所有句子的推導始終不會到此規(guī)則，顯然這種規(guī)則是多余的。也稱這種非終結符為 .從文法的某個非終結符號U推不出終結符號串，顯然，所有含有U的規(guī)則多余的。也稱這種非終結符為 。LL∪{εLε}分別是上下文有關語言、 和正規(guī)語言。設有文法G，對于其中某一非終結符號U可能作出一些不同推導U=>+其中S叫頭符號由于推導不同由U產(chǎn)生的頭符號S也可能不同這些頭符S構成的集合，稱為U的推導的 .一個上下文無關文法G包括四個組成部分依次是： , , , .11文法所描述的語言是 的集合。詞法分析器工作的第一步是輸入源程序文本。輸入串一般是放在一個緩沖中，這個緩沖區(qū)稱 。二、選擇編譯程序是一種常用的 軟件A.應用 B.系統(tǒng) C.工具 D.測試在使用高級語言編程時首先可通過編譯程序發(fā)現(xiàn)源程序的全部 錯誤部分 錯誤。語法B.語義 C.語用 D.運行編譯程序生成的目標程序 是機器語言的程序。一定 B.不一定C.某種情況下一定D.某種情況下不一4.編譯程序生成的目標程序 是可執(zhí)行的程序。A.一定 B.不一定 C.某種情況下一定D.某種情況下不一5.一個語言的文法是 .A．惟一的 B．不惟一的 C.個數(shù)有限的 D.無限的6.巴科斯-諾爾范式(即BNF)是一種廣泛采用的 的工具A．描述規(guī)則 B.描述語言 C．描述文法 D．描述句子r=(a|b|c)(x|y|z)L（r）中元素為個（）A．9B．6C．18 D．278、正則集合L={an|n≧0}相應的正則表達式是（）A．a(chǎn)*B．a(chǎn)+C．a(chǎn)a*D．a(chǎn)a+編譯過程中掃描器的任務包括 。①組織源程序的輸入②按詞法規(guī)則分割出單詞，識別出其屬性，并轉換成屬性字的形式輸出⑧刪除注解④刪除空格及無用字符⑤行計數(shù)、列計數(shù)⑥發(fā)現(xiàn)并定位詞法錯誤⑦建立符號表B．②③④⑥⑦C．①②③④⑥⑦ D．①②③④⑤⑥⑦10、編譯過程中，語法分析器的任務是 。分析單詞是怎樣構成的c.分析語句和說明是如何構成程序的d.分析程序的結構A.bc Bd C．bcd D．a(chǎn)bcd、語法分析的常用方法是 a.自頂向下b.自底向上 c.自左向右d.自右向B．a(chǎn)b C．cd D．a(chǎn)bc12、編譯程序中的語法分析器接受以 為單位的輸入，并產(chǎn)生有關信供以后各階段使用。表達式 B．產(chǎn)生式 C．單詞 D．語句13、LL(1)文法的條件是 。U->Xl|X2?|XnFIRST(Xi∩FIRST(Xj)=Φ，(≠j)BU->Xl|X2|?|XnXi=>*ε)FOLLOW(U)=ΦC．A和BD．都不是14、一個右線性文法G一定是（）A．LL（1）文法C．SLR（1）文法B．LR（1）文法D．上述三者都不是15、算符文法是指 的文法。26U-?VW?的規(guī)則(，，W∈VN)②終結符號集VT中任意兩個符號對之間至多有一種優(yōu)先關系成立⑧沒有相同的規(guī)則右部④沒有形如U->ε的規(guī)則B．①② C．①②③ 16、算符優(yōu)先文法是指 的文法。U-?VW?的規(guī)則(，，W∈VN)②終結符號集VT中任意兩個符號對之間至多有一種優(yōu)先關系成立⑧沒有相同的規(guī)則右部④沒有形如U->ε的規(guī)則A.①② B．①②③ C.①②③④ D．①②④17、下列文法G[S]的句型aR／aSb／aTb／,b 的最左素短為 S->aTb|，T->RR->R／S|SA.aTb B.aSb C.S D.R／18算符優(yōu)先分析法每次都是對 進行歸約簡單優(yōu)先分析法每次都是對柄進行歸約。A．最左短語 B.簡單短語 C.最左素短浯 D．素短19、xab+cde-*f/:=是賦值語句( )相應的后綴式A．x:=a+b+c*d-e/f B．x:=a+(b+c)*d-e/fC．x:+a+b+c*(d-e)/f 20、LR(K)方法是 。A．從左到右分析，每次走K步的一種編譯方法B．從左到右分析，共經(jīng)過K步的一種編譯方法C．從左到右分析，每次向前預測K步的一種編譯方法D．從左到右分析，每次向貌似句柄的符號串后看K個輸入符號的一種編譯方法21、下面三個文法中，為SLR(1)文法的是 。G1：P->PaP|bG2：P->bPb|cPc|b|cG3：P->bPb|bPc|d僅Gl B．僅G2 C．僅G3 D．G2和22、有下列文法：11S->Pa|Pb|cP->Pd|Se|f該文法是 。文法 B.SLR(1)文法C.a和b D.都不是23．代碼優(yōu)化的主要目標是( ②如何減少目標程序運行所需的空間③如何協(xié)調(diào)①和②④如何使生成的目標代碼盡可能短A①② B①②③ C①②④ D ①②③④24、設文法G（S為其開始符號）產(chǎn)生式如下：S→aSb|ab|G是一個（）A．LR（1）文法B．SLR（1）文C．三型文法 D．二型文法在編譯程序采用的優(yōu)化方法中， 是在循環(huán)語句范圍內(nèi)進行的。12①合并已知常量 ②刪除多余運算，③刪除歸納變量 ④強度削弱⑤代碼外提A①④ B①⑤ C①④⑤ D③④⑤合并表達式中常量運算的目的是 。12①合并常量，使表達式中的常量盡可能少②合并常量，使表達式盡可能簡短③將可在編譯時刻計算的常量運算在編譯時刻計算出來，然后用所計算出來的值替換表達式中出現(xiàn)的所有這種常量運算，使得生成的代碼指令盡可能少A① B② C③ D①②③下面的程序段可以進行哪些優(yōu)化 。i：=1j：=l0read L：x：=x*ij*iz：=writeji：=i+1ifi<100 goto halt①合并已知常量 ②刪除多余運算③刪除歸納變量 ④強度削弱⑤代碼外提可選項有：A．①④ B①⑤C，①④⑤D．③④⑤屬于低級語言的是（）AFortran B.Pascal C.Lisp DMasmoct是字母表{0，1，…，7}C號整規(guī)表達式是（。A.(oct)8 B.(oct)* C.(oct)+ D.(oct)#采用（）實現(xiàn)三地址代碼時，不利于對中間代碼進行優(yōu)化。A.四元式B.間接三元式C.三元式D.有向無循環(huán)圖一個正規(guī)語言只能對應( A一個正規(guī)文法；B一個最小有限狀態(tài)自動機；C.一個下推自動機D.一個確定的有限自動機文法G[A]：A→εA→aBB→AbB→a是( A正規(guī)文法 B二型文法C.上下無關文法 D.不確定下面說法正確的是( )：ASLR（1）LALR（1）BLR（1）LALR（1）文法一個上下文無關文法消除了左遞歸，提取了左公共因子后是滿足法的( )：A．必要條件BC.充分條件D．無法確定PL/0語言的目標程序解釋執(zhí)行時用到的數(shù)據(jù)對象有( A目標代碼CODEBTABLECDSPL/0語言編譯時產(chǎn)生或使用的數(shù)據(jù)對象不包括( A目標代碼CODEBCSDWORD37、編譯程序是一種常用的 軟件A.應用 B.系統(tǒng) C支撐 D.自動化38在使用高級語言編程時首先可通過編譯程序發(fā)現(xiàn)源程序的全部 錯和部分語義錯誤。A.語法 B語義 C.語用 D.運行39.LR（1）LALR（1）A則可能存在移進/歸約沖突B則可能存在歸約/歸約沖突C則可能存在移進/歸約沖突和歸約/歸約沖突D不存在沖突40、運算符與運算對象類型不符屬于 。A.語法錯誤 B.語義錯誤 C.語用錯誤 D.規(guī)41．語言是A．句子的集合 B．產(chǎn)生式的集合C．符號串的集合 D．句型的集42．編譯程序前三個階段完成的工作是A．詞法分析、語法分析和代碼優(yōu)化B．代碼生成、代碼優(yōu)化和詞法分析C．詞法分析、語法分析、語義分析和中間代碼生成D．詞法分析、語法分析和代碼優(yōu)化43．一個句型中稱為句柄的是該句型的最左A．非終結符號 B．短語 C．句子 D．直接短44．下推自動機識別的語言是A．0型語言 B．1型語言C．2型語言 D．3型語言掃描器所完成的任務是從字符串形式的源程序中識別出一個個具有獨立含A．字符 B．單詞 C．句子 D．句46．對應Chomsky四種文法的四種語言之間的關系是A．L0L1L2L3 B．L3L2L1L0C．L3=L2L1L0 D．L0L1L2=L3詞法分析的任務是A．識別單詞 B．分析句子的含義C．識別句子 D．生成目標代48．常用的中間代碼形式不含A．三元式 B．四元式 C．逆波蘭式 D．語法樹代碼優(yōu)化的目的是A．節(jié)省時間 B．節(jié)省空間C．節(jié)省時間和空間 D．把編譯程序進行等價交50．代碼生成階段的主要任務是A．把高級語言翻譯成匯編語言B．把高級語言翻譯成機器語言CD．把匯編語言翻譯成機器語言語言是A．句子的集合 B．產(chǎn)生式的集合C．符號串的集合 D．句型的集52．編譯程序前三個階段完成的工作是A．詞法分析、語法分析和代碼優(yōu)化B．代碼生成、代碼優(yōu)化和詞法分析C．詞法分析、語法分析、語義分析和中間代碼生成D．詞法分析、語法分析和代碼優(yōu)化53．一個句型中稱為句柄的是該句型的最左A．非終結符號 B．短語 C．句子 D．直接短54．下推自動機識別的語言是A．0型語言 B．1型語言C．2型語言 D．3型語言掃描器所完成的任務是從字符串形式的源程序中識別出一個個具有獨立含A．字符 B．單詞 C．句子 D．句56．對應Chomsky四種文法的四種語言之間的關系是A．LLLL B．LLLL0 1 2 3 3 2 1 0C．L=LLL D．LLL=L3 2 1 0 0 1 2 3詞法分析的任務是A．識別單詞 B．分析句子的含義C．識別句子 D．生成目標代58．常用的中間代碼形式不含A．三元式 B．四元式 C．逆波蘭式 D．語法樹代碼優(yōu)化的目的是A．節(jié)省時間 B．節(jié)省空間C．節(jié)省時間和空間 D．把編譯程序進行等價交60．代碼生成階段的主要任務是A．把高級語言翻譯成匯編語言B．把高級語言翻譯成機器語言CD．把匯編語言翻譯成機器語言三、名詞解釋題詞法分析LL(1)文法語法樹LR(0)分析器語言和文法四、判斷題1．正規(guī)文法產(chǎn)生的語言都可以用上下文無關文法來描述。????????( )?????????（ ）???????（ ）????????????????（ ）（ ）． 一 個 LL( l) 文 法 一 定 是 無 二 的。??????????????????( )．在規(guī)范規(guī)約中用最左素短語來刻劃可歸約串。????????????( )．目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。?????( )9．編譯程序是對匯編程序的翻譯。 ??????????????（ ）10 ．逆波蘭法表示的表達式亦稱前式。?????????????????( )五、簡答題有人認為編譯程序的五個組成部分卻一不可，這種看法正確嗎？解釋程序定義哪些寄存器?PL／0LIT?LOD?STO?CAL?INT?JMP?JPC?OPR?5S→a|∧|(T)T→T，S|S寫出句子((a，a)，a)的規(guī)范歸約過程及每一步的句柄。何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級優(yōu)化？目標代碼有哪幾種形式？生成目標代碼時通常應考慮哪幾個問題？寫出表達式(a＋b*c)/(a＋b)－d的逆波蘭表示及三元式序列。0?關系有哪些基本性質(zhì)？解釋字母表,符號,符號串,符號串的長度,符號串聯(lián)結？自下而上分析算法的基本思想是什么？s::=Qc|cQ::=Rb|bR::=Sa|a試求HARD(S),HARD(Q),HARD(R).BNF范式表示下述文法以消去ε規(guī)則：S::=aABb|abA::=Aab|εB::=Aa|a考慮下面程序…………Vara：integer；ProcedureS(X)；VarX：integer；Begina：＝a＋1；X：＝a＋XEnd；Begina：＝5；S(a)；Print(a)End．a(chǎn)么？G[I]:8I->I1/I0/Ia/Ic/a/b/c判斷下面符號串中哪些是該文法的句子.ab0(2)a0c01(3)aaa(4)bc10(5)aabc(6)bbca為了正確地對源程序進行編譯，不允許文法有二義性，那么怎樣才能排除文法的二義性呢?9什么是簡單子樹？什么是子樹？什么是句型的分析？自下而上分析算法的基本思想是什么？s::=Qc|cQ::=Rb|bR::=Sa|a試求HARD(S),HARD(Q),HARD(R).編譯程序和高級語言有什么區(qū)別?編譯程序的工作分為那幾個階段?簡述自下而上的分析方法。簡述代碼優(yōu)化的目的和意義。六、綜合題Whilea＞0∨b＜0 BeginX：＝X＋1；ifa＞0thena：＝a－1elseb：＝b＋1End；翻譯成四元式序列。設布爾表達式的文法為E→E(1)∨E(2)E→E(1)∧E(2)E→i假定它們將用于條件控制語句中，請改寫文法，使之適合進行語法制導翻譯和實現(xiàn)回填；寫出改寫后的短個產(chǎn)生式的語義動作。G(S)：S→(L)|aL→L，S|S消除左遞歸和回溯；FIRSTFOLLOW；G:S'->#S#S->D(R)R->R;P|pP->S|iD->i計算文法中每個非終結符的FIRSTVT集和LASTVT集 。A[i,j]:=B[i,j]C[A[k,l]]D[i+j]6、設布爾表達式的文法為E→E(1)∨E(2)E→E(1)∧E(2)E→i假定它們將用于條件控制語句中，請改寫文法，使之適合進行語法制導翻譯和實現(xiàn)回填；7（8）PASCALwhilea>bdoifa>0thena:=a-1elsea:=a+1;將該語句翻譯成逆波蘭式；thenFIRST集？G：SaSbS|aS|d是二義性文法。對于文法baSb短語和句柄？句型baSb的語法樹如圖五(2)所示。SA Bb B S ba圖五(2)句型baSb的的語法樹11．設有非確定的有自限動機NFA 中：(A，0)={C}(A，1)={A，B}(B，1)={C}(C，1)={C}轉換距陣和狀態(tài)轉換圖。華中師范大學網(wǎng)絡教育學院《編譯原理》練習測試題庫參考答案一、填空機器語言程序或匯編程序結構編譯程序源程序，目標程序。終結符編譯解釋執(zhí)行系統(tǒng)一趟掃描方法直觀、易讀終結符和非終結符串無關PASCAL語言12.18解釋執(zhí)行程序無窮的句子集語法分析自頂向下的遞歸子程序法說明部分的處理,程序體部分的處理語法分析,語法分析局部量濾空格,識別標識符,輸出源程序程序結束符語法,語用集合空集相等的并集交集全集冪集序偶笛卡爾乘積自反的對稱的傳遞的35.（1，9（3，7（2，5）}有關,不同于,不同于句型句子39.(1)遞歸 (2)無數(shù)四種上下文無關的規(guī)范推導規(guī)范句型不同語法樹簡單短語句型短語簡單短語句柄句柄傳遞閉包語法圖不可達到的不可終止的上下文無關語言頭符號集合終結符號，非終結符號，開始符號，產(chǎn)生式由文法的識別符推出的所有終結符號串輸入緩沖區(qū)二、選擇1.B 2.A 3.B 4.B 5.B 6.B 7.B 8.A 9.D 10.C11.B 12.C 13.C 14.A 15.A 16.D 17.B 18.D 19.A 20.D21.C 22.B 23.B 24.D 25.D 26.D 27.C 28.D 29.D 30.C31.B 32.B 33.A 34.A 35.A 36.C 37.B 38.A 39.B 40.A41.A 42.C 43.D 44.C 45.B 46.B 47.A 48.D 49.C 50.C51A 52C 53D 54C 55B 56B 57A 58D 59C 60C三．名詞解釋題從構成源程序的字符串中識別出一個個具有獨立意義的最小語法單位，并轉換成統(tǒng)一的內(nèi)部表示(token)，送給語法分析程序。A|都滿足下面兩個條件：FIRST()FIRST()=*FIRST()FOLLOW(A)=。LL(1)文法LL表示產(chǎn)生最左推導，1代表在決定分析器的每步動作時向前看一個輸入符號。除了沒有公共左因子外，LL(1)文法還有一些明顯的性質(zhì)，它不是二義的，也不含左遞歸。句子的樹結構表示法稱為語法樹(語法分析樹或語法推導樹)。G=(VN，VT，P，S)G語法樹。這棵樹具有下列特征：S。V中的一個符號。AA1A2…AR，那么AA1A2…AR一定是P中的一條產(chǎn)生式。AAVN。wwG的句型；若w中僅含終結符號，則w為文法G所產(chǎn)生的句子。LR(0)每一步，只須根據(jù)分析棧當前已移進和歸約出的全部文法符號，并至多再0個輸入符號，就能確定相對于某一產(chǎn)生式左部符號的句柄是否已在分析棧的頂部形成，從而也就可以確定當前所應采取的分析動作(是移進還是按某一產(chǎn)生式進行歸約等)。G定義為四元組的形式：N G=(V，V，P，N 其中：VN是非空有窮集合，稱為非終結符號集合；VT是非空有窮集合，稱為終結符號集合；P是產(chǎn)生式的集合(非空)；S是開始符號(或識別符號)這里，V∩V=，SV。V=V∪VG的字母表，它是出現(xiàn)N T N N T文法產(chǎn)生式中的一切符號的集合。文法G所描述的語言用L(G)表示，它由文法G所產(chǎn)生的全部句子組成，即L(G)={x|S*x，其中S為文法開始符號，且xV }T簡單的說，文法描述的語言是該文法一切句子的集合。四判斷題1× √ √ × √ √ 、× √ × 10、×五、簡答題以，上述說法不對。答：不正確。編譯程序的五個組成部分中，詞法分析，語法分析，語義分析和沒有優(yōu)化部分的編譯程序也能生成目標代碼。指令寄存器,程序地址寄存器,棧頂寄存器,基址寄存器(1以校正。校正的方式就是補上逗號或分號。為止。LITLOD：STO：CAL：INT：6. 句型 歸約規(guī)則句柄((a，a)，a)S→aa((S，a)，a)T→SS((T，a)，a)S→aa((T，S)，a)T→T，ST，S((S)，a)T→SS((T)，a)S→S(T)(T)(S，a)T→SS(T，a)S→aa(T，S)T→T，ST，S(T)S→(T)(T)S發(fā)，能產(chǎn)生更有效的目標代碼。三種級別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化。機器語言模塊。應著重考慮的問題：如何使生成的目標代碼較短；(3)如何充分利用指僅系統(tǒng)的的特點。逆波蘭表示：abc*＋ab＋/d－三元式序列：①(*，b，c)②(＋，a，①)③(＋，a，b)④(/，②，③)⑤(－，④，d)G(N)：N→AB|BA→AC|DB→1|3|5|7|9D→B|2|4|6|8C→0|D編譯過程的六個階段的任務，再加上表格管理和出錯處理的工作可分別由幾程序、中間代碼生成程序、代碼優(yōu)化程序、目標代碼生成程序、表格管理程序和出錯處理程序。自反的 在集合X上的關系R，如對任意x∈X，均∈R，則稱系R是自反的。非自反的在集合X上的關系R，如對任意x∈X，均有(x，x) R，則稱系R是非自反。對稱的 在集合X上的關系R，如果(x，y)∈R，便必∈R，則關系R是對稱的。非對稱的在集合X上的關系R，如果有(x，y)∈R叢x≠y，便必有(y，x)R，則稱關系R是非對稱的。傳遞的 在集合X上的關系R，如果合(x，y)∈R且(y，z)∈R，必有(x，z)∈R，則稱關系R是傳遞的。13.元素的非空有窮集合。字母表中的元素。由字母表中的符號組成的任何有窮序列，慣用小寫字母tuvxxyx的符號之后所得的符號串，叫xyxy。答：從所給符號串x并用該規(guī)則的左部取代此子串(即歸約)，重復此過程，步步向上歸約，最后試圖x歸約到文法的識別符號x是文法的句子。HARD(S)={S,Q,R,a,b,c}HARD(Q)={S,Q,R,a,b,c}HARD(R)={S,Q,R,a,b,c}S::=aABb|abA::={ab}B::=Aa|a17傳名：a＝12 傳值：a＝618.(1)錯誤正確正確正確錯誤錯誤錯誤19.(1)在語義上加些限制，或者說加一些語法的非形式規(guī)定。這樣做不必改變文法中原有的語法規(guī)則。(2)把排除二義性的規(guī)則合并到原有文法中，即構造一個等價的無二義性的文法G'。這樣做，需要改造原有文法。只有單層分支的子樹稱為簡單子樹。由某一結點及其所有分支組成的部分，成為原語法樹的一棵子樹。程。x用該規(guī)則的左部取代此子串(即歸約)，重復此過程，步步向上歸約，最后試xx句子。HARD(S)={S,Q,R,a,b,c}HARD(Q)={S,Q,R,a,b,c}HARD(R)={S,Q,R,a,b,c}用匯編語言或高級語言編寫的程序，必須先送入計算機，經(jīng)過轉換成用機器語言表示的目標程序（這個過程即編譯），才能由計算機執(zhí)行。執(zhí)行轉換過程的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語言源文件。編譯程序轉換過的叫目標程序，也就是機器語言。編譯程序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來將匯編語言編寫的程序，按照一一對應的關系，轉換成用機器語言表示的程序。"對話"，隨時可以修改高級語言的程序。BASIC語言就是解釋型高級語言。編譯型編譯程序將在過程中，不能進行人機對話修改。FORTRAN語言就是編譯型高級語言。詞法分析、語法分析和語義分析是對源程序進行的分析(端)，而中間代碼生成、代碼優(yōu)化和代碼生成三個階段合稱為對源程序進行綜合(編譯程序的后端)，它們從源程序的中間表示建立起和源程序等價的目標程序所謂自下而上分析法就是從輸入串開始，逐步進行“歸約”的開始符號；或者說從語法樹的末端開始，步步向上“歸約”，直到根節(jié)點。28代碼優(yōu)化是盡量生成“好”一種等價變換，在保證變換前后代碼執(zhí)行結果相同的前提下，盡量使目標程序運行時所需要的時間短，同時所占用的存儲空間少。五、綜合題每題10分，3題共30分1.解：(1)(j＞，a，0，5)(2)(j，－，－，3)(3)(j＜，b，0，5＝(4)(j，－，－，15)(5)(＋，×，1，T1)(6)(：＝，T1，－，×)(7)(j≥，a，0，9)(8)(j，－，－，12)(9)(－，a，1，T2)(10)(：＝，T2，－，a)(11)(j，－，－，1)(12)(＋，b，1，T3)(13)(：＝，T3，－，b)(14)(j，－，－，1)2.解：(1)E0→E(1)E→E0E(2)EA→E(1)E→EAE(2)E→i(2)E→E(1){BACKPATCH(E(1)·FC，NXQ)；E0·TC：＝E(1)·TC}E→E0E(2){E·FC：＝E(2)·FC；E·TC：＝MERG(E0·TC，E(2)·TC)}EA→E(1){BACKPATCH(E(1)·TC，NXQ)；E0·FC：＝E(1)·FC}E→EAE(2){E·TC：＝E(2)·TC；E·FC：＝MERG(EA·FC，E(2)·FC)E→i{E·TC：＝NXQ；E·FC：＝NXQ＋1；GEN(jn2，entry(i)，－0)；GEN(j，－，－，0)3(1)

S→(L)|aS’S’→S|εL→SL’L’→SL’|ε(2)FIRST)S)＝{(，a}FOLLOW(S)＝{#，，，)}FIRST(S’)＝{，a,εFIRST(L)＝{(，a}}FOLLOW(S’)＝{#，，，)}FOLLOW(L)＝{)}FIRST(L’)＝{，，ε(3)}FOLLOW(L’〕＝{)}a，()＃SS→aS’S→(L)S’S’→SS’→εS’→SS’→ε S’→εLL→SL’L→SL’L’L’→εL’→ε4.(1)文法G中每個非終結符的FIRSTVT集和LASTVT集為FIRSTVT(s')={#} FIRSTVT(P)={i,()FIRSTVT(s)={(,i) FIRSTVT(D)={i}FIRSTVT(R)={;,(,i)(2)文法G中每個非終結符