簡(jiǎn)單的一遍編譯器

1、第2章 簡(jiǎn)單的一遍編譯器v這一章是本書(shū)第3章到第8章的內(nèi)容簡(jiǎn)介。本章通過(guò)開(kāi)發(fā)一個(gè)把中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的C程序來(lái)展示一些基本編譯技術(shù)。本章重點(diǎn)描述編譯器的前端部分，即詞法分析、語(yǔ)法分析和中間代碼生成。第9章和第10章講述代碼生成和代碼優(yōu)化。2.1 概述v程序設(shè)計(jì)語(yǔ)言可以通過(guò)描述以下兩個(gè)方面來(lái)定義：第一方面是程序模式，即語(yǔ)言的語(yǔ)法；第二方面是程序含義，即語(yǔ)言的語(yǔ)義。v為了說(shuō)明語(yǔ)言的語(yǔ)法，我們介紹一種廣為使用的表示法：上下文無(wú)關(guān)文法或者BNF（Backus-Naur）范式v在定義語(yǔ)言的語(yǔ)義時(shí)，我們將使用非形式化方法和啟發(fā)性實(shí)例。v上下文無(wú)關(guān)文法除了可以用于定義語(yǔ)言的語(yǔ)法之外，還可用于指導(dǎo)源程

2、序的翻譯。面向語(yǔ)法的編譯技術(shù)，如語(yǔ)法制導(dǎo)翻譯技術(shù)，對(duì)于組織編譯器的前端十分有用v在我們的編譯器里，詞法分析器首先把輸入字符流轉(zhuǎn)換成記號(hào)流。然后，記號(hào)流作為下一個(gè)階段的輸入，產(chǎn)生源程序的中間表示，這個(gè)過(guò)程如圖2-1所示。圖中的“語(yǔ)法制導(dǎo)翻譯器”由一個(gè)語(yǔ)法分析器和一個(gè)中間代碼生成器構(gòu)成。2.2 語(yǔ)法定義v本節(jié)介紹一種定義語(yǔ)言語(yǔ)法的表示法，稱為上下文無(wú)關(guān)文法（簡(jiǎn)稱文法）。上下文無(wú)關(guān)文法將貫穿本書(shū)始末，作為編譯器前端定義的一部分。vif-else語(yǔ)句的構(gòu)造規(guī)則可以表達(dá)為stmt - if ( expr ) stmt else stmt(2-1)這里，箭頭可以讀作“可以具有形式”。這樣的規(guī)則稱為產(chǎn)生式(

3、production)。在一個(gè)產(chǎn)生式中，像關(guān)鍵字if和括號(hào)這樣的詞法元素稱為記號(hào)(token)，像expr和stmt這樣的變量表示一個(gè)記號(hào)序列，并稱之為非終結(jié)符(nonterminal)。v上下文無(wú)關(guān)文法包含如下四個(gè)部分：一個(gè)記號(hào)集合，稱為終結(jié)符號(hào)。一個(gè)非終結(jié)符集合。一個(gè)產(chǎn)生式集合。每個(gè)產(chǎn)生式具有一個(gè)左部和一個(gè)右部，左部和右部由箭頭連接，左部是一個(gè)非終結(jié)符。右部是記號(hào)和（或）非終結(jié)符序列。一個(gè)開(kāi)始符號(hào)。開(kāi)始符號(hào)是一個(gè)指定的非終結(jié)符。v我們約定，定義語(yǔ)法時(shí)只需列出文法的產(chǎn)生式，并把以開(kāi)始符號(hào)為左部的產(chǎn)生式列在最前面。在以后的討論中我們假設(shè)：數(shù)字、類似于 list + digit(2-2)list

4、 - list digit(2-3)list - digit(2-4)digit - 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9(2-5)左部的非終結(jié)符皆為list （列表）的三個(gè)產(chǎn)生式的右部可以合并成：list - list + digit | list digit | digitv按照我們前邊的約定，文法的記號(hào)是下列符號(hào)：+ - 0 1 2 3 4 5 6 7 8 9斜體詞list 和digit 是非終結(jié)符，list 是開(kāi)始非終結(jié)符，因?yàn)樗鶎?duì)應(yīng)的產(chǎn)生式列在最前面。v如果一個(gè)非終結(jié)符出現(xiàn)在一個(gè)產(chǎn)生式的左部，該產(chǎn)生式稱為該非終結(jié)符的產(chǎn)生式。記號(hào)串是零個(gè)或者多個(gè)

5、記號(hào)的序列。一個(gè)包含零個(gè)記號(hào)的記號(hào)串稱為空串，記為。v例2.2 由例2.1的文法定義的語(yǔ)言是由加號(hào)和減號(hào)分隔的數(shù)字序列。v非終結(jié)符digit的10個(gè)產(chǎn)生式表示digit可以代表0,1, ,9中的任何記號(hào)。產(chǎn)生式(2-4)表明單個(gè)數(shù)字本身是一個(gè)列表。產(chǎn)生式(2-2)和(2-3)表示：當(dāng)我們碰到一個(gè)列表后面跟著一個(gè)加號(hào)或者減號(hào)，隨后是另外一個(gè)數(shù)字，則我們得到了一個(gè)新的列表。v顯然，產(chǎn)生式(2-2)到產(chǎn)生式(2-5)足以定義我們需要的語(yǔ)言。例如，我們可以按下面的方法推導(dǎo)出9-5+2是一個(gè)list：a) 由于9是一個(gè)digit，根據(jù)產(chǎn)生式(2-4)，9是一個(gè)list；b) 由于9是一個(gè)list，5是一

