第七講語法分析1

第3章語法分析3.1文法和語言3.1文法和語言

文法是程序語言的生成系統(tǒng)，而自動(dòng)機(jī)則是程序語言的識別系統(tǒng)；用文法可以精確地定義一個(gè)語言，并依據(jù)該文法構(gòu)造出識別這個(gè)語言的自動(dòng)機(jī)。因此，文法對程序語言和編譯程序的構(gòu)造具有重要意義，如程序語言的詞法可用正規(guī)文法描述，語法可用上下文無關(guān)文法描述，而語義則要借助于上下文有關(guān)文法描述。3.1.1文法和語言的概念1．語言通常我們用Σ表示字母表，字母表中的每個(gè)元素稱為字符或符號。不同語言的字母表可能是不同的，程序語言的字母表通常是ASCII字符集。由字母表Σ中的字符所組成的有窮系列稱為Σ上的字符串或字，字母表Σ上的所有字符串(包括空串)組成的集合用Σ*表示。那么，對字母表Σ來說，Σ*上的任意一個(gè)子集都稱為Σ上的一個(gè)語言，記為L(LСΣ*)，該語言的每一個(gè)字符串稱為語言L的一個(gè)語句或句子。2．文法文法通常表示成四元組G=(VT，VN，S，ξ)，其中：(1)VT為終結(jié)符號集，這是一個(gè)非空有限集，它的每個(gè)元素稱為終結(jié)符號；(2)VN為非終結(jié)符集，它也是一個(gè)非空有限集，其每個(gè)元素稱為非終結(jié)符號，且有VT∩VN=Φ；(3)S為一文法開始符，是一個(gè)特殊的非終結(jié)符號，即S∈VN；(4)ξ是產(chǎn)生式的非空有限集，其中每個(gè)產(chǎn)生式(或稱規(guī)則)是一序偶(α，β)，通常寫作α→β或α::=β讀作“α是β”或“α定義為β”。在此，α為產(chǎn)生式的左部，而β為產(chǎn)生式的右部，α、β是由終結(jié)符和非終結(jié)符組成的符號串，α∈(VT∪VN)+且至少有一個(gè)非終結(jié)符，而β∈(VT∪VN)*。終結(jié)符號是指語言不可再分的基本符號，通常是一個(gè)語言的字母表；終結(jié)符代表了語法的最小元素，是一種個(gè)體記號。非終結(jié)符號也稱語法變量，它代表語法實(shí)體或語法范疇；非終結(jié)符代表一個(gè)一定的語法概念，因此，一個(gè)非終結(jié)符是一個(gè)類、一個(gè)集合。例如，在程序語言中，可以把變量、常數(shù)、“+”、“*”等看作是終結(jié)符，而像“算術(shù)表達(dá)式”這個(gè)非終結(jié)符則代表著一定算術(shù)式組成的類，如i*(i+i)、i+i+i等；也即每個(gè)非終結(jié)符代表著由一些終結(jié)符和非終結(jié)符且滿足一定規(guī)則的符號串組成的集合。

文法開始符號是一個(gè)特殊的非終結(jié)符，它代表文法所定義的語言中我們最終感興趣的語法實(shí)體，即語言的目標(biāo)，而其它語法實(shí)體只是構(gòu)造語言目標(biāo)的中間變量；如表達(dá)式文法的語言目標(biāo)是表達(dá)式，而程序語言的目標(biāo)通常為程序。

產(chǎn)生式(也稱產(chǎn)生規(guī)則或規(guī)則)是定義語法實(shí)體的一種書寫規(guī)則。一個(gè)語法實(shí)體的相關(guān)規(guī)則可能不止一個(gè)。例如，有：P→α1P→α2P→αn為書寫方便，可將這些有相同左部的產(chǎn)生式合并為一個(gè)，即縮寫成P→α1∣α2∣…∣αn其中，每個(gè)αi(i=1,2,…,n)稱為P的一個(gè)候選式，直豎“∣”讀為“或”，它與“→”一樣是用來描述文法的元語言符號(即不屬于Σ的字符)。例3.1試構(gòu)造產(chǎn)生標(biāo)識符的文法。[解答]首先，標(biāo)識符是以字母開頭的字母數(shù)字串，我們用L表示“字母”類非終結(jié)符，用D表示“數(shù)字”類非終結(jié)符，而用T表示“字母或數(shù)字”類非終結(jié)符，則有：L→a∣b∣…∣zD→0∣1∣…∣9T→L∣D其次，如果用S表示“字母數(shù)字串”類，則T是一字母或數(shù)字，ST也是字母數(shù)字串，即有S→T∣ST其中，產(chǎn)生式S→T∣ST是一種左遞歸形式，由它可以產(chǎn)生一串T。最后，作為“標(biāo)識符”的非終結(jié)符I，它或者是一單個(gè)字母，或者為一字母后跟字母數(shù)字串，即I→L∣LS因此，產(chǎn)生標(biāo)識符的文法G[I]為：

