【正文】 的靜態(tài)變量，而現(xiàn)在可以通過這些例程在yylex()之外設置和獲取這些值。在制作“純”詞法分析器中可能需要在主函數(shù)中添加以下代碼：yyscan_t scaninfo。 指向詞法分析器每個實例數(shù)據(jù)的指針int yylex_init(amp。scaninfo)。 創(chuàng)建一個詞法分析器；int yylex_init_extra(userstuff,amp。scaninfo)。 創(chuàng)建一個詞法分析器，其帶有指向用戶數(shù)據(jù)的指針while(…){tok = yylex(scaninfo)。 一直調(diào)用直到分析結束}yylex_destroy(scaninfo) 釋放詞法分析器的數(shù)據(jù)因為整個Bison的分析就只發(fā)生在一次調(diào)用yyparse例程中，因此語法分析器可以在分析開始時創(chuàng)建實例數(shù)據(jù)進行分析，最后不需要調(diào)用其他程序就能釋放數(shù)據(jù)。 二義性沖突Flex在掃描過程中可能會遇到二義性的情況，這時詞法分析的識別算法應該有一定的原則用來解決二義性問題，一般情況下應該有兩個原則要遵守：1) 優(yōu)先匹配原則：如果有兩個或者更多個正則式可以和某個子串匹配，而且匹配的長度相同，那么Flex就會以最前面出現(xiàn)的那么正則式為準，也就是說，正則式越處在前面，它匹配的優(yōu)先級越高。如果任何一個非空子串沒有正則式相匹配，那么詞法分析器應該報錯。2) 最長匹配原則：當詞法分析在識別符號時，如果有幾個規(guī)則都能適用，F(xiàn)lex總是尋找最長可能的子串與正則式匹配。由于Bison并不分析二義性文法，所以它在把語法翻譯成語法分析器時有可能報告沖突。一些情況下語法確實存在歧義而Bison無法處理這種情況；其他情況下，語法本身并不存在歧義，但是Bison所使用的標準分析技術還不夠強大到分析該語法。當Bison試圖創(chuàng)建語法分析器時存在兩種可能的沖突，即移近/規(guī)約和規(guī)約/規(guī)約沖突，兩種沖突的分類基于一個指針歸約時另外一個指針的情況。移近/規(guī)約沖突是指一個輸入字符串存在兩種可能的語法分析器，并且其中一個分析器結束一條規(guī)則，而另外一個并不結束。規(guī)約/規(guī)約發(fā)生在同一個記號可以結束兩條不同規(guī)則的時候。要講述這兩種沖突，就要從Bison內(nèi)部運行的方式講起。在Bison的操作模型模型中用移動一個指針(↑)來代表Bison讀入記號%token A B C%%Start : ↑ A B C。當Bison語法分析器讀入記號時，這個指針進行移動，當語法分析器讀入了A和B時：Start: A B ↑ C。有時候因為Bison語法中存在多種選擇，所以可能存在不止一個指針：%token A B C D E F%%Start: x | y。x: A B ↑ C D。y: A B ↑ E F。上面的例子中有兩種方法讓指針消失：一種發(fā)生在后續(xù)記號無法匹配當前已經(jīng)部分匹配的規(guī)則時。如果下一個語法分析器讀到的記號時C的話，第二個指針將消失而第一個指針可以向前移動：Start: x | y。x: A B C ↑ D。y: A B E F。另外一種讓指針消失的方法是把它們合并成一個公共的子規(guī)則，如下面的例子：Start: x| y。x: A B z R。y：A B z S。z: C D。在讀到一個A后，存在兩種指針：Start: x | y。x: A ↑ B z R。y: A ↑ B z S。z: C D。在A B C后將只有一個指針存在于規(guī)則z中：Start: x | y。x: A B z R。y: A B z S。z: C ↑ D。而在A B C D后，這個語法分析器結束規(guī)則z，再次出現(xiàn)兩個指針：Start: x | y。x: A B z ↑ R。y: A B z ↑ S。z: C D。歸約/歸約沖突發(fā)生在類似這些情況下：Start: X b | y b。x: A ↑。y: A ↑。讀到A后在規(guī)則x和規(guī)則y的末尾各又一個指針，他們都希望被歸約，所以這是一個歸約/歸約沖突。但下面的例子就不存在沖突：Start: x B | y B。x: A ↑。y； A ↑。這個例子沒有沖突的原因是Bison語法分析器可以在A之后預讀一個記號。如果它看到的是B，規(guī)則y中的指針將在規(guī)則x被歸約之前消失。相似的，如果它看到的是C，規(guī)則x中的指針將在規(guī)則y被歸約之前消失。移近/歸約沖突：Start: x | y R。x: A ↑ R。y: A ↑。在語法分析器讀到A后，規(guī)則y需要歸約規(guī)則start，這樣R就可以被接納，而規(guī)則x也能夠接受R。 小結本章講述了語法分析的實現(xiàn)，在介紹了語法分析的知識和Bison語法分析器的知識之后，論述了用Bison實現(xiàn)Prolog編譯器的語法分析部分。在開發(fā)Prolog編譯器過程中會遇到一些特殊性的問題，例如Flex和Bison合作的問題，F(xiàn)lex和Bison的知識各大教材上都有或多或少的介紹，但是真正介紹它們聯(lián)合工作并且只是作為整個編譯過程的一部分工作的書籍卻很少，而且它們合作的特殊性還體現(xiàn)在根據(jù)開發(fā)者需要的不同，接口的表示就會不同，這也就是說如果要用Flex和Bison一起完成可重入的詞法語法分析，就要具體問題具體分析。二義性應該說是語法分析中可能會遇到的問題，在語法分析器中，遇到二義性除了修改語法規(guī)則外，就要規(guī)定優(yōu)先級，這也是開發(fā)編譯器遇到的特殊性問題。第5章 語義分析的實現(xiàn) 語義分析語義分析階段是計算編譯過程所需的附加信息階段，它與語法分析階段的不同是語義分析要計算上下文無關文法和標準分析算法以外的信息。語義分析根據(jù)編譯器完成的分析是靜態(tài)定義的這個原因也叫做靜態(tài)語義分析。在典型的靜態(tài)類型語言類似于C語言，語義分析包括記錄聲明中建立的名字的含義和構建符號表等。編譯程序在語義分析階段主要有兩個任務：第一個任務是對每個語法結構進行檢查類型是否合理、名字是否定義、語法上正確的程序是否真正有意義等靜態(tài)語義檢查；第二個任務是如果靜態(tài)語義正確，那么就繼續(xù)執(zhí)行語義處理，從而生成某種格式統(tǒng)一的中間代碼或者直接生成目標代碼。通常有專門的語義子程序來完成語義分析和中間代碼生成階段的工作。這些語義子程序可以由語法分析程序在進行語法分析的過程中分析出某個語法單位時直接調(diào)用，也可以在生成語法樹后在調(diào)用，進行語義處理。因為語義的上下有關性，要對語義進行形式化描述是十分困難的，在描述程序語言語義工具的選擇上，目前較為常使用的是屬性文法和采用語法制導翻譯的方法完成對語法成分的翻譯工作。 靜態(tài)語義檢查靜態(tài)語義檢查的目的就是檢查每個語法成分的靜態(tài)語義，如果程序中有某些類型錯誤靜態(tài)語義檢查會報告錯誤。在進行詞法分析時會進行詞法檢查，語法分析會進行語法檢查，在語義分析階段也必會進行語義檢查。動態(tài)語義檢查是在運行時進行的，它需要生成相應的目標代碼[13]。靜態(tài)語義檢查不同于動態(tài)語義檢查，它完成于編譯的時候，它的檢查范圍分為：(1) 相關名字的檢查。編譯程序必須檢查每個地方出現(xiàn)的名字是否相同來預防一個出現(xiàn)多次而沒檢查出來。(2) 控制流檢查。這是為了保證控制語句有合法的轉向點。(3) 一致性檢查。在多數(shù)語言中要求只能定義一次對象。就像不能重復出現(xiàn)枚舉類型的元素、在相同作用域中只能說明一次標識符等。(4) 類型檢查。編譯程序必須在操作符用于的操作數(shù)互不相容的時候報錯。同樣的，類型檢查不許驗證指針地址訪問只作用于指針、下標只作用于數(shù)組、函數(shù)必須有正確的參數(shù)個數(shù)和類型等。 屬性文法在編譯技術中屬性文法是用來說明程序語言語義的工具，屬性文法是當前比較流行的一種語義描述方法。編譯程序中用屬性來描述處理對象的特征。文法符號的屬性可分為綜合屬性和繼承屬性兩類：由相應語法樹中結點的子節(jié)點屬性計算得到綜合屬性，綜合屬性用于自底向上傳遞信息，即沿語法樹從分支結點到根結點向上傳遞；有相應語法樹中結點的父結點屬性計算得到繼承屬性，繼承屬性用于自頂向下傳遞信息，即沿語法樹從根結點到分支結點向下傳遞。繼承屬性可以利用反應上下文依賴的特性方便的表示程序語言的上下文結構關系。在語言的文法中增加了屬性的文法就是屬性文法，它是適用于定義語義的一種特殊文法。屬性文法在各個文法的符號上加入了該文法符號以“屬性”的形式存在的語義信息，然后給出每個文法符號屬性的求值規(guī)則，這些規(guī)則是根據(jù)產(chǎn)生式所包含的含義給出的，這樣，帶有語義屬性的上下文無關的屬性文法就形成了。例如，圖51所示簡單算術表達式求值的屬性文法：圖51 簡單算術表達式求值的屬性文法圖中產(chǎn)生式每一個非終結符都用一個val屬性表示整數(shù)值。E、T、F等這些與產(chǎn)生式關聯(lián)的語義規(guī)則的左部符號，它們各自相應的右部符號決定它們屬性值的計算，這也叫做綜合屬性。S的屬性可以理解為是一個虛屬性，因為它在語義規(guī)則中沒有出現(xiàn)。常見的中間語言有：抽象語法樹、逆波蘭表示法、三地址代碼。抽象語法樹在中間語言表示中比較常見。在抽象語法樹中諸如常量或者變量這樣的運算對象都在葉子結點中表示，運算符用其他內(nèi)部結點表示。抽象語法樹描述了源程序的層次結構并同時展示了一個操作過程。逆波蘭式是一種表示表達式的方法，它是由波蘭人盧卡西維奇設計發(fā)明的，這種表示法在后面寫運算符，在前面寫運算量。比如a+b寫成逆波蘭式就是ab+。把逆波蘭式的定義歸結一下，就是對于表達式E，它的逆波蘭式遞歸為：(1) 如果E為(E1)形式，那么E的逆波蘭式就是E1的逆波蘭式。(2) 如果E是E1 op E2的形式，如果op是二元運算符，那么它的逆波蘭式就是E1‘E2’op；如果op是一元運算符，那么視E1和E1‘為空。(3) 如果E是變量或者常量，那么它自身既是它的逆波蘭式。三地址代碼語句的一般形式是z=x op y，其中x、y、z是常量、名字或者臨時變量；op是類似于浮點運算符、邏輯運算符或者定點運算符等運算符。三地址代碼的三個地址中一個用來存放運算結果，兩個用來存放運算對象。 符號表在編譯程序中符號表用來存放屬性信息。這些屬性信息是標示符的信息并且是其語義特征屬性的集中反映，詞法分析和語法分析過程中不斷積累和更新符號表中屬性信息。用以下幾個方面歸結符號表的功能[14]：1) 收集符號屬性在分析語言程序中標示符說明部分時編譯程序會根據(jù)說明信息收集有關標示符的屬性，并把符號的相應屬性信息建立在符號表中。例如當程序分析到下述說明語句：int A。 float B[5]符號A的屬性收集到符號表中是一個整型變量，符號B是一個帶有5個元素的浮點型一維數(shù)組。2) 目標代碼生成階段地址分配以符號表作為依據(jù)每個符號變量需要在目標代碼生成時確定其在存儲分配的位置。語言程序中的符號變量由它被定義的存儲類別（如在C、FORTRAN語言中）或被定義的位置（如分程序結構的位置）來確定。首先要確定符號變量被分配的區(qū)域。在C語言中首先要確定該符號變量是分配在函數(shù)靜態(tài)區(qū)、公共區(qū)、函數(shù)運行時的動態(tài)區(qū)還是文件靜態(tài)區(qū)等。其次是決定該變量在某個區(qū)中所處的具體位置，這個一般來說通常根據(jù)變量出現(xiàn)的次序來決定。而作為該變量的語義信息如有關區(qū)域的標志及相對位置都被收集在該變量的符號表屬性中。3) 上下文語義的合法性檢查的依據(jù)在程序的不同地方可能出現(xiàn)同一個標示符，這樣也需要在不同情況下收集相應的符號屬性。標示符在多趟編譯及程序分段編譯的情況下，更應該在上下文中檢查其屬性的合法性一致性。相應的上下文語義檢查通過符號表中屬性記錄進行。 符號的主要屬性及作用大體上語言符號可分為三種：即關鍵字符號、標識符符號和操作符符號。我們?yōu)樗鼈兘⒘瞬煌姆柋?，建立不同符號表的原因是因為它們的屬性之間的較大差別，也有些編譯程序在同一個符號表中建立關鍵字符號和標識符符號。有些屬性通常不管在什么情況下都是需要的，盡管在不同語言中標識符不盡相同。1) 符號名在語言中，可以使一個變量的名字、一個過程的名字或者一個函數(shù)的名字等由若干個不包含空格的字符組成的字符串作為標識符。在語言程序中有許多個函數(shù)、變量和過程，而標識符字符串就是它們的惟一標志，在符號表中各個表項之間的唯一區(qū)別就是符號名，正因為這個原因一般符號名是不允許重名的。我們可以把符號名用該符號在表中的位置替換，因為該符號名已經(jīng)和它在符號表中的位置有了對應關系。既然可以把符號名用該符號在表中的位置替換，那么這個位置信息應該也可以用便于識別比較的方式表達，這樣就有了標識符的內(nèi)部代碼，即標識符在符號表中位置的整數(shù)值。有了標識符內(nèi)部代碼，還縮短了符號表位置表達的長度。2) 符號的類型函數(shù)和變量標識符，除了過程標識符之外，都有數(shù)據(jù)類型屬性，函數(shù)值的數(shù)據(jù)類型是函數(shù)的數(shù)據(jù)類型?；镜臄?shù)據(jù)類型有實型、字符型、整型、布爾型等，在一個符號的定義中得到該符號的類型屬性。變量的數(shù)據(jù)在存儲空間的存儲格式由變量符號的類型屬性決定，這個屬性還決定了在該變量上可以進行的運算操作。3) 符號的存儲類別大多數(shù)語言采用兩種方式對變量的存儲類別定義：一種是根據(jù)定義說明在程序中的位置來決定，例如在C語言中，默認在函數(shù)體內(nèi)存儲類關鍵字所定義的變量是內(nèi)部變量，而默認在函數(shù)體外存儲類關鍵字所定義的變量是外部變量，也是公共存儲變量。另一種方式是使用關鍵字指定，例如在C語言中用regist定義使用寄存器存儲的變量，用static定義是屬于函數(shù)內(nèi)部的靜態(tài)存儲變量或者是屬于穩(wěn)健的靜態(tài)存儲變量。在FORTRAN中用save來定義過程或者函數(shù)的內(nèi)部靜態(tài)存儲變量。4) 符號的作用域及可視性符號的作用域即一個符號變量在程序中的作用范圍。一般來說，符號的作用域被決定于由定義該符號的存儲類關鍵字及該符號的位置。一個外部變量的作用域在C語言中可以是整個程序，這樣在整個程序中一個外部變量符號的定義只能出現(xiàn)一次，為了使用和編譯的方便同名變量的說明可以出現(xiàn)多次，而FORTRAN語言中mon公共變量通常僅在定義說明這個mon塊的過程或者函數(shù)中起作用[15]。一般來說一個變量可以出現(xiàn)的場合就是它的作用域，也就是說變量可以再其作用域范圍