編譯原理習(xí)題1

※<習(xí)題一>填空題：1、編譯階段按前后端組合，可分為編譯前端和編譯后端，其中與目標(biāo)機有關(guān)的階段一般屬于分析階段，而與源語言相關(guān)的階段一般屬于綜合階段。2、設(shè)文法G=（VN，VT，P，S），若P中的每一個規(guī)則A→β滿足：A∈VN，β∈(VN∪VT)*,則稱此文法為0型文法。3、已知M為一個確定的有窮自動機，M=（Q，∑，q0，F(xiàn)，δ），則Q表示一個有窮的狀態(tài)集合;∑表示字母表，δ表示狀態(tài)轉(zhuǎn)換函數(shù)，q0是唯一的初始狀態(tài)。4、規(guī)范推導(dǎo)是指最右推導(dǎo)，每步推導(dǎo)只變換符號串中最右邊的非終結(jié)符，其逆過程即最左規(guī)約，稱為規(guī)范歸約。5、LR(0)項目集規(guī)范族中的項目可分為四類，即移進項目、待約項目、歸約項目和接受項目，其中歸約項目和歸約項目或移進項目共存于一個項目集中會引起沖突。6、表達(dá)式s:=a+b*c/d+(b-d)的逆波蘭式表示為sabc*d/bd-++:=。判斷題：1、從功能上看，一個編譯程序就是一個語言翻譯程序。T 2、ＬＥＸ是一個語法分析程序的生成系統(tǒng)。F 3、一個句型的最左（直接）簡單短語稱為句柄。T 4、已證明文法的二義性是可判定的。F 5、一個ＮＦＡ一定能轉(zhuǎn)換為ＤＦＡ。T 6、遞歸下降分析法是一種不確定的自頂向下分析法。F簡答：1、文法Ｇ是LL(1)文法的充要條件是什么？答：（1）.不能有左遞歸；（2）.LL(1)文法的分析表不出現(xiàn)多重定義即：對于文法G的每個非終結(jié)符A的任何兩條不同規(guī)則A→α|β，下面條件成立：?FIRST(α)∩FIRST(β)=φ即頭符號集不相交。?假若β==*>ε，那么，F(xiàn)IRST(α)∩FOLLOW(A)=φ，即α所能推出的符號串的頭符號集中的元素不能出現(xiàn)在FOLLOW(A)中。2、將表達(dá)式A:=B*（C-D）/D：翻譯成波蘭后綴表達(dá)式。答：ABCD-D/*:=※<習(xí)題二>填空題：1、對給定文法G[E]，由推導(dǎo)序列E=>E+T=>T+T=>i+T=>i+i可知：該推導(dǎo)為（最左）推導(dǎo)，從該推導(dǎo)序列可得到（5）個句型，其中的（i+i）同時也是句子。2、用四元組G=（VN，VT，P，S）表示文法，則其元素VN表示（非終結(jié)符）集；元素VT表示（終結(jié)符）集；元素P表示規(guī)則集；元素S表示開始符號，它必須是一個（至少在某個產(chǎn)生式的左部出現(xiàn)一次的非終結(jié)符）符號。3、YACC是一種（語法）分析程序的自動構(gòu)造工具；而LEX是一種（詞法）分析程序的自動構(gòu)造工具。4、對一個文法G，在其LR(0)項目集規(guī)范族DFA中，當(dāng)有歸約項目和（規(guī)約）項目或（移進）項目共存于同一個狀態(tài)中時，該文法就不是LR(0)文法。5、編譯程序是一種語言翻譯程序，它將源語言程序翻譯成功能等價的（目標(biāo)語言程序）。6、所謂規(guī)則或產(chǎn)生式是指形如α→β或α::=β的(α,β)有序?qū)?，其中α是字母表V的（正閉包元素）,而β是字母表V的（閉包元素）。7、設(shè)文法G=（VN，VT，P，S），若P中的每一個規(guī)則都是A→aB或A→a，其中A和B是非終結(jié)符，而a是終結(jié)符，則稱此文法G為正規(guī)文法或（3）型文法。8、實用文法中不得含有形如U→U的（有害規(guī)則），也不得含有由不可達(dá)或不可終止的非終結(jié)符所構(gòu)成的（多余規(guī)則）。9、對任意給定的一個正則表達(dá)式R，都可以將它轉(zhuǎn)換為與之功能等價的（正則）文法，或與之功能等價的（有窮自動機）。判斷題：

1、在語法分析過程中，隨著分析的步步進展，根據(jù)每個規(guī)則所對應(yīng)的語義子程序或語義動作進行翻譯的辦法，稱為語法制導(dǎo)翻譯，它被現(xiàn)代很多編譯程序所采用。T2、可歸前綴本身就是活前綴，它是包含句柄在內(nèi)的活前綴。T簡答：一、現(xiàn)有文法G[E]：E→EE+E→EE*E→FF→i1、證明ii*i+是文法的一個句子。2、構(gòu)造句型ii*i+的語法推導(dǎo)樹。3、指出該句型所有短語、簡單短語和句柄。答：1、因為存在一個最左推導(dǎo)過程：E→EE+→FE+→FE+→iE+→iE*E+→iF*E+→ii*E+→ii*F+→ii*i+并且，ii*i+只含有終結(jié)符。2、E+EE+EFiEEE*FFEii簡單短語：i*＋句柄：i二、現(xiàn)有文法G[E]：E→E+T|E-T|TT→T*F|T/F|FF→i|(E)1、證明：F+T*(E)是文法的一個句型。2、構(gòu)造句型F+T*(E)的語法推導(dǎo)樹。3、指出該句型所有短語、直接短語和句柄。答：1、因為存在這樣的一個推導(dǎo)過程：E→E+T→T+T→F+T→F+T*F→F+T*(E)2、EEE+TTFT*FT（E）T3、短語：F+T*(E)T*(E)(E)簡單短語：(E)句柄：(E)※<習(xí)題三>填空題：1、在語法分析過程中，隨著分析的步步進展，根據(jù)每個規(guī)則所對應(yīng)的語義子程序或語義動作進行翻譯的辦法，稱為（語法制導(dǎo)）翻譯方法，它被現(xiàn)代很多編譯程序所采用。2、（YACC）是一種語法分析程序的自動構(gòu)造工具，用它可以直接構(gòu)造各種語言的語法分析器；而（LEX）是一種（詞法分析）程序的自動構(gòu)造工具，用它可以直接構(gòu)造各種語言的詞法分析器。3、所謂2型文法就是指（上下文無關(guān)）文法，若用G=（VN，VT，P，S）表示它，則它要求G中的所有規(guī)則α→β都滿足：α是（Vn），而β屬于（VNUVT）*。4、文法中形如U→U的規(guī)則稱為（有害）規(guī)則；由不可達(dá)的非終結(jié)符或不可終止的非終結(jié)符作為左部的規(guī)則稱為（無用）規(guī)則。在實用文法中一般不允許含有這兩類規(guī)則。6、語法分析方法分為自上而下與自下而上兩類，自上而下的分析方法方要有遞歸子程序分析法和（ll（1））；而自下而上的分析方法主要有（算符優(yōu)先方法）和（LR分析方法）。7、LR(0)項目集規(guī)范族中的項目可分為四類，它們是移進項目、（待約）、歸約項目和接受項目。其中，接受項目是（規(guī)約）的一種特例。8、將非LL(1)文法轉(zhuǎn)換為等價的LL(1)文法所采用的兩種方法是（左遞歸轉(zhuǎn)換為有遞歸）和（提取公因子解決分析表多重定義）。但這兩種方法并不能保證所有的非LL(1)文法都能轉(zhuǎn)換為等價的LL(1)文法。9、編譯階段按前后端組合，可分為編譯前端和編譯后端，其中與目標(biāo)機有關(guān)的階段一般屬于分析階段，而與源語言相關(guān)的階段一般屬于綜合階段0簡答：0求出正規(guī)式a(a|b)*a對應(yīng)的NFA，并將之確定化,如有可能，將其最小化。答：先構(gòu)造等價的NFA如下圖所示：ab01ab0124a3εεaq0=ε-closure({0})={0}δ(q0,a)=ε-closure(δ(0,a))={2,3,4}=q1δ(q1,a)={3.4}=q2δ(q1,b)={3.4}=q2δ(q2,a)={1}=q3bbaaaq0q1q2Qq32※<習(xí)題四>填空題：1、（2）型文法又稱為（上下文無關(guān)）文法，是描述程序設(shè)計語言語法部分的主要文法；高級程序設(shè)計語言的單詞符號，如標(biāo)識符、無符號整數(shù)常用（3）型文法來描述。2、從0型文法到3型文法對規(guī)則的限制逐漸（增加），產(chǎn)生的語言類卻逐步（縮?。：喆穑?/p>

一、現(xiàn)有文法G[S]：S→aBS→BbB→ScB→d1、消除文法G[S]的左遞歸；2、指出消除了左遞歸之后的文法是否是LL(1)文法,為什么?二、已知G[S]：S→b|+|(T)T→T,S|S1、給出(+,(b,+))的最左推導(dǎo)。2、證明G[S]不是LL(1)文法。3、將G[S]改寫為LL(1)文法，再給出它的分析表；4、給出輸入串(b,+)#的分析過程。三、已知G[S]：S→(A)|a|bA→A,S|S1、給出(a,(b,b))的最左推導(dǎo)。2、判斷該文法是否為LL(1)文法。若是，直接給出它的分析表；若不是，先將其改寫為LL(1)文法，再給出它的分析表；3、給出輸入串(b,b)#的分析過程，并說明該串是否為G[S]的句子。四、對給定文法G[S’]:0)S’→S1)S→A2