自底向上的語法分析
從分析樹的底部(葉節(jié)點(diǎn))向頂部(根節(jié)點(diǎn))方向構(gòu)造分析樹
可以看成是將輸入串w歸約為文法開始符號(hào)S的過程
自頂向下的語法分析采用最左推導(dǎo)方式，自底向上的語法分析采用最左歸約方式（反向構(gòu)造最右推導(dǎo)）救巷。
自底向上語法分析的通用框架移入-歸約分析 (Shift-Reduce Parsing)
分析過程中一旦句柄在棧頂形成就馬上進(jìn)行歸約操作蝇狼，保證了每一步的歸約都是最左歸約。關(guān)于什么是句柄可以查看文章 句柄與移入-歸約分析的關(guān)系棒坏。
最左歸約是最右推導(dǎo)的逆過程，最右推導(dǎo)的每一步得到的符號(hào)串都是一個(gè)句型我們稱之為最右句型或者是規(guī)范句型，因此最左歸約得到符號(hào)串也是規(guī)范句型摘盆。
因此棧內(nèi)符號(hào)串+剩余輸入=“規(guī)范句型”，在自底向上的分析過程中每次歸約的符號(hào)串是當(dāng)前句型的直接短語饱苟。
移入-歸約分析的工作過程
在對(duì)輸入串的一次從左到右掃描過程中孩擂，語法分析器將零個(gè)或多個(gè)輸入符號(hào)移入到棧的頂端，直到它可以對(duì)棧頂?shù)囊粋€(gè)文法符號(hào)串β進(jìn)行歸約為止箱熬。
然后类垦，它將β歸約為某個(gè)產(chǎn)生式的左部。
語法分析器不斷地重復(fù)這個(gè)循環(huán)城须，直到它檢測(cè)到一個(gè)語法錯(cuò)誤蚤认，或者棧中包含了開始符號(hào)且輸入緩沖區(qū)為空(當(dāng)進(jìn)入這樣的格局時(shí)，語法分析器停止運(yùn)行糕伐，并宣稱成功完成了語法分析)砰琢。
移入-歸約分析器可采取的4種動(dòng)作
移入：將下一個(gè)輸入符號(hào)移到棧的頂端
歸約：被歸約的符號(hào)串的右端必然處于棧頂。語法分析器在棧中確定這個(gè)串的必然處于棧頂。語法分析器在棧中確定這個(gè)串的 左端氯析，并決定用哪個(gè)非終結(jié)符來替換這個(gè)串亏较，并決定用哪個(gè)非終結(jié)符來替換這個(gè)串。
接收：宣布語法分析過程成功完成掩缓。
報(bào)錯(cuò)：發(fā)現(xiàn)一個(gè)語法錯(cuò)誤雪情，并調(diào)用錯(cuò)誤恢復(fù)子例程。
問: 開始沒有分析樹我怎么知到棧頂符號(hào)串是不是句柄你辣？如果有分析樹說明句型符合文法那我還有做分析的必要巡通？
答: 這就需要LR分析法，去解決上述問題舍哄⊙缌梗可參考文章 LR分析法概述
