[理學(xué)]第四章2自下而上語法分析-免費閱讀
【正文】 ? 算符優(yōu)先分析比規(guī)范歸約過程要快，跳過了所有的單非產(chǎn)生式。 s[k] := N。 – 分析過程的結(jié)束 ：分析棧中為 S，輸入串為 ? 例 : EE+T|T TT*F|F F(E)|i ? 把 入棧 ,讀一符號 i, 因為 i, 所以把 i入棧 ? 因為 i + ,所以歸約 :Fi ? 因 + , 所以 +入棧 ? 因 + i , 所以 i入棧 ? 因 i * , 所以歸約 :Fi ? 因 + * , 所以 *入棧 ? 因 * i , 所以 i入棧 ? 因 i , 所以歸約 :Fi ? 因 * , 所以歸約 :TF*F ? 因 + , 所以歸約 :ET+F ? 分析成功 求 i+i*i的算符優(yōu)先分析過程 棧 輸入緩沖區(qū) i+i*i i +i*i F +i*i F+ i*i F+i *i F+F *i F+F* i F+F*i F+F*F F+T E k:=1。各種優(yōu)先關(guān)系已經(jīng)存于優(yōu)先關(guān)系表中。 IF not F[P,a] then begin f[p,a] = true。 算符優(yōu)先關(guān)系表 的構(gòu)造 ? 用表格形式來表示各終結(jié)符號的優(yōu)先關(guān)系，這種表稱為優(yōu)先表。 (2) a優(yōu)先性高于 b， 記作 a b。 規(guī)范歸約：使用 句柄 來定義可歸約串 算符優(yōu)先：使用 最左素短語 來定義可歸約串 ? 自下而上語法分析主要有以下三種方法： ① 簡單優(yōu)先分析法 (規(guī)范歸約 )—— 文法按 一定原則規(guī)定文法符號的優(yōu)先關(guān)系 ②算符優(yōu)先分析法 (不規(guī)范歸約 )—— 規(guī)定 算符 之間的優(yōu)先關(guān)系 ③ LR分析法（規(guī)范歸約） —— LR(0)、LR(1)、 SLR(1)和 LALR(1) 語法分析樹的生成演示 a b b c d e A A B S A→b A→Abc B→d S→aABe (1)S ? aABe (2)A ? b (3)A ? Abc (4)B ? d S ? aABe ? aAde ? aAbcde ? abbcde 規(guī)范歸約相關(guān)概念復(fù)習(xí) ? 有文法 G，開始符號為 S, 如果有 S=xβ y,則 xβ y是文法 G的 句型 ， x,y是任意的符號串 ? 如果有 S=xAy, 且有 A=β ,則 β 是句型 xβ y相對于非終結(jié)符 A的 短語 ? 如果有 S=xAy, 且有 Aβ ,則 β 是句型 xβ y相對于Aβ 的 直接短語 ? 位于 一個 句型最左邊的直接短語稱為 句柄 . ? 句型 短語 直接短語 句柄 * * + * 注 : 每次歸約的部分就是分析為 句柄 的字符串 (最右推導(dǎo) )。 ? 注意：決定移進和歸約的依據(jù)是什么？ 棧頂是否出現(xiàn)了可歸約的符號串。 a b a A a b A a c b A a A a d A a B A a e B A a S 1 移進a 2 移進b 3 歸約2 4 移進b 5 移進c 6 歸約3 7 移進d 8 歸約4 9 移進e 10 歸約1 ―移進 歸約”分析法中棧的使用 ? 移進 歸約分析器使用了一個符號棧和一個輸入緩沖區(qū) ? 句型表示 a1 a2 a3 …… … X1 X2 X3 ―移進 歸約” 分析程序 輸出 棧(存放句型前綴) 輸入串 符號棧內(nèi)容 + 輸入緩沖區(qū)內(nèi)容 ＝ 當(dāng)前句型 一般形式： 符號棧的內(nèi)容 剩余輸入串 初態(tài)： 輸入串 終態(tài)： S ? 分析器結(jié)構(gòu) ? 3. 過程描述： do{ do { 將輸入串最左邊的符號移入棧內(nèi) 。 – 從 語法樹的角度 看：從語法樹的 樹葉 開始 ， 逐步向上歸約 構(gòu)造分析樹 ， 直到形成根結(jié)點 。 是推導(dǎo) 的逆過程 。} while (在棧里符號串中找到一個可歸約串 )； 歸約可歸約串 while （文法開始符號出現(xiàn)在棧頂或者發(fā)現(xiàn)錯誤）； ? 分析成功的條件 ：棧頂為文法符號，輸入串為空。 ? ―移進 —歸約”語法分析小結(jié)： – 從輸
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1