[理學(xué)]第四章2自下而上語(yǔ)法分析(完整版)
【正文】 終結(jié)符代替 ， 稱為 歸約 。 – 與最右歸約對(duì)應(yīng)。實(shí)際上，不同的找可歸約串的方法，構(gòu)成了不同的分析算法。 – 歸約就是將棧頂?shù)囊淮?hào)用文法產(chǎn)生式的左部代替，歸約可能重復(fù)多次，然后繼續(xù)移進(jìn)。 E=E+T =E+T*F =E+T*id =E+F*id =E+id*id =T+id*id =F+id*id =id+id*id 動(dòng)作 棧 輸入緩沖區(qū) 1) 準(zhǔn)備 id1+id2*id3 2) 移進(jìn) id1 +id2*id3 3) 歸約 F→id F +id 2*id3 4) 歸約 T→F T +id 2*id3 5) 歸約 E→T E +id 2*id3 6) 移進(jìn) E+ id2*id3 7) 移進(jìn) E+id2 *id3 8) 歸約 F→id E+F *id 3 9) 歸約 T→F E+T *id 3 10) 移進(jìn) E+T* id3 11) 移進(jìn) E+T*id3 12) 歸約 F→id E+T*F 13) 歸約 T→T*F E+T 14) 歸約 E→E+T E 15) 接受 所得的結(jié)果是：用產(chǎn)生式序列表示語(yǔ)法分析樹 (1) EE+T|T (2) TT*F|F (3) F(E)|id id1 + id2 * id3 F T E F T F T E 移進(jìn)歸約分析中的問題 ? 1) 移進(jìn) 歸約沖突 – 在分析到某一步時(shí)，既可以移進(jìn)，又可以歸約 – 上例第 10)步可以移進(jìn) *，也可以按產(chǎn)生式E→E+T 進(jìn)行歸約。 如果以上四種關(guān)系中的任意兩種都不會(huì)同時(shí)成立，則可以根據(jù)終結(jié)符號(hào)之間的歸約關(guān)系進(jìn)行語(yǔ)法分析。a * * * * * * * ? 在優(yōu)先表中，空白部分是一種錯(cuò)誤關(guān)系 ? 相同的終結(jié)符之間的優(yōu)先關(guān)系不一定是 ? 如果有 a b,不一定有 b a(不具傳遞性 )， 因?yàn)橹欢x相鄰運(yùn)算符之間的優(yōu)先關(guān)系， a,b相鄰時(shí)，不一定 b,a相鄰。 – 若產(chǎn)生式右部有 ...aP...的形式 ,則對(duì)于每個(gè) b∈FIRSTVT(P) 都有 a b(優(yōu)先集 ) – 若產(chǎn)生式右部有 ...Pb的形式 ,則對(duì)于每個(gè)a∈LASTVT(P) 集 ,都有 a b – 若產(chǎn)生是形如： A→…ab… 或 A→…aBb…形式，則有 a b ? 構(gòu)造優(yōu)先關(guān)系表的 算法如下： For 每條形如 P?X1X2…X n的 產(chǎn)生式 do for i =1 to n1 do begin if Xi和 Xi+1都是終結(jié)符 then Xi = Xi+1 if i= n2 且 xi和 Xi+2都是終結(jié)符 , Xi+1為非終結(jié)符 then Xi = Xi+2 if Xi為終結(jié)符 , Xi+1為非終結(jié)符 then for firstVT中的每個(gè)元素 a do Xi a 。 ? (leftmost prime phrase)：是指位于句型最左邊的那個(gè)素短語(yǔ)。 If s[k] ∈ Vt THEN j:=k ELSE j:=k1。 end。 算符優(yōu)先分析法小結(jié) ? 優(yōu)點(diǎn) – 簡(jiǎn)單、效率高 – 能夠處理部分二義性文法 ? 缺點(diǎn) – 文法書寫限制大 – 占用內(nèi)存空間大 – 不規(guī)范、存在查不到的語(yǔ)法錯(cuò)誤 設(shè)文法為： E’→E T→F E→E+T F→P↑F|P E→T P→（ E ） T→T*F P→I 求算符優(yōu)先關(guān)系表 。 UNTIL a=‘’。 if s[j1] ∈ Vt THEN j:=j1 else j:=j2。 其中： T+T*F (含 T*F素短語(yǔ) )、 T+T*F+i (含 T*F素短語(yǔ) ) 和 T(不含終結(jié)符 )也不是素短語(yǔ) T*F為 最左素短語(yǔ) 。 end。 構(gòu)造 FIRSTVT集 算法 : ? 按照下面兩條 規(guī)則 來構(gòu)造 FIRSTVT集： – ① 若有產(chǎn)生式 Pa...或 PQa...,則 a∈FIRSTVT(P) – ② 若有產(chǎn)生式 PR...,則 FIRSTVT(R)包含在 FIRSTVT(P)中 a b c P Q 所有終結(jié)符
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1