【文章內(nèi)容簡(jiǎn)介】
提示:不妨以A、B、然后消除B中左遞歸;再將A、B代入C中。再消除C中左遞歸。 最后結(jié)果為:G[A]: A→BaC|CbB B→CbBcB39。|cB39。 B39?!鷄CcB39。|ε C→cB39。bC39。|bC39。 C39?!鷅BcB39。bC39。|ε寫出表達(dá)式a+b*(cd)+e/(cd)*n的三元式序列或P代碼表示。(1)(_,c,d) (2) (*,b,(1)) (3) (+,a,(2)) (4) (_,c,d)(5) (/,e,(4)) (6) (*,n,(5)) (7)(+,(3),(6))什么樣的文法是算符優(yōu)先文法,請(qǐng)舉個(gè)算符優(yōu)先文法的例子。設(shè)文法G,如果它的產(chǎn)生式右部不包含相鄰非終結(jié)符號(hào),則稱文法G為算符文法,如果算符文法的終結(jié)符號(hào)集中任意兩個(gè)符號(hào)之間至多存在一種優(yōu)先關(guān)系,則稱該算符文法為算符優(yōu)先文法。例如:EE+T|T TT*F|F F(E)|i+*()i+*(=)i解釋什么是歸約?我們稱αγβ直接歸約出αAβ,僅當(dāng)A→γ 是一個(gè)產(chǎn)生式, 且α、β∈(VN∪VT)*。歸約過程就是從輸入串開始,反復(fù)用產(chǎn)生式右部的符號(hào)替換成產(chǎn)生式左部符號(hào),直至文法開始符。DFA和NFA有何區(qū)別?DFA和NFA的區(qū)別表現(xiàn)在三個(gè)方面。一是NFA可有若干個(gè)開始狀態(tài),而DFA僅有一個(gè)。二是DFA的映像M是從K╳Σ到K,而的映象M是從K╳Σ到K的子集,即映像M將產(chǎn)生一個(gè)狀態(tài)集合(可能為空集),而不單個(gè)狀態(tài)。三是NFA在沒有掃描輸入符號(hào)的情況下,也可以進(jìn)行空移。已知文法G為:S aAcB|BdA AaB|cB bScA|b寫出句子acabcbbdcc得最左推導(dǎo)及語(yǔ)法樹saAcBaAaBcBaCaBcBacabcBacabcbScAacabcbBCCAacabcbbdcc S a A c B A a B b S c A C b B d b寫出表達(dá)式A=(x+y)*(c+d)+(x+y+c)的四元式序列或P代碼表示。(1)(+,x,y)(2) (+,c,d)(3) (*,(1),(2))(4) (+,x,y)(5) (+,(4),c)(6) (+,(3),(5))語(yǔ)法分析的主要(功能)任務(wù)是什么?有哪二種分析分方法?語(yǔ)法分析的主要任務(wù)是對(duì)詞法分析的輸出結(jié)果單詞序列進(jìn)行分析,識(shí)別合法的 語(yǔ)法單位。若給定的輸入符號(hào)是該文法所產(chǎn)生的語(yǔ)言中的句子,就給出它的語(yǔ)法樹,否則就報(bào)告出錯(cuò)信息。自上而下語(yǔ)法分析和自下而上語(yǔ)法分析。令文法G為S→a|ε|(T)T→T,S|S(1)給出(a,(a,a))的最右推導(dǎo)和最左推導(dǎo)。(2)畫出語(yǔ)法分析樹最左推導(dǎo):S=(T) =(T,S) =(a,S)=(a,(T,S)) =(a,(S,S))=(a,(a,S))=(a,(a,a))最右推導(dǎo):S=(T)=(T,S)=(T,(T))=(T,(T,S)) =(T,(T,a))=(T,(S,a))=(T,(a,a)) =(S,(a,a))=(a,(a,a))寫出表達(dá)式A=(a+b)+(c+d)*(x+y+c)的三元式序列或P代碼表示。(1)(+,a,b)(2) (+,c,d)(3) (+,x,y)(4) (+,(3),c)(5) (*,(2),(4))(6) (+,(1),(5))什么是二義性文法?請(qǐng)舉例說(shuō)明。一個(gè)文法如果它的一個(gè)句子有兩棵或兩棵以上的語(yǔ)法樹,則稱此句子具有二義性,如果一個(gè)文法含有二義性的句子,則稱此文法具有二義性。例: E224。i | (E) | EAE A224。 + | | * | /i+i+i E E E A E E A E E A E t I i t E A E i t i i t i在一個(gè)基本塊內(nèi)通??蓪?shí)現(xiàn)哪些優(yōu)化?①合并已知量 ②刪除公共子表達(dá)式 ③刪除無(wú)用代碼 ④復(fù)寫傳播什么是語(yǔ)法樹?滿足下面4個(gè)條件的樹稱之為文法G[S]的一棵語(yǔ)法樹。①每一終結(jié)均有一標(biāo)記,此標(biāo)記為VN∪VT中的一個(gè)符號(hào);②樹的根結(jié)點(diǎn)以文法G[S]的開始符S標(biāo)記;③若一結(jié)點(diǎn)至少有一個(gè)直接后繼,則此結(jié)點(diǎn)上的標(biāo)記為VN中的一個(gè)符號(hào);④若一個(gè)以A為標(biāo)記的結(jié)點(diǎn)有K個(gè)直接后繼,且按從左至右的順序,這些結(jié)點(diǎn)的標(biāo)記分別為X1,X2,…,Xk,則A→X1,X2,…,Xk, 必然是G的一個(gè)產(chǎn)生式。在編譯過程中為什么要建立符號(hào)表,簡(jiǎn)述符號(hào)表的組織,即它一般分成幾部分,含有那些域?在編譯過程中,始終涉及到對(duì)一些語(yǔ)法符號(hào)的處理,需要用到這些語(yǔ)法符號(hào)的相關(guān)屬性。為了在需要的時(shí)候能找到這些語(yǔ)法成分及其相關(guān)屬性,必須使用一些表格保存這些語(yǔ)法成分及其屬性,這些表格就是符號(hào)表。符號(hào)表應(yīng)包括語(yǔ)法符號(hào)的名字和相關(guān)屬性,不同語(yǔ)法符號(hào)在符號(hào)表中存放的信息不同。符號(hào)表的條目一般由兩部分組成,即名字欄和信息欄。符號(hào)表域包括標(biāo)識(shí)符名、其他信息、地址等。對(duì)名字欄,為節(jié)省空間,可另外設(shè)立一個(gè)存放標(biāo)識(shí)符的字符數(shù)組。對(duì)信息欄中的類型等信息可以用數(shù)值或向量來(lái)表示,以節(jié)省空間1. 對(duì)如下文法:G[S]:S224。abS|aaB|ad B224。bbB|b分別給出句子abaabbb和ad的句柄(6分)句子abaabbb的句柄是b;句子ad的句柄是ad2. 什么是可規(guī)約活前綴?舉一例說(shuō)明。(6分)若活前綴是含句柄的活前綴,即有α =α′π ,且π是句柄,則活前綴α為可歸約活前綴。例S 224。a|bCd C224。 e則be為一個(gè)可歸約活前綴(a+b*c)/(a+b)-d的逆波蘭表示及三元式序列或P代碼。(6分)(1)(*,b,c)(2) (+,a,(1))(3) (+,a,b)(4) (/,(2),(3))(5) (,(4),d),二者有何區(qū)別?(4分)在詞法分析和語(yǔ)法分析中,都是對(duì)輸入符號(hào)串進(jìn)行識(shí)別。但詞法分析的輸入符號(hào)串是一個(gè)單詞,而語(yǔ)法分析的輸入符號(hào)串是一個(gè)句子或者說(shuō)是一個(gè)程序。為了討論方便,我們都是用小寫字母來(lái)表示終結(jié)符號(hào),但一定要明白在詞法分析中小寫字母表示組成單詞的字符,而在語(yǔ)法分析中小寫字母表示組成程序的的一個(gè)單詞,識(shí)別方式來(lái)說(shuō),詞法分析和語(yǔ)法分析都是對(duì)輸入符號(hào)串結(jié)構(gòu)的識(shí)別,但由于單詞和程序的結(jié)構(gòu)有所區(qū)別,所以具體的識(shí)別方式不一樣。[S]為:S→a|^|(T) T→T,S|S判斷該文法是否是算符優(yōu)先文法?如是,請(qǐng)給出算符優(yōu)先關(guān)系表。(8分)(1) FIRSTVT和LASTVT FIRSTVT LASTVT S a、^、( a、^、) T ,、a、^、( ,、a、^、) (2) 算符優(yōu)先關(guān)系 a ( ) , ^ a ≯ ≯ ≯ ( ≮ ≮ ≡ ≮ ) ≯ ≯ ≯ , ≮ ≮ ≯ ≯ ≮ ^ ≯ ≯ ≯ ≮ ≮ ≮ 計(jì)算機(jī)執(zhí)行用高級(jí)語(yǔ)言編寫的程序有那些途徑?它們之間的主要區(qū)別是什么?計(jì)算機(jī)執(zhí)行用于高級(jí)語(yǔ)言編寫的程序主要有兩種途徑:解釋和編譯。在解釋方式下,翻譯程序并不對(duì)高級(jí)語(yǔ)言進(jìn)行徹底的翻譯,而是讀入一條語(yǔ)句,就解釋其含義并執(zhí)行,然后再讀入下一條語(yǔ)句,再執(zhí)行。在編譯方式下,翻譯程序先對(duì)高級(jí)語(yǔ)言進(jìn)行徹底的翻譯并生成目標(biāo)代碼,然后再對(duì)目標(biāo)代碼進(jìn)行優(yōu)化,即對(duì)源程序的處理是先翻譯后執(zhí)行。從速度上看,編譯方式下,源程序的執(zhí)行比解釋方式下快,但在解釋方式下,有利于程序的調(diào)試。編譯程序的實(shí)現(xiàn)途徑有那些? 編譯程序的實(shí)現(xiàn)途徑可有: 手工構(gòu)造:用機(jī)器語(yǔ)言、匯編語(yǔ)言或高級(jí)程序設(shè)計(jì)語(yǔ)言書寫?! ?自動(dòng)構(gòu)造工具:Lex,Yacc。 Lex ,Yacc分別是詞法和語(yǔ)法分析器的生成器。 移植方式:目標(biāo)程序用中間語(yǔ)言 自展方式:用T型圖表示 文法G[E]為: E→E+T|T T→T*F|F F→(E)|i 試給出句型(E+F)*i的短語(yǔ),簡(jiǎn)單(直接)短語(yǔ),句柄和最左素短語(yǔ)。短語(yǔ)有: (E+F)*i ,(E+F) ,E+F ,F(xiàn) ,i 簡(jiǎn)單(直接)短語(yǔ)有: F ,i 句柄是: F 最左素短語(yǔ)是: E+F有人認(rèn)為:“1型文法對(duì)規(guī)則的限制比2型文法對(duì)規(guī)則的限制要多一些”,這種說(shuō)法對(duì)嗎?文法是嚴(yán)格按照規(guī)則的形式來(lái)分類的1型文法的規(guī)則是:xUyxuy u∈Vn u∈V+ x,y∈V*要求將U替換為u時(shí),U的前后一定要有x和y。而2型文法的規(guī)則形式為Uu u∈Vn u∈V*沒有什么要求,似乎1型的規(guī)則限制要多一些。但仔細(xì)看看1型規(guī)則中的條件x和y時(shí),就不難發(fā)現(xiàn)當(dāng)x和y為空時(shí),正好是2型文法。從0型文法到3型文法,是依次增加對(duì)文法的限制,所以描述的語(yǔ)言集合越來(lái)越小。簡(jiǎn)述自底向上分析法?;舅枷胧牵簭拇斎氲姆?hào)串開始,利用文法的規(guī)則步步向上歸約,試圖歸約到文法的識(shí)別符號(hào)。從語(yǔ)法樹的角度看,自底向上分析的過程是以輸入符號(hào)串作為末端結(jié)點(diǎn)符號(hào)串,向著根結(jié)點(diǎn)方向往上構(gòu)造語(yǔ)法樹,使識(shí)別符號(hào)正好是該語(yǔ)法樹的根結(jié)點(diǎn)。如果最終根結(jié)點(diǎn)是識(shí)別符號(hào),則輸入符號(hào)串被識(shí)別是相應(yīng)語(yǔ)言的一個(gè)句子;否則不是。 自底向上分析過程實(shí)際上是一個(gè)不斷進(jìn)行直接歸約的過程。什么是規(guī)范推導(dǎo)?每個(gè)句型都有規(guī)范推導(dǎo)嗎?規(guī)范推導(dǎo)就是最右推導(dǎo)每一個(gè)句子都有一個(gè)規(guī)范推導(dǎo),而每一個(gè)句型則不一定都有規(guī)范推導(dǎo),比如說(shuō)采用非規(guī)范推導(dǎo)得到的句型。已知文法G[E]: E→ET+|T T→TF* | F F→F^ | a 試證:FF^^*是文法的句型,指出該句型的短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。該句型對(duì)應(yīng)的語(yǔ)法樹如下:該句型相對(duì)于E的短語(yǔ)有FF^^*;相對(duì)于T的短語(yǔ)有FF^^*,F。相對(duì)于F的短語(yǔ)有F^。F^^。簡(jiǎn)單短語(yǔ)有F。F^。句柄為F. 寫出表達(dá)式w+(a+b)*(c+d/(e10)+8)的逆波蘭表示及三元式序列。(1)(+,a,b)(2) (,e,10)(3) (/,d,(2))(4) (+,c,(3))(5) (+,(4),8)(6) (*,(1),(5))(7) (+,w,(6))何謂優(yōu)化?按所涉及的程序范圍可分為哪幾級(jí)優(yōu)化?所謂優(yōu)化,一般是指為提高目標(biāo)程序的質(zhì)量而進(jìn)行的各項(xiàng)工作,即對(duì)程序或中間代碼進(jìn)行各種等價(jià)變換,使得從變換后的程序出發(fā),能生成更有效的目標(biāo)代碼。 在源程序級(jí) 在語(yǔ)義動(dòng)作的設(shè)計(jì)上 在中間代碼級(jí) 在目標(biāo)代碼級(jí)簡(jiǎn)述自頂向下分析法。從識(shí)別符號(hào)出發(fā),不斷建立直接推導(dǎo),試圖構(gòu)造一個(gè)推導(dǎo)序列,最終由它推導(dǎo)出與輸入符號(hào)串相同的符號(hào)串。從語(yǔ)法樹角度看,自頂向下分析過程是以識(shí)別符號(hào)為根結(jié)點(diǎn),試圖向下構(gòu)造一棵語(yǔ)法樹,使其末端結(jié)點(diǎn)符號(hào)串正好與輸入符號(hào)串相同。實(shí)現(xiàn)高級(jí)語(yǔ)言程序的途徑有哪幾種?它們之間的區(qū)別?計(jì)算機(jī)執(zhí)行用于高級(jí)語(yǔ)言編寫的程序主要有兩種途徑:解釋和編譯。在解釋方式下,翻譯程序并不對(duì)高級(jí)語(yǔ)言進(jìn)行徹底的翻譯,而是讀入一條語(yǔ)句,就解釋其含義并執(zhí)行,然后再讀入下一條語(yǔ)句,再執(zhí)行。在編譯方式下,翻譯程序先對(duì)高級(jí)語(yǔ)言進(jìn)行徹底的翻譯并生成目標(biāo)代碼,然后再對(duì)目標(biāo)代碼進(jìn)行優(yōu)化,即對(duì)源程序的處理是先翻譯后執(zhí)行。從速度上看,編譯方式下,源程序的執(zhí)行比解釋方式下快,但在解釋方式下,有利于程序的調(diào)試。文法G[S]為: SAc|aB Aab Bbc 該文法是否為二義的?為什么?對(duì)于串a(chǎn)bc (1)S=Ac=abc (2)S=aB=abc 即存在兩不同的最右推導(dǎo) 所以,該文法是二義的。將文法G[S] 改寫為等價(jià)的G39。[S],使G39。[S]不含左遞歸和左公共因子?! [S]: S→SAe|Ae A→dAbA|dA|d文法G[S] 改寫為等價(jià)的不含左遞歸和左公共因子的G39。[S]為: 16S →AeS39。 S39。 →AeS39。|ε A →dA39。 A39。 →AB|ε B →bA |ε證明LL(1)文法是無(wú)二義性文法證明:LL(1)文法中任意兩個(gè)產(chǎn)生式Pi,Pj,(Pi,Pj具有相同的左部非終極符) Predict(Pi) ∩Predict(Pj) 為空設(shè) Pi: A→α1α2…αn Pj: A→α11α21…αm1(A∈VN, α1α2…αn, α11α21…αm1∈ VN∪VT) 因?yàn)镻redict(Pi) ∩Predict(Pj) 為空,因此 Pi,Pj中的A經(jīng)一步推導(dǎo),最左的終極符肯定不同,因此,對(duì)于一個(gè)字符串,不可能有兩種方法推導(dǎo)。文法G[S]為: SAc|aB Aab Bbc 寫出L(G[S])的全部元素S=Ac=