句柄/可歸約串(handle)
當你組裝模型、桌上有好幾個零件鬆散擺著時,只有一種組合是接下來該黏起來的正確組合,那個符合說明書、且能讓其餘部分仍可組裝的組合。在由下而上剖析中,句柄就是那個正確的下一步組合:你在這一步該歸約的確切子字串,以及該用來歸約它的規則,好讓你留在通往有效剖析的路上。
更精確地說,由下而上剖析過程中,堆疊內容加上未讀的輸入構成一個句型,一個由起始符號可推導出的字串。句柄是匹配某產生式 A -> alpha 右側的子字串,且位於這樣的位置:在此歸約它(以 A 取代 alpha)會還原最右推導的一步。重點是並非每個匹配都是句柄。堆疊中可能含有恰好匹配某規則右側的符號,但在那裡歸約卻是會讓剖析出軌的錯誤;句柄是內容正確、位置也正確的那唯一一個匹配。找出句柄正是移位-歸約剖析器每一步必須做的移位或歸約決定。
整套 LR 剖析機制的存在就是為了自動辨識句柄。由文法建出的 LR 狀態機追蹤足夠的脈絡,使得在給定目前狀態與下一個前瞻詞符時,它知道堆疊頂端是否為一個可歸約的句柄,或它必須先移位更多輸入。當文法使這件事變得歧義時,一個句柄能以兩種方式歸約,或無法確定該移位還是歸約,結果便是歸約-歸約或移位-歸約衝突。
用 E -> E + E | num 剖析 num + num,歸約第一個 num 後,堆疊與輸入讀作 E + num。句柄是右邊那個孤立的 num(以 E -> num 歸約),此刻還不是 E + num,因為太早歸約會讓剖析卡住。直到那之後,E + E 才成為 E -> E + E 的句柄。
句柄是接下來該歸約的正確子字串「且」正確位置,而非任何規則匹配。
匹配某規則右側的子字串不會自動成為句柄:位置很重要。歸約一個非句柄的匹配是會破壞剖析的錯誤動作,這也是為何找句柄需要 LR 狀態機,而不只是樣式匹配。