2009年1月高等教育自學(xué)考試福建省統(tǒng)一命題考試編譯原理試卷(課程代碼7016)一、單項(xiàng)選擇題(本大題共10小題,每小題2分,共20分】在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。1．構(gòu)造編譯程序應(yīng)掌握【】A．源程序B．目標(biāo)語言C．編譯方法D．A、B、C三個(gè)選項(xiàng)2．變量應(yīng)當(dāng)【】A．持有左值B．持有右值C．既持有左值又持有右值D．既不持有左值也不持有右值3．編譯程序是對(duì)【】A．匯編程序的翻譯B．高級(jí)語言程序的解釋執(zhí)行C．機(jī)器語言的執(zhí)行D．高級(jí)語言的翻譯4．有限狀態(tài)自動(dòng)機(jī)能識(shí)別【】A．上下文無關(guān)文法B．上下文有關(guān)文法C．正規(guī)文法D．短語文法5．文法G：EE+T／TTT*P／PP（E)／i則句型P+T+i的句柄和最左索短語為【】A．P+T和iB．P和P+TC．i和P+T+iD．P和T6．詞法分析器的輸出結(jié)果是【】A．單詞的種別編碼B．單詞在符號(hào)表中的位置C．單詞的種別編碼和自身值D．單詞自身值7．若a為終結(jié)符，則A為【】A．歸約項(xiàng)目B．移進(jìn)項(xiàng)目C．接受項(xiàng)目D．待約項(xiàng)目8．后綴式ab+cd+／可用表達(dá)式為【】A．a(chǎn)+b／c+dB．(a+b)／(C+d)Ca+b／(c+d)D．a(chǎn)+b+c／d9．文法G:SxSx／y所識(shí)別的語言是【】A．xyxB．(xyx)*C．xyx8(n≥O)D．xyx10．不可能是目標(biāo)代碼的是【】A．匯編指令代碼B．可重定位指令代碼C．絕對(duì)指令代碼D．中間代碼二、多項(xiàng)選擇題(本大題共5小題,每小題3分,共15分)在每小題的五個(gè)備選項(xiàng)中至少有兩個(gè)是符合題目要求的,請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選、少選或未選均無分。11．編譯程序各階段的工作都涉及到【】A．語法分析B．表格管理C．出錯(cuò)處理D．語義分析E．詞法分析12．對(duì)正規(guī)文法描述的語言，以下有能力描述它的是【】A．O型文法B．1型文法C．上下文無關(guān)文法D．右線性文法E．左線性文法13．對(duì)LR分析表的構(gòu)造，有可能存在動(dòng)作沖突【】A．移進(jìn)B．歸約C．移進(jìn)／歸約D．移進(jìn)／移進(jìn)E．歸約／歸約14．下面中間代碼形式中，能正確表示算術(shù)表達(dá)式a+b+c的有【】++A．a(chǎn)b+c+B．a(chǎn)be++C．+cD．a(chǎn)+E．a(chǎn)+b+cAbbc15．符號(hào)表的每一項(xiàng)均包含【】A．名字欄B．類型欄C．信息欄D．值欄E．指令三、填空題(本大題共6小題．每空1分，共10分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。16．編譯過程通?？煞譃?個(gè)階段，分別是______、語法分析、__________、代碼優(yōu)化和目標(biāo)代碼生成。17．編澤程序工作過程中，第—段輸入是________最后階段的輸出為________程序。18．在語法分析中，最常見的兩種方法：一是_______，_______分析法，另一是______分析法。19．文法符號(hào)的屬性有兩種，一種稱為_______，另一種稱為_______。20．后綴式abc-／所代表的嘉扶式縣__________。21．局部?jī)?yōu)化是_________范圍內(nèi)進(jìn)行的—種優(yōu)化。四、簡(jiǎn)答題(本大題共2小題。每小題5分。共10分)22．什么是編譯程序?23．說明如下簡(jiǎn)單表達(dá)式文法娃二義性的：EE+E／E*E／(E)／i其中，E為唯一的非終結(jié)符，且為開始符號(hào)。五、綜合題(本大題共3小題，第24題10分，第25題15分，第26題20分。共45分)24．文法G[S]：SABAA0／1BB燈／Sl請(qǐng)給出句子101001的最左和最右推導(dǎo)。25．將下圖1的DFAM最小化。26．設(shè)有文法G[S]為：Sa／b／(A)ASdA／S(1)完成下列算符優(yōu)先關(guān)系表，見表1，并判斷G[S]是否為算符優(yōu)先文法。表1算符優(yōu)先關(guān)系表ab()d#a>>b>>(<<<=)>>#<<<#(2)給出句型(SdSdS)的短語、簡(jiǎn)單短語、句柄和最左素短語。[提示：“(”和“)”也是終結(jié)符](3)給出輸人串(adb)#的分析過程。