6、個(gè)digit，根據(jù)產(chǎn)生式(2-3)，9-5是一個(gè)list；c) 由于9-5是一個(gè)list，2是一個(gè)digit，根據(jù)產(chǎn)生式(2-2)，9-5+2是一個(gè)list。v上述推理過(guò)程如圖2-2中的樹(shù)所示。樹(shù)中的每個(gè)節(jié)點(diǎn)用一個(gè)文法符號(hào)標(biāo)記。一個(gè)內(nèi)節(jié)點(diǎn)和它的所有子節(jié)點(diǎn)對(duì)應(yīng)一個(gè)產(chǎn)生式。內(nèi)節(jié)點(diǎn)對(duì)應(yīng)產(chǎn)生式的左部，子節(jié)點(diǎn)對(duì)應(yīng)產(chǎn)生式的右部。這樣的樹(shù)稱作分析樹(shù)。v例2.3 Pascal 語(yǔ)言的begin-end語(yǔ)句塊(block)是由分號(hào)分隔的語(yǔ)句序列。begin-end語(yǔ)句塊的文法結(jié)構(gòu)類似于例2.1中的列表，差別僅在于begin和end之間允許有空語(yǔ)句。我們從以下的產(chǎn)生式開(kāi)始，開(kāi)發(fā)begin-end語(yǔ)句塊的文法：bl

7、ock - begin opt_stmts endopt_stmts - stmt_list | stmt_list - stmt_list ; stmt | stmtv請(qǐng)注意， opt_stmts右部的第二個(gè)可選項(xiàng)表示空符號(hào)串，即opt_stmts可以用空串代替。于是block可以只由begin和end這兩個(gè)記號(hào)構(gòu)成。stmt_list的產(chǎn)生式類似于例2.1中l(wèi)ist的產(chǎn)生式，分號(hào)對(duì)應(yīng)于算術(shù)操作符，stmt對(duì)應(yīng)于digit。我們還沒(méi)有寫(xiě)出stmt的產(chǎn)生式。稍后，我們將討論不同語(yǔ)句對(duì)應(yīng)的產(chǎn)生式，如if語(yǔ)句、賦值語(yǔ)句等等。2.2.1 分析樹(shù)v分析樹(shù)描繪了如何從文法的開(kāi)始符號(hào)開(kāi)始推導(dǎo)出它的語(yǔ)言中的

8、一個(gè)語(yǔ)句。v形式地說(shuō)，給定一個(gè)上下文無(wú)關(guān)文法，分析樹(shù)是具有如下特性的樹(shù)：樹(shù)根標(biāo)記為開(kāi)始符號(hào)。每個(gè)葉節(jié)點(diǎn)由記號(hào)或者標(biāo)記。每個(gè)內(nèi)節(jié)點(diǎn)由一個(gè)非終結(jié)符標(biāo)記。如果A是某個(gè)內(nèi)節(jié)點(diǎn)的非終結(jié)符號(hào)標(biāo)記，X1,X2, ,Xn是該節(jié)點(diǎn)從左到右排列的所有子節(jié)點(diǎn)的標(biāo)記，則AX1X2 Xn是一個(gè)產(chǎn)生式。這里，X1,X2, ,Xn是一個(gè)終結(jié)符或非終結(jié)符。對(duì)于A，分析樹(shù)中標(biāo)記為A的節(jié)點(diǎn)只有一個(gè)標(biāo)記為的子節(jié)點(diǎn)。v一棵分析樹(shù)從左到右的葉節(jié)點(diǎn)是這棵分析樹(shù)生成的結(jié)果。分析樹(shù)生成的結(jié)果是由根節(jié)點(diǎn)的非終結(jié)符生成或?qū)С龅拇?。v任何樹(shù)的葉節(jié)點(diǎn)都滿足從左到右排列的自然順序，即如果a和b具有相同的父節(jié)點(diǎn)，且a在b的左部，則a和a的所有后代都在b

9、和b的所有后代的左部。v使用分析樹(shù)的概念，我們可以定義：一個(gè)文法生成的語(yǔ)言是它的某個(gè)分析樹(shù)生成的串的集合。為給定的記號(hào)串找到一個(gè)分析樹(shù)的過(guò)程稱為這個(gè)串的語(yǔ)法分析（parsing）。2.2.2 二義性v一棵分析樹(shù)讀完它的葉節(jié)點(diǎn)只能生成惟一的一個(gè)串，但是，一個(gè)文法可能有多棵分析樹(shù)生成相同的記號(hào)串。這樣的文法稱為具有二義性的文法。判斷一個(gè)文法是否具有二義性，我們只需檢查是否存在一個(gè)具有多棵分析樹(shù)的記號(hào)串。v例2.5 如果不區(qū)分例2.1中的digit和list，例2.1中的文法可以改寫(xiě)成如下形式：string - string + string | string string | 0 | 1 | 2

10、| 3 | 4 | 5 | 6 | 7 | 8 | 9把digit和list的概念合成一個(gè)非終結(jié)符串string是有意義的，因?yàn)橐粋€(gè)digit是list的特例。v從圖2-3中可以看到，表達(dá)式9-5+2現(xiàn)在有了不止一棵分析樹(shù)，分別對(duì)應(yīng)著不同的帶括號(hào)表達(dá)式(9-5)+2和9-(5+2)。這兩個(gè)表達(dá)式的值是不同的，分別是6和2。例2.1的文法不允許這樣的解釋。2.2.3 操作符的結(jié)合規(guī)則v在大多數(shù)的程序設(shè)計(jì)語(yǔ)言中，加、減、乘、除四種算術(shù)操作符都是左結(jié)合的。v某些常用操作符是右結(jié)合的，如指數(shù)操作。C語(yǔ)言中的賦值運(yùn)算操作符“ =”號(hào)也是右結(jié)合的。2.2.4 操作符的優(yōu)先級(jí)v當(dāng)不止一種操作符出現(xiàn)的時(shí)候，我

