9. Deterministic Bottom-Up Parsing
名詞定義
handle：別識(shí)別出的字符串片段（segment）菲盾，和產(chǎn)生是規(guī)則（production rule）颓影。
操作符文法（operator grammar）：是一種上下文無關(guān)文法，每條產(chǎn)生式的右邊至少包含一個(gè)終結(jié)符或一個(gè)非終結(jié)符懒鉴，并且右邊的任意兩個(gè)非終結(jié)符都不相連诡挂。操作符文法中的終結(jié)符，稱為操作符（operator）临谱。
有界上下文文法（bounded-context grammar）：對(duì)歸約進(jìn)行了上下文限制璃俗，產(chǎn)生式 A -> α 的右邊 α，只有當(dāng)出現(xiàn)在合適的上下文 β_1 α β_2 中時(shí)悉默，才會(huì)被歸約為 A城豁。其中 β_1 稱為左上下文，β_2 稱為右上下文抄课，它們都是有限長(zhǎng)度的唱星，分別為 m，n跟磨。如果對(duì)于任意的 α魏颓，存在唯一確定的上下文 β_1 α β_2，就稱該文法為有界上下文文法吱晒，記為 BC(m,n)甸饱。
右界上下文文法（bounded-right context grammar）：如果有界上下文文法中的右邊界（right context）只包含終結(jié)符，該文法就稱為右界上下文文法，記為 BRC(m,n)叹话。
station：handle查找自動(dòng)機(jī)（handle-?nding automata）的一種狀態(tài)偷遗，它表示只有通過ε 字符轉(zhuǎn)入的邊，沒有跳轉(zhuǎn)出去的邊驼壶。
不充分狀態(tài)（inadequate state）：確定性自動(dòng)機(jī)中的氏豌，包含歧義的狀態(tài)。
LR(0)文法：可以構(gòu)造一個(gè)不含歧義狀態(tài)LR(0)自動(dòng)機(jī)的文法热凹，稱為L(zhǎng)R(0)文法泵喘。
LR(1)文法：通過前瞻一個(gè)字符，可以得到一個(gè)不含歧義的LR(1)自動(dòng)機(jī)般妙，這樣的文法稱為L(zhǎng)R(1)文法纪铺。
item look-ahead：當(dāng)前推導(dǎo)后面可以跟的字符串的集。
dot look-ahead：當(dāng)前解析位置碟渺，后面可以跟的字符串集鲜锚。
LALR(1)文法：帶前瞻特性的LR(0)解析器（Look Ahead LR(0) with a look-ahead of 1 token）
LA(k)LR(j)文法：LA(k)表示右上下文（前瞻），LR(j)表示左上下文（狀態(tài)機(jī)）苫拍。LALR(1)實(shí)際上是LA(1)LR(0)芜繁，LALR(k)是LA(k)LR(0)。
內(nèi)容總結(jié)
確定性自底向上解析器的主要任務(wù)是尋找handle绒极，一定handle確定下來骏令，解析方法也就確定下來了。
對(duì)自底向上解析來說垄提，語義動(dòng)作（semantic actions）在的歸約（reduction）時(shí)觸發(fā)的榔袋，在產(chǎn)生式被確定的那一刻。
優(yōu)先級(jí)解析（precedence parsing）的關(guān)鍵在于確定優(yōu)先級(jí)關(guān)系（precedence relation）塔淤，或優(yōu)先級(jí)表（precedence table）。
操作符文法中的優(yōu)先級(jí)關(guān)系速妖，也可以用優(yōu)先級(jí)函數(shù)（precedence function）來表示高蜂，占用更少的空間。
LR解析器的重要部分是一個(gè)狀態(tài)機(jī)（handle-?nding automata）罕容，它可以由任意的上下文無關(guān)文法構(gòu)造出來备恤，它表示任意的非終結(jié)符接受任意字符會(huì)跳轉(zhuǎn)到哪個(gè)狀態(tài)（包括ε 字符）。
狀態(tài)機(jī)的狀態(tài)數(shù)锦秒，與語法中的非終結(jié)符數(shù)目成正比露泊。
根據(jù)文法，我們可以先得到一個(gè)非確定性狀態(tài)機(jī)旅择，然后通過子集構(gòu)造法（subset construction）惭笑，轉(zhuǎn)換成確定性自動(dòng)機(jī)。
借助確定性狀態(tài)機(jī)，可以得到LR(0)解析算法沉噩。
（1）如果當(dāng)前狀態(tài)不是接受狀態(tài)捺宗，則讀取下一個(gè)字符。
（2）如果是接受狀態(tài)川蒙，則從彈出一個(gè)狀態(tài)蚜厉，以及相應(yīng)長(zhǎng)度的輸入字符串，進(jìn)行一次歸約畜眨，再把歸約后的非終結(jié)符壓棧昼牛。
確定性狀態(tài)機(jī)的行為，經(jīng)常表示成兩個(gè)表ACTION和GOTO康聂，ACTION表示歸約或移入字符贰健，GOTO表示當(dāng)前狀態(tài)接受字符后跳轉(zhuǎn)到哪個(gè)狀態(tài)。
LR(0)根據(jù)當(dāng)前字符的所有左上下文早抠，來判斷歸約方式霎烙，相當(dāng)于具有無窮長(zhǎng)左邊界的右界上下文文法 BRC(∞,0)。
LR(0)對(duì)應(yīng)的確定性自動(dòng)機(jī)的接受狀態(tài)可能是有歧義的蕊连，包括兩種：shift/reduce歧義性（shift還是reduce都可行）悬垃，reduce/reduce歧義性（兩種reduce方式）。
包含空串規(guī)則（ε-rules）的文法不是LR(0)的甘苍，解決方法可以采用動(dòng)態(tài)解析（dynamically parse）檢查當(dāng)前的狀態(tài)棧尝蠕。
由于LR(0)的要求比較嚴(yán)格，所以只有很少的文法是LR(0)的载庭。
因此看彼，可以加入前瞻機(jī)制，來提升解析器的能力囚聚，通過前瞻一個(gè)字符得到解析器稱為L(zhǎng)R(1)解析器靖榕。
LR(1)自動(dòng)機(jī)，也可以表示為兩個(gè)表ACTION和GOTO顽铸。
LR(1)解析器有足夠的能力處理空串規(guī)則（ε-rules）茁计。
LR(k>1)不是簡(jiǎn)單的LR(1)擴(kuò)展，需要引入兩種前瞻：item look-ahead 和 dot look-ahead谓松。
對(duì)于LR(1)而言星压，dot look-ahead 與 item look-ahead 是同一個(gè)集合。
LR(k)文法的性質(zhì)：
（1）LR(k>1)鬼譬，總是轉(zhuǎn)換為L(zhǎng)R(k-1)娜膘，但是LR(1)卻不總是能轉(zhuǎn)換成LR(0)。
（2）下推自動(dòng)機(jī)可解析的語言优质，是LR(1)的竣贪，也稱為確定性語言（deterministic languages）军洼。
（3）任何用確定性方法可解析的語言，都是LR(1)的贾富。
（4）LR(k)是目前能力最強(qiáng)大的解析器歉眷。
LR(1)的缺點(diǎn)是，占用了太多了內(nèi)存空間颤枪。
一個(gè)簡(jiǎn)單的文法對(duì)應(yīng)的自動(dòng)機(jī)汗捡，可能會(huì)包含成千上萬個(gè)狀態(tài)。
LALR(1)是LR(0)自動(dòng)機(jī)和前瞻方法的合并畏纲，狀態(tài)數(shù)與LR(0)一樣扇住。
構(gòu)建LALR(1)解析表的通常方法是，先構(gòu)造LR(1)解析表盗胀，然后再進(jìn)行狀態(tài)合并艘蹋，這個(gè)方法比較繁瑣。
另外還有一些常見的解析表構(gòu)造方法：
（1）一個(gè)簡(jiǎn)單的算法：在構(gòu)造解析表的時(shí)候票灰，避免重復(fù)的狀態(tài)
（2）yacc使用的channel算法
（3）relations算法：對(duì)LR(0)狀態(tài)機(jī)進(jìn)行調(diào)整女阀，找到不充分的狀態(tài)（inadequate state）消除歧義。具體處理方法比較復(fù)雜：包括lookback relation和includes relation屑迂。
（4）通過文法變化浸策，把LALR(1)轉(zhuǎn)換成SLR(1)。
SLR(1)解析器的能力介于LR(0)和LALR(1)之間惹盼，但是SLR(1)解析器的大小卻跟LALR(1)差不多庸汗。所以，LALR(1)更常見手报。