2010年1月高等教育自學(xué)考試福建省統(tǒng)一命題考試編譯原理試卷(課程代碼07016)一、判斷題(本大題共20小題,每小題1分,共20分)判斷下列各題是否正確。正確的打“√”，錯(cuò)誤的打“×”。1.實(shí)用文法中不得含有形如U->U的有害規(guī)則，也不得含有由不可達(dá)或不可終止的非終結(jié)符所構(gòu)成的多余規(guī)則?！尽?．一個(gè)句型的最左直接短語稱為最左素短語。【】3.編譯程序是一種語官翻譯程序．它將源程序翻譯成功能等價(jià)的目標(biāo)程序?！尽?．正則文法一定是上下文無關(guān)文法。【】5．每個(gè)文法都能改寫為LL(1)文法?！尽?．一個(gè)NFA一定是DFA，反之也成立?！尽?．局部?jī)?yōu)化是基本塊范圍內(nèi)進(jìn)行的一種優(yōu)化?！尽?．算術(shù)表達(dá)式是LR(0)文法。【】9.不同語義的標(biāo)識(shí)符屬性不盡相同，但符號(hào)名、符號(hào)類型、符號(hào)的存儲(chǔ)類別、符號(hào)的作用域及可視性等屬性是各種標(biāo)識(shí)符都需要的通用屬性?！尽?0.假設(shè)現(xiàn)有五元組表示的有窮自動(dòng)機(jī)M=(K，V，F(xiàn)，S，Z)，若M是NFA，則S表示初態(tài)，且S具有唯一性，它是狀態(tài)集K的一個(gè)元素?！尽?1．目標(biāo)程序運(yùn)行時(shí)的動(dòng)態(tài)數(shù)據(jù)存儲(chǔ)區(qū)分為堆區(qū)和棧區(qū)，它用于存放可變數(shù)據(jù)以及管理過程活動(dòng)的控制信息?！尽?2.僅考慮一個(gè)基本塊，不能確定一個(gè)賦值是否真是無用的?！尽?3.逆波蘭式又稱為四元式，它是一種普遍使用的中間代碼形式，它的四個(gè)組成部分是算符、兩個(gè)運(yùn)算對(duì)象和結(jié)果?！尽?4.數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。【】15.對(duì)于數(shù)據(jù)空間的存貯分，F(xiàn)ORTRAN采用動(dòng)態(tài)貯存分配策略?！尽?6.優(yōu)化實(shí)質(zhì)上是對(duì)代碼進(jìn)行等價(jià)變換，使得變換后的代碼運(yùn)行結(jié)果與變換前的代碼運(yùn)行結(jié)果相同，但運(yùn)行速度或占用的存儲(chǔ)空間加大?！尽?7.若文法c所產(chǎn)生的每一句子都有不同的語法樹，則該文法具有二義性?！尽?8.YACC是一個(gè)用于構(gòu)造各種各樣語言的詞法分析程辱；LEX是一個(gè)用于構(gòu)造各種各樣語言的語法分析程序。【】19.符號(hào)表用來存放語言程序中出現(xiàn)的有關(guān)標(biāo)識(shí)符的屬性信息，這些信息集中反映了標(biāo)識(shí)符的語義特征屬性。【】20．從磁盤中讀取信息，必須以扇區(qū)為單位，即使只讀一個(gè)字節(jié)也這樣?！尽慷?、填空題(本大題共10小題,每小題2分,共20分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。21.所謂2型文法就是指_____文法，若用G=(VN，VT，P，S)表示它，則它要求G中的所有規(guī)則α—>β都滿足：α是_____，而β屬于(VNUVT)*。22．對(duì)一個(gè)文法G，在其LR(0)項(xiàng)目集規(guī)范族DFA中，當(dāng)有歸約項(xiàng)目和____項(xiàng)目或____項(xiàng)目共存于同一個(gè)狀態(tài)中時(shí)，該文法就不是LR(0)文法。23.語法分析方法分為自頂向下與自底向上兩類，自頂向下的分析方法主要有____和____。24.一般，符號(hào)表的每一項(xiàng)都由兩個(gè)欄目組成：第一欄為____、第二欄為____25.動(dòng)態(tài)分配有兩種方案：_____和_____，前者較好地解決了程序運(yùn)行時(shí)動(dòng)態(tài)申請(qǐng)存儲(chǔ)空間等問題。26．當(dāng)一個(gè)過程調(diào)用其他過程時(shí)，調(diào)用過程和被調(diào)用過程之間的通信經(jīng)由非局部變量或者經(jīng)由參數(shù)傳遞，常用的參數(shù)傳遞方式有_____、______等。27.在用五元組表示的確定的有窮自動(dòng)機(jī)DFAM=(K，V，F(xiàn)，S，Z)中，元素V表示字母表：元素S表示唯一的初態(tài)，它是狀態(tài)集K的一個(gè)元索；元索F表示____；元素Z表示終態(tài)集，它是狀態(tài)集K的一個(gè)_____。28.在編譯程序中符號(hào)表用來存放語言程序中出現(xiàn)的有關(guān)標(biāo)識(shí)符的屬性信息，這些信息集中反映了標(biāo)識(shí)符的語義特征屬性。符號(hào)表的功能可以歸結(jié)為三個(gè)主要方面，即收集符號(hào)屬性、作為_____的依據(jù)和作為_____的依據(jù)。29.將非LL(1)文法轉(zhuǎn)換為等價(jià)的LL(1)文法所采用的兩種方法是_____和_____。但這兩種方法并不能保證所有的非LL(1)文法都能轉(zhuǎn)換為等價(jià)的LL(1)文法．30.編譯程序的邏輯結(jié)構(gòu)是以_____為中心的。常常將編譯過程的各階段劃分為前段和后端,代碼優(yōu)化部分屬于______。三、計(jì)算題(本大題共6小題，第31、32小題各6分，第33小題7分，第34、35小題各10分，第36小題9分，共48分)31．寫出能產(chǎn)生字母表{x，yl上的不含兩個(gè)相鄰的x，且不含兩個(gè)相鄰的y的全體符號(hào)串的有限狀態(tài)自動(dòng)機(jī)。(6分)32．試分別構(gòu)造產(chǎn)生下劌語言的文法。(6分)(1)｛anbmcp|n,m,p≥0｝；(2){w#wr#|w∈｛0，1｝}*，wr是將w中的符號(hào)按逆序排列所得的符號(hào)串}；(3)所有由偶數(shù)個(gè)0和偶數(shù)個(gè)l所組成的符號(hào)串的集合。33．證明：文法：(7分)S->ABS->DCA->aAA->aB->bBcB->bcC->cCC->cD->aDbD->ab為二義性文法。34．已知G[S]：(10分)S->(A)|a|bA->A，S|S(1)給出(a，(b，b))的最左推導(dǎo)；(2)P判斷該文法是否為LL(1)文法。若是，直接給出它的預(yù)測(cè)分析表；若不是，先將其改寫為LL(1)文法，再給出它的預(yù)測(cè)分析表。35．現(xiàn)有文法G[S]：(共10分)S—>SS*S—>SS+S—>a(1)證明aa+a*是文法的一個(gè)句子；(2)構(gòu)造句型aa+a*的語法推導(dǎo)樹；(3)指出該句型所有短語、直接短語和句柄。36.設(shè)有算術(shù)表達(dá)式a+b*c一(c*b+a—e)，(9分)(1)寫出該表達(dá)式的四元組中間代碼：(2)把上述四元組中間代碼理解成一個(gè)基本塊，構(gòu)造該基本塊所對(duì)應(yīng)的DAG圖。四、簡(jiǎn)答題(本大題共2小題，每小題6分,共12分)37.簡(jiǎn)述對(duì)任意給定的一個(gè)上下文無關(guān)文法G[S]，如何判斷G[S]是否為LR(0)文法。38．簡(jiǎn)述運(yùn)行時(shí)內(nèi)存被劃分為哪幾個(gè)部分以及各自的作用。2012年1月高等教育自學(xué)考試福建省統(tǒng)一命題考試編譯原理試題課程代碼：07016考生答題注意事項(xiàng)：本卷所有試卷必須在答題卡上作答。答在試卷和草稿紙上的無效。第一部分為選擇題。必須對(duì)應(yīng)試卷上的題號(hào)使用2B鉛筆將“答題卡”的相應(yīng)代碼涂黑。第二部分為非選擇題。必須注明大、小題號(hào)，使用0.5毫米黑色字跡筆作答。合理安排答題空間，超出答題區(qū)域無效。第一部分選擇題一、判斷選擇題(本大題共20小題，每小題1分，共20分)判斷正誤，正確的將答題卡上該小題的“[A]”涂黑，錯(cuò)誤的將“[B]”涂黑。1．算術(shù)表達(dá)式不是LR(0)文法。2．可歸前綴本身就是活前綴，它是包含句柄在內(nèi)的活前綴。3．所謂正則或產(chǎn)生式是指形如α→β或α::=β的(α,β)有序?qū)?，其中α是字母表V的正閉包元素，而β是字母表V的閉包元素。4．編譯階段按前后端組合，可分為編譯前端和編譯后端，其中與目標(biāo)機(jī)有關(guān)的階段一般屬于前端，而與源語言相關(guān)的階段一般屬于后端。5．一個(gè)句型的最右直接短語被稱為句型的句柄。6．遍指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次。7．整數(shù)集A上的小于等于關(guān)系是傳遞的，既不自反也不對(duì)稱。8．已存在這樣一種算法，它能在有限步內(nèi)證明任意給定的一個(gè)文法是否為二義性的。9．描述一個(gè)語言的文法是不唯一的。10．算符優(yōu)先關(guān)系表一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。11．最適合動(dòng)態(tài)建立數(shù)據(jù)實(shí)體的內(nèi)存分配方式是堆式分配策略。12．算符優(yōu)先分析方法和LR分析方法都是自下而上的分析方法，它們的分析過程實(shí)際上就是規(guī)范歸約過程。13．語法制導(dǎo)翻譯是指根據(jù)文法中的每個(gè)規(guī)則所對(duì)應(yīng)的語義子程序或語法規(guī)則所描述的語義動(dòng)作進(jìn)行翻譯的辦法。14．如果某一個(gè)文法所產(chǎn)生的句子有多個(gè)不同的語法樹，則此文法沒有二義性。15．逆波蘭式又稱為四元式，它是一種普遍使用的中間代碼形式，它的四個(gè)組成部分是算符、兩個(gè)運(yùn)算對(duì)象和結(jié)果。16．符號(hào)表用來存放語言程序中出現(xiàn)的有關(guān)標(biāo)識(shí)符的屬性信息，這些信息集中反映了標(biāo)識(shí)符的語義特征屬性。17．?dāng)?shù)據(jù)空間的使用和管理方法分為三種，即：靜態(tài)存儲(chǔ)分配、動(dòng)態(tài)存儲(chǔ)分配、靜態(tài)與動(dòng)態(tài)相結(jié)合的存儲(chǔ)分配。18．自底向上語法分析過程采用的是最右規(guī)約，句柄一旦形成必出現(xiàn)在棧頂。19．狀態(tài)轉(zhuǎn)換圖是設(shè)計(jì)和實(shí)現(xiàn)詞法分析程序的一種有效工具。20．功能上，程序語言的語句大體可分為執(zhí)行性語句和說明性語句兩大類。第二部分非選擇題二、填空題(本大題共20空，每空1分，共20分)請(qǐng)?jiān)诖痤}卡上作答。21．編譯方式在計(jì)算機(jī)上執(zhí)行高級(jí)語言編寫的程序，一般分成兩個(gè)階段：第一階段是編譯階段，其任務(wù)是________；第二階段是________，其任務(wù)是目標(biāo)計(jì)算機(jī)上執(zhí)行第一階段所得到的目標(biāo)程序。22．屬于綜合部分的代碼優(yōu)化和目標(biāo)代碼生成，一般只依賴于________，通常稱之為編譯程序的__________。23．YACC是一種__________的自動(dòng)構(gòu)造工具，而LEX是一種__________的自動(dòng)構(gòu)造工具。24．動(dòng)態(tài)分配有兩種方案：________和________，后者較好地解決了程序運(yùn)行時(shí)動(dòng)態(tài)申請(qǐng)存儲(chǔ)空間等問題。25．對(duì)給定文法G[E]，由推導(dǎo)序列E=>E+T=>T+T=>i+T=>i+i可知：該推導(dǎo)為__________推導(dǎo)，其中的__________同時(shí)也是句子。26．語法分析方法分為自頂向下與自底向上兩類，而自底向上的分析方法主要有__________和__________。27．將非LL(1)文法轉(zhuǎn)換為等價(jià)的LL(1)文法所采用的兩種方法是_________和__________。但這兩種方法并不能保證所有的非LL(1)文法都能轉(zhuǎn)換為等價(jià)的LL(1)文法。28．在編譯程序中符號(hào)表的功能可以歸結(jié)為三個(gè)主要方面，即______、作為上下文語義合法性檢查的依據(jù)和作為__________的依據(jù)。29．對(duì)一個(gè)文法G，在其LR(0)項(xiàng)目集規(guī)范族DFA中，當(dāng)有歸約項(xiàng)目和__________項(xiàng)目或__________項(xiàng)目共存于同一個(gè)狀態(tài)中時(shí)，該文法就不是LR(0)文法。30．設(shè)計(jì)和實(shí)現(xiàn)詞法分析程序的一種有效工具是__________，它是__________的直觀圖示。三、計(jì)算題(本大題共6小題，第31、33小題每小題8分，第32、35小題每小題6分，第34、36小題每小題10分，共48分)請(qǐng)?jiān)诖痤}卡上作答。31．設(shè)有文法G1[<S>]：<S>→<N><N>→<D>|<N><D><D→0|1|2|…|9試寫出4321的最左推導(dǎo)和最右推導(dǎo)過程。32．試分別構(gòu)造產(chǎn)生下列語言的文法。(1){anbn|n≥0}；(2){an#bn|n≥O}∪{cn#dn|n≥O}；(3)任何不是以O(shè)開始的所有奇整數(shù)所組成的集合。33．試寫出VT={0，1}上下述集合的正則表達(dá)式。(1)所有以1開始和結(jié)束的符號(hào)串；(2)恰含有3個(gè)1的所有符號(hào)所組成的集合；(3)集合{01，1}；(4)所有以111結(jié)束的符號(hào)串。34．現(xiàn)有文法G[E]：E→E+T|E-T|TT→T*F|T/F|FF→i|(E)(1)證明：E-F*(i)是文法的一個(gè)句型；(2)構(gòu)造句型E-F*(i)的語法推導(dǎo)樹；(3)指出該句型所有短語、直接短語和句柄。35．考察下面程序段：procedurep(x，y，z)beginy：=y+1；z：=z+x；end；begina：=2；b：=3；p(a+b，a，a)；write(a)；end；若參數(shù)通信是按名和按值兩種方式，上述程序執(zhí)行后，輸出a的值分別是多少?36．已知G[S]：S→b|+|(T)1→T，S|S(1)給出(+，(b，+))的最左推導(dǎo)；(2)證明G[S]不是LL(1)文法；(3)將G[S]改寫為LL(1)文法，再給出它的預(yù)測(cè)分析表。四、簡(jiǎn)答題(本大題共2小題，每小題6分，共12分)請(qǐng)?jiān)诖痤}卡上作答。37．簡(jiǎn)述一個(gè)典型的編譯系統(tǒng)的組成部分及各部分的主要功能。38．對(duì)任意給定的一個(gè)上下文無關(guān)文法G[S]，如何判斷G[S]是否為SLR(1)文法?

2013年10月高等教育自學(xué)考試福建省統(tǒng)一命題考試編譯原理試卷（課程代碼07016）本試卷滿分100分，考試時(shí)間150分鐘?？忌痤}注意事項(xiàng)：1．本卷所有試題必須在答題卡上作答。答在試卷上無效，試卷空白處和背面均可作草稿紙。2．第一部分為選擇題。必須對(duì)應(yīng)試卷上的題號(hào)使用2B鉛筆將“答題卡”的相應(yīng)代碼涂黑。3．第二部分為非選擇題。必須注明大、小題號(hào)，使用0.5毫米黑色字跡簽字筆作答。4．合理安排答題空間，超出答題區(qū)域無效。第一部分選擇題一、單項(xiàng)選擇題（本大題共10小題，每小題2分，共20分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其選出并將“答題卡”的相應(yīng)代碼涂黑。未涂、錯(cuò)涂或多涂均無分。1．構(gòu)造編譯程序應(yīng)掌握A．源程序B．目標(biāo)語言C．編譯方法D．以上三項(xiàng)都是2．編譯程序絕大多數(shù)時(shí)間花在____上。A．出錯(cuò)處理B．詞法分析C．目標(biāo)代碼生成D．表格管理3．詞法分析器的輸出結(jié)果是A．單詞的種別編碼B．單詞在符號(hào)表中的位置C．單詞的種別編碼和自身值D．單詞自身值4．正規(guī)式M1和M2等價(jià)是指A．MI和M2的狀態(tài)數(shù)相等B．M1和M2的有向邊條數(shù)相等C．M1和M2所識(shí)別的語言集相等D．M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等5．DFAM(見題5圖)接受的字集是B．以o開頭的二進(jìn)制數(shù)組成的集合B．以0結(jié)尾的二進(jìn)制數(shù)組成的集合C．含奇數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合D．含偶數(shù)個(gè)O的二進(jìn)制數(shù)組成的集合6．詞法分析器作為獨(dú)立的階段使整個(gè)編譯程序結(jié)構(gòu)更加簡(jiǎn)潔、明確，因此A．詞法分析器應(yīng)作為獨(dú)立的一遍B．詞法分析器作為子程序較好C．詞法分析器分解為多個(gè)過程，由語法分析器選擇使用D．詞法分析器并不作為一個(gè)獨(dú)立的階段7．按喬姆斯基分類，文法G[S]：S-→dAA→aAIAbB→bIBb至多屬于____型文法。A．O型文法B．1型文法C．2型文法D．3型文法8．下列哪些屬于代碼優(yōu)化的基本方法？A．代碼削弱B．合并已知變量C．代碼增強(qiáng)D．代碼重用9．下列哪項(xiàng)是代碼優(yōu)化必須遵守的原則？A．代碼最短原則B．代碼重用原則C．等價(jià)原則D．開放原則10.下列哪項(xiàng)不屬于編譯程序中符號(hào)表構(gòu)造和處理方法？A．雙向查找B．二叉樹C．線性查找D．雜湊技術(shù)二、判斷選擇題（本大題共15小題，每小題1分，共15分）判斷下列每小題的正誤，正確的將答題卡上該小題的“[A]”涂黑，錯(cuò)誤的將“[B]”涂黑。11.編譯程序生成的目標(biāo)程序是機(jī)器語言程序。12.∑上的一個(gè)符號(hào)串集V∈∑?是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè)在∑機(jī)N，使得V=L(N)。13．有窮自動(dòng)機(jī)只有一個(gè)初態(tài)。14.一個(gè)文法所有句型的結(jié)合構(gòu)成該文法所接受的語言。15.無論是一遍掃描的編譯器還是多遍掃描的編譯器都要對(duì)源程序掃描一遍。16.所有的LL(k)文法都不是二義性的。17.文法的預(yù)測(cè)分析表中的列標(biāo)題中不包含ε。18.使用優(yōu)先函數(shù)進(jìn)行分析是因?yàn)閮?yōu)先表和優(yōu)先函數(shù)完全等價(jià)。19.一個(gè)算符優(yōu)先文法有且僅有一對(duì)優(yōu)先函數(shù)與之對(duì)應(yīng)。20.LL(k)文法都是無二義性的。21．語法制導(dǎo)的翻譯方法只限于自底向上的分析方法。22．逆波蘭表示法表示表達(dá)式時(shí)無須使用括號(hào)。23．符號(hào)表由詞法分析程序建立，由語法分析程序使用。24.在編譯的各個(gè)階段都要涉及到符號(hào)表的操作。25.使用語法制導(dǎo)翻譯方法的編譯程序能同時(shí)進(jìn)行語法分析和語義分析。2014年10月高等教育自學(xué)考試福建省統(tǒng)一命題考試編譯原理試卷(課程代碼07016)本試卷滿分100分。考試時(shí)間l50分鐘?？忌痤}注意事項(xiàng)：1．本卷所有試題必須在答題卡上作答。答在試卷上無效。試卷空白處和背面均可作草稿紙。2．第一部分為選擇題。必須對(duì)應(yīng)試卷上的題號(hào)使用2B鉛筆將“答題卡”的相應(yīng)代碼涂黑。3。第二部分為非選擇題。必須注明大、小題號(hào)，使用0．5毫米黑色字跡簽字筆作答。4．合理安排答題空間。超出答題區(qū)域無效。第一部分選擇題一、單項(xiàng)選擇題(本大題共l0小題。每小題2分，共20分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其選出并將“答題卡”的相應(yīng)代碼涂黑。未涂、錯(cuò)涂或多涂均無分.1．編譯程序是對(duì)A．匯編程序的翻譯B．高級(jí)語言程序的解釋執(zhí)行C．機(jī)器語言的執(zhí)行D．高級(jí)語言的翻譯2.下列選項(xiàng)中不可能是目標(biāo)代碼的是A．匯編指令代碼B．中間代碼C．可重定位代碼D．絕對(duì)指令代碼3．詞法分析器的輸出結(jié)果是A．單詞的種別編碼B．單詞在符號(hào)表中的位置C．單詞的種別編碼和自身值D.單詞自身值4．下列選項(xiàng)中不是DFA的成分的是A．有窮字母表B．初始狀態(tài)集合C．終止?fàn)顟B(tài)集合D.有限狀態(tài)集合5．程序語言的生成機(jī)構(gòu)是A．自動(dòng)機(jī)B．文法C．產(chǎn)生式D．語言本身6．若一個(gè)文法是遞歸的，則它產(chǎn)生語言的句子個(gè)數(shù)A．必定是無窮的B．根據(jù)情況而定C．是有窮個(gè)D．有窮個(gè)，但是個(gè)數(shù)很大7．按喬姆斯基分類，文法至多屬于A.0型文法B．1型文法C．2型文法D.3型文法8.編譯程序中符號(hào)表的主要作用是A．用來查證編譯過程的標(biāo)識(shí)符屬性B．用來產(chǎn)生編譯過程的語法樹C.用來查證編譯過程的中間結(jié)果D．用來識(shí)別編譯過程出現(xiàn)的錯(cuò)誤信息9.下列選項(xiàng)屬于代碼優(yōu)化的基本方法的是A．復(fù)寫傳播B．代碼削弱C．強(qiáng)度增強(qiáng)D．代碼重用10．下列選項(xiàng)不屬于代碼優(yōu)化的基本方法的是A．合并已知變量B．強(qiáng)度削弱C．代碼重用D.復(fù)寫傳播二、判斷選擇題(本大題共l5小題，每小題l分，共l5分)判斷下列每小題的正誤，正確的將答題卡上該小題的“[A]”涂黑，錯(cuò)誤的將“[B]”涂黑。11.無論是一遍掃描的編譯器還是多遍掃描的編譯器都要對(duì)源程序掃描一遍。12.解釋程序和編譯程序的區(qū)別在于是否生成目標(biāo)代碼程序。13．上下文無關(guān)文法的開始符號(hào)可以是終結(jié)符或非終結(jié)符。14．1型文法對(duì)規(guī)則的限制比2型文法對(duì)規(guī)則的限制要多一些。15．與某一個(gè)NFA對(duì)應(yīng)的DFA是唯一的。16．LL(1)文法一定不含左遞歸和二義性。17.不含左遞歸和左公因子的文法一定是LL(1)文法。18.一個(gè)算符優(yōu)先文法有且僅有一對(duì)優(yōu)先函數(shù)與之對(duì)應(yīng)。19.算符優(yōu)先分析法采用移進(jìn)-歸約技術(shù)，其歸約過程是規(guī)范的。20．LR方法不一定是最左歸約。21．非終結(jié)符可以有綜合屬性，但不能有繼承屬性。22.語法制導(dǎo)翻譯方法可用來產(chǎn)生各種中間代碼，但不能用來產(chǎn)生目標(biāo)代碼J23．循環(huán)中的無用賦值在循環(huán)優(yōu)化時(shí)均可刪除。24．一個(gè)程序可用一個(gè)流圖來表示。25．優(yōu)化工作只能在中間代碼這一層次上進(jìn)行。第二部分非選擇題三、計(jì)算題(本大題共6小題，第26、27、29小題各12分，第28小題l3分，第30題6分，第31小題l0分，共65分)請(qǐng)?jiān)诖痤}卡上作答。26．設(shè)有文法(1)填寫所有非終結(jié)符的First集和Follow集。(8分)(2)填寫如下LL(1)分析表。(4分)27．設(shè)有文法(1)填寫所有非終結(jié)符的FkstVT集和LastVT集。(3分)(2)填寫所有終結(jié)符的優(yōu)先關(guān)系。(9分)28．設(shè)有文法：(1)補(bǔ)充完整如下LR(0)的項(xiàng)目集及狀態(tài)轉(zhuǎn)換圖。(8分)(2)填寫如下LR(O)分析表。(5分)29．設(shè)有正規(guī)式(1)請(qǐng)?zhí)顚懭缦翹FA中各結(jié)點(diǎn)間的狀態(tài)轉(zhuǎn)換標(biāo)記字母。(4分)(2)填寫將其確定化過程中的狀態(tài)轉(zhuǎn)換矩陣。(6分)(3)畫出其確定化后的狀態(tài)轉(zhuǎn)換圖。(2分)30.給出下列賦值語句所產(chǎn)生的三址代碼31.設(shè)有文法及其翻譯方案：請(qǐng)給出對(duì)應(yīng)于輸入符號(hào)串bcccaadadadb的語義動(dòng)作的輸出。2015年10月高等教育自學(xué)考試福建省統(tǒng)一命題考試編譯原理試卷(課程代碼07016)本試卷滿分100分，考試時(shí)間l50分鐘?？忌痤}注意事項(xiàng)：1．本卷所有試題必須在答題卡上作答。答在試卷上無效，試卷空白處和背面均可作草稿紙.2．第一部分為選擇題。必須對(duì)應(yīng)試卷上的題號(hào)使用2B鉛筆將“答題卡”的相應(yīng)代碼涂黑。3．第二部分為非選擇題。必須注明大、小題號(hào)，使用0．5毫米黑色字跡簽字筆作答。4．合理安排答題空間，超出答題區(qū)域無效。第一部分選擇題一、單項(xiàng)選擇題(本大題共9小題，每小題2分，共18分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的。請(qǐng)將其選出并將“答題卡”的相應(yīng)代碼涂黑。未涂、錯(cuò)涂或多涂均無分。1．編譯程序是對(duì)A．匯編程序的翻譯B．高級(jí)語言程序的解釋執(zhí)行C．機(jī)器語言的執(zhí)行D．高級(jí)語言的翻譯2．把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由___________完成的。A．編譯器B．匯編器C．解釋器D．預(yù)處理器3．正規(guī)式M1和M2等價(jià)是指A．M1和M2的狀態(tài)數(shù)相等B．M1和M2的有向弧條數(shù)相等C．M1和M2所識(shí)別的語言值相等D．M1和M2狀態(tài)數(shù)和有向弧條數(shù)相等4．______不是DFA的成分。A．有窮字母表B．初始狀態(tài)集合C．終止?fàn)顟B(tài)集合D．有限狀態(tài)集合5．______這樣一些語言它們能被確定的有窮自動(dòng)機(jī)識(shí)別，但不能用正規(guī)表達(dá)式表示。A．不存在B．存在C．無法判斷是否存在D．以上都不對(duì)6．按喬姆斯基分類，文法G[s]：S→asb∣ab至多屬于A．0型文法B．1型文法C．2型文法D．3型文法7．編譯程序中符號(hào)表的主要作用是A．用來存儲(chǔ)和查找編譯過程的語法樹B．用來查證編譯過程的標(biāo)識(shí)符C．用來查證編譯過程的中間結(jié)果D．用來識(shí)別編譯過程出現(xiàn)的錯(cuò)誤信息8．下列哪個(gè)不屬于代碼優(yōu)化的基本方法?A．合并已知變量B．強(qiáng)度削弱C．代碼重用D．復(fù)寫傳播9．下列哪個(gè)屬于代碼優(yōu)化的基本方法?A．代碼削弱B．強(qiáng)度削弱C．代碼增強(qiáng)D．代碼重用二、判斷選擇題(本大題共14小題，每小題1分，共14分)判斷下列每小題的正誤，正確的將答題卡上該小題的“[A]”涂黑，錯(cuò)誤的將“[B]”涂黑。10．用高級(jí)語言書寫的源程序都必須通過編譯，產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行。11．所有的LL(k)文法都不是二義性的。12．對(duì)任一個(gè)正規(guī)式r，都存在一個(gè)NFAM，使得L(M)=L(r)。13．與某一個(gè)NFA對(duì)應(yīng)的DFA是唯一的。14．接受L的最小狀態(tài)有窮自動(dòng)機(jī)不計(jì)同構(gòu)是唯一的。15．目標(biāo)程序一定是機(jī)器語言程序。16．語法分析時(shí)必須先消除文法中的左遞歸。17．若一個(gè)句型中出現(xiàn)了某一規(guī)則的右部，則此右部一定是該句型的句柄。18．任何一個(gè)句型都有最左最右推導(dǎo)。19．活前綴是指規(guī)范句型的一個(gè)前綴，它不包含該句型句柄右邊的任何符號(hào)。20．對(duì)任何一個(gè)編譯程序而言，中間代碼階段是必不可少的。21．終結(jié)符只有繼承屬性，它們由詞法分析器提供。22．非終結(jié)符只有綜合屬性，它們由詞法分析器提供。23．在編譯階段只對(duì)可執(zhí)行語句進(jìn)行翻譯。第二部分非選擇題三、計(jì)算題(本大題共6小題。第24、25、27小題各12分，第26小題13分。第28小題7分，第29小題12分，共68分)請(qǐng)?jiān)诖痤}卡上作答。24．設(shè)有文法G[S]：26.設(shè)有文法：(O)S’→S(1)S→aSb(2)S→aSc(3)S→ab(1)補(bǔ)充完整如下LR(O)的項(xiàng)目集及狀態(tài)轉(zhuǎn)換圖。28．將下列語句翻譯成逆波蘭表達(dá)式、三元式-(a+b)*(c—d)／e+(a—b)／(c+d)29．設(shè)有文法及其翻譯方案如下：該文法針對(duì)輸入符號(hào)串a(chǎn)abbb的LR歸約過程如下：假設(shè)歸約過程中，每使用到一個(gè)產(chǎn)生式就立即執(zhí)行括號(hào)中相應(yīng)的語義動(dòng)作。試問完成上述歸約過程后．輸出的字符串是_______。2018年10月高等教育自學(xué)考試福建省統(tǒng)一命題考試編譯原理試卷(課程代碼07016)本試卷滿分100分，考試時(shí)間l50分鐘?？忌痤}注意事項(xiàng)：1．本卷所有試題必須在答題卡上作答。答在試卷上無效，試卷空白處和背面均可作草稿紙。2．第一部分為選擇題。必須對(duì)應(yīng)試卷上的題號(hào)使用2B鉛筆將“答題卡”的相應(yīng)