G=({a,b,…,z,0,…,9},{I,S,T,L,D},I,ξ)ξ:I→L∣LSS→T∣STT→L∣DL→a∣b∣…∣zD→0∣1∣…∣9例3.2寫一文法，使其語言是奇數(shù)集合，但不允許出現(xiàn)以0打頭的奇數(shù)。[解答]根據(jù)題意，我們可以將奇數(shù)劃分為如圖3–1所示的三個(gè)部分，即最高位允許出現(xiàn)1～9，用非終結(jié)符B表示；中間部分可以出現(xiàn)任意多位數(shù)字0～9，每一位用非終結(jié)符D表示；最低位只允許出現(xiàn)1、3、5、7、9等奇數(shù)，用A表示。圖3–1奇數(shù)劃分示意由于中間部分可出現(xiàn)任意位，所以另引入了一個(gè)非終結(jié)符M，它包括最高位和中間位部分。假定開始符為N，則可得到文法G[N]為：G=({0,1,…,9},{N,A,M,B,D},N,ξ)ξ:N→A∣MA /*一位數(shù)字│多位數(shù)字*/M→B∣MD /*僅兩位數(shù)字(無中間位)│多于兩位數(shù)字*/A→1∣3∣5∣7∣9B→1∣2∣3∣4∣5∣6∣7∣8∣9D→0∣B3．文法產(chǎn)生的語言設(shè)文法G=(VT,VN,S,ξ)且α、β∈(VT∪VN)*，如果存在產(chǎn)生式A→δ(δ∈(VT∪VN)*)，則稱αAβ可直接推出αδβ，即αAβαδβ其中“”表示直接推導(dǎo)出，是應(yīng)用產(chǎn)生規(guī)則進(jìn)行推導(dǎo)的記號。注意“”與“→”不同，“→”是產(chǎn)生式中的定義記號。直接推導(dǎo)是對文法符號串αAβ中的非終結(jié)符A用相應(yīng)的產(chǎn)生式A→δ的右部δ來替換，從而得到αδβ。我們給出推導(dǎo)的說明如下：(1)如果α1可直接推出α2，α2可直接推出α3，…，αn-1可直接推出αn，即存在一個(gè)自α1至αn的推導(dǎo)序列：α1α2α3…

αn(n>0)，則我們稱α1可推導(dǎo)出αn，記為α1αn，它表示從α1出發(fā)經(jīng)過一步或若干步可推導(dǎo)出αn。(2)如果記α1α1，則α1αn表示從α1出發(fā)，經(jīng)過0步或若干步可推導(dǎo)出αn；也即α1αn意味著或者α1=αn，或者α1αn。例如，對下面的文法G[E]：E→E+E∣E*E∣(E)│i(3.1)其中，惟一的非終結(jié)符E可以看成是代表一類算術(shù)表達(dá)式。我們可以從E出發(fā)進(jìn)行一系列的推導(dǎo)，如表達(dá)式i+i*i的推導(dǎo)如下：EE+EE+E*EE+E*iE+i*ii+i*i假定G[S]是一個(gè)文法，S是它的開始符號，如果Sα，α∈(VT∪VN)*，則稱α是文法G[S]的一個(gè)句型；如果α∈VT*，則稱α是文法G[S]的一個(gè)句子。僅含終結(jié)符的句型是一個(gè)句子。由定義可知，開始符S本身只能是文法的一個(gè)句型而不可能是一個(gè)句子；此外，上面推導(dǎo)出的i+i*i是文法G[E]的一個(gè)句子(當(dāng)然也是一個(gè)句型)，而E+E、E+E*E、E+E*i和E+i*i都是文法G[E]的句型。對于文法G[S]，它所產(chǎn)生的句子的全體稱為由文法G[S]產(chǎn)生的語言，記為L[G]，即有L(G)={α∣Sα且α∈VT*}3.1.2形式語言分類語言學(xué)家NoamChomsky于1956年首先建立了形式語言的描述，定義了四類文法及相應(yīng)的形式語言，并分別與相應(yīng)的識別系統(tǒng)相聯(lián)系，它對程序語言的設(shè)計(jì)、編譯方法、計(jì)算復(fù)雜性等方面都產(chǎn)生了重大影響。1．0型文法與0型語言(對應(yīng)圖靈機(jī))如果文法G的每一個(gè)產(chǎn)生式具有下列形式：α→β其中，α∈V*VNV*(注：V=VN∪VT)，即至少含有一個(gè)非終結(jié)符；β∈V*；則稱文法G為0型文法或短語文法，記為PSG。0型文法相應(yīng)的語言稱為0型語言或稱遞歸可枚舉集，它的識別系統(tǒng)是圖靈(Turing)機(jī)。2．1型文法與1型語言(對應(yīng)線性界限自動(dòng)機(jī)，自然語言)文法G的每一個(gè)產(chǎn)生式α→β，均在0型文法的基礎(chǔ)上增加了字符長度上滿足∣α∣≤∣β∣的限制，則稱文法G為1型文法或上下文有關(guān)文法，記為CSG。1型文法相應(yīng)的語言稱為1型語言或上下文有關(guān)語言，它的識別系統(tǒng)是線性界限自動(dòng)機(jī)。

