第四章語(yǔ)法分析(3)-資料下載頁(yè)
2025-07-22 09:44本頁(yè)面
【正文】 mrsmrAs*, aiai+1… an$) 55 語(yǔ)法分析器的下一動(dòng)作由當(dāng)前輸入符號(hào) ai和棧頂狀態(tài) sm查詢分析表 action[sm, ai]： ? If action[sm, ai]=“acc”, accept, success ? If action[sm, ai]=“Error”, report error 56 算法 LR分析算法 輸入 ：一個(gè)輸入串 w和文法 G的一張 LR分析表 M。 輸出 ：若 w?L(G)，輸出 w的一個(gè)自底向上的分析； 否則，報(bào)錯(cuò)。 方法 ：初始狀態(tài) s0 分別放在棧頂， w$放在輸入緩沖區(qū)；語(yǔ)法分析器執(zhí)行下面的程序，直至遇見(jiàn)接受或出錯(cuò)動(dòng)作。 57 LR分析程序 置 ip指向 w$的第一個(gè)符號(hào)； repeat forever begin 令 s是棧頂狀態(tài)， a是 ip所指向的符號(hào) if action[s, a] = “shift s?” then begin 將 a和 s?先后 壓入棧內(nèi)； 讓 ip指向下一個(gè)輸入符號(hào)； end 58 LR分析程序 (cont.) else if action[s,a] = “reduce A??” then begin 從棧頂彈出 2*|?|個(gè)符號(hào)； 令 s?是當(dāng)前 棧頂狀態(tài)； 把 A和 goto[s?, A]先后入棧； 輸出產(chǎn)生式 A? ? end else if action[s, a] = “acc” then return else error( ) end 59 例 算法表達(dá)式文法 (1) E ? E + T (4) T ? E (2) E ? T (5) F ? (E ) (3) T ? T * F (6) F ? id 各個(gè)動(dòng)作的編碼的含義： 1. si表示把當(dāng)前輸入符號(hào)和狀態(tài) i進(jìn)棧 2. rj表示用第 j條產(chǎn)生式規(guī)約 3. acc表示接受 4. 空白項(xiàng)表示出錯(cuò) 60 圖 表達(dá)式文法的 LR分析表 action go to 狀 態(tài) id + * ( ) $ E T F 0 1 2 3 4 5 6 7 8 9 10 11 s5 s4 s6 ac c r2 s7 r2 r2 r4 r4 r4 r4 s5 s4 r6 r6 r6 r6 s5 s4 s5 s4 s6 s11 r1 s7 r1 r1 r3 r3 r3 r3 r5 r5 r5 r5 1 2 3 8 2 3 9 3 1 0 61 圖 關(guān)于 id*id+id的 LR分析過(guò)程 棧 輸入 動(dòng)作 (1) 0 (2) 0 id 5 (3) 0 F 3 (4) 0 T 2 (5) 0 T 2*7 (6) 0 T 2*7 id 5 (7) 0 T 2*7 F 10 (8) 0 T 2 (9) 0 E 1 (10) 0 E 1+6 (11) 0 E 1+6 id 5 (12) 0 E 1+6 F 3 (13) 0 E 1+6 T 9 (14) 0 E 1 id * id + id $ * id + id $ * id + id $ * id + id $ id + id $ + id $ + id $ + id $ + id $ id $ $ $ $ $ sh if t redu ce by F ? id redu ce by T ? F sh if t sh if t redu ce by F ? id redu ce by T ? T * F redu ce by E ? T sh if t sh if t redu ce by F ? id redu ce by T ? F redu ce by E ? E + T ac ce pt 62 LR分析方法的特點(diǎn) ? 棧中的文法符號(hào)總是形成一個(gè)活前綴。 ? 分析表的轉(zhuǎn)移函數(shù)本質(zhì)上是識(shí)別活前綴的 DFA。 ? 棧頂?shù)臓顟B(tài)符號(hào)包含了確定句柄所需要的一切信息。 ? 是已知的最一般的無(wú)回溯的移進(jìn) ?歸約方法。 ? 能分析的文法類(lèi)是預(yù)測(cè)分析法能分析的文法類(lèi)的真超集。 ? 能及時(shí)發(fā)現(xiàn)語(yǔ)法錯(cuò)誤。 ? 手工構(gòu)造分析表的工作量太大。 63 在下面的推導(dǎo)中，最后一步用的是 A? a? S ?rm … ? rm ? A b w ? rm ? a ? b w LL(1)決定用該 產(chǎn)生式的位置 LR(1)決定用該 產(chǎn)生式的位置 LR分析方法和 LL分析方法的比較 64 LR(1)方 法 LL(1)方 法 建立分析樹(shù)的方式 自 下 而 上 自 上 而 下 歸約還是推導(dǎo) 規(guī) 范 歸 約 最 左 推 導(dǎo) 決定使用產(chǎn)生式的時(shí)機(jī) 看見(jiàn)產(chǎn)生式整個(gè)右部推出的東西后才算是看準(zhǔn)了用哪個(gè)產(chǎn)生式進(jìn)行歸約 看見(jiàn)產(chǎn)生式右部推出的第一個(gè)終結(jié)符后便確定用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo) LR分析方法和 LL分析方法的比較 65 LR(1)方 法 LL(1)方 法 對(duì)文法的顯式限制 對(duì)文法沒(méi)有限制 無(wú)左遞歸、無(wú)公共左因子 分析表比較 狀態(tài) 文法符號(hào) 分析表大 非終結(jié)符 終結(jié)符 分析表小 分析棧比較 狀態(tài)棧 ， 通常狀態(tài)比文法符號(hào)包含更多信息 文法符號(hào)棧 LR分析方法和 LL分析方法的比較 66 LR(1)方 法 LL(1)方 法 確定句柄 根據(jù)棧頂狀態(tài)和下一個(gè)符號(hào)便可以確定句柄和歸約所用產(chǎn)生式 無(wú)句柄概念 語(yǔ)法錯(cuò)誤 決不會(huì)將出錯(cuò)點(diǎn)后的符號(hào)移入分析棧 和 LR一樣 ， 決不會(huì)讀過(guò)出錯(cuò)點(diǎn)而不報(bào)錯(cuò) LR分析方法和 LL分析方法的比較 67 LR文法和 LL文法 ? 每步需要向前看 k個(gè)符號(hào)的 LR語(yǔ)法分析器所能分析的文法稱(chēng)為 LR(k)文法。 ? 我們討論 k=0或 k=1的情況。 ? LR文法比 LL文法描述的語(yǔ)言更多。 ? 注：書(shū)上 P145最后一行的“歸約”是否應(yīng)改為“推導(dǎo)”。
外語(yǔ)相關(guān)推薦
鄂ICP備17016276號(hào)-1