課件，編譯原理，編譯原理課件，屬性文法，語(yǔ)法制導(dǎo)，2005課件說(shuō)明，第四章-文庫(kù)吧在線文庫(kù)
【正文】 代計(jì)算機(jī)上實(shí)現(xiàn)的計(jì)算都能用圖靈機(jī)描述 27 2型文法（上下文無(wú)關(guān)文法 CFG）：產(chǎn)生式的形式為 A→ β ， β 取代 A時(shí)與 A的上下文無(wú)關(guān)。 對(duì) VT中的每一個(gè) a ,有 f(N,a)=φ 29 3型文法 和 有窮自動(dòng)機(jī)（ FA） G［Ｓ］： S→aA|bB A→bB|aD|a B→aA|bD|b D→aD|bD|a|b B A S a a a b b b a,b D Z a b a b ? 30 3型文法 和 有窮自動(dòng)機(jī)（ FA） 定理 已知一有窮自動(dòng)機(jī) M= (K, ∑ , f, A, Z) ,存在有一個(gè) 3型文法 G = （ VN， VT， P， S） ,使得 L(G)=L(M) G 的定義： 二義文法改造為無(wú)二義文法 G‘[E]:E → i G[E] ： E → T|E+T E → E+E T → F|T*F E → E*E F → （ E） |i E → (E) 規(guī)定算符優(yōu)先性和結(jié)合性 如果產(chǎn)生上下文無(wú)關(guān)語(yǔ)言的每一個(gè)文法都是二義的，則說(shuō)此語(yǔ)言是先天二義的。 48 兩種方法反映了兩種語(yǔ)法樹(shù)的構(gòu)造過(guò)程。 58 練習(xí) 1. 寫(xiě)一文法，使其語(yǔ)言是偶正整數(shù)的集合。會(huì) 引起 文法的 二義性 多余規(guī)則 ：指文法中 任何句子的推導(dǎo) 都 不會(huì)用到的規(guī)則 文法中 不含有 不可到達(dá)和不可終止的 非終結(jié)符 1）文法中某些 非終結(jié)符不在任何規(guī)則的右部出現(xiàn) ，該非終結(jié)符稱(chēng)為 不可到達(dá) 。分析算法又稱(chēng) 識(shí)別算法 。 若 f(D,t)=B ，則 D→tB 在 P中 若 f(D,t)=B ，且 B在 Z中，則 D→t 在 P中 31 3型文法 和 有窮自動(dòng)機(jī)（ FA） G［Ｓ］： S→aA|bB A→bB|aD|a B→aA|bD|b D→aD|bD|a|b D B A S a a a b b a,b b ? 32 正規(guī)文法和正規(guī)式 對(duì) ?上的正規(guī)式 r ,存在一個(gè) RG=(VN,VT,P,S)：L(G)=L(r) 初始， VT= ?,S ? VN ， 生成正規(guī)產(chǎn)生式 S?r () 對(duì)形如 A?r1r2的 正規(guī)產(chǎn)生式： A?r1B B?r2 B?VN ()對(duì)形如 A?r?r1的 正規(guī)產(chǎn)生式： A?rB A?r1 B?rB B?r1 B?VN ()對(duì)形如 A?r1?r2的 正規(guī)產(chǎn)生式 : A?r1 A? r2 不斷應(yīng)用 ()做變換，直到每個(gè)產(chǎn)生式右端至多有一個(gè) VN 33 例 r=a(a?d)? (1) S?a(a?d)? (2) S?aA A?(a?d)? (3) A?(a?d)B A?? B?(a?d)B B?? G[s]: S?aA A?? VT={a,d} A?aB VN={S,A,B} A?dB B?aB B?dB B?? 34 正規(guī)文法和正規(guī)式 對(duì) G=(VN,VT,P,S),存在一個(gè) ? =VT上的正規(guī)式 r : L(r)=L(G) A?xB , B?y 形成正規(guī)式 A=xy A?xA?y 形成正規(guī)式 A=x?y A?x?y 形成正規(guī)式 A=x?y 35 正規(guī)文法和正規(guī)式 G[s]:S?aA|a A?aA?a?dA?d A?(a?d)A?(a?d) A?(a?d)?(a?d) S=a(a?d)?(a?d)?a =a((a?d)?(a?d)??) =a((a?d)???) R=a(a?d)? 36 上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù) 上下文無(wú)關(guān)文法有足夠的能力描述程序設(shè)計(jì)語(yǔ)言的語(yǔ)法結(jié)構(gòu) 語(yǔ)法樹(shù) 句型推導(dǎo) 的 直觀表示 37 語(yǔ)法樹(shù) 句型推導(dǎo) 的 直觀表示 (句型、推導(dǎo) ) G[E]： E→E+T|T T→T*F|F F→(E)|a E?E+T ?T+T ?F+T ?a+T ?a+T*F ?a+F*F ?a+a*F ?a+a*a E?E+T ?E+T*F ?E+
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1