簡單優(yōu)先和算符優(yōu)先分析方法

1、 編譯原理1編譯原理編譯原理主 講：溫 璞責(zé)任教師：蔣慧平 編譯原理2第六講第六講簡單優(yōu)先和算符簡單優(yōu)先和算符優(yōu)先分析方法優(yōu)先分析方法 編譯原理3本講主要內(nèi)容本講主要內(nèi)容i簡單優(yōu)先文法及其分析算法i算符優(yōu)先文法及其分析算法i優(yōu)先函數(shù)的構(gòu)造 編譯原理4簡單優(yōu)先文法簡單優(yōu)先文法之所以稱為簡單是因?yàn)樵诳赡芊Q為句柄的那些符號(hào)串兩邊各取一個(gè)符號(hào)就能幫助判斷它是否是句柄 編譯原理5簡單優(yōu)先分析算法描述簡單優(yōu)先分析算法描述 編譯原理6例例6.13 運(yùn)用簡單優(yōu)先分析算法檢查運(yùn)用簡單優(yōu)先分析算法檢查(a),a)是否是文法是否是文法G42的一個(gè)句子的一個(gè)句子文法G42S：S(R)|a| RTTS,T|S 編譯原理

2、7i簡單優(yōu)先分析方法的局限性 只適用于簡單優(yōu)先文法 一般的程序設(shè)計(jì)語言不是簡單優(yōu)先文法 不實(shí)用，因?yàn)榇嬖谟趦蓚€(gè)符號(hào)之間的優(yōu)先關(guān)系常多于一種i算符優(yōu)先方法對(duì)以上情況有所改善 編譯原理8算符優(yōu)先分析方法算符優(yōu)先分析方法i算符優(yōu)先分析方法 根據(jù)算符之間的優(yōu)先關(guān)系來設(shè)計(jì)的一種字下而上語法分析方法 有利于表達(dá)式的分析 不是一種規(guī)范歸約法 算符優(yōu)先分析就是：定義算符之間（終結(jié)符）的某種關(guān)系，借助于這種優(yōu)先關(guān)系尋找“可歸約串”并進(jìn)性歸約 編譯原理9算符優(yōu)先文法算符優(yōu)先文法i算符文法i終結(jié)符之間存在的三種優(yōu)先關(guān)系 編譯原理10i算符優(yōu)先文法 編譯原理11例例6.15文法G44S：EE+T|T TT*F|FF(

3、E)|i 編譯原理12OPG優(yōu)先關(guān)系的構(gòu)造優(yōu)先關(guān)系的構(gòu)造i定義如下集合i它們的傳遞閉包定義如下 編譯原理13 編譯原理14 編譯原理15算法描述算法描述 編譯原理16例例6.16文法G44S：EE+T|T TT*F|F F(E)|i 編譯原理17例例6.16文法G44S：EE+T|T TT*F|F F(E)|i 編譯原理18 編譯原理19i由于未對(duì)非終結(jié)符定義算符優(yōu)先關(guān)系，所以不能使用算符優(yōu)先關(guān)系去查找由單個(gè)非終結(jié)符組成的句柄i引入素短語概念替代簡單優(yōu)先關(guān)系中的句柄概念，進(jìn)行規(guī)約 編譯原理20素短語及句型的分析素短語及句型的分析 編譯原理21示例示例 編譯原理22算符優(yōu)先分析算法算符優(yōu)先分析算

4、法 編譯原理23 編譯原理24 編譯原理25 編譯原理26文法G44S：EE+T|T TT*F|F F(E)|i 編譯原理27 編譯原理28優(yōu)先函數(shù)優(yōu)先函數(shù)i在實(shí)際實(shí)現(xiàn)算符優(yōu)先分析算法時(shí)，一般不直接用前述的優(yōu)先表，而是用兩個(gè)優(yōu)先函數(shù)f和g.i把每個(gè)終結(jié)符與兩個(gè)自然數(shù)相對(duì)應(yīng) 編譯原理29i使用優(yōu)先函數(shù)優(yōu)點(diǎn) 可減少優(yōu)先矩陣的存儲(chǔ)空間 便于比較運(yùn)算i使用優(yōu)先函數(shù)缺點(diǎn) 原先不存在優(yōu)先關(guān)系的兩個(gè)終結(jié)符，由于與自然數(shù)相對(duì)應(yīng)，變得可比較了?？赡軙?huì)掩蓋輸入串的某些錯(cuò)誤.i優(yōu)先函數(shù)構(gòu)造方法：Bell法和Floyd法 編譯原理30優(yōu)先函數(shù)構(gòu)造：優(yōu)先函數(shù)構(gòu)造：Bell方法方法 編譯原理31優(yōu)先函數(shù)構(gòu)造：優(yōu)先函數(shù)構(gòu)造：Floyd方法方法 編譯原理32小結(jié)小結(jié)i簡單優(yōu)先分析方法 簡單優(yōu)先關(guān)系矩陣計(jì)算 句柄的尋找i算符優(yōu)先分析方法