第二章 語法分析

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

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

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

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

5、左推導的概念為表達式(343)42提供一個最右推導和最左推導。最右推導為：(1)exp?expopexp(2)?expopnumber(3)?expnumber(4)?(exp)number(5)?(expopexp)number(6)?(expopnumber)number(7)?(exp–number)number(8)?(number–number)number最左推導為：(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語法分析樹和抽象語法樹語法分析樹和抽象語法樹根據(jù)表達式(343)42的最右推導和最左推導所示，最左和最右推導二者唯一的差別在于提供的替換順序，而這其實是一個表面的差別。

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