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

第六章自底向上優(yōu)先分析第1頁(yè)，共43頁(yè)，2023年，2月20日，星期三自底向上的分析，也稱(chēng)移進(jìn)-規(guī)約分析?；舅枷胧牵簩?duì)輸入符號(hào)串自左向右進(jìn)行掃描，并將輸入符逐個(gè)移入一個(gè)后進(jìn)先出棧中，邊移入邊分析，一旦棧頂符號(hào)串形成某個(gè)句型的句柄或可規(guī)約串時(shí)，就用產(chǎn)生式的左部代替右部的文法符號(hào)串，這稱(chēng)為一步規(guī)約。重復(fù)規(guī)約直到規(guī)約到棧中只剩文法的開(kāi)始符號(hào)時(shí)則分析成功，也即確認(rèn)輸入串是文法的句子。 備注：自底向上分析的移進(jìn)-規(guī)約過(guò)程是自頂向下最右推倒的逆過(guò)程，最右推導(dǎo)為規(guī)范推導(dǎo)，所以自左向右的規(guī)約稱(chēng)為規(guī)范規(guī)約。第2頁(yè)，共43頁(yè)，2023年，2月20日，星期三第3頁(yè)，共43頁(yè)，2023年，2月20日，星期三第4頁(yè)，共43頁(yè)，2023年，2月20日，星期三第5頁(yè)，共43頁(yè)，2023年，2月20日，星期三第6頁(yè)，共43頁(yè)，2023年，2月20日，星期三第7頁(yè)，共43頁(yè)，2023年，2月20日，星期三第8頁(yè)，共43頁(yè)，2023年，2月20日，星期三第9頁(yè)，共43頁(yè)，2023年，2月20日，星期三第10頁(yè)，共43頁(yè)，2023年，2月20日，星期三第11頁(yè)，共43頁(yè)，2023年，2月20日，星期三第12頁(yè)，共43頁(yè)，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ī)約，并不考慮規(guī)約到哪個(gè)非終結(jié)符名，因?yàn)樗惴麅?yōu)先規(guī)約不是規(guī)范規(guī)約第13頁(yè)，共43頁(yè)，2023年，2月20日，星期三文法G：(1)E->E+E(2)E->E*E(3)E->i對(duì)輸入串i1+i2*i3

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

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

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

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