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