1型文法的另一種定義方法是文法G的每一個(gè)產(chǎn)生式具有下列形式：αAδ→αβδ其中，α、δ∈V*，A∈VN，β∈V+；顯然它滿足前述定義的長度限制，但它更明確地表達(dá)了上下文有關(guān)的特性，即A必須在α、δ的上下文環(huán)境中才能被β所替換。3．2型文法與2型語言(對應(yīng)下推自動(dòng)機(jī)，程序設(shè)計(jì)語言)文法G的每一個(gè)產(chǎn)生式具有下列形式：A→α其中，A∈VN，α∈V*，則稱文法G為2型文法或上下文無關(guān)文法，記為CFG。2型文法相應(yīng)的語言稱為2型語言或上下文無關(guān)語言，它的識別系統(tǒng)是下推自動(dòng)機(jī)。4．3型文法與3型語言(對應(yīng)有限自動(dòng)機(jī))文法G的每個(gè)產(chǎn)生式具有下列形式：A→a或A→aB其中，A、B∈VN，a∈VT*，則文法G稱為3型文法、正規(guī)文法或右線性文法，記為RG。3型文法相應(yīng)的語言為3型語言或正規(guī)語言，它的識別系統(tǒng)是有限自動(dòng)機(jī)。3型文法還可以呈左線性形式：A→a或A→Ba5．四類文法的關(guān)系與區(qū)別由四類文法的定義可知，從0型文法到3型文法逐漸增加限制。1～3型文法都屬于0型文法，2、3型文法均屬于1型文法，3型文法屬于2型文法。四類文法的區(qū)別如下：(1)1型文法中不允許有形如“A→ε”的產(chǎn)生式存在，而2、3型文法則允許形如“A→ε”的產(chǎn)生式存在；(2)0、1型文法的產(chǎn)生式左部存在含有終結(jié)符號的符號串或兩個(gè)以上的非終結(jié)符，而2型和3型文法的產(chǎn)生式左部只允許是單個(gè)的非終結(jié)符號。例3.3試判斷下列產(chǎn)生式集所對應(yīng)的文法和產(chǎn)生的語言：(1) ①S→ACaB(2) ①S→aSBC(3) ①S→Ac(4) ①S→aS ②Ca→aaC ②S→aBC ②S→Sc ②S→aA ③CB→DB ③CB→DB ③A→ab ③A→bA ④CB→E ④DB→DC ④A→aAb ④A→bB ⑤aD→Da ⑤DC→BC⑤B→cB ⑥AD→AC ⑥aB→ab⑥B→c ⑦aE→Ea ⑦bB→bb ⑧AE→ε ⑧bC→bc ⑨cC→cc[解答]由四類文法的定義與區(qū)別可知，1～4分別為0～3型文法。(1)該0型文法產(chǎn)生的0型語言為L0(G)={a2n∣n>0}。例如：當(dāng)n=2時(shí)，句子a2×2=aaaa,(2)該1型文法產(chǎn)生的1型語言為L1(G)={anbncn∣n≥1}。例如，當(dāng)n=2時(shí)，句子a2b2c2=aabbcc是通過下列推導(dǎo)得到的：(3)該2型文法產(chǎn)生的2型語言為L2(G)={anbncm∣m、n≥1}。例如當(dāng)n=2、m=3時(shí)，句子a2b2c3=aabbccc是通過下列推導(dǎo)得到的：(4)該3型文法產(chǎn)生的3型語言為L3(G)={ambnck∣m、n、k≥1}。例如當(dāng)m=2、n=3、k=4時(shí)，句子a2b3c4=aabbbcccc是通過下列推導(dǎo)得到的：由例3.3可知：{anbncn∣n≥1}{anbnc