11、們需要確定操作符之間的優(yōu)先關(guān)系。v在普通的算術(shù)運(yùn)算中，乘法和除法比加法和減法具有較高的優(yōu)先級(jí)。v表達(dá)式的語(yǔ)法。算術(shù)表達(dá)式的文法可以根據(jù)操作符的結(jié)合性和優(yōu)先級(jí)表來(lái)構(gòu)建。我們從四個(gè)常用的算術(shù)操作符和一個(gè)優(yōu)先級(jí)表開(kāi)始說(shuō)起。在優(yōu)先級(jí)表中，操作符按照優(yōu)先級(jí)遞增的次序排列，相同優(yōu)先級(jí)的操作符出現(xiàn)在同一行上：左結(jié)合：+ -右結(jié)合：* /v語(yǔ)句的語(yǔ)法。在多數(shù)語(yǔ)言中，我們可以使用關(guān)鍵字識(shí)別語(yǔ)句。除了賦值語(yǔ)句和過(guò)程調(diào)用語(yǔ)句以外，所有的Pascal 語(yǔ)句都由一個(gè)關(guān)鍵字開(kāi)始。2.3 語(yǔ)法制導(dǎo)翻譯v為了翻譯程序設(shè)計(jì)語(yǔ)言的某個(gè)結(jié)構(gòu)，除了為該結(jié)構(gòu)生成的代碼以外，編譯器還需要保存許多信息。例如，編譯器可能需要知道這個(gè)結(jié)構(gòu)的類

12、型、目標(biāo)代碼中第條指令的位置、生成的指令個(gè)數(shù)等等。我們抽象地稱這些信息為與該結(jié)構(gòu)相關(guān)的屬性。v本節(jié)給出一種稱為語(yǔ)法制導(dǎo)定義的形式化方法，用以說(shuō)明程序設(shè)計(jì)語(yǔ)言中各種結(jié)構(gòu)的翻譯。一個(gè)語(yǔ)法制導(dǎo)定義根據(jù)與其語(yǔ)義部分相關(guān)聯(lián)的屬性說(shuō)明了程序設(shè)計(jì)語(yǔ)言的一個(gè)結(jié)構(gòu)的翻譯。v我們還要介紹一個(gè)更加過(guò)程化的概念，叫做翻譯模式，用來(lái)描述翻譯過(guò)程。本章我們將翻譯模式用于把中綴表達(dá)式翻譯成后綴表達(dá)式。2.3.1 后綴表示v一個(gè)表達(dá)式E 的后綴表示可以歸納地定義如下：如果E是一個(gè)變量或者常量，則E的后綴表示是E本身。如果E是形如E1 op E2的表達(dá)式，其中op是一個(gè)二元操作符，則E的后綴表示是E1 E2 op，這里E1和E

13、2分別是E1和E2的后綴表示。如果E是形如（E1）的表達(dá)式，則E1的后綴表示是E的后綴表示。v例如，(9-5)+2的后綴表示是95-2+，9-(5+2)的后綴表示是952+-。2.3.2 語(yǔ)法制導(dǎo)定義v語(yǔ)法制導(dǎo)定義使用上下文無(wú)關(guān)文法來(lái)說(shuō)明輸入的語(yǔ)法結(jié)構(gòu)。它通過(guò)每個(gè)文法符號(hào)和一個(gè)屬性集合相關(guān)聯(lián)，通過(guò)每一個(gè)產(chǎn)生式和一個(gè)語(yǔ)義規(guī)則集合相關(guān)聯(lián)。語(yǔ)義規(guī)則用來(lái)計(jì)算與產(chǎn)生式中出現(xiàn)的符號(hào)相關(guān)聯(lián)的屬性的值。文法和語(yǔ)義規(guī)則集合構(gòu)成了語(yǔ)法制導(dǎo)定義。v翻譯是一個(gè)輸入到輸出的映射。每個(gè)輸入x的輸出用下面的方式來(lái)說(shuō)明。首先，構(gòu)建x的分析樹(shù)。假定分析樹(shù)的節(jié)點(diǎn)n用文法符號(hào)X標(biāo)識(shí)。我們用X.a表示節(jié)點(diǎn)n上X的屬性a的值。節(jié)點(diǎn)n上

14、的X.a的值是使用與X產(chǎn)生式相關(guān)聯(lián)的屬性a的語(yǔ)義規(guī)則來(lái)計(jì)算的。每個(gè)節(jié)點(diǎn)都具有屬性值的分析樹(shù)稱為注釋分析樹(shù)。2.3.3 綜合屬性v如果分析樹(shù)的某個(gè)節(jié)點(diǎn)的屬性值是由其子節(jié)點(diǎn)的屬性值確定的，則我們稱該屬性為綜合屬性。一棵分析樹(shù)的所有綜合屬性值的計(jì)算只需要分析樹(shù)的一次自底向上遍歷。v例2.6 把一個(gè)由加號(hào)和減號(hào)分隔的數(shù)字序列組成的表達(dá)式翻譯成后綴表示的語(yǔ)法制導(dǎo)定義如圖2-5所示。圖中與每個(gè)非終結(jié)符相關(guān)聯(lián)的是一個(gè)具有字符串值的屬性t，屬性t表示該非終結(jié)符產(chǎn)生的表達(dá)式的后綴表示。v一個(gè)數(shù)字的后綴形式是該數(shù)字本身。例如，與產(chǎn)生式term 9相關(guān)聯(lián)的語(yǔ)義規(guī)則定義：當(dāng)該產(chǎn)生式在分析樹(shù)的節(jié)點(diǎn)上被使用時(shí)，term.

