第二章 語(yǔ)法分析

1、1第二章第二章語(yǔ)法分析語(yǔ)法分析語(yǔ)法分析是編譯過(guò)程的第二個(gè)階段，也是其核心的部分。2.1語(yǔ)法分析器的作用語(yǔ)法分析器的作用語(yǔ)法分析的基本任務(wù)是在詞法分析識(shí)別出單詞符號(hào)串的基礎(chǔ)上，分析源程序的語(yǔ)法結(jié)構(gòu)，即分析由這些單詞如何組成各種語(yǔ)法范疇（如“程序“，“語(yǔ)句“，“表達(dá)式“等等），并分析判斷程序的語(yǔ)法結(jié)構(gòu)是否符合語(yǔ)法規(guī)則，語(yǔ)法分析可以有多種不同的輸出形式，這里我們假定分析程序的輸出是某種分析樹(shù)的形式，如圖2.1所示。另外，我們希望語(yǔ)法分析器能報(bào)

2、告發(fā)現(xiàn)的任何語(yǔ)法錯(cuò)誤，并能從錯(cuò)誤中恢復(fù)過(guò)來(lái)，使后面的分析能繼續(xù)進(jìn)行下去。語(yǔ)言的語(yǔ)法結(jié)構(gòu)用上下文無(wú)關(guān)文法來(lái)描述，因此，語(yǔ)法分析器的任務(wù)本質(zhì)上是按上下文無(wú)關(guān)文法的產(chǎn)生式，確定整個(gè)單詞串是否構(gòu)成語(yǔ)法上正確的程序。語(yǔ)法分析的方法通常分為兩類：自頂向下分析法和自底向上分析法。自頂向下語(yǔ)法分析沿著從頂（根）向底（葉）的方向建立分析樹(shù)，自底向上語(yǔ)法分析則沿著從葉向根的方向建立分析樹(shù)。但是不論哪一種方法，語(yǔ)法分析器都是自左向右地掃描輸入字符串，每次只讀

3、一個(gè)符號(hào)。2.2上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法2.2.1上下文無(wú)關(guān)文法的描述上下文無(wú)關(guān)文法的描述使用上下文無(wú)關(guān)文法重要的原因在于它們擁有足夠強(qiáng)的表達(dá)力來(lái)表示大多數(shù)程序設(shè)計(jì)語(yǔ)言的語(yǔ)法；實(shí)際上，幾乎所有程序設(shè)計(jì)語(yǔ)言都是通過(guò)上下文無(wú)關(guān)文法來(lái)定義的。另一方面，上下文無(wú)關(guān)文法又足夠簡(jiǎn)單，使得我們可以構(gòu)造有效的分析算法來(lái)檢驗(yàn)一個(gè)給定字串是否是由某個(gè)上下文無(wú)關(guān)文法產(chǎn)生的。形式上說(shuō)，一個(gè)上下文無(wú)關(guān)文法G是一個(gè)四元組（VTVNSP），其中：（1）VT是一個(gè)

4、非空有限集合，其元素稱為終結(jié)符。在我們談?wù)摮绦蛟O(shè)計(jì)語(yǔ)言的文法時(shí)，記號(hào)是終結(jié)符的同義詞。源程序圖2.1分析器在編譯器模型中的位置分析樹(shù)詞法分析器記號(hào)取下一個(gè)記號(hào)符號(hào)表語(yǔ)法分析器32.3推導(dǎo)推導(dǎo)最右推導(dǎo):在推導(dǎo)過(guò)程中若每一步推導(dǎo)都是對(duì)句型中的最右非終結(jié)符用相應(yīng)產(chǎn)生式的右部進(jìn)行替換則稱這種推導(dǎo)為最右推導(dǎo)。最左推導(dǎo):在推導(dǎo)過(guò)程中若每一步推導(dǎo)都是對(duì)句型中的最左非終結(jié)符用相應(yīng)產(chǎn)生式的右部進(jìn)行替換則稱這種推導(dǎo)為最左推導(dǎo)。根據(jù)上述文法規(guī)則和最右推導(dǎo)和最

5、左推導(dǎo)的概念為表達(dá)式(343)42提供一個(gè)最右推導(dǎo)和最左推導(dǎo)。最右推導(dǎo)為：(1)exp?expopexp(2)?expopnumber(3)?expnumber(4)?(exp)number(5)?(expopexp)number(6)?(expopnumber)number(7)?(exp–number)number(8)?(number–number)number最左推導(dǎo)為：(1)exp?expopexp(2)?(exp)opexp

6、(3)?(expopexp)opexp(4)?(numberopexp)opexp(5)?(number–exp)opexp(6)?(number–number)opexp(7)?(number–number)exp(8)?(number–number)number2.4語(yǔ)法分析樹(shù)和抽象語(yǔ)法樹(shù)語(yǔ)法分析樹(shù)和抽象語(yǔ)法樹(shù)根據(jù)表達(dá)式(343)42的最右推導(dǎo)和最左推導(dǎo)所示，最左和最右推導(dǎo)二者唯一的差別在于提供的替換順序，而這其實(shí)是一個(gè)表面的差別。

7、為了把它表示得更清楚一些，我們需要表示出終結(jié)符串的結(jié)構(gòu)，而這些終結(jié)符將推導(dǎo)的主要特征抽取出來(lái)，同時(shí)卻將表面的差別按順序分解開(kāi)來(lái)。這樣的表示法就是樹(shù)結(jié)構(gòu)，我們稱之為語(yǔ)法分析樹(shù)。與推導(dǎo)相對(duì)應(yīng)的分析樹(shù)是一個(gè)作了標(biāo)記的樹(shù)，其中內(nèi)部的節(jié)點(diǎn)由非終結(jié)符標(biāo)出，樹(shù)葉節(jié)點(diǎn)由終結(jié)符標(biāo)出，每個(gè)內(nèi)部節(jié)點(diǎn)的子節(jié)點(diǎn)都表示推導(dǎo)的一個(gè)步驟中的相關(guān)非終結(jié)符的替換。語(yǔ)法分析樹(shù)也稱為具體語(yǔ)法樹(shù)，因?yàn)檫@種樹(shù)中的一切都是明示的，完全而又具體，顯示了如何根據(jù)相應(yīng)上下文無(wú)關(guān)文法推導(dǎo)出