freepeople性欧美熟妇, 色戒完整版无删减158分钟hd, 无码精品国产vα在线观看DVD, 丰满少妇伦精品无码专区在线观看,艾栗栗与纹身男宾馆3p50分钟,国产AV片在线观看,黑人与美女高潮,18岁女RAPPERDISSSUBS,国产手机在机看影片

正文內(nèi)容

編譯原理西北工業(yè)大學(xué)第三版課后答案(編輯修改稿)

2024-07-22 19:32 本頁(yè)面
 

【文章內(nèi)容簡(jiǎn)介】 Z21aZ21bZ11 : (1)產(chǎn)生式first集follow集S→SaB→bB{,a,c}A→S→a{a}{c}B→Ac{a,b}{,a,c}(2)將S→SaB | bB改寫為S→bBS’,S’ →aBS’|ω,可驗(yàn)證,新文法是LL(1)的。 : 1)為方便書寫,記:布爾表達(dá)式為A,布爾因子為B,布爾二次量為C,布爾初等量為D,原文法可以簡(jiǎn)化為: A→A∨B | B B→B∧C | CC→┐D | DD→(A) | true | false,顯然,文法含有左遞歸,消去后等價(jià)LL(1)文法為:A→BA’ A’ →∨BA’|ω B→CB’,B’ →∧CB’|ωC→┐D|DD→(A)| true|false(2)略 證:若LL(1)文法G有形如B→aAAb的產(chǎn)生式,且AT+ε及AT*ag,根據(jù)FIRST集FOLLOW集的構(gòu)造算法可知,F(xiàn)IRST(A)中一切非ε加到FOLLOW(A)中,則a∈FOLLOW(A);又因?yàn)閍∈FIRST(ag),所以兩集合相交非空,因此,G不是LL(1)文法;與前提矛盾,假設(shè)不成立,得證。 解: (1)SA(a)bS==A==(==a=)b不是簡(jiǎn)單優(yōu)先文法。(2)SRT()∧a,S=R=T(=)∧a,=是簡(jiǎn)單優(yōu)先文法。(3) SR(a,)S=R(=a,=)是簡(jiǎn)單優(yōu)先文法。o 首先消去無(wú)用產(chǎn)生式Z→E, Z→E+T SZTi()SZ==T=I(=)化簡(jiǎn)后的文法是簡(jiǎn)單優(yōu)先文法; 解: SA/ASA===/aA和/之間同時(shí)有關(guān)系=和,所以不是簡(jiǎn)單優(yōu)先文法; 提示:分析教材中給出的算法,選擇一種合適的表示給定文法的方法(盡量簡(jiǎn)單),使得對(duì)文法的輸入比較簡(jiǎn)單的同時(shí)(需要把輸入轉(zhuǎn)化為計(jì)算機(jī)語(yǔ)言表示,這種轉(zhuǎn)化應(yīng)該盡量簡(jiǎn)單),能夠比較簡(jiǎn)單地構(gòu)造3個(gè)基本關(guān)系矩陣(=,LEAD和LAST)。 證明:設(shè)xjxj+1...xi是滿足條件xj1xj=xj+1=...=xi xi+1的最左子串。由=關(guān)系的定義,可知xjxj+1...xi必出現(xiàn)在某產(chǎn)生式的右部中。又因xj1xj可知xj1與xj不處于同一產(chǎn)生式,且xj是某右部的首符。同理,xi為某產(chǎn)生式的尾符號(hào)。即存在產(chǎn)生式 U→xjxj+1...xi設(shè) ST* aUb其中,aT*... xj1 ,bT* xi+1... 對(duì)于aUb可構(gòu)造一語(yǔ)法樹,并通過(guò)對(duì)其剪枝(歸約),直到U出現(xiàn)在句柄中。從而xjxj+1...xi必為句柄。反之,若xjxj+1...xi是句柄,由簡(jiǎn)單優(yōu)先關(guān)系的定義,必滿足上述條件。 解:為描述方便,用符號(hào)表示各非終結(jié)符:D=變量說(shuō)明,L=變量表, V= 變量,T=類型,a=VAR,則消去V,并采用分層法改寫文法,得到:D→aW:T。W→LL→L,i|iT→r|n|b|c 其全部簡(jiǎn)單優(yōu)先關(guān)系是:DWTLa:。,ir|n|b|cDW=T=L=a=:=。,=ir|n|b|c是簡(jiǎn)單優(yōu)先文法。 證:設(shè)STna,我們對(duì)n用歸納法,證明a不含兩個(gè)非終結(jié)符相鄰情況。n=1時(shí),STa,即S→a是文法的產(chǎn)生式,根據(jù)定義,它不含上述情況。設(shè)n=k時(shí),上述結(jié)論成立,且設(shè)STkdAb,由歸納假設(shè),A兩側(cè)必為終結(jié)符。我們?cè)龠M(jìn)行一步推導(dǎo),得STkdAbTdub, 其中,A→u是文法中的產(chǎn)生式,由定義,u中不含兩個(gè)非終結(jié)符相鄰情況,從而dub兩個(gè)非終結(jié)符相鄰情況。得證。 證:由于G不是算符文法,G中至少有一個(gè)產(chǎn)生式,其右部含有兩個(gè)非終結(jié)符相鄰的情況。不失一般性,設(shè)其形為U→xABy,x,y∈V*,由于文法不含無(wú)用產(chǎn)生式,則必存在含有U的句型dUb,即存在推導(dǎo)ST*。 文法為:E→E↑A | AA→A*T | A/T | TT→T+V | TV | VV→i | (E) 解: (1)構(gòu)造算符優(yōu)先矩陣:*()i*(=)I(2)在(,)、(,*)和(*,)處有多重定義元素,不是算符優(yōu)先文法;(3)改寫方法: 將E→ET中的減號(hào)與F→P中的賦值運(yùn)算符強(qiáng)制規(guī)定優(yōu)先關(guān)系; 或者將FP中的賦值運(yùn)算符改為別的符號(hào)來(lái)表示; (1)證明:由設(shè)句型a =…Ua…中含a的短語(yǔ)不含U,即存在A,A=*ay,則a可歸約為a =…Ua…252。*…UA…=b,b是G的一個(gè)句型,這與G是算符文法矛盾,所以,a中含有a的短語(yǔ)必含U。 (2)的證明與(1)類似,略。 證:(1)對(duì)于a=…aU…是句型,必有ST*a(=…aU…) T+…ab….即在歸約過(guò)程中,b先于a被歸約,從而,a(2)的情況類似可以證明。 證明略. 證明略. 證明略。 證:(1) 用反證法。設(shè)沒(méi)有短語(yǔ)包含b但是不包含a,則a,b一定同時(shí)位于某個(gè)短語(yǔ)中,從而必使得a,b同時(shí)位于同一產(chǎn)生式的右部,所以a=b,與G是算符優(yōu)先文法(=與不能并存)矛盾。 (2)、(3)類似可證。 證:只要證u中不含有除自身以外的素短語(yǔ)。設(shè)有這樣的素短語(yǔ)存在,即存在bxby是素短語(yǔ),其中1x或者yn之一成立。因素短語(yǔ)是短語(yǔ),根據(jù)短語(yǔ)定義,則必有:1xTbx1bx或ynTbyby+1,與bx1=bx及 by=by+1矛盾,得證。 提示:根據(jù)27題的結(jié)論,只要證u是句型α的短語(yǔ),根據(jù)=關(guān)系的定義容易知道u是句型α的素短語(yǔ)。 證:與28題的不同點(diǎn)只是a0,an+1可以是’’,不影響結(jié)論。 證:設(shè)不能含有素短語(yǔ),則只能是含有短語(yǔ)(不能含有終結(jié)符號(hào)),則該短語(yǔ)只能含有一個(gè)非終結(jié)符號(hào),否則不符合算符文法定義,得證。 解: (1)算符優(yōu)先矩陣:+*↑()i+*↑(=)I(2)用Floyd方法將優(yōu)先矩陣線性化得到得的優(yōu)先函數(shù)為:+*↑()iF3551771G2466161 解:用Floyd方法對(duì)已知的優(yōu)先矩陣構(gòu)造的優(yōu)先函數(shù)為: zbMLa()f1567747g1654667 解: (1)優(yōu)先矩陣如下:[]a[=]a(2)用Bell方法求優(yōu)先函數(shù)的過(guò)程如下:[]af5751g5561(3)顯然,文法不是算符優(yōu)先文法, 所以不能線性化。 略。 35解: (1)識(shí)別全部活前綴的DFA如下:(以表格的形式來(lái)表示,很容易可以轉(zhuǎn)化為圖的形式,本章中其余的題目也是采用這種形式表示。)狀態(tài)項(xiàng)目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)I0S’ →SS→aSbS→aScS→abSaI1I2I1S’ →SI2S→aSbS→aScS→abS→aSbS→aScS→abSabI3I2I4I3S→aSbS→aScbcI5I6I4S→abI5S→aSbI6S→aSc(2)識(shí)別全部活前綴的DFA如下:狀態(tài)項(xiàng)目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)I0S’ →SS→cAS→ccBScI1II1S’ →SI2S→cAS→ccBA→cAA→aAcaI3I4I5I3S→cAI4S→ccBA→cAB→ccBB→bA→cAA→aBAcbaI6I5I7I8I5I5A→aI6S→ccBI7B→ccBA→cAA→cAA→aCAaI9I10I5I8B→bI9B→ccBA→cAB→ccBB→bA→cAA→aBAcbaI11I10I7I8I5I10A→cAI11B→ccB所求的LR(0)項(xiàng)目規(guī)范族C={I0,I1,…,I11}(3)狀態(tài)項(xiàng)目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)I0S’ →SS→aSSbS→aSSSS→cScaI1I2I3I1S’ →SI2S→cI3S→aSSbS→aSSSS→aSSbS→aSSSS→cScaI4I2I3I4S→aSSbS→aSSSS→aSSbS→aSSSS→cScaI5I2I3I5S→aSSbS→aSSSS→aSSbS→aSSSS→cSabcI7I3I6I2I6S→aSSbI7S→aSSS(4)狀態(tài)項(xiàng)目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)I0S’ →SS→AA→AbA→aSAaI1I2I3I1S’ →SI2S→AS→AbbI4I3A→aI4S→Ab36解: (1)是LR(0)文法,其SLR(1)分析表如下:FOLLOW(S)={,b,c}ACTIONGOTOabcS0S211ACC2S2S433S5S64R3R3R35R1R1R16R2R2R2(2)是LR(0)文法,其SLR(1)分析表如下:FOLLOW(S)=FOLLOW(A)=FOLLOW(B)={}ACTIONGOTOabcSAB0S211ACC2S5S433R14S5S8S7365R46R27S5S9108R69S5S8S7101110R311R5(3)是LR(0)文法,其SLR(1)分析表如下:FOLLOW(S)={,a,b,c}ACTIONGOTOabcS0S3S211ACC2R3R3R3R33S3S244
點(diǎn)擊復(fù)制文檔內(nèi)容
環(huán)評(píng)公示相關(guān)推薦
文庫(kù)吧 www.dybbs8.com
備案圖片鄂ICP備17016276號(hào)-1