15、t的值是9。當(dāng)產(chǎn)生式expr term被應(yīng)用時(shí)，term.t的值成為expr.t的值。v產(chǎn)生式expr expr1 + term導(dǎo)出一個(gè)包含加號(hào)的表達(dá)式。加操作符的左操作數(shù)由expr1給出，右操作數(shù)由term給出。產(chǎn)生式中expr1的下標(biāo)是為了區(qū)別產(chǎn)生式左右兩側(cè)的expr。與這個(gè)產(chǎn)生式關(guān)聯(lián)的語(yǔ)義規(guī)則expr.t := expr1.t | trem.t | +定義了屬性expr.t值的計(jì)算方式，即首先連接左右操作數(shù)的后綴形式expr1.t和term.t，然后連接上加號(hào)。語(yǔ)義規(guī)則中的操作符表示字符串的連接。v圖2-6給出了對(duì)應(yīng)于圖2-2中分析樹(shù)的注釋分析樹(shù)。每個(gè)節(jié)點(diǎn)上的t屬性的值用與該節(jié)點(diǎn)的產(chǎn)生式

16、相關(guān)聯(lián)的語(yǔ)義規(guī)則計(jì)算。根節(jié)點(diǎn)的屬性值是該分析樹(shù)生成的串的后綴表示。v例2.7 假定一個(gè)機(jī)器人可以被指示從當(dāng)前位置向東、向北、向西或者向南移動(dòng)一步。這樣的指令序列可以由下面的文法產(chǎn)生：seq - seq instr | begininstr - east | north | west | south根據(jù)輸入：begin west south east east east north north機(jī)器人產(chǎn)生的位置改變?nèi)鐖D2-7所示。v在圖2-7中，每個(gè)位置用（x, y）對(duì)標(biāo)志，其中x和y分別表示從起點(diǎn)開(kāi)始，向東和向北的步數(shù)。如果x是負(fù)數(shù)，則機(jī)器人在起始位置向西移動(dòng)。如果y是負(fù)數(shù)，則機(jī)器人在起始位置向

17、南移動(dòng)。v我們來(lái)構(gòu)建一個(gè)語(yǔ)法制導(dǎo)定義，把指令序列翻譯成機(jī)器人的位置。我們要使用兩個(gè)屬性seq.x和seq.y來(lái)記錄非終結(jié)符seq生成的指令序列所產(chǎn)生的位置。最初，seq生成begin，seq.x和seq.y均被初始化為0，如圖2-8中begin westsouth的分析樹(shù)的最左內(nèi)節(jié)點(diǎn)所示。v用instr.dx和instr.dy來(lái)給定instr生成的單個(gè)指令所產(chǎn)生的位置變化。例如，如果instr生成west，則instr.dx=-1，instr.dy 0。假定seq是由一個(gè)序列seq1后面跟隨一個(gè)新指令所形成的，則機(jī)器人的新位置由下面的規(guī)則給出：seq.x := seq1.x + instr.d

18、xseq.y := seq1.y + instr.dyv用于將指令序列翻譯成機(jī)器人位置的語(yǔ)法制導(dǎo)定義如圖2-9所示。2.3.4 深度優(yōu)先遍歷v樹(shù)的遍歷是指從根開(kāi)始，以某種順序訪問(wèn)樹(shù)的每一個(gè)節(jié)點(diǎn)。本章使用圖2-10定義的深度優(yōu)先遍歷計(jì)算語(yǔ)義規(guī)則。它從根開(kāi)始，從左到右遞歸訪問(wèn)每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)，如圖2-11所示。一旦給定節(jié)點(diǎn)的所有后代都被訪問(wèn)，則該節(jié)點(diǎn)的語(yǔ)義規(guī)則將被計(jì)算。之所以稱之為“深度優(yōu)先”遍歷，是因?yàn)樗M可能地訪問(wèn)一個(gè)節(jié)點(diǎn)的未訪問(wèn)的子節(jié)點(diǎn)，于是它盡可能快地訪問(wèn)離根最遠(yuǎn)的節(jié)點(diǎn)。2.3.5 翻譯模式v。一個(gè)翻譯模式是一個(gè)上下文無(wú)關(guān)文法，其中被稱為語(yǔ)義動(dòng)作的程序段被嵌入到產(chǎn)生式右部。一個(gè)翻譯模式類似

19、于語(yǔ)法翻譯制導(dǎo)定義，只是語(yǔ)義規(guī)則的計(jì)算順序是顯式給出的。一個(gè)語(yǔ)義動(dòng)作的執(zhí)行位置通過(guò)用括號(hào)把語(yǔ)義動(dòng)作括起來(lái)并將其放在產(chǎn)生式右部來(lái)表示，如rest + term print(+) rest1v翻譯模式對(duì)于由基本語(yǔ)法產(chǎn)生的每個(gè)語(yǔ)句x都產(chǎn)生一個(gè)輸出，方法是：按照x的分析樹(shù)的深度優(yōu)先遍歷順序執(zhí)行語(yǔ)義動(dòng)作。2.3.6 翻譯的輸出v翻譯模式的語(yǔ)義動(dòng)作把翻譯的輸出以一次一個(gè)字符或一個(gè)字符串的形式寫(xiě)入一個(gè)文件。v語(yǔ)義制導(dǎo)定義具有如下特性：每個(gè)產(chǎn)生式左部的非終結(jié)符的翻譯是將該產(chǎn)生式右部的非終結(jié)符的翻譯按照它們?cè)谟也砍霈F(xiàn)的次序連接起來(lái)得到的，在連接過(guò)程中可能還需要附加（也可能不需要）一些額外的串。具有這樣特性的語(yǔ)義

