【正文】 8 gid f* g+ f$ fid g* f+ g$ 圖 優(yōu)先函數的構造 表 ： + * id $ f g 2 1 4 3 4 5 0 0 id + * $ id + * $ 例 49 算符優(yōu)先分析中的錯誤恢復 ? 兩種語法錯誤 – 棧頂的終結符和當前輸入之間沒有優(yōu)先關系 – 發(fā)現句柄，但句柄不是任何產生式的右部 50 LR分析器 ? 本節(jié)介紹 LR(k)分析技術 ? “ L”： lefttoright scanning 自左向右掃描 ? “ R”： rightmost derivation in reverse 最右推導的逆 ? the k for the number of input symbols of lookahead ? when (k) is omitted, k is assumed to be 1 51 LR分析器的特點 ? 適用于一大類上下文無關文法 ? 效率高 ? 主要介紹構造 LR分析表的三種技術 – 簡單的 LR方法（簡稱 SLR） – 規(guī)范的 LR方法 – 向前看的 LR方法（簡稱 LALR） 52 LR分析算法 輸入 LR分析程序 輸出 棧 LR分析器的模型 action goto sm Xm sm1 Xm1 … s0 … a1 ai … an $ 53 LR語法分析器的行為 ? LR語法分析器的格局 (Configuration)用二元組表示： (s0X1s1X2s2… Xmsm, aiai+1… an$) 棧的內容 尚未處理的輸入 ? 代表右句型 X1X2… Xmaiai+1… an 54 語法分析器的下一動作由當前輸入符號 ai和棧頂狀態(tài) sm查詢分析表 action[sm, ai]： ? If action[sm, ai]=“shift and goto state s*” Shift。 輸出 ：若 w?L(G)，輸出 w的一個自底向上的分析； 否則，報錯。 57 LR分析程序 置 ip指向 w$的第一個符號； repeat forever begin 令 s是棧頂狀態(tài)， a是 ip所指向的符號 if action[s, a] = “shift s?” then begin 將 a和 s?先后 壓入棧內； 讓 ip指向下一個輸入符號； end 58 LR分析程序 (cont.) else if action[s,a] = “reduce A??” then begin 從棧頂彈出 2*|?|個符號； 令 s?是當前 棧頂狀態(tài)； 把 A和 goto[s?, A]先后入棧； 輸出產生式 A? ? end else if action[s, a] = “acc” then return else error( ) end 59 例 算法表達式文法 (1) E ? E + T (4) T ? E (2) E ? T (5) F ? (E ) (3) T ? T * F (6) F ? id 各個動作的編碼的含義： 1. si表示把當前輸入符號和狀態(tài) i進棧 2. rj表示用第 j條產生式規(guī)約 3. acc表示接受 4. 空白項表示出錯 60 圖 表達式文法的 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 圖 關于 id*id+id的 LR分析過程 棧 輸入 動作 (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分析方法的特點 ? 棧中的文法符號總是形成一個活前綴。 ? 棧頂的狀態(tài)符號包含了確定句柄所需要的一切信息。 ? 能分析的文法類是預測分析法能分析的文法類的真超集。 ? 手工構造分析表的工作量太大。 ? 我們討論 k=0或 k=1的情況。 ? 注：書上 P145最后一行的“歸約”是否應改為“推