Can you summarize the following document?
        
  以表格為主(table-based)由下而上的剖析器可用圖一描述其結構,它包含:

  LR剖析過程如下:

  考慮以下文法:  待剖析的輸入字串是:

  LR(0)剖析器使用的表格如下:  動作表用以表示目前狀態遇到"終端符號"(包含結尾字元$)的對應動作,欄位中可能有三種動作:  狀態轉移表用以表示簡化後的狀態遇到"非終端符號"時的轉移規則。

  下表是剖析過程中的各步驟,堆疊的頂端在最右邊,狀態的轉移與堆疊的化簡都以上表為依據,而特殊字元'$'也被加到輸入串的尾端表示結尾。

  剖析起始時堆疊會包含元素$與0:  剖析器首先從輸入緩衝區看到符號'1',根據"動作表"當狀態0碰到終端符號'1'時採用移位動作s2,即是將'1'從輸入緩衝區中移出並推入堆疊,再將新的狀態2也推入堆疊,這時堆疊會變成:  (為避免終端符號與狀態混淆,故堆疊中的終端符號都加上單引號區別)  接著看到的終端符號是 '+',根據動作表無論狀態2碰到任何終端符號,都執行r5動作(以第五條文法規則B → 1化簡堆疊內容)。此化簡的動作表示剖析器已經在堆疊中認出第五條文法規則的右手邊部分,因此可以用該規則的左手邊符號"B"取代。因為第五條文法的右邊有一個符號,因此我們將兩個元素(1 × 2 = 2)自堆疊彈出,此時會回到狀態0,再推入符號"B",並查詢轉移表中狀態0遇到非終端符號"B"後的新狀態。新的狀態是4,完成此步驟後的堆疊是:  由於上一個終端符號 '+'尚未被處理,因此仍保留在輸入緩衝區中。依據動作表,在狀態4碰到 '+'時做r3化簡。根據第三條文法E → B,我們將4與"B"從堆疊彈出,回到狀態0。接著壓入"E",根據狀態轉移表,當狀態0遇到非終端符號"E"時需轉移至狀態3,因此將3壓入堆疊:  繼續尚未處理的符號 '+',當狀態3遇到 '+'時的對應動作是s6,將 '+'從輸入中移出並壓入堆疊,再將新的狀態6也壓入堆疊:  下一個符號是'1',在狀態6看到'1'時的動作是s2,將'1'從輸入中移出並壓入堆疊,再將新的狀態2也壓入堆疊:  最後看到的輸入符號是$,狀態2遇到$時的動作是r5,以第五條文法規則化簡堆疊內容。此化簡動作與第二步驟相似,堆疊彈出兩個元素後回到狀態6,這時再壓入符號"B"後會進入狀態8(根據狀態轉移表),因此也將8壓入堆疊:  在狀態8看到符號$時剖析器會繼續化簡,根據動作表執行r2化簡動作,採用第二條文法規則E → E + B簡化堆疊。由於該規則的右手邊有三個符號,故從堆疊中彈出六個元素。這時回到狀態0,將規則左邊的符號"E"推入堆疊後,進入新狀態3(根據狀態轉移表),將之壓入後堆疊為:  最後在狀態3看到符號$,對應的動作是acc,表示剖析順利完成。

  

  建構剖析表的過程須使用"LR(0)專案"(以下簡稱為「專案」),這些專案是在文法規則的右手邊插入一個特殊的符號「·」所產生。例如文法"E → E + B"有下列四個對應的專案:  若文法規則的形式是"A → ε",則對應的唯一專案是:  建立專案的用意是要決定剖析器的狀態,例如"E → E· + B"的意義是「剖析器已經在輸入的符號中認出"E"的部分,目前正等著看到一個 '+'符號與接續的"B"的部分」。

  在一般的情形中,剖析器不能預知未來要用哪一條文法規則來化簡堆疊內容,因此很難以單一個專案決定狀態。例如以下文法:  當剖析器認出堆疊中的"E"部分時,它無法預測未來會繼續看到 '+'或'*',因此這時的狀態須以兩個專案表示:  故我們使用專案的集合{ "E → E· + B", "E → E·* B" }來表示「剖析器認出"E"並期待 "+ B"或"* B"」的狀態。

  如前段敘述,剖析器總是期待在下個輸入中看到專案中的'·'之後的符號。如果'·'之後的符號是非終端符號,則應加入該符號所推演出的文法規則,如此才能正確的描述狀態。例如規則:  當我們來到狀態"E → E + ·B"時,剖析器期待看到非終端符號"B",而"B"又可推演為終端符號"0"與"1"。因此這時的狀態應表示為:  即是「已辨認出"E +"部分,目前期待看到"B",而"B"也就是'0'與'1'」之意。此現象可以描述為:  每個專案集合都應該以此規則擴充,將潛在的專案加到集合中直到所有在·之後的非終端符號都處理過。如此所產生的新集合稱作該專案集合的「封閉集」,符號的表示為closure("I"),其中"I"表示原專案集合。剖析過程中的各種狀態即是由這些封閉集所構成。

  在決定狀態間的轉移前,我們必須先加入一條擴充文法:  其中"S"是新的起始符號(start symbol)而"E"是原先的起始符號。這一做法是為了使剖析器能有一個唯一的起始狀態,例如考慮以下文法:  有三條規則從起始符號開始,剖析器不得不選擇一條作為起始狀態。加入擴充文法後,我們使用下列規則來決定專案集合與狀態:  可見起始狀態唯一確定。

  建構剖析表的第一步是找出封閉集合之間的轉移。封閉集可以視為自動機中的狀態,而狀態間的轉移則由終端符號與非終端符號決定。起始狀態是由擴充的第0條文法規則對應的專案所形成的封閉集:  集合中的第一個專案是該集合的核心,透過集合的封閉規則,我們加入其他專案補足集合使其封閉。這組封閉集合是第一個狀態(I0),現在我們要找出這組狀態可能的轉移情形。
LR剖析器是一種由下而上(bottom-up)的上下文無關語法剖析器。LR意指由左(Left)至右處理輸入字串,並以最右邊優先衍生(Right derivation)的推導順序(相對於LL剖析器)建構語法樹。能以此方式剖析的語法稱為LR語法。而在LR(k)這樣的名稱中,k代表的是剖析時所需前瞻符號(lookahead symbol)的數量,也就是除了目前處理到的輸入符號之外,還得再向右參照幾個符號之意;省略 (k)時即視為LR(1),而非LR(0)。