20、制導(dǎo)定義稱之為簡(jiǎn)單的語(yǔ)義制導(dǎo)定義。v例2.8 圖2-5是把表達(dá)式翻譯成后綴形式的一個(gè)簡(jiǎn)單的語(yǔ)法制導(dǎo)定義。由該定義得到的翻譯模式如圖2-13所示，帶語(yǔ)義動(dòng)作的9-5+2的分析樹(shù)如圖2-14所示。注意，盡管圖2-6和圖2-14描述的是相同的輸入-輸出映射，但兩者構(gòu)造翻譯的過(guò)程是不相同的。圖2-6是把輸出附加在分析樹(shù)的根，而圖2-14輸出遞增地顯示出來(lái)。v圖2-14的根表示圖2-13中的第一個(gè)產(chǎn)生式。在深度優(yōu)先遍歷中，當(dāng)我們遍歷根節(jié)點(diǎn)的最左子樹(shù)時(shí)，先執(zhí)行左操作數(shù)expr的子樹(shù)中的所有語(yǔ)義動(dòng)作。然后，我們?cè)L問(wèn)沒(méi)有語(yǔ)義動(dòng)作的葉節(jié)點(diǎn)+。接下來(lái)，我們執(zhí)行右操作數(shù)term的子樹(shù)中的所有語(yǔ)義動(dòng)作。最后，執(zhí)行特殊

21、節(jié)點(diǎn)上的語(yǔ)義動(dòng)作print(+)。v由于term產(chǎn)生式右部只有一個(gè)數(shù)字，語(yǔ)義動(dòng)作只顯示該數(shù)字。產(chǎn)生式exprterm不產(chǎn)生輸出，頭兩個(gè)產(chǎn)生式的語(yǔ)義動(dòng)作只須顯示操作符。在深度優(yōu)先遍歷分析樹(shù)的過(guò)程中執(zhí)行圖2-14中的語(yǔ)義動(dòng)作顯示95-2+。v作為一般規(guī)則，多數(shù)分析方法都以一種“貪心”的方式從左到右地處理輸入，即在讀入下一個(gè)記號(hào)之前構(gòu)造盡可能多的分析樹(shù)的組成部分。在簡(jiǎn)單翻譯模式（由簡(jiǎn)單語(yǔ)義制導(dǎo)定義得到的）中，語(yǔ)義動(dòng)作也是按照從左到右的順序執(zhí)行的。因此，實(shí)現(xiàn)簡(jiǎn)單翻譯模式時(shí)，我們可以在語(yǔ)法分析的時(shí)候執(zhí)行語(yǔ)義動(dòng)作，完全沒(méi)有必要構(gòu)造分析樹(shù)。2.4 語(yǔ)法分析v語(yǔ)法分析是決定一個(gè)記號(hào)串是否能夠由一個(gè)文法產(chǎn)生的過(guò)

22、程。語(yǔ)法分析器應(yīng)該具有構(gòu)造分析樹(shù)的能力，否則，不能保證翻譯的正確性。v本節(jié)介紹一種語(yǔ)法分析方法，這種方法可以用來(lái)構(gòu)造語(yǔ)法制導(dǎo)翻譯器。下節(jié)給出一個(gè)實(shí)現(xiàn)圖2-13的翻譯模式的完整C程序。使用軟件工具直接從翻譯模式生成翻譯器是構(gòu)造翻譯器的理想方法。4.9節(jié)將詳細(xì)介紹這樣一種軟件工具。這個(gè)軟件工具無(wú)需修改就可以實(shí)現(xiàn)圖2-13的翻譯模式。v語(yǔ)法分析方法可以分為兩類：自頂向下方法和自底向上方法。這些術(shù)語(yǔ)是指構(gòu)造分析樹(shù)節(jié)點(diǎn)的順序。前者按照從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的順序構(gòu)造分析樹(shù)，后者按照從葉節(jié)點(diǎn)到根節(jié)點(diǎn)的順序構(gòu)造分析樹(shù)。自頂向下分析器是常用的語(yǔ)法分析器，其原因在于這種語(yǔ)法分析器可以很容易地通過(guò)自頂向下的方法手工構(gòu)造

23、出來(lái)。然而，自底向上分析方法可以處理大量文法和翻譯模式，所以直接從文法產(chǎn)生語(yǔ)法分析器的軟件工具通常使用自底向上的方法。2.4.1 自頂向下語(yǔ)法分析v我們通過(guò)一種適于自頂向下語(yǔ)法分析的文法來(lái)介紹自頂向下的分析方法。我們將在本節(jié)的后面考慮構(gòu)造自頂向下語(yǔ)法分析器的一般方法。下面的文法生成一個(gè)Pascal的類型子集。我們用記號(hào)dotdot表示“.”，dotdot強(qiáng)調(diào)該字符序列是一個(gè)基本符號(hào)單元。v為了自頂向下地構(gòu)造一個(gè)分析樹(shù)，我們從標(biāo)有開(kāi)始非終結(jié)符的根節(jié)點(diǎn)開(kāi)始，反復(fù)執(zhí)行下面兩步（見(jiàn)圖2-15中的例子）：在標(biāo)有非終結(jié)符A的節(jié)點(diǎn)n，選擇A的一個(gè)產(chǎn)生式，用該產(chǎn)生式右部的符號(hào)構(gòu)造節(jié)點(diǎn)n的子節(jié)點(diǎn)。尋找下一個(gè)要構(gòu)

