自底向上分析把一個輸入符號串逐步歸約到文法的開始符-在線瀏覽
2024-08-31 08:47本頁面
【正文】 S S?aABe ? aAde ? aAbcde? abbcde a b b c d e ?abbcde A ?aAbcde A ?aAde B S ?aABe S S A ? ? w ?Aw? ? ?w 已知 ? ?w， 分 析已識別出 ?，產(chǎn)生式 A? ? 的右部 ?， 再看待輸入串 w的最左邊符號，用 A替 換 ?得到 ?Aw； 自上而下分析是 從w A?， 看 FIRST(?), w A? ? w ? ? 定義 假定 ?是文法 G的一個句子。 如果文法 G是無二義的，那么，規(guī)范推導 (最右推導 )的逆過程必是規(guī)范歸約 (最左歸約 )。 句柄的“最左”特征使得在移進 歸約方法中，它處于符號棧的棧頂。例如， 文法 G[E]: E→ E＋ E ? E*E ?(E) ? id 句子 id＋ id*id有二個不同的最右推導 : E?E+E E?E*E ? E＋ E*E ? E *id ? E＋ E*id3 ? E+E*id ? E+id2*id3 ? E+id*id ? id1+id2*id3 ? id1+id2*id3 句型 E＋ E*id3中 ，句柄不 唯一 。 “移進 歸約”分析法的棧實現(xiàn) “移進一歸約 ” 分析器使用一個棧和一個存放輸入符號串 w的緩沖器。這種歸約可能持續(xù)多次，直至棧頂不再呈現(xiàn)句柄為止。 規(guī)范句型 (右句型 )的“活前綴” ,定義如下 : 定義 4． 4 一個規(guī)范句型的一個前綴，若不含句柄之后的任何符號 ，則稱它為該規(guī)范句型的一個 活前綴 。而且棧里的文法符號串正好是這個句型的一個活前綴。 “移進 歸約”分析識別規(guī)范句型的活前綴。 G[E]: E→ E＋ E|EE|E*E|E/E|E?E|(E)|E|id 是算符文法。因右部 EAE具有相鄰的非終結(jié) 符號。 文法的句子 id＋ id－ id*(id＋ id)的歸約過程為： (1)id＋ id－ id*〔 id＋ id ) (2) E＋ id－ id*(id＋ id ) (3) E＋ E－ id*(id＋ id ) (4) E－ id*(id＋ id ) (5) EE*(id＋ id) (6) EE*(E＋ id) (7) EE*(E＋ E) (8) E－ E*(E) (9) E－ E* E (10) E－E (11) E 這個歸約過程是唯一的 。一旦確定了這種優(yōu)先關系，就可以借助這種關系去尋找可歸約串并進行歸約。例如， a＜ a， 例如： + +。 利用算符優(yōu)先關系尋找右句型的可歸約串 算符文法右句型的形式為（可以證明） β0a1β1a2β2… anβn 其中， βi?VN?{?}, an ?VT 。,=, 進而， ＄作為每一個右句型符號串的左右分界符，算 符文法右句型的形式為： ＄ β0a1β1a2β2… anβn ＄ 并規(guī)定，
物理相關推薦
鄂ICP備17016276號-1