[理學(xué)]第四章2自下而上語法分析-資料下載頁
2024-10-16 22:57本頁面
【正文】 1≮ ai, ai≡ ai+1≡ ….. ≡ aj1≡ aj ， aj≯ aj+1 該定理說明了最左素短語與周圍符號(hào)之間的關(guān)系 ? 例 :文法 G ? EE+T|T TT*F|F F(E)|i ? 句型 T+T*F+i的語法樹如圖： E E T + E + T F T T * F P i 根據(jù)語法樹可知： 句型 T+T*F+i的 短語 有： T — 相對(duì)非終結(jié)符 E的短語 T*F — 相對(duì)非終結(jié)符 T的短語 T+T*F — 相對(duì)非終結(jié)符 E的短語 i — 相對(duì)非終結(jié)符 P、 F、 T的短語 T+T*F+i —相對(duì)非終結(jié)符 E的短語 根據(jù) 素短語 的定義可知： i和 T*F為素短語。 其中： T+T*F (含 T*F素短語 )、 T+T*F+i (含 T*F素短語 ) 和 T(不含終結(jié)符 )也不是素短語 T*F為 最左素短語 。 ? ： (根據(jù)最左素短語的定義 ) – 句型 的一般形式 : N1a1N2a2...NnanNn+1(ai為終結(jié)符 ,Ni為可有可無的非終結(jié)符 ) – 從左向右掃描各符號(hào) ,依次查看算符優(yōu)先矩陣 ,直至找到滿足 ai ai+1的終結(jié)符為止 ,一直移進(jìn) .再從 ai開始往左掃描 ,直至找到滿足關(guān)系 aj1 aj的終結(jié)符為止 ,進(jìn)行歸約。 – 此時(shí) ,形如 :Nj aj Nj+1 aj+1.....Ni ai Ni+1的子串即為 最左素短語 ，應(yīng)被歸約。 – 分析過程的結(jié)束 ：分析棧中為 S，輸入串為 ? 例 : EE+T|T TT*F|F F(E)|i ? 把 入棧 ,讀一符號(hào) i, 因?yàn)? i, 所以把 i入棧 ? 因?yàn)?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。s[k] = ‘’。 Repeat a := 下一個(gè)輸入符號(hào) 。 If s[k] ∈ Vt THEN j:=k ELSE j:=k1。 WHILE s[j] a DO BEGIN repeat q:=s[j]。 if s[j1] ∈ Vt THEN j:=j1 else j:=j2。 UNTIL s[j] q。 把 s[j+1]….s[k] 歸約為某個(gè) N； k:=j+1。 s[k] := N。 END If s[j] a or s[j] = a THEN begin k:=k+1。 s[k]:=a。 end。 else error。 UNTIL a=‘’。 ? 算符優(yōu)先分析一般并不等價(jià)于規(guī)范規(guī)約 ? 并不對(duì)文法的非終結(jié)符定義優(yōu)先關(guān)系，無法發(fā)現(xiàn)由單個(gè)非終結(jié)符組成的“可歸約串”。即無法使用單非產(chǎn)生式 (如： T?F)進(jìn)行歸約。 ? 算符優(yōu)先分析比規(guī)范歸約過程要快，跳過了所有的單非產(chǎn)生式。 ? 可能將本來不是句子的輸入串誤認(rèn)為是句子。 ? 總結(jié)歸約的策略 : 在文法中尋找這樣的產(chǎn)生式 : 它的右部形如 :uj aj uj+1 aj+1... ui ai ui+1,其中每個(gè)終結(jié)符號(hào)與最左素短語對(duì)應(yīng)位置上的 終結(jié)符號(hào)完全相同 ,而每一個(gè) 非終結(jié)符號(hào) uk應(yīng)與相應(yīng)位置上的非終結(jié)符號(hào) Nk相對(duì)應(yīng) ,不必完全相同 。 算符優(yōu)先分析法小結(jié) ? 優(yōu)點(diǎn) – 簡單、效率高 – 能夠處理部分二義性文法 ? 缺點(diǎn) – 文法書寫限制大 – 占用內(nèi)存空間大 – 不規(guī)范、存在查不到的語法錯(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)系表 。 (分析過程見呂映芝課本 ) 練習(xí)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1