課件，編譯原理，編譯原理課件，屬性文法，語法制導(dǎo)，2005課件說明，第四章(編輯修改稿)
2025-06-15 23:00 本頁面
【文章內(nèi)容簡介】 3型文法產(chǎn)生的語言是有窮自動(dòng)機(jī)（ FA）所接受的集合 . 定理 設(shè) G=（ VN， VT， P， S）是 3型文法，則存在一個(gè)有窮自 動(dòng)機(jī) M=(K, ∑ , f, A, Z) ，使得 L(M)=L(G) 有窮自動(dòng)機(jī) NFA M ∑= VT K= VN ∪{ N}, N為一個(gè)新狀態(tài) ,它不在 VN中 A=S Z={N} 對 G中的形如 D→tB 的產(chǎn)生式 ,t為終結(jié)符或 ε ,有 f(D,t)=B； 對 G中形如 D→t 的產(chǎn)生式， t為終結(jié)符或 ε ,有 f(D,t)=N。 對 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 的定義： VT =∑ VN= K S = A 若 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ī)式 對 ?上的正規(guī)式 r ,存在一個(gè) RG=(VN,VT,P,S)：L(G)=L(r) 初始， VT= ?,S ? VN ， 生成正規(guī)產(chǎn)生式 S?r () 對形如 A?r1r2的 正規(guī)產(chǎn)生式： A?r1B B?r2 B?VN ()對形如 A?r?r1的 正規(guī)產(chǎn)生式： A?rB A?r1 B?rB B?r1 B?VN ()對形如 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ī)式 對 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 上下文無關(guān)文法及其語法樹 上下文無關(guān)文法有足夠的能力描述程序設(shè)計(jì)語言的語法結(jié)構(gòu) 語法樹 句型推導(dǎo) 的 直觀表示 37 語法樹 句型推導(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+T*a ?E+F*a ?E+a*a ?T+a*a ?F+a*a ?a+a*a E?E+T ?T+T ?T+T*F ?F+T*F ?F+F*F ?a+F*F ?a+F*a ?a+a*a 38 規(guī)范
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1