第六章自底向上優(yōu)先分析

第六章自底向上優(yōu)先分析第1頁，共43頁，2023年，2月20日，星期三自底向上的分析，也稱移進(jìn)-規(guī)約分析?；舅枷胧牵簩斎敕柎宰笙蛴疫M(jìn)行掃描，并將輸入符逐個移入一個后進(jìn)先出棧中，邊移入邊分析，一旦棧頂符號串形成某個句型的句柄或可規(guī)約串時，就用產(chǎn)生式的左部代替右部的文法符號串，這稱為一步規(guī)約。重復(fù)規(guī)約直到規(guī)約到棧中只剩文法的開始符號時則分析成功，也即確認(rèn)輸入串是文法的句子。 備注：自底向上分析的移進(jìn)-規(guī)約過程是自頂向下最右推倒的逆過程，最右推導(dǎo)為規(guī)范推導(dǎo)，所以自左向右的規(guī)約稱為規(guī)范規(guī)約。第2頁，共43頁，2023年，2月20日，星期三第3頁，共43頁，2023年，2月20日，星期三第4頁，共43頁，2023年，2月20日，星期三第5頁，共43頁，2023年，2月20日，星期三第6頁，共43頁，2023年，2月20日，星期三第7頁，共43頁，2023年，2月20日，星期三第8頁，共43頁，2023年，2月20日，星期三第9頁，共43頁，2023年，2月20日，星期三第10頁，共43頁，2023年，2月20日，星期三第11頁，共43頁，2023年，2月20日，星期三第12頁，共43頁，2023年，2月20日，星期三算符優(yōu)先分析基本思想：只規(guī)定算符之間的優(yōu)先關(guān)系，即只考慮終結(jié)符之間的優(yōu)先關(guān)系，由于算符優(yōu)先分析不考慮非終結(jié)符之間的優(yōu)先關(guān)系，在規(guī)約過程中只要找到可規(guī)約的串就規(guī)約，并不考慮規(guī)約到哪個非終結(jié)符名，因為算符優(yōu)先規(guī)約不是規(guī)范規(guī)約第13頁，共43頁，2023年，2月20日，星期三文法G：(1)E->E+E(2)E->E*E(3)E->i對輸入串i1+i2*i3

的規(guī)約過程第14頁，共43頁，2023年，2月20日，星期三第15頁，共43頁，2023年，2月20日，星期三6．3．1直觀算符優(yōu)先分析法

通常在算術(shù)表達(dá)式求值過程中，運算次序是先乘除后加減，這說明了乘除運算的優(yōu)先級高于加減運算的優(yōu)先級，乘除為同一優(yōu)先級但運算符在前邊的先做，這稱為左結(jié)合，同樣加減運算也是如此，這也說明了運算的次序只與運算符有關(guān)，而與運算對象無關(guān).因而直觀算符優(yōu)先分析法的關(guān)鍵是對一個給定文法G，人為地規(guī)定其算符的優(yōu)先順序，即給出優(yōu)先級別和同一個級別中的結(jié)合性質(zhì)，算符間的優(yōu)先關(guān)系表示與簡單優(yōu)先關(guān)系的表示類似，其規(guī)定如下：a<b表示a的優(yōu)先性低于b。a=b表示a的優(yōu)先性等于b，即與b相同。a>b表示a的優(yōu)先性高于b。但必須注意，這三個關(guān)系和數(shù)學(xué)中是不同的，它們是有序的，也就是若有a>b，不一定有b<a，a=b成立不一定有b=a。第16頁，共43頁，2023年，2月20日，星期三下面給出一個表達(dá)式的文法為：E→E+E|E-E|E*E|E/E|E↑E|(E)|i我們可以對此表達(dá)式的文法按公認(rèn)的計算順序規(guī)定優(yōu)先級和結(jié)合性如下：（1）↑優(yōu)先級最高，遵循右結(jié)合。相當(dāng)↑<↑。例如：2↑3↑2＝2↑9＝512。即同類運算符在歸約時為從右向左歸約。即i1↑i2↑i3為i2↑i3先歸約。（2）*，/優(yōu)先級其次，服從左結(jié)合。相當(dāng)*>*、*>/、/>/、/>*（3）＋，－優(yōu)先級最低，服從左結(jié)合。相當(dāng)+>+、+>-、->+、->-、+<*、+</、+<↑。（4）對‘（’，‘）’規(guī)定括號的優(yōu)先性大于括號外的運算符，小于括號內(nèi)的運算符，內(nèi)括號的優(yōu)先性大于外括號。對于句子括號‘?！栆?guī)定與它相鄰的任何運算符的優(yōu)先性都比它大。此外，對運算對象的終結(jié)符i其優(yōu)先級最高。

第17頁，共43頁，2023年，2月20日，星期三第18頁，共43頁，2023年，2月20日，星期三第19頁，共43頁，2023年，2月20日，星期三第20頁，共43頁，2023年，2月20日，星期三很顯然，所給表達(dá)式文法顯然是二義性文法，但我們?nèi)藶橹庇^地給出運算符之間的優(yōu)先關(guān)系且這種優(yōu)先關(guān)系是唯一的，有了這個優(yōu)先關(guān)系表我們就能分析了。

第21頁，共43頁，2023年，2月20日，星期三第22頁，共43頁，2023年，2月20日，星期三第23頁，共43頁，2023年，2月20日，星期三第24頁，共43頁，2023年，2月20日，星期三第25頁，共43頁，2023年，2月20日，星期三第26頁，共43頁，2023年，2月20日，星期三第27頁，共43頁，2023年，2月20日，星期三第28頁，共43頁，2023年，2月20日，星期三第29頁，共43頁，2023年，2月20日，星期三第30頁，共43頁，2023年，2月20日，星期三第31頁，共43頁，2023年，2月20日，星期三第32頁，共43頁，2023年，2月20日，星期三第33頁，共43頁，2023年，2月20日，星期三第34頁，共43頁，2023年，2月20日，星期三第35頁，共43頁，2023年，2月20日，星期三第36頁，共43頁，2023年，2月20日，星期三第37頁，共43頁，2023年，2月20日，星期三第38頁，共43頁，2023年，2月20日，星期三第39頁，共43頁，2023年，2月20日，星期三第40頁，共43頁，2023年，2月20日，星期三第41頁，共43頁，2023年，