歸約

定義：我們可以將自底向上語(yǔ)法分析過(guò)程看成是建一個(gè)串w“歸約”慰問(wèn)發(fā)開(kāi)始符號(hào)的過(guò)程，在歸約中，一個(gè)與某產(chǎn)生式體相匹配的特定子串被替換為該產(chǎn)生式的頭部的非終結(jié)符號(hào)。
定義理解起來(lái)比較晦澀，我們來(lái)看個(gè)例子就知道了。
已知有文法

E ——> E + T | T
T ——> T * F | F
F ——> ( E ) | id

他的產(chǎn)生式為 id * id
那么歸約過(guò)程為：

id * id =》 F * id =》 T * id =》 T * F =》 T =》 E

顯而易見(jiàn)，這就是一個(gè)反向的最右推導(dǎo)。

句柄

定義：如果有S=》αAw=》αβw，那么緊跟α的產(chǎn)生式A->β是αβw的一個(gè)句柄。
特性：
1）句柄右邊的串w一定只包含終結(jié)符號(hào)。
2）如果一個(gè)文法無(wú)二義性，那么該文法的每個(gè)右句型都有且只有一個(gè)句柄。

例如，對(duì)于上述例子而言

• id₁ * id₂ 句柄為 id₁
• F * id₂ 句柄為 F
• T * id₂ 句柄為 id₂
• T * F 句柄為 T * F
• T 句柄為 T

移入——?dú)w約分析技術(shù)

移入——?dú)w約語(yǔ)法分析是自底向上語(yǔ)法分析的一種形式。他使用一個(gè)棧來(lái)保存文發(fā)符號(hào)，并用一個(gè)輸入緩沖區(qū)來(lái)存放將要進(jìn)行語(yǔ)法分析的其余符號(hào)。
其分析器會(huì)采取以下四中動(dòng)作：

1. 移入（shift）：將下一個(gè)輸入符號(hào)移入到棧頂端。
2. 歸約（reduce）：被歸約的符號(hào)串右端必然是棧頂。語(yǔ)法分析器在棧中確定這個(gè)串的左端并決定用哪個(gè)非終結(jié)符號(hào)來(lái)替換這個(gè)串。
3. 接受（accept）：宣布語(yǔ)法分析過(guò)程成功完成。
4. 報(bào)錯(cuò)（error）：發(fā)現(xiàn)一個(gè)語(yǔ)法錯(cuò)誤，并調(diào)用一個(gè)錯(cuò)誤恢復(fù)。

還是以上述為例，展現(xiàn)一個(gè)完整的推導(dǎo)過(guò)程。

分析過(guò)程

當(dāng)然，這種語(yǔ)法中也存在沖突
1）移入/歸約沖突：無(wú)法確定進(jìn)行移入還是歸約操作
2）歸約/歸約沖突：多個(gè)可能歸約中無(wú)法確定
對(duì)于沖突，我們后續(xù)也會(huì)用不同的具體LR語(yǔ)法來(lái)解決。