編譯概述語(yǔ)法分析

編譯概述語(yǔ)法分析三、編譯程序得組成詞法分析、語(yǔ)法分析、語(yǔ)義分析、優(yōu)化、目標(biāo)代碼生成、符號(hào)表管理、出錯(cuò)處理。相互關(guān)系如下圖:源程序字符串詞法分析器語(yǔ)法分析器語(yǔ)義分析、中間代碼生成器代碼優(yōu)化器目標(biāo)代碼生成器單詞流語(yǔ)法單位中間代碼序列中間代碼序列目標(biāo)程序符號(hào)表管理程序出錯(cuò)處理程序編譯程序得結(jié)構(gòu)詞法分析: 1)輸入字符串,根據(jù)詞法規(guī)則識(shí)別出單詞符號(hào)。

2)二元式結(jié)果(單詞類(lèi)別、單詞屬性)

3)記號(hào)(Token):基本字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符、界符

4)詞法出錯(cuò)處理2、語(yǔ)法分析:

根據(jù)語(yǔ)法規(guī)則,將單詞符號(hào)構(gòu)成各類(lèi)語(yǔ)法單位,并進(jìn)行語(yǔ)法檢查。 例:語(yǔ)法單位中有表達(dá)式、短語(yǔ)、句子、程序等等。3、語(yǔ)義分析與代碼生成: 1)根據(jù)語(yǔ)義規(guī)則,進(jìn)行初步實(shí)質(zhì)性翻譯。

2)中間代碼(對(duì)應(yīng)抽象機(jī))4、優(yōu)化:對(duì)中間代碼進(jìn)行等價(jià)變換,以使代碼更有效。時(shí)間與空間5、目標(biāo)代碼生成:生成機(jī)器語(yǔ)言程序或匯編語(yǔ)言程序。6、符號(hào)表管理:完成符號(hào)表得建立,查找,更新。7、出錯(cuò)處理報(bào)告錯(cuò)誤性質(zhì)與出錯(cuò)得地點(diǎn)限制錯(cuò)誤得影響到盡可能小得范圍,便于其它部分繼續(xù)編譯?！煲粚?duì)詞法分析器得要求1、詞法分析器得功能與輸出形式功能:輸入源程序,輸出單詞符號(hào)。單詞符號(hào)就是一個(gè)程序語(yǔ)言得基本語(yǔ)法符號(hào)。第8章詞法分析程序語(yǔ)言得單詞符號(hào)一般可分為下列五種:

關(guān)鍵字:具有固定意義得標(biāo)識(shí)符,稱為保留字或基本字。如begin,end,if…,通常不用作一般標(biāo)識(shí)符。

標(biāo)識(shí)符:表示各種名字,如變量名、數(shù)組名、過(guò)程名……

常數(shù):其類(lèi)型一般有整型、實(shí)型、布爾、文字等。如100、3、14159、TRUE、’sample’

運(yùn)算符:分為算術(shù)運(yùn)算符(如:＋、－、*、/等),邏輯運(yùn)算符(如:not、and、or),關(guān)系運(yùn)算符(如:<、>、>=、<=、=)等。

界符:逗號(hào),分號(hào),括號(hào),/,/等。一個(gè)程序語(yǔ)言得關(guān)鍵字、運(yùn)算符與界符都就是確定得,一般只有幾十個(gè)或上百個(gè),標(biāo)識(shí)符與常數(shù)則不受限制。大家有疑問(wèn)的，可以詢問(wèn)和交流可以互相討論下，但要小聲點(diǎn)常采用二元式來(lái)表示識(shí)別出得單詞符號(hào):(單詞種別,單詞符號(hào)得屬性值)

單詞種別通常用整數(shù)編碼,如何分種,怎樣編碼,取決于處理得方便性。標(biāo)識(shí)符一般統(tǒng)歸一種常數(shù)按類(lèi)關(guān)鍵字:全體為一種或一字一種運(yùn)算符:一符一種,或具有共性得為一種界符:一符一種Sample語(yǔ)言得單詞編碼

對(duì)一符一種,可不需屬性,但多符一種時(shí)必須要有屬性信息,屬性反映單詞符號(hào)得特性或特征,而屬性值反映特性或特征得值。例如:對(duì)標(biāo)識(shí)符,其屬性值可為存放它得有關(guān)信息得符號(hào)表項(xiàng)得指針。若假定關(guān)鍵字、運(yùn)算符、界符都就是一符一種,標(biāo)識(shí)符單列一種,常數(shù)按類(lèi),則代碼段:while(i>=j)i––;可轉(zhuǎn)換為如下序列: <while,–>