24、造子樹(shù)的節(jié)點(diǎn)。v對(duì)于某些文法，上面的步驟可以通過(guò)一次從左到右掃描輸入串來(lái)實(shí)現(xiàn)。輸入中當(dāng)前被掃描的記號(hào)通常是被稱為超前掃描符號(hào)(lookahead symbol)。以下我們也稱超前掃描符號(hào)為當(dāng)前符號(hào)。最初，超前掃描符號(hào)是輸入串的第一個(gè)記號(hào)，即最左端的記號(hào)。圖2-16說(shuō)明了對(duì)如下輸入串的語(yǔ)法分析過(guò)程：array num dotdot num of integerv最初，記號(hào)array是超前掃描符號(hào)，分析樹(shù)的已知部分只有標(biāo)記為開(kāi)始非終結(jié)符type的根節(jié)點(diǎn)，如圖2-16a所示。我們的目標(biāo)是：以構(gòu)造出來(lái)的分析樹(shù)所產(chǎn)生的字符串與輸入字符串匹配的方法構(gòu)造分析樹(shù)的其余部分。v為了與輸入串匹配，圖2-16a中的

25、非終結(jié)符type必須導(dǎo)出一個(gè)以超前掃描符號(hào)array開(kāi)始的串。在文法(2-8)中，只有一個(gè)以type為左部的產(chǎn)生式可以導(dǎo)出這樣的串，所以我們使用這個(gè)產(chǎn)生式來(lái)構(gòu)造根節(jié)點(diǎn)type的子節(jié)點(diǎn)，并在子節(jié)點(diǎn)上標(biāo)上產(chǎn)生式右部的符號(hào)。v在圖2-16所示的三個(gè)步驟中，都有兩個(gè)箭頭。一個(gè)指向輸入串中超前掃描符號(hào)，另一個(gè)箭頭指向分析樹(shù)當(dāng)前被考慮的節(jié)點(diǎn)。當(dāng)一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)都已經(jīng)構(gòu)造完畢，我們從該節(jié)點(diǎn)的最左端子節(jié)點(diǎn)開(kāi)始繼續(xù)構(gòu)造分析樹(shù)的其余部分。在圖2-16b中，根節(jié)點(diǎn)的子節(jié)點(diǎn)都已經(jīng)構(gòu)造完畢，下一個(gè)要考慮的節(jié)點(diǎn)是標(biāo)記為array的最左端的子節(jié)點(diǎn)。v如果當(dāng)前被考查的分析樹(shù)的節(jié)點(diǎn)是一個(gè)終結(jié)符，而且該終結(jié)符與超前符號(hào)匹配，則分

26、析樹(shù)的箭頭和輸入的箭頭都前進(jìn)一步。輸入的下一個(gè)記號(hào)成為新的超前掃描符號(hào)，分析樹(shù)的下一個(gè)子節(jié)點(diǎn)將被考查。在圖2-16c中，分析樹(shù)中的箭頭指向了根的下一個(gè)子節(jié)點(diǎn)，輸入的箭頭指向了下一個(gè)記號(hào)“”。接下來(lái)，分析樹(shù)的箭頭指向標(biāo)記非終結(jié)符simple的子節(jié)點(diǎn)。在考慮一個(gè)標(biāo)有非終結(jié)符的節(jié)點(diǎn)時(shí)，我們將重復(fù)為這個(gè)非終結(jié)符選擇一個(gè)適當(dāng)?shù)漠a(chǎn)生式的過(guò)程。v通常，為非終結(jié)符選擇產(chǎn)生式可能會(huì)涉及“試驗(yàn)和錯(cuò)誤”的問(wèn)題，即在選擇產(chǎn)生式的時(shí)候，如果一個(gè)產(chǎn)生式不合適，我們將不得不回溯，測(cè)試另外一個(gè)產(chǎn)生式。一個(gè)產(chǎn)生式“不適合”是指使用了該產(chǎn)生式之后無(wú)法產(chǎn)生與輸入串匹配的分析樹(shù)。下面我們介紹預(yù)測(cè)分析方法，在這種分析方法中不會(huì)發(fā)生回溯

27、問(wèn)題。2.4.2 預(yù)測(cè)分析法v遞歸下降分析法是一種自頂向下的語(yǔ)法分析方法，在這種方法中，我們執(zhí)行一組遞歸過(guò)程來(lái)處理輸入串。每一個(gè)過(guò)程都惟一地與文法的一個(gè)非終結(jié)符相關(guān)聯(lián)。這里，我們考慮一種特殊的遞歸下降分析法，稱為預(yù)測(cè)分析法。在預(yù)測(cè)分析法中，超前掃描符號(hào)無(wú)二義地確定了為每個(gè)非終結(jié)符選擇的過(guò)程。處理輸入時(shí)調(diào)用的過(guò)程序列隱式地定義了輸入串的分析樹(shù)。v圖2-17的預(yù)測(cè)語(yǔ)法分析器由非終結(jié)符type的過(guò)程、非終結(jié)符simple的過(guò)程和一個(gè)稱為match的過(guò)程組成。我們用match過(guò)程來(lái)簡(jiǎn)化type過(guò)程和simple過(guò)程的代碼。如果變量t和超前掃描符號(hào)匹配，輸入符號(hào)串的箭頭將前進(jìn)一步，指向下一個(gè)輸入記號(hào)。因

28、此，match過(guò)程改變了當(dāng)前被掃描的輸入記號(hào)lookahead變量的值。v在我們的文法中，分析過(guò)程從調(diào)用開(kāi)始非終結(jié)符type的過(guò)程開(kāi)始。輸入串與圖2-16中的串相同，lookahead初始化為第一個(gè)記號(hào)array。過(guò)程type對(duì)應(yīng)著產(chǎn)生式typearray simple of type的右部執(zhí)行如下代碼：v預(yù)測(cè)分析依賴于產(chǎn)生式右部產(chǎn)生的第一個(gè)符號(hào)是什么。更精確地說(shuō)，令是非終結(jié)符A的某產(chǎn)生式的右部。定義FIRST()是作為由產(chǎn)生的一個(gè)或多個(gè)串的第一個(gè)符號(hào)出現(xiàn)的集合。如果是或者可以產(chǎn)生，則也屬于FIRST()。例如：v如果有兩個(gè)產(chǎn)生式A 和A 可供選用，則必須考慮相應(yīng)的FIRST集合。無(wú)回溯的遞歸

