【文章內(nèi)容簡介】 自頂向下的語法分析時(shí)，通常有兩個(gè)障礙須加以解決： (1) 由于采取了最左推導(dǎo)，故當(dāng)相應(yīng)文法 G 中含有左遞歸的非終結(jié)符號時(shí)，便會使語法分析過程陷入循環(huán)不已的狀況。 (2) 采用最左推導(dǎo)以實(shí)現(xiàn)對符號串 w 的匹配，實(shí)際上是一個(gè)用文法產(chǎn)生式的諸候選式反復(fù)進(jìn)行試探的過程，這勢必會 出現(xiàn)大量的回溯，從而導(dǎo)致語法分析效率的大幅度下降。 因此，欲實(shí)現(xiàn)自頂向下的語法分析，其首要任務(wù)是改造程序設(shè)計(jì)語言的文法，使得文法無左遞歸且無左公因子，以消除其中的左遞歸和避免回溯的出現(xiàn)。 自底向上的語法分析 所謂自底向上的語法分析，是指從給定的輸入串 w=a1a2?an 出發(fā)，試圖利用相應(yīng)文法中的產(chǎn)生式，逐步將其歸約為文法的開始符號 S，即從葉結(jié)點(diǎn) a1,a2,?,an 出發(fā)，試圖逐步向上構(gòu)造一個(gè)語法樹，而其根結(jié)點(diǎn)恰好為 S0 由于上述分析過程通常采用的是最左歸約，所以實(shí)現(xiàn)此種語法分析的關(guān)鍵，是在分析的每一步 ，如何尋找或確定當(dāng)前句型的句柄，以及確定將其歸約為什么非終結(jié)符號。 和自頂向下的分析過程一樣，實(shí)現(xiàn)自底向上的分析，通常也須使用一個(gè)分析棧來存放分析過程中所得的文法符號。分析開始時(shí)，在棧底放置一個(gè)界符 ，然后將輸入符號逐個(gè)推入棧內(nèi)，一旦在分析棧的棧頂出現(xiàn)句柄，就用相應(yīng)的產(chǎn)生式的左部去替換這個(gè)句柄，即進(jìn)行一次歸約。由于歸約，便得到了新的棧頂，此時(shí)再查看棧的頂部是否形成新的句柄：若是，再進(jìn)行歸約；反之，則繼續(xù)將后續(xù)的輸入符號移入棧內(nèi)，并重復(fù)上述過程。若最終能將全部輸入符號（不包括右界符 ）移掉，且分析棧中只留下棧 底符號 及最后一步歸約所得的文法開始符號，則表明對輸入串的分析已經(jīng)成功。但若全部輸入符號已被移掉，而分析棧卻不能出現(xiàn)上述格局，則表明輸入符號串不是文法的一個(gè)句子，其中必定存在語法錯(cuò)誤。通常將上述過程稱為“移進(jìn) 歸約”分析，它是最基本的自底向上分析過程。在此基礎(chǔ)上，根據(jù)尋找句柄策略的不同，便形成了不同的自底向上的語法分析方法。 6 語義分析 在完成了上述過程后編譯程序?qū)⒃闯绦蜃兂梢环N內(nèi)部表示形式，這種內(nèi)部表示形式就叫做中間代碼或中間語言，它是一種結(jié)構(gòu)簡單、含義明確的記號系統(tǒng)。有些快速編譯程序幾乎沒有中間 代碼，但是為了使目標(biāo)代碼的優(yōu)化比較容易實(shí)現(xiàn)，獨(dú)立于機(jī)器進(jìn)行，許多編譯程序都采用了某種復(fù)雜性程度介于源程序語言和機(jī)器語言之間的中間語言。但是，想對于詞法分析和語法分析都已有相當(dāng)成熟的理論和算法，中間代碼目前還沒有一種公認(rèn)的形式系統(tǒng)，比較接近形式化的方法是語法制導(dǎo)翻譯。 符號表 符號表的信息欄中登記了每個(gè)名字的有關(guān)性質(zhì)，如類型（整、實(shí)或布爾等）、種屬（簡單變量、數(shù)組、過程等）、大?。ㄩL度，即所需的存儲單元字?jǐn)?shù)）以及相對數(shù)（指分配給該名宇的存儲單元的相對地址）。不同的程序語言對于名字性質(zhì)的定義各有不同。 現(xiàn)今多數(shù)程序語言中的名字或者是用說明語句規(guī)定其性質(zhì)，或者采用某種隱含約定（如 FORTRAN 中凡以字符 I， J，? N開頭的標(biāo)識符代表整型變量名）。有些程序語言，如 ADL 沒有說明語句也沒有隱含約定，因此，符號表的性質(zhì)須到目標(biāo)程序運(yùn)行時(shí)才能確定下來。但編譯時(shí)登記在符號表中的各名字的性質(zhì)只能來自說明語句（包括隱含約定和標(biāo)號定義）或其它引用情形。 對于變量名、數(shù)組名和過程名而言，它們的信息欄中一般要求有下列信息： 變量 類型（整、實(shí)、雙實(shí)、布爾、字符、復(fù)、標(biāo)號或指針等）； 種屬（簡單變量、數(shù)組或記錄結(jié)構(gòu)等）； 長度（ 所需的存儲單元數(shù)）； 相對數(shù)（存儲單元相對地址）； 若為數(shù)組，則記錄其內(nèi)情向量； 若為記錄結(jié)構(gòu)，則把它與其分量按某種形式聯(lián)系起來； 形式參數(shù)標(biāo)志； 若在 COMMON 或 EQUVALENCE 語句中（ FORTRAN 語言），把它和有關(guān)名字連接在一起；它的說明是否已處理過（即標(biāo)志位“定義否”）； 是否對這個(gè)變量進(jìn)行過賦值（包括出現(xiàn)在輸人名表中）的標(biāo)志位。 過程 是否為程序的外部過程？ 若為函數(shù)，類型是什么？ 其說明是否處理過？ 是否遞歸？ 形式參數(shù)是些什么？為了與實(shí)參進(jìn)行比較，必須把它們的種屬、類型信息同過程名 聯(lián)系在一起。 對于那些只使用單一符號表的簡單語言，對符號表填入新項(xiàng)的工作可由詞法分析程序 7 來完成。也就是，當(dāng)掃描器碰到一個(gè)標(biāo)識符時(shí)就對它查填符號表，然后回送它在符號表中的位置作為單詞值。但在某些語言中，甚至在同一過程段里允許用同一標(biāo)識符標(biāo)識各種不同對象。例如， XYZ 可能既是一個(gè)實(shí)變量名又是一個(gè)標(biāo)號名，或者又是某個(gè)結(jié)構(gòu)型數(shù)據(jù)的一個(gè)分量名。在這種情況下，使用單一符號表或由詞法分析程序負(fù)責(zé)查填符號表都是非常不方便的。因此，采用多種符號表并讓語法 —— 語義分析程序負(fù)責(zé)查填工作是比較妥當(dāng)?shù)?。對于詞法分析程序來說，只要求它 凡碰到標(biāo)識符就直接送出此標(biāo)識符自身即可。 符號表中信息欄的具體組織和安排取決于所翻譯的具體語言與目標(biāo)機(jī)器（的字長和指令系統(tǒng)）。 類型檢查 為了進(jìn)行類型檢查，編譯器需要給源程序的每一個(gè)組成成分賦予一個(gè)類型表達(dá)式。然后，編譯器需要確定這些類型表達(dá)式是否滿足一組邏輯規(guī)則。這些規(guī)則被稱為源語言的類型系統(tǒng)。 類型檢查具有發(fā)現(xiàn)程序中的錯(cuò)誤的功能。原則上，如果目標(biāo)代碼在保存元素值的同時(shí)保存了元素類型的信息，任何檢查都可以動態(tài)地進(jìn)行。一個(gè)健全的類型系統(tǒng)可以消除對動態(tài)類型檢查的需要，因?yàn)樗梢詭椭覀冹o態(tài)地確定這些 錯(cuò)誤不會在程序運(yùn)行的時(shí)候發(fā)生。如果編譯器可以保證它接受的程序在運(yùn)行時(shí)刻不會發(fā)生類型錯(cuò)誤，那么該語言的這個(gè)實(shí)現(xiàn)就被稱為強(qiáng)類型的。 8 第 3 章 系統(tǒng)詳細(xì)設(shè)計(jì) 系統(tǒng)設(shè)計(jì)基本思路 基于 C 語言源程序分析器的開發(fā)在可行性分析的基礎(chǔ)上進(jìn)一步全面、深入的分析，弄清 C語言的編譯原理及運(yùn)行狀況，在編譯程序工作的五個(gè)階段中 ,每個(gè)階段都必須遵從功能等價(jià)的原則。詞法規(guī)則與語法分析階段依據(jù)的語法規(guī)則一同構(gòu)成了一個(gè)語言的語法 ,而語法則是從 形 的角度衡量一個(gè)程序是否合法。所以在詞法分析階段 ,詞法規(guī)則成為重要的研究對象。詞法分析器所 處理的對象即詞法分析程序的輸入數(shù)據(jù) ,實(shí)際上是源程序經(jīng)過編譯預(yù)處理 ,去掉多余的符號后而形成的代碼 ,這樣給詞法分析帶來方便。詞法分析的過程是線性的從頭至尾掃描一遍 ,復(fù)雜度較低 ,易實(shí)現(xiàn)。最后概括出要實(shí)現(xiàn)的幾個(gè)功能流程圖如下： 詞法分析模塊設(shè)計(jì) 詞法分析程序需要完成的任務(wù)如下 : 1) 識別出源程序的各個(gè)語法單位 。 2) 剔除無用的空白字符、制表符、回車字符以及其他與輸入介質(zhì)相關(guān)的非實(shí)質(zhì)性字符 。 3) 過濾掉源程序中的注釋 。 4) 進(jìn)行 詞法檢查，如果出現(xiàn)錯(cuò)誤，記錄出錯(cuò)信息并報(bào)告。 我們將編譯程序的重點(diǎn)放在中間代碼生成階段。詞法分析器的功能是輸入源程序，輸出單詞符號。這部分程序主要包括兩個(gè)類： 包括兩個(gè)類： 輸入文件 開始 詞法分析 語法分析 建立符號表 類型檢查 輸出信息 語法樹 符號表 9 Class CTokenizer： 從一個(gè)字符串中（這個(gè)把一個(gè)文件看作是一個(gè)字符串， MFC 中 CFileCString）分離出一個(gè)一個(gè) token，配上簡單的類型通過 NextToken（）返回： define TT_EOL 39。\n39。 define TT_EOF 1 define TT_INTEGER 2 define TT_REAL 3 define TT_WORD 4 define TT_STRING 39。39。 define TT_CHAR 39。\39。39。 Class CScaner： 得到具體的的 token 類型，定義 TokenType 如下： enum TokenType { // reserved Keyword _AUTO, _DOUBLE, _INT, _STRUCT, _BREAK, _ELSE, _LONG, _SWITCH, _CASE, _ENUM, _REGISTER, _TYPEDEF, _CHAR, _EXTERN, _RETURN, _UNION, _CONST, _FLOAT, _SHORT, _UNSIGNED, _CONTINUE, _FOR, _SIGNED, _VOID, _DEFAULT, _GOTO, _SIZEOF, _VOLATILE, _DO, _IF, _STATIC, _WHILE, _READ, _WRITE, _PRINTF, // operations ASSIGN, PLUS, MINUS, TIMES, DIV, MOD, BITWISE_AND, BITWISE_OR, BITWISE_NOT, LOGICAL_NOT, LT, GT, // interpunctions LPARAN, RPARAN, LBRACE, RBRACE, LSQUARE, RSQUARE, COMMA, DOT, SEMI, COLON, // plex operations 10 EQ/* == */, NEQ/* != */, PLUS_PLUS/* ++ */, MINUS_MINUS/* */, PLUS_ASSIGN/* += */, MINUS_ASSIGN/* = */, TIMES_ASSIGN/* *= */, DIV_ASSIGN/* /= */, NGT/* = */, NLT/* = */, LOGICAL_AND/* amp。amp。 */, LOGICAL_OR/* || */, // others _EOF, _ID, _NUM, _STRING, _CHARACTER, _LABEL