lr分析器序471lr分析器的邏輯結(jié)構(gòu)及工作過(guò)程472-文庫(kù)吧資料
2024-07-30 13:56本頁(yè)面
【正文】 I2: E ?T ? I9: E ?E+T ? E ?E?+T T ?T ? *F T ?T ? *F I={X ?? ?b ?, A ?? ?, B ?? ?} 若 ?FOLLOW(A) ? FOLLOW(B)=? 則，面對(duì)當(dāng)前讀入符號(hào) a， 狀態(tài) I的解決方法： 1. 若 a=b,則移進(jìn)。??E E ??E+T E ??T T ??T*F T ??F F ? ?(E) F ??id E E 180。?E (1) E ?E+T (2) E ?T (3) T ?T*F (4) T ?F (5) F ?(E) (6) F ?id E 180。 24 四 . SLR分析表的構(gòu)造 有的文法，識(shí)別它的活前綴的 DFA的狀態(tài)集中，有的狀態(tài)的項(xiàng)目集中含有沖突項(xiàng)目。 對(duì)同一個(gè)活前綴存在若干不同的項(xiàng)目對(duì)它是有效的，而且它告訴我們應(yīng)做的事情可能各不相同，互相沖突。事實(shí)上，在任何時(shí)候分析棧中的活前綴 X1X2… Xm的有效項(xiàng)目集恰恰是棧頂狀態(tài) Sm所代表的那個(gè)集合。??S S ??aA S ??bB a S ?a?A A ? ? cA A ? ? d S 180。 21 三 .例示 LR(0)分析表的構(gòu)造 例 （ 0） S180。 REPEAT FOR ?I?C 和 ?X ?{VT ∪ VN} 把 go(I,X) 加入到 C中 UNTIL C不在增大 END。 20 LR(0)項(xiàng)目集規(guī)范族的構(gòu)造 PROCEDURE items(G ?)。 BEGIN J:={ }。 x∈ {VT∪ VN}) :SET OF item。 Return (I) END。 算法 計(jì)算 closure(I)和 go(I,x) FUNCTION closure(I:SET OF item):SET OF item。 Xβ是識(shí)別某個(gè)活前綴 γ=δα 的有效項(xiàng)目，則有規(guī)范推導(dǎo)： 18 S ?Aw ? ?X?w J中項(xiàng)目 A→α X Xβ J: A→α X Xβ的后繼。項(xiàng)目 A→α Xβ|當(dāng) A→α 顯然對(duì)任何有效項(xiàng)目集 I,都有 I= closure(I)。η加進(jìn) closure(I)中 。 2． 若項(xiàng)目 A→α文法 G的所 有有效項(xiàng)目集組成的集合稱(chēng)為 G的 LR(0)項(xiàng)目集規(guī)范族。η 在同一個(gè)項(xiàng)目集中。 A→α Bβ對(duì) 識(shí)別 活前綴 ? =δα是有效，則存在一個(gè)規(guī)范推導(dǎo) S δAw δαBβw 設(shè) βw xw , 則對(duì)任何 B→η ?P ，有 S δAw δαBβw δαBxw δα η xw 則 B→η 對(duì) 識(shí)別 活前綴 ?=δα也是有效的。 有下面的結(jié)論： 若項(xiàng)目 A→α 14 二 . 有效項(xiàng)目集和轉(zhuǎn)移函數(shù) 定義 (識(shí)別活前綴的有效項(xiàng)目 ) 如果存在一個(gè)規(guī)范推導(dǎo) S αAw αβ1β2w 項(xiàng)目 A→β 1?S, S180。 *? rm ? rm 12 活前綴和句柄的關(guān)系： 1. 活前綴不含有句柄的任何符號(hào)， ?； 2. 活前綴含有句柄的部分符號(hào)， ??1 ； 3. 活前綴已含有句柄的全部符號(hào)， ??。 一 . 項(xiàng)目 識(shí)別活前綴的 DFA m每個(gè)狀態(tài)是一個(gè)項(xiàng)目集。 11 SLR分析表的構(gòu)造 根椐文法 G，構(gòu)造識(shí)別文法 G的所有活前綴的 DFA m，根椐 DFA m構(gòu)造分析表。 4 .若 action[sm,ai]=error,則 轉(zhuǎn)出錯(cuò)處理程序。 構(gòu)造分析器的工作量很大，不大可能手工構(gòu)造；用軟件工具 yaccYet Another Compiler Compiler,Bell,1974. LR(0) SLR(1) LR(1) LALR(1) 4 LR分析器的邏輯結(jié)構(gòu)及工作過(guò)程 一個(gè)輸入、一個(gè)輸出、一個(gè)棧、一個(gè)驅(qū)動(dòng)程序和一張分析表 id+id*id$ Sm Xm Sm1 Xm1 … S0 LR驅(qū) 動(dòng)程序 動(dòng)作 轉(zhuǎn)移 action goto 輸出 5 分析表： 移進(jìn) ai 和 s=
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1