[理學(xué)]第四章2自下而上語(yǔ)法分析(參考版)
2024-10-19 22:57本頁(yè)面
【正文】 算符優(yōu)先分析法小結(jié) ? 優(yōu)點(diǎn) – 簡(jiǎn)單、效率高 – 能夠處理部分二義性文法 ? 缺點(diǎn) – 文法書(shū)寫(xiě)限制大 – 占用內(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)系表 。 ? 可能將本來(lái)不是句子的輸入串誤認(rèn)為是句子。即無(wú)法使用單非產(chǎn)生式 (如： T?F)進(jìn)行歸約。 UNTIL a=‘’。 end。 END If s[j] a or s[j] = a THEN begin k:=k+1。 把 s[j+1]….s[k] 歸約為某個(gè) N； k:=j+1。 if s[j1] ∈ Vt THEN j:=j1 else j:=j2。 If s[k] ∈ Vt THEN j:=k ELSE j:=k1。s[k] = ‘’。 – 此時(shí) ,形如 :Nj aj Nj+1 aj+1.....Ni ai Ni+1的子串即為 最左素短語(yǔ) ，應(yīng)被歸約。 其中： T+T*F (含 T*F素短語(yǔ) )、 T+T*F+i (含 T*F素短語(yǔ) ) 和 T(不含終結(jié)符 )也不是素短語(yǔ) T*F為 最左素短語(yǔ) 。 ? (leftmost prime phrase)：是指位于句型最左邊的那個(gè)素短語(yǔ)。 ? 柄。 ? 分析的方法 ：根據(jù)優(yōu)先性“高于”來(lái)識(shí)別句柄的頭，根據(jù)優(yōu)先性“低于”來(lái)識(shí)別句柄的尾。 end。 – 若產(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 。 (P,a)進(jìn)棧 end。 End. PROCEDURE insert(P,a)。 構(gòu)造 FIRSTVT集 算法 : ? 按照下面兩條 規(guī)則 來(lái)構(gòu)造 FIRSTVT集： – ① 若有產(chǎn)生式 Pa...或 PQa...,則 a∈FIRSTVT(P) – ② 若有產(chǎn)生式 PR...,則 FIRSTVT(R)包含在 FIRSTVT(P)中 a b c P Q 所有終結(jié)符 所有非終結(jié)符 數(shù)組值為真假，為真的條件是 c ∈FIRSTVT (Q) ? 通過(guò)構(gòu)造一個(gè)二維數(shù)組 F來(lái)實(shí)現(xiàn) ,該從數(shù)組 F反映任何一個(gè)非終結(jié)符 P的 FIRSRVT集中的元素。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相鄰。 ? 構(gòu)造優(yōu)先關(guān)系表的方法： – ①按照定義手工計(jì)算 – ②使用算法 ? 由 F(E) 得 ( = ) T = i, 得 + i T = T*F, 得 + * T = (E), 得 + ( 由 EE+T E = i, 得 i + E = E+T, 得 + + E = T*F, 得 * + E = (E), 得 ) + + * i ( ) + * i ( ) 例 : P: EE+T|T TT*F|F F(E)|i 求算符優(yōu)先表。 ? – 算符文法 G的任何終結(jié)符 a,b之間要么沒(méi)有優(yōu)先關(guān)系，若有優(yōu)先關(guān)系 ,至多有 = , , 中的一種成立 ,則 G為一 算符優(yōu)先文法 。 ? 的定義 (自底向上 ,可通過(guò)樹(shù)形結(jié)構(gòu)觀察 ) ① a b,G中有 P...ab...或 P...aQb... (在同一產(chǎn)生式中 ) ② a b,G中有 P...aR...的產(chǎn)生式 ,且 R=b...或R=Qb... (注意 ab相鄰 ) ③ a b,G中有 P...Rb.
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1