29、下降分析方法要求FIRST()和FIRST()不相交。這樣超前掃描符號(hào)就可以選擇正確的過(guò)程去執(zhí)行。如果超前掃描符號(hào)在FIRST()集合中，則使用，否則，如果超前掃描符號(hào)在FIRST()中，則使用。2.4.3 何時(shí)使用產(chǎn)生式v右部是的產(chǎn)生式稱為產(chǎn)生式，需要特殊處理。當(dāng)沒(méi)有其他產(chǎn)生式可用的時(shí)候，遞歸下降語(yǔ)法分析器把產(chǎn)生式作為默認(rèn)產(chǎn)生式使用。2.4.4 設(shè)計(jì)一個(gè)預(yù)測(cè)語(yǔ)法分析器v預(yù)測(cè)語(yǔ)法分析器是一個(gè)由多個(gè)過(guò)程組成的程序，每個(gè)過(guò)程對(duì)應(yīng)一個(gè)非終結(jié)符。每個(gè)過(guò)程完成如下兩項(xiàng)任務(wù)：檢查超前掃描符號(hào)，決定使用哪個(gè)產(chǎn)生式。如果超前掃描符號(hào)在FIRST()中，則選擇使用右部為的產(chǎn)生式。對(duì)于任何超前掃描符號(hào)，如果產(chǎn)生式

30、右部存在沖突，那么我們不能在這種文法上使用這種分析方式。如果超前掃描符號(hào)不在任何其他右部的FIRST集合中，右部具有的產(chǎn)生式將被使用。過(guò)程通過(guò)模仿其右部來(lái)使用一個(gè)產(chǎn)生式。一個(gè)非終結(jié)符導(dǎo)致該非終結(jié)符對(duì)應(yīng)的過(guò)程被調(diào)用。一個(gè)與超前掃描符號(hào)匹配的記號(hào)導(dǎo)致下一個(gè)輸入記號(hào)被讀入。如果在某個(gè)點(diǎn)上，產(chǎn)生式的記號(hào)與超前掃描符號(hào)不匹配，則報(bào)告出錯(cuò)。圖2-17是對(duì)文法(2-8)應(yīng)用這些規(guī)則的結(jié)果。v類似于通過(guò)擴(kuò)展文法來(lái)形成一個(gè)翻譯模式，我們也可以通過(guò)擴(kuò)展預(yù)測(cè)語(yǔ)法分析器來(lái)形成一個(gè)語(yǔ)法制導(dǎo)翻譯器。實(shí)現(xiàn)此目的的算法在5.5節(jié)中給出。因?yàn)楸菊聦?shí)現(xiàn)的翻譯模式不涉及非終結(jié)符的屬性，下面僅給出滿足當(dāng)前要求的構(gòu)造方法：構(gòu)造一個(gè)預(yù)測(cè)

31、語(yǔ)法分析器，忽略產(chǎn)生式中的語(yǔ)義動(dòng)作。把翻譯模式中的語(yǔ)義動(dòng)作拷貝到語(yǔ)法分析器。如果一個(gè)語(yǔ)義動(dòng)作出現(xiàn)在產(chǎn)生式p的文法符號(hào)X的后面，則該語(yǔ)義動(dòng)作被拷貝到實(shí)現(xiàn)X的代碼后面。否則，如果語(yǔ)義動(dòng)作出現(xiàn)在一個(gè)產(chǎn)生式的開(kāi)始，則該語(yǔ)義動(dòng)作被拷貝在該產(chǎn)生式的實(shí)現(xiàn)代碼的最前面。2.4.5 左遞歸v遞歸下降語(yǔ)法分析器很可能造成無(wú)限循環(huán)。當(dāng)出現(xiàn)下面這樣一個(gè)左遞歸產(chǎn)生式時(shí)，無(wú)限循環(huán)就會(huì)出現(xiàn)：v在這里，產(chǎn)生式右部的最左符號(hào)和產(chǎn)生式左部的非終結(jié)符是相同的。假定expr對(duì)應(yīng)的過(guò)程要使用這個(gè)產(chǎn)生式。因?yàn)橛也渴怯蒭xpr開(kāi)始的，所以expr過(guò)程被遞歸調(diào)用，出現(xiàn)了無(wú)限循環(huán)。注意，只有右部終結(jié)符與超前掃描符號(hào)匹配時(shí)，超前掃描符號(hào)才會(huì)發(fā)生

32、改變。因?yàn)楫a(chǎn)生式是以非終結(jié)符expr開(kāi)始的，輸入符號(hào)在遞歸調(diào)用期間沒(méi)有機(jī)會(huì)改變，所以導(dǎo)致無(wú)限循環(huán)。v通過(guò)重寫(xiě)與遞歸相關(guān)的產(chǎn)生式，我們可以消除左遞歸產(chǎn)生式。考慮下面非終結(jié)符A的兩個(gè)產(chǎn)生式：v可通過(guò)以如下方式改寫(xiě)產(chǎn)生式得到2.5 簡(jiǎn)單表達(dá)式的翻譯器v使用前面三節(jié)介紹的技術(shù)，我們可以用C語(yǔ)言編寫(xiě)一個(gè)語(yǔ)法制導(dǎo)翻譯器，這個(gè)翻譯器可以把算術(shù)表達(dá)式翻譯成后綴形式。為了使最初的程序比較小而且易于理解，我們從最簡(jiǎn)單的表達(dá)式開(kāi)始，即由加號(hào)和減號(hào)分隔的由數(shù)字構(gòu)成的表達(dá)式。2.5.1 抽象語(yǔ)法和具體語(yǔ)法v為了便于理解，我們從抽象語(yǔ)法樹(shù)開(kāi)始討論一個(gè)輸入串的翻譯。在一個(gè)抽象語(yǔ)法樹(shù)中，每個(gè)節(jié)點(diǎn)表示一個(gè)操作符，該節(jié)點(diǎn)的子節(jié)點(diǎn)