<(,–>

<id,指向i得符號(hào)表項(xiàng)得指針>

<>=,–>

<id,指向j得符號(hào)表項(xiàng)得指針>

<),–>

<id,指向i得符號(hào)表項(xiàng)得指針>

<––,–>

<;,–>詞法分析程序得實(shí)現(xiàn)方式完全獨(dú)立方式:詞法分析程序作為單獨(dú)一趟來(lái)實(shí)現(xiàn)。詞法分析程序讀入整個(gè)源程序,它得輸出作為語(yǔ)法分析程序得輸入。相對(duì)獨(dú)立方式:把詞法分析程序作為語(yǔ)法分析程序得一個(gè)獨(dú)立子程序。語(yǔ)法分析程序需要新符號(hào)時(shí)調(diào)用這個(gè)子程序。2、詞法分析器作為一個(gè)獨(dú)立子程序完全獨(dú)立方式采用詞法分析工作完全獨(dú)立得原因:簡(jiǎn)化設(shè)計(jì),降低語(yǔ)法分析得復(fù)雜性提高編譯效率增加編譯系統(tǒng)得可移植性源程序詞法分析程序語(yǔ)法分析程序?qū)傩宰中蛄小?、相?duì)獨(dú)立方式當(dāng)采用遞歸下降分析等技術(shù)實(shí)現(xiàn)一趟編譯程序時(shí)常采用這種方式。詞法分析器語(yǔ)法分析器符號(hào)表源程序單詞符號(hào)取下一單詞...1、單詞符號(hào)得識(shí)別:超前搜索1基本字識(shí)別:例如:1DO99K=1,10 DO99K=1,102IF(5、EQ、M)GOTO55IF(5、EQ、M)GOTO553DO99K=1、104IF(5)=55需要超前搜索才能確定哪些就是基本字詞法分析程序在讀取單詞時(shí),為了判斷就是否已讀入整個(gè)單詞得全部字符,常采取向前多讀取字符并通過(guò)讀取得字符來(lái)判別,即所謂超前搜索技術(shù)。二、詞法分析器得設(shè)計(jì)

標(biāo)識(shí)符字母開(kāi)頭得“字母/數(shù)字”串。由于后跟算符或界符,所以容易識(shí)別。

常數(shù)如FORTRAN得5、E08與5、EQ、M也必須超前搜索。

算符與界符多字符復(fù)合而成得算符與界符(如:=,**,、EQ、,++,--,>=等)拼合成一個(gè)單詞符號(hào)。就是不可分得整體,同樣需要超前搜索。2、狀態(tài)轉(zhuǎn)換圖——設(shè)計(jì)詞法分析器得一個(gè)好工具狀態(tài)轉(zhuǎn)換圖就是一張有限方向圖。213XY結(jié)點(diǎn)代表狀態(tài),用圓圈表示。狀態(tài)之間用箭弧連結(jié),箭弧上得標(biāo)記(字符)代表射出結(jié)狀態(tài)下可能出現(xiàn)得輸入字符或字符類(lèi)。一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài),其中有一個(gè)為初態(tài),至少要有一個(gè)終態(tài)。狀態(tài)轉(zhuǎn)換圖可用于識(shí)別/接受一定得字符串:210字母字母或數(shù)字其它*(a)標(biāo)識(shí)符的識(shí)別210數(shù)字

數(shù)字其它*(b)整數(shù)的識(shí)別1072345數(shù)字?jǐn)?shù)字?jǐn)?shù)字.E或D+或-數(shù)字?jǐn)?shù)字其它*6.數(shù)字E或D數(shù)字其它(c)Fortran實(shí)常數(shù)的識(shí)別幾點(diǎn)重要限制——不必使用超前搜索所有基本字都就是保留字;用戶不能用它們作自己得標(biāo)識(shí)符基本字作為特殊得標(biāo)識(shí)符來(lái)處理;不用特殊得狀態(tài)圖來(lái)識(shí)別,只要查保留字表。如果基本字、標(biāo)識(shí)符與常數(shù)(或標(biāo)號(hào))之間沒(méi)有確定得運(yùn)算符或界符作間隔,則必須使用一個(gè)空白符作間隔。

DO99K=1,10

