1、第 5 章 語法分析 語法分析是編譯的第二階段；其任務(wù)是識別和處理比單詞更大的語法單位，如：程序設(shè)計語言中的表達(dá)式、各種說明和語句乃至全部源程序，指出其中的語法錯誤；必要時，可生成內(nèi)部形式，便于下一階段處理。 內(nèi)容提要:5.1 語法分析的基本概念5.2 遞歸子程序法5.3 LL(1)分析法5.4 LR()分析法5.5 簡單優(yōu)先分析法5.1 語法分析的基本概念5.1.1 語法分析的定義與分類 【定義】形式上說，語法分析是指對給定的符號串（），判定其是否是某文法G(Z)的句子。即Z 成立嗎 ? = + Z 成立嗎 ? = .+ 【分類】語法分析方法通常分兩大類： 1. 自頂向下法（推導(dǎo)法） 2.

2、自底向上法（歸約法） 從開始符號出發(fā)，采用推導(dǎo)運(yùn)算，試圖自頂向下構(gòu)造語法樹。 從給定的符號串出發(fā)，采用歸約運(yùn)算，試圖自底向上構(gòu)造語法樹。或 通常采用“最左推導(dǎo)法”。 通常采用“最左歸約法”給定： = a*(b+c)， 是否是表達(dá)式？(接上頁)5.1.2 算法設(shè)計分析1【例5.1】 G(E)： E - T | E+T | E-T T - F | T*F | T/F F - i | (E) 最左推導(dǎo)分析過程：【結(jié)論】自頂向下分析的關(guān)鍵技術(shù)是如何確定具有相同左部的產(chǎn)生式之侯選者！即 E a*(b+c) = +=T*F=F*F=a*F=a*(E)=a*(E+T)=a*(T+T)=a*(F+T)=a*(

3、b+T)=a*(b+F)=a*(b+c)- 自頂向下法:E=T 為了清楚每次歸約的是什麼？我們觀察語法樹的 = a*(b+c)5.1.2 算法設(shè)計分析2 E - T | E+T | E-T T - F | T*F | T/F F - i | (E) - 自底向上法a*(b+c)=.F*(b+c)=.T*(E+c)=.T*(b+c)=.T*(F+c)=.T*(T+c)=.T*(E+F)=.T*(E+T)=.T*(E)=.T*F=.E=.T=.+E a*(b+c)即【結(jié)論】自底向上分析的關(guān)鍵技術(shù)是如何確定當(dāng)前句型的句柄！最左歸約分析過程： 構(gòu)造過程： 5.2.1 遞歸子程序法的設(shè)計原理： 語法分析

4、的核心技術(shù)是“文法”的機(jī)內(nèi)表示問題；遞歸子程序法直接把文法變成程序。 對每一個非終結(jié)符，構(gòu)造一個子程序，用以識別該非終結(jié)符所定義的符號串。每個子程序以產(chǎn)生式左部非終結(jié)符命名，以產(chǎn)生式右部構(gòu)造子程序內(nèi)容。例如：設(shè)有如下產(chǎn)生式： A - aBeD | bAc | 則有：遞歸子程序 A: 遞歸子程序法屬于自頂向下語法分析方法。故又名遞歸下降法。 設(shè)計原理：yn入口出口a?b?NEXT(w)yNEXT(w) NEXT(w)nc?ynerr2e?遇時 B A Dyerr1nNEXT(w)A - aBeD | bAc | 判斷當(dāng)前單詞是否是c即w=c?調(diào)用子程序A(接上頁)讀單詞函數(shù)5.2.2 遞歸子程序

5、的構(gòu)造算法 擴(kuò)展文法：增設(shè)一個產(chǎn)生式，作為主程序：Z-Z ， 入出口約定： 子程序入口時，其首符號已經(jīng)讀來！子程序出口時，其后繼符應(yīng)該讀來！ 子程序內(nèi)容設(shè)計：遇終結(jié)符，判定之 ，確認(rèn)后讀下一單詞；遇非終結(jié)符,調(diào)用之,返回后不讀下一單詞； 遇空串( ) ，直接出口； 【例5.2】G(S):令 Z - S , 則 遞歸子程序:子程序A開始結(jié)束 #SNEXT(w)err0yn入口出口 a berr1NEXT(w)A berr2NEXT(w)SNEXT(w)子程序Snnnyyy入口 cNEXT(w)出口遇時ny dNEXT(w)err3yn主程序S - aAb |bS , A - cd | 實際上，上

6、述兩點(diǎn)可歸納為同一個條件，即： 遞歸子程序要求文法應(yīng)是： 5.2.3 遞歸子程序法對文法的要求： 遞歸子程序是根據(jù)文法各產(chǎn)生式的首符號與當(dāng)前所讀單詞進(jìn)行匹配，以決定候選產(chǎn)生式的；這就要求文法： 具有相同左部的各產(chǎn)生式，首符號不同； 文法不能有左遞歸！如：A - a|a (首符號相同，)； A - A| (直接左遞歸，)。 LL(1)文法!（見 5.3節(jié)）。 5.2.4 遞歸子程序的構(gòu)造例： . 消除左遞歸后的文法1:G(E) :T - F 2 F F - i | ( E )E - T 1T 【提示】 根據(jù)文法變換：A - A | A - 【例5.3】G(E)： E - T | E1T T -

7、F | T2F F - i | (E) 其中：1(+,-),2(*,/),i(變量或常數(shù))主程序T - F 2 F F - i | ( E )E - T 1 T 子程序E令 Z - E開始結(jié)束 #ENEXT(w)err0yn入口出口NEXT(w)T 1Tyn入口出口NEXT(w)F 2Fyn子程序T(接上頁)T - F 2 F F - i | ( E )E - T 1 T 入口出口 i (err1NEXT(w)err2NEXT(w)E )yyynnn子程序F(接上頁). 消除左遞歸后的文法2 :G(E) :T - F 2 F F - i | ( E )E - T 1 T E - T EE -

8、1T E | T - F TT - 2F T | F - i | ( E ) 文法 G(E)消除花括號后可得：令 Z - E ，則可構(gòu)造遞歸子程序如下： （主程序 省略）入口出口TE子程序E入口 1NEXT(w)T出口遇時nyE子程序EE - T EE - 1T E | T - F TT - 2F T | F - i | ( E )(接上頁)練習(xí)題：【習(xí)題5.1】解釋下述詞語： 語法分析 ；語法分析的分類。【習(xí)題5.2】構(gòu)造下述文法的遞歸子程序： G(S): S - a A S b | B d A - c S | B - b B | d 【習(xí)題5.3】構(gòu)造下述文法的遞歸子程序： 產(chǎn)生式 S - Bd 的首符號為 b,d ! 產(chǎn)生式 A - 的首符號(后繼符) a,b,d提示G(E): E - T + T | - T T - F * F | / F F - i | ( E )a * ( b + c )FTTEFFTETFEaFbFTcFE+T