33、表示操作數(shù)。與此相對(duì)應(yīng)，分析樹(shù)稱為具體語(yǔ)法樹(shù)，相應(yīng)的文法稱作具體語(yǔ)法。抽象語(yǔ)法樹(shù)（或簡(jiǎn)稱語(yǔ)法樹(shù)）與分析樹(shù)是不同的。因?yàn)樾问缴系牟顒e（不影響翻譯）沒(méi)有出現(xiàn)在語(yǔ)法樹(shù)中，所以抽象語(yǔ)法樹(shù)與分析樹(shù)有所不同。v在語(yǔ)法樹(shù)中，操作符都是內(nèi)節(jié)點(diǎn)；在分析樹(shù)中，操作符皆為葉節(jié)點(diǎn)。v例2.9 下面的文法不適合將表達(dá)式翻譯成后綴形式，盡管它和圖2-19產(chǎn)生相同的語(yǔ)言并且能夠用于遞歸下降分析：v這個(gè)文法存在如下問(wèn)題：rest + expr和rest - expr產(chǎn)生的操作符的操作數(shù)是不明顯的。用下面兩種模式從expr.t翻譯rest.t都是無(wú)法接受的：v我們只列出了減號(hào)操作符的產(chǎn)生式及其語(yǔ)義動(dòng)作。9-5的正確翻譯是95-

34、。然而，如果我們使用(2-12)的語(yǔ)義動(dòng)作，則減號(hào)出現(xiàn)在expr.t的前面，9-5的翻譯還是9-5，這顯然是不對(duì)的。v另一方面，如果我們使用(2-13)以及相似的加法規(guī)則，操作符將一直移到右部末尾。這樣，9-5+2被錯(cuò)誤地翻譯成952+-，而正確的翻譯應(yīng)該是95-2+。2.5.2 調(diào)整翻譯模式圖2-21說(shuō)明了如何使用上面的文法把9-5+2翻譯成為95-2+。2.5.3 非終結(jié)符expr,term和rest的過(guò)程2.5.4 翻譯器的優(yōu)化2.5.5 完整程序2.6 詞法分析v詞法分析器讀入輸入串，將其轉(zhuǎn)換成將被語(yǔ)法分析器分析的記號(hào)流。v一個(gè)語(yǔ)言的語(yǔ)句是由記號(hào)串構(gòu)成的。構(gòu)成一個(gè)記號(hào)的一個(gè)輸入字符序列

35、稱為詞素。詞法分析器把語(yǔ)法分析器和記號(hào)的詞素表示分隔開(kāi)來(lái)。v我們先來(lái)討論我們希望詞法分析器完成的一些功能。v2.6.1 剔除空白符和注釋v2.6.2 常數(shù)處理v2.6.3 識(shí)別標(biāo)識(shí)符和關(guān)鍵字2.6.4 詞法分析器的接口v詞法分析器介于語(yǔ)法分析器和輸入流之間，并與這兩者交互（如圖2-25所示）。詞法分析器從輸入串讀字符并形成詞素，然后將詞素生成的記號(hào)及其屬性值傳遞給編譯器的下一個(gè)階段。在某些情況下，詞法分析器在把記號(hào)傳給語(yǔ)法分析器之前，需要從輸入串超前地讀入一些字符，以確定需要傳遞給語(yǔ)法分析器的正確記號(hào)。2.6.5 詞法分析器2.7 符號(hào)表v符號(hào)表是一種數(shù)據(jù)結(jié)構(gòu)，通常用于保存源語(yǔ)言結(jié)構(gòu)的各種信息

36、。編譯器在分析階段收集信息放入符號(hào)表，在綜合階段使用符號(hào)表中的信息生成目標(biāo)代碼。例如，在詞法分析階段，形成標(biāo)識(shí)符的字符串或詞素被存儲(chǔ)在符號(hào)表的一個(gè)表項(xiàng)中。編譯器的以后各階段會(huì)在這個(gè)表項(xiàng)上逐步添加其他信息，如標(biāo)識(shí)符的類型、用處（如用作過(guò)程名、變量名或標(biāo)號(hào)）以及存儲(chǔ)位置。在代碼生成階段，編譯器使用這些信息生成存取這些變量的正確代碼。2.7.1 符號(hào)表接口vinsert(s,t)：將字符串s和記號(hào)t的插入符號(hào)表，返回相應(yīng)表項(xiàng)的索引。vlookup(s)：到符號(hào)表中查找字符串s，如果找到則返回相應(yīng)表項(xiàng)的索引，否則返回0。2.7.2 處理保留的關(guān)鍵字v任何保留關(guān)鍵字的集合都可以通過(guò)適當(dāng)?shù)爻跏蓟?hào)表而得到正確的處理。v比如：2.7.3 符號(hào)表的實(shí)現(xiàn)方法2.8 抽象堆棧機(jī)v編譯器可以劃分為前端和后端兩部分。前端構(gòu)造源程序的中間表示，后端從中間表示