要寫(xiě)成DO99K=1,10123456789101112130空白字母字母或數(shù)字非字母與數(shù)字?jǐn)?shù)字非數(shù)字?jǐn)?shù)字=+*非*,()其它****狀態(tài)轉(zhuǎn)換圖得實(shí)現(xiàn)思想:每個(gè)狀態(tài)結(jié)點(diǎn)對(duì)應(yīng)一小段程序。做法:1)對(duì)不含回路得分叉結(jié),可用一個(gè)CASE語(yǔ)句或一組IF-THEN-ELSE語(yǔ)句實(shí)現(xiàn)GetChar();if(IsLetter()){…狀態(tài)j得對(duì)應(yīng)程序段…;}elseif(IsDigit()){…狀態(tài)k得對(duì)應(yīng)程序段…;}elseif(ch=‘/’){…狀態(tài)l得對(duì)應(yīng)程序段…;}else{…錯(cuò)誤處理…;}ijkl字母數(shù)字/2)對(duì)含回路得狀態(tài)結(jié),可對(duì)應(yīng)一段由WHILE結(jié)構(gòu)與IF語(yǔ)句構(gòu)成得程序、i字母或數(shù)字其它jGetChar();while(IsLetter()orIsDigit()) GetChar();…狀態(tài)j得對(duì)應(yīng)程序段…3)終態(tài)結(jié)點(diǎn)表示識(shí)別出某種單詞符號(hào),因此,對(duì)應(yīng)語(yǔ)句為

RETURN(C,VAL)

其中,C為單詞種別,VAL為單詞自身值、全局變量與過(guò)程1)ch字符變量、存放最新讀入得源程序字符2)strToken字符數(shù)組,存放構(gòu)成單詞符號(hào)得字符串3)GetChar子程序過(guò)程,把下一個(gè)字符讀入到ch中4)GetBC子程序過(guò)程,跳過(guò)空白符,直至ch中讀入一非空白符5)Concat子程序,把ch中得字符連接到strToken6)IsLetter與IsDisgital布爾函數(shù),判斷ch中字符就是否為字母與數(shù)字7)Reserve整型函數(shù),對(duì)于strToken中得字符串查找保留字表,若它就是保留字則給出它得編碼,否則回送08)Retract子程序,把搜索指針回調(diào)一個(gè)字符位置9)InsertId整型函數(shù),將strToken中得標(biāo)識(shí)符插入符號(hào)表,返回符號(hào)表指針10)InsertConst整型函數(shù)過(guò)程,將strToken中得常數(shù)插入常數(shù)表,返回常數(shù)表指針。intcode,value;strToken:=“”; /*置strToken為空串*/GetChar();GetBC();if(IsLetter())begin while(IsLetter()orIsDigit()) begin Concat();GetChar(); end Retract(); code:=Reserve(); if(code=0) begin value:=InsertId(strToken); return($ID,value); end else return(code,-); endelseif(IsDigit())begin while(IsDigit()) begin Concat();GetChar(); end Retract(); value:=InsertConst(strToken); retrnr($INT,value);endelseif(ch=‘=’)return($ASSIGN,-);elseif(ch=‘+’)return($PLUS,-);elseif(ch=‘*’)begin GetChar(); if(ch=‘*’)return($POWER,-); Retract();return($STAR,-);endelseif(ch=‘;’)return($SEMICOLON,-);elseif(ch=‘(’)return($LPAR,-);elseif(ch=‘)’)return($RPAR,-);elseProcError(); /*錯(cuò)誤處理*/非法字符不合規(guī)則得常數(shù)標(biāo)識(shí)符前綴為保留字3、詞法錯(cuò)誤檢查35編譯過(guò)程中編譯程序需要不斷匯集與反復(fù)查證出現(xiàn)在源程序中各種名字得屬性與特征等有關(guān)信息。這些信息通常記錄在一張或多張符號(hào)表中,每一項(xiàng)分兩部分:名字(標(biāo)識(shí)符)與此名字得有關(guān)信息。每個(gè)名字得有關(guān)信息一般指種屬(如簡(jiǎn)單變量、數(shù)組、過(guò)程等)、類(lèi)型(如整、實(shí)、布爾等)等等。這些信息將用于語(yǔ)義檢查、產(chǎn)生中間代碼以及最終生成目標(biāo)代碼等階段。36在編譯程序中符號(hào)表用來(lái)存放語(yǔ)言程序中出現(xiàn)得有關(guān)標(biāo)識(shí)符得屬性信息,這些信息集中反映了標(biāo)識(shí)符得語(yǔ)義特征屬性。在詞法分析及語(yǔ)法在分析過(guò)程中不斷積累與更新表中得信息,并在詞法分析到代碼生成得各階段,按各自得需要從表中獲取不同得屬性信息。不論編譯策略就是否分趟,符號(hào)表得作用與地位就是完全一致得。

