【文章內(nèi)容簡(jiǎn)介】 中共享一些特定數(shù)據(jù)[8]。（1） 記號(hào)（token）當(dāng)掃描程序?qū)⑷舾蓚€(gè)字符收集到一個(gè)記號(hào)中時(shí)，它通常是以符號(hào)表示這個(gè)記號(hào)的，也就是說(shuō)，用一個(gè)枚舉數(shù)據(jù)類型的值來(lái)表示源程序的記號(hào)集。有時(shí)還必須保留字符串本身或由此派生出的其他信息（例如：與標(biāo)識(shí)符記號(hào)相關(guān)的名字或數(shù)字記號(hào)值）。在C編譯器中，掃描程序一次只需要生成一個(gè)記號(hào)（這稱為單符號(hào)先行），考慮到這種情況，可以用全程變來(lái)量放置記號(hào)信息。（2） 符號(hào)表（symbol table）符號(hào)表中的信息與標(biāo)識(shí)符（函數(shù)、變量、常量以及數(shù)據(jù)類型等）有關(guān)。它幾乎與編譯器的所有階段交互：掃描程序、分析程序或?qū)?biāo)識(shí)符輸入到表格中的語(yǔ)義分析程序；語(yǔ)義分析程序?qū)⒃黾訑?shù)據(jù)類型和其它語(yǔ)義信息；優(yōu)化階段和代碼生成階段也將利用由符號(hào)表提供的信息生成正確而恰當(dāng)?shù)拇a。因?yàn)樵诰幾g的全程中對(duì)符號(hào)表的訪問(wèn)非常頻繁，所以插入、刪除和訪問(wèn)等符號(hào)表操作都必須比常規(guī)操作更有效。盡管可以使用各種樹的結(jié)構(gòu)，但雜湊表卻是能達(dá)到這一要求的最理想的數(shù)據(jù)結(jié)構(gòu)。（3） 項(xiàng)目（item）在文法G中，某個(gè)產(chǎn)生式的右部標(biāo)上“點(diǎn)號(hào)”的產(chǎn)生式，再放置一個(gè)向前所搜符號(hào)a，成為L(zhǎng)R（1）項(xiàng)目。每個(gè)LR（1）項(xiàng)目集簇由若干狀態(tài)組成，每個(gè)狀態(tài)由若干項(xiàng)目組成。因此，對(duì)于構(gòu)建項(xiàng)目集簇，項(xiàng)目的操作相當(dāng)頻繁，如何表示和處理項(xiàng)目成為構(gòu)造分析表的重點(diǎn)。（4） 中間代碼（intermediate code）根據(jù)中間代碼的類型（例如三元式代碼和P代碼）和優(yōu)化的類型，該代碼可以是字符串?dāng)?shù)組（指針數(shù)組）、臨時(shí)文本文件或是結(jié)構(gòu)的連接列表。對(duì)于進(jìn)行復(fù)雜優(yōu)化的編譯器，應(yīng)特別注意選擇允許簡(jiǎn)單重組的中間代碼表示。第四章 C編譯器的實(shí)現(xiàn)C編譯器從整體上被劃分為4個(gè)階段：詞法分析、語(yǔ)法分析、語(yǔ)義分析、代碼生成，這4個(gè)階段分別用不同的程序模塊來(lái)實(shí)現(xiàn)（如表31）。一個(gè)C源程序經(jīng)過(guò)C編譯器的編譯之后，生成三地址的四元表達(dá)式目標(biāo)代碼，在整個(gè)編譯過(guò)程中，這4個(gè)階段分別承擔(dān)了相應(yīng)的翻譯任務(wù)。 詞法分析階段 概述編譯器的詞法分析階段可將源程序讀作有序字符文件并將其掃描分解為若干個(gè)記號(hào)（token）。記號(hào)與自然語(yǔ)言中的單詞類似：每一個(gè)記號(hào)都是表示源程序中信息單元的字符序列。典型的有：關(guān)鍵字(keyword)，例如if和while，它們是字母的固定串，在該語(yǔ)言中具有特定的含義；標(biāo)識(shí)符(identifier)是由用戶定義的串，它們通常由字母和數(shù)字組成并由一個(gè)字母開頭，例如變量名函數(shù)名等；算符符（operation symbol）在語(yǔ)言中是作為語(yǔ)法上的運(yùn)算符號(hào)使用的。例如，+，，*，/，（，），和++， ， =；界符在語(yǔ)言中作為語(yǔ)法上的分界；數(shù)字，廣義上就是源程序中的字面值。如前所述，詞法分析程序的輸入是源程序字符串，輸出是與源程序等價(jià)的符號(hào)序列。作為詞法分析程序的符號(hào)可以有各種不同的內(nèi)部表現(xiàn)形式，原則是不同的符號(hào)能彼此區(qū)別開且有唯一的表示。為了便于編譯程序的進(jìn)一步加工（語(yǔ)法分析），內(nèi)部表示的符號(hào)都按屬性字形式，因此，詞法分析程序的輸出即是屬性字序列，采用二元式來(lái)表示一個(gè)單詞符號(hào)的內(nèi)部形式。符號(hào)類別符號(hào)值表41 詞法Token字這五類單詞將用不同的方法處理。關(guān)鍵字、算符與界符將直接形成Token字；標(biāo)識(shí)符將插入符號(hào)表后形成Token字，數(shù)字將插入常數(shù)表后形成Token字。 在實(shí)際做詞法分析時(shí)，考慮了所有的C語(yǔ)言現(xiàn)象，使得每一個(gè)C語(yǔ)言程序都可以被此法分析切割為單詞并且賦值上屬性。一般情況下，可以通過(guò)兩種途徑來(lái)設(shè)計(jì)詞法分析程序。一種是用手工方式構(gòu)造，另一種是所謂詞法分析程序的自動(dòng)生成。為了實(shí)現(xiàn)簡(jiǎn)單，本實(shí)驗(yàn)采取手工構(gòu)造方式。 C詞法分析程序的實(shí)現(xiàn)C語(yǔ)言的記號(hào)分為5種類型：標(biāo)示符，關(guān)鍵字，數(shù)字，算符和界限符。關(guān)鍵字一共有8個(gè)，它們的含義類似于標(biāo)準(zhǔn)C語(yǔ)言中的相應(yīng)關(guān)鍵字。特殊符號(hào)共有12種：分別是4種基本的整數(shù)運(yùn)算符號(hào)，5種比較符號(hào)（等號(hào)、小于號(hào)、小于等于、大于、大于等于），以及左括號(hào)、右括號(hào)、分號(hào)、賦值符號(hào)。其中，除了比較等號(hào)、小于等于符號(hào)和大于等于是兩個(gè)字符的長(zhǎng)度之外，其余均為單個(gè)字符。“其他”記號(hào)就是數(shù)和標(biāo)識(shí)符了，數(shù)是一個(gè)或多個(gè)數(shù)字的序列，而標(biāo)識(shí)符又是一個(gè)或多個(gè)字母的序列。所有這些記號(hào)歸納如下表42：關(guān)鍵字（8個(gè)）Int、if、while、double、return、void、continue、break界限符（12個(gè)）+、*、/、==、= 、=、=、( 、) 、。 其它數(shù)(1個(gè)或更多的數(shù)字序列)標(biāo)識(shí)符(1個(gè)或更多的字母序列)表42C語(yǔ)言的記號(hào)除了上表的記號(hào)之外，C語(yǔ)言的源程序還要遵循以下的詞法規(guī)則：代碼應(yīng)是自由書寫格式；空白符由空格、制表位和新行組成。根據(jù)對(duì)語(yǔ)言中各類單詞某種描述的定義，用手工方式構(gòu)造詞法分析程序。詞法分析程序的主要任務(wù)就是掃描程序、識(shí)別單詞、轉(zhuǎn)換并輸出屬性字。下面給出單獨(dú)成趟詞法分析控制流程圖。開 始輸入C源文件 是否文件結(jié)尾巴尾Y N 進(jìn)入主控模塊選擇識(shí)別的單詞形成Token字Y停 止 圖41 單獨(dú)成趟的詞法分析控制流程圖，其核心函數(shù)是scan( )，它每次從第一個(gè)非空格或換行符開始識(shí)別，直到遇到空格或者換行符，遇到單行注釋就跳過(guò)本行從“//”開始的以后字符識(shí)別，遇到多行注釋就跳過(guò)直到遇到“*/”為止（不支持注釋嵌套）。每次返回一個(gè)識(shí)別的單詞，遇到不識(shí)別的單詞就報(bào)錯(cuò)，輸出不識(shí)別的單詞和該單詞的行數(shù)。掃描程序在識(shí)別出每個(gè)記號(hào)的同時(shí)，還會(huì)計(jì)算出該記號(hào)的特性（比如串值）這五類單詞將用不同的方法處理。關(guān)鍵字、算符與界符將直接形成Token字；標(biāo)識(shí)符將插入符號(hào)表后形成Token字，數(shù)字將插入常數(shù)表后形成Token字。 Token是本實(shí)驗(yàn)的所有類的基類，有2個(gè)成員變量：Tag，Value。Value是文法中非終結(jié)符，而Tag是Value對(duì)應(yīng)的唯一標(biāo)記。 關(guān)鍵字與標(biāo)識(shí)符的識(shí)別C對(duì)于關(guān)鍵字的識(shí)別，是通過(guò)先將它們看作是標(biāo)識(shí)符，然后再調(diào)用Token類的get_int()方法，根據(jù)返回值Tag是否22（標(biāo)示符的標(biāo)志）為來(lái)判斷是標(biāo)示符還是關(guān)鍵字。 詞法識(shí)別具體實(shí)現(xiàn)//分析一個(gè)單詞，并返回單詞的Token字Token Scanner::scan(){ int i=0。 string s。 static char prev_c = 0。 char line[Token::NAME_SIZE] = {0}。 prev_c = c。 while (true) { if ((c)==NULL) //到文件結(jié)尾 return (Token())。 if (c==39。\n39。) //遇到換行符 linenum++。 //行數(shù)+1 else if (c==39。 39。 || c==39。\t39。) //遇到空格或者制表符 continue。 //跳過(guò)，繼續(xù)讀 else //遇到普通字符，跳出循環(huán) break。 } //遇到注釋的情況 while (c==39。/39。 amp。amp。 (()==39。/39。 || ()==39。*39。)) { //處理注釋 } //end while if (isalpha(c)) //字母 return (alpha_process())。 else if (isdigit(c)) //數(shù)字 return (digit_process())。 else //其他 { switch(c) //對(duì)字符進(jìn)行分析 { case 39。+39。: {...} case 39。39。: {...} case 39。*39。: {...} case 39。/39。: {...} case 39。=39。: {...} case 39。39。: {...} case 39。39。: {...} case 39。!39。: {...} case 39。amp。39。: {...} case 39。|39。: {...} case 39。~39。: {...} case 39。(39。: return (Token(get_int((), ())。 case 39。)39。: return (Token(get_int()), )))。 case 39。[39。: return (Token(get_int([), [))。 case 39。]39。: return (Token(get_int(]), ]))。 case 39。{39。: return (Token(get_int({), {))。 case 39。}39。: return (Token(get_int(}), }))。 case 39。39。: return (string_process())。 case 39。39。: return (Token(get_int(。),。))。 case 39。,39。: return (Token(get_int(,),))。 case 39。.39。: return (Token(get_int(.),.))。 case 39。:39。: return (Token(get_int(:),:))。 case 39。\39。39。: {...} case 39。39。: {...} default: std::cout Error, line linenum :\tillegal character \39。 c \39。\n。 line[0] = c。 line[1] = 39。\039。 return (Token(get_int(ILLEGAL), (line)))。 } } return Token()。} 語(yǔ)法分析階段 概述語(yǔ)法分析是編譯過(guò)程的核心，分析的任務(wù)是根據(jù)語(yǔ)法規(guī)則分析源程序的語(yǔ)法結(jié)構(gòu)，并在分析過(guò)程中，對(duì)源程序進(jìn)行語(yǔ)法檢查，如果語(yǔ)法沒(méi)有錯(cuò)誤，則給出正確的語(yǔ)法結(jié)構(gòu)，為語(yǔ)義分析和代碼生成做準(zhǔn)備。目前語(yǔ)法分析方法有多種多樣，大致分為自頂而下和自底而上兩大類。自頂而下又分為L(zhǎng)L（1）分析方法和遞歸下降分析方法。自底而上又分為簡(jiǎn)單優(yōu)先文法、算符優(yōu)先文法、LR（K）分析方法。下面主要介紹自底而上的LR（K）分析方法。自底向上分析法，也稱移進(jìn)歸約分析法。它的實(shí)現(xiàn)思想是對(duì)輸入符號(hào)串自左向右進(jìn)行掃描，并將輸入符逐個(gè)移入一個(gè)后進(jìn)先出棧中，邊移入邊分析，一旦棧頂符號(hào)串形成某個(gè)句型的句柄時(shí)，(該句柄對(duì)應(yīng)某產(chǎn)生式的右部)，就用該產(chǎn)生式的左部非終結(jié)符代替相應(yīng)右部的文法符號(hào)串，這稱為移步歸約。重復(fù)這一過(guò)程直到歸約到棧中只剩文法的開始符號(hào)時(shí)則為分析成功，也就確認(rèn)輸入串是文法的句子。否則，分析失敗，表示輸入符號(hào)串不是文法的一個(gè)句子，其中必定存在語(yǔ)法錯(cuò)誤。LR（K）。自底而上的分析方法就是移進(jìn)規(guī)約的過(guò)程。LR（K）分析法能根據(jù)分析棧的當(dāng)前內(nèi)容以及向前看輸入串的K個(gè)字符來(lái)決定分析動(dòng)作移進(jìn)還是規(guī)約。LR（K）分析方法適用范圍較廣，分析速度較快，并且能準(zhǔn)確及時(shí)地發(fā)現(xiàn)語(yǔ)法錯(cuò)誤。由于LR（K）分析方法對(duì)文法限制很少，因而大多數(shù)能用上下文無(wú)關(guān)文法描述的程序設(shè)計(jì)語(yǔ)言都可用LR分析法進(jìn)行有效分析，而且LR分析效率不亞于自頂向下分析法好、算法優(yōu)先分析法，及其他“移進(jìn)規(guī)約”分析法。因此，LR分析法是當(dāng)前最一般的語(yǔ)法分析方法。對(duì)于一般使用的程序設(shè)計(jì)語(yǔ)言的文法而言，若手工構(gòu)造分析程序，則工作量太大，而且K越大，構(gòu)造越復(fù)雜，實(shí)現(xiàn)越困難。因此，綜合考慮，本實(shí)驗(yàn)采用LR（1）分析方法進(jìn)行語(yǔ)法分析。 C語(yǔ)言抽象出來(lái)的文法規(guī)則文法是為了深入研究語(yǔ)言的內(nèi)在性質(zhì)，而構(gòu)造語(yǔ)言的方法。換句話說(shuō)，給定一個(gè)文法，就能從結(jié)構(gòu)上唯一的確定語(yǔ)言（形式語(yǔ)言理論可以證明此結(jié)論為真）。一個(gè)文法必須由4部分組成：1. 字母表，表中的字符成為終結(jié)符。因?yàn)橥ㄟ^(guò)文法規(guī)則，最終得到的句子只能含有這些字符，這種字母稱為終結(jié)符集合，記為termanal。2. 一個(gè)中間字母集，稱為非終結(jié)符，記為nontermanal，一般出現(xiàn)在規(guī)則左部的符號(hào)都是非終結(jié)符。3. 文法規(guī)則集合。規(guī)則形如type_specifier void。讀作“導(dǎo)出”、“產(chǎn)生”、“生成”或者“定義為”。4. 文法的開始符號(hào)S0。S0為特殊的非終結(jié)符。下面是總結(jié)出來(lái)的c語(yǔ)言的文法，總共有57條規(guī)則：1 S0 translation_unit 2 translation_unit external_declaration 3 external_declaration function_definition 4 external_declaration declaration 5 declaration type_specifier id 。 6 type_specifier void 7 type_specifier int 8 type_specifier double 9function_definitiontype_specifier function_name parameter p