SLR(1)分析

SLR(1) SLR(1) SLR(1)

簡介

簡單 LR(1) 分析,或 SLR(1) 分析,也如上一節中一樣使用了 LR (0) 項目集合的 DFA 。但是,通過使用輸入串中下一個記號來指導它的動作,它大大地提高了 LR(0) 分析的能力。它通過兩種方法做到這一點。首先,它在一個移進之前先考慮輸入記號以確保存在著一個恰當的 DFA 。其次,使用構造的非終結符的 Follow 集合來決定是否應執行一個歸約。令人吃驚的是,先行的這個簡單套用的能力強大得足以分析幾乎所有的一般的語言構造。定義:SLR(1) 分析算法(SLR(1) parsing algorithm)。令s 為當前狀態(位於分析棧的頂部)。

定義

則動作可定義如下:
(1)若狀態s 包含了格式A →a.Xb 的任意項目,其中X 是一個終結符,且X 是輸入串中的下一個記號,則動作將當前的輸入記號移進到棧中,且被壓入到棧中的新狀態是包含了項目A →aX.b 的狀態。
(2)若狀態s 包含了完整項目A →g.,則輸入串中的下一個記號是在 Follow (A) 中,所以動作是用規則A →g 歸約。用規則S¢ →S 歸約與接受等價,其中S 是開始狀態;只有當下一個輸入記號是$時,這才會發生。在所有的其他情況中,新狀態都是如下計算的:刪除串a 和所有它的來自分析棧中的對應狀態。相對應地,DFA 回到a 開始構造的狀態。通過構造,這個狀態必須包括格式B →g. Ab 的一個項目。將A 壓入到棧中,並將包含了項目B →aA.b 的狀態壓入。
(3)若下一個輸入記號都不是上面兩種情況所提到的,則聲明一個錯誤。若上述的 SLR(1) 分析規則並不導致二義性,則文法為 SLR(1) 文法(SLR(1) grammar)。

相關詞條

相關搜尋

熱門詞條

聯絡我們