①收集符號(hào)屬性

②上下文語(yǔ)義得合法性檢查得依據(jù)

③作為目標(biāo)代碼生成階段地址分配得依據(jù)

37收集符號(hào)屬性

編譯程序掃描說(shuō)明部分收集有關(guān)標(biāo)識(shí)符得屬性,并在符號(hào)表中建立符號(hào)得相應(yīng)屬性信息。例如,編譯程序分析到下述兩個(gè)說(shuō)明語(yǔ)句

intA;

floatB[5];

38上下文語(yǔ)義得合法性檢查得依據(jù)同一個(gè)標(biāo)識(shí)符可能在程序得不同地方出現(xiàn),而有關(guān)該符號(hào)得屬性就是在這些不同情況下收集得。特別就是在多趟編譯及程序分段編譯(在PASCAL及C中以文件為單位)得情況下,更需檢查標(biāo)識(shí)符屬性在上下文中得一致性與合法性。通過(guò)符號(hào)表中屬性記錄可進(jìn)行相應(yīng)上下文得語(yǔ)義檢查。

例如,在一個(gè)C語(yǔ)言程序中出現(xiàn)

…

inti[3,5];//定義整型數(shù)組i

…

floati[4,2];//定義實(shí)型數(shù)組i,重定義沖突

…

inti[3,5];//定義整型數(shù)組i,重定義沖突39③作為目標(biāo)代碼生成階段地址分配得依據(jù)

每個(gè)符號(hào)變量在目標(biāo)代碼生成時(shí)需要確定其在存儲(chǔ)分配得位置(主要就是相對(duì)位置)。首先要確定其被分配得區(qū)域。在C語(yǔ)言中首先要確定該符號(hào)變量就是分配在公共區(qū)(extern)、文件靜態(tài)區(qū)(externstatic)、函數(shù)靜態(tài)區(qū)(函數(shù)中static)、還就是函數(shù)運(yùn)行時(shí)得動(dòng)態(tài)區(qū)(auto)等。其次就是根據(jù)變量出現(xiàn)得次序決定該變量在某個(gè)區(qū)中所處得具體位置,這通常使用在該區(qū)域中相對(duì)區(qū)頭得相對(duì)位置確定。而有關(guān)區(qū)域得標(biāo)志及相對(duì)位置都就是作為該變量得語(yǔ)義信息被收集在該變量得符號(hào)表屬性中。40§8、1符號(hào)表得組織與作用在編譯得各個(gè)分析階段,每當(dāng)遇到一個(gè)名字都要查找符號(hào)表。若就是新名字或發(fā)現(xiàn)已有名字得新信息,則要加入(填入)。因此,合理組織符號(hào)表,使其存儲(chǔ)占用最少,同時(shí)提高編譯期間對(duì)符號(hào)表得訪問(wèn)效率,至關(guān)重要。一、符號(hào)表的作用41概括地說(shuō),符號(hào)表得每一項(xiàng)(或稱入口)包含兩大欄(或稱區(qū)段、字域),即名字欄與信息欄。表格得形式如下:第1項(xiàng)(入口1)第2項(xiàng)(入口2)第n項(xiàng)(入口n)名字欄(NAME)信息欄(INFORMATION)…42信息欄包含許多子欄與標(biāo)志位,記錄相應(yīng)名字得種種不同屬性。由于查填符號(hào)表一般就是通過(guò)匹配名字來(lái)實(shí)現(xiàn)得,故名字欄也稱主欄,其內(nèi)容稱為關(guān)鍵字(keyword)。符號(hào)表中每一項(xiàng)都就是關(guān)于名字得說(shuō)明。因?yàn)樗４娴藐P(guān)于名字得信息取決于名字得用途,所以各表項(xiàng)得格式不一定統(tǒng)一,為使表中得每個(gè)記錄格式統(tǒng)一,可采用指針技術(shù),在記錄中設(shè)置指針,把某些信息放在表得外邊,用指針指向存放另外信息得空間。43對(duì)符號(hào)表得操作大致可以分為五類(lèi):·查詢某個(gè)名字就是否已在表中?！ぬ钊胍粋€(gè)新得名字?！ぬ砑踊蚋履硞€(gè)名字得某些信息?！h除一個(gè)或一組無(wú)用得項(xiàng)?！ぴL問(wèn)某個(gè)名字得某些信息。44對(duì)符號(hào)表進(jìn)行操作得時(shí)機(jī):定義性出現(xiàn)使用性出現(xiàn)按名字得不同種屬建立多張符號(hào)表,如常數(shù)表、變量名表、過(guò)程名表、…符號(hào)得組織方式:1、安排各項(xiàng)各欄得存儲(chǔ)單元為固定長(zhǎng)度2、用間接方式安排各欄存儲(chǔ)單元45最簡(jiǎn)單得組織方式:各項(xiàng)各欄長(zhǎng)度固定——易于組織、填寫(xiě)與查找。這種表格,每一欄得內(nèi)容可直接填寫(xiě)在有關(guān)得區(qū)段內(nèi)。例如,對(duì)于名字欄,其大小可按標(biāo)識(shí)符最大允許長(zhǎng)度來(lái)確定。如標(biāo)準(zhǔn)FORTRAN語(yǔ)言規(guī)定每一標(biāo)識(shí)符不得超過(guò)6個(gè)字符,因此就可用6個(gè)字符得空間作為名字欄得長(zhǎng)度。若標(biāo)識(shí)符長(zhǎng)度不足6個(gè)字符,則以空白符補(bǔ)齊。二、符號(hào)表得組織方式46但就是,有許多語(yǔ)言對(duì)標(biāo)識(shí)符得長(zhǎng)度幾乎不加以限制,或者說(shuō),標(biāo)識(shí)符得長(zhǎng)度范圍很寬。比如說(shuō),最長(zhǎng)可允許由100個(gè)字符組成得名字。此時(shí),如果名字欄得長(zhǎng)度設(shè)為100個(gè)字符,則勢(shì)必會(huì)大量浪費(fèi)存儲(chǔ)空間。因此,最好采用指針技術(shù)。用另外一獨(dú)立得字符串?dāng)?shù)組,把所有標(biāo)識(shí)符都存放其中。在符號(hào)表得主欄放一指示器與一整數(shù),或僅放一指示器,同時(shí)在標(biāo)識(shí)符前放一個(gè)整數(shù)。指示器指出標(biāo)識(shí)符在字符串?dāng)?shù)組中得位置;整數(shù)代表此標(biāo)識(shí)符得長(zhǎng)度。47SAMPLELOOPINFORMATIONNAME，6，4在符號(hào)表得主欄放一指示器與一整數(shù)48INFORMATIONNAME6SAMPLE4LOOP在符號(hào)表得主欄放一指示器,同時(shí)在標(biāo)識(shí)符前放一個(gè)整數(shù)49

