編譯原理復(fù)習(xí)(編輯修改稿)
2025-09-01 19:49 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 E(用 0表示 )； 例 2，設(shè)有文法 G[E]: E?E+T |T T?T*F | F F?(E) | i STACK + * ( ) i E T F F 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ② 從文法中找出形如 U?b… 或 U?Vb的產(chǎn)生式，并使對(duì)應(yīng)的 數(shù)組元素F[U,b]=TRUE(用 1表示 )； E?E+T 1 T?T*F 1F?(E) 1 F?i 1 ③ 將 F[U,b]的值為真的符號(hào)對(duì) U,b壓入工作棧 (順序任意 )； F , ( E , + T , * F , i ③ 若工作棧不空，將棧頂項(xiàng)彈出，此項(xiàng)記為 V,b,若文法中有形如： U ?V… 的產(chǎn)生式，則 b?FIRSTVT(U)，此時(shí)，若數(shù)組中F[U,b]=FALSE,則 令 F[U,b]=TRUE,且將 U,b壓入 STACK,此過(guò)程重復(fù)進(jìn)行，直到棧空。 1 T 1 E , 1 E , 1 T , ( 1 E , FIRSTVT(E)={+,*,(,i} FIRSTVT(T)={*,(,i} FIRSTVT(F)={(,i} 用類(lèi)似的算法可以求出LASTVT(U) (P92) ?檢查文法中的每一條產(chǎn)生式，找出形如 U?…ab… 或 U?…aVb… 的產(chǎn)生式，則滿(mǎn)足優(yōu)先關(guān)系 a b。 . a b . ?若文法中有產(chǎn)生式 U?…aW… ，且 b?FIRSTVT(W)，則 a b ?若文法中有產(chǎn)生式 U?…Wb… ，且 a?LASTVT(W)，則 . for 每條產(chǎn)生式 U?x1x2…x n do begin for i:=1 to n1 do begin if xi,xi+1?VT then 置 xi xi+1 if i? n2 且 xi,xi+2?VT, xi+1?VN then 置 xi xi+2 if xi?VT, xi+1?VN then for b?FIRSTVT(xi+1) do xi b if xi?VN, xi+1?VT then for a?LASTVT(xi) do a xi+1 end end . . . . ：對(duì)于文法 G，其產(chǎn)生式的右部添加一個(gè)特殊符號(hào)“ .”就構(gòu)成文法的一個(gè) LR(0)項(xiàng)目，簡(jiǎn)稱(chēng)項(xiàng)目。 2. 求項(xiàng)目集規(guī)范族 ，每個(gè)項(xiàng)目集對(duì)應(yīng)一個(gè) DFA狀態(tài)，它們的全體稱(chēng)這個(gè)文法的項(xiàng)目集規(guī)范族，下面給出求各個(gè)項(xiàng)目集的方法，以便得到識(shí)別文法活前綴的 DFA。 (1)求項(xiàng)目集 設(shè) Si是狀態(tài) Sk輸入符號(hào) x后到達(dá)的狀態(tài) (Si是 Sk關(guān)于符號(hào) x的后繼狀態(tài) )，則有： ① Si狀態(tài)中的基本部分為： BASIC(Si)={A??x.?| A??.x??Sk} ② 用閉包函數(shù)構(gòu)造項(xiàng)目集 CLOSURE(Si)： a. BASIC(Si)?CLOSURE(Si)： b. 若 A??.B??CLOSURE(Si),B?VN ,B?.??CLOSURE(Si) ③ 重復(fù)②直到 CLOSURE(Si)不再增加項(xiàng)目為止。
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1