類(lèi)似地,如果各種名字所需得信息空間長(zhǎng)短不一,則將共同屬性直接登記在信息欄中,而特殊屬性登記在別得地方。在信息欄中附設(shè)一指示器,指向存放特殊屬性得地方。

例如對(duì)于數(shù)組標(biāo)識(shí)符,需存儲(chǔ)得信息包含維數(shù)等,如果將它們與其它名字全部集中在一張符號(hào)表中,處理起來(lái)很不方便。因此,常另辟一個(gè)信息表區(qū),稱數(shù)組信息表(或內(nèi)情向量表),用來(lái)保存數(shù)組得有關(guān)信息。在符號(hào)表得地址欄內(nèi)存入符號(hào)表與內(nèi)情向量表連接得入口地址。當(dāng)填寫(xiě)或查詢數(shù)組有關(guān)信息時(shí),通過(guò)符號(hào)表來(lái)訪問(wèn)此內(nèi)情向量表。50

對(duì)過(guò)程名以及其它一些含信息較多得名字,都可類(lèi)似地開(kāi)辟專(zhuān)用信息表,存放那些不宜全部存放在符號(hào)表中得信息,而在符號(hào)表中保留與信息表相聯(lián)系得地址信息。51

在編譯時(shí),雖然從原則上說(shuō),使用一張統(tǒng)一得符號(hào)表就夠了。但許多編譯程序按名字得不同種屬分別使用許多符號(hào)表。如常數(shù)表、變量名表、過(guò)程名表等等。這就是因?yàn)?不同種屬名字得相應(yīng)信息往往不同,信息欄得長(zhǎng)度也各有差異。因而,按不同種屬建立不同得符號(hào)表在處理上常常就是比較方便得。52例:PASCAL程序段:PROCEDUREINCWAP(M,N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END、53PROCEDUREINCWAP(M,N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END、54PROCEDUREINCWAP(M,N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END、55PROCEDUREINCWAP(M,N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART: