第七講語法分析1

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

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

文法開始符號是一個特殊的非終結符，它代表文法所定義的語言中我們最終感興趣的語法實體，即語言的目標，而其它語法實體只是構造語言目標的中間變量；如表達式文法的語言目標是表達式，而程序語言的目標通常為程序。

產生式(也稱產生規(guī)則或規(guī)則)是定義語法實體的一種書寫規(guī)則。一個語法實體的相關規(guī)則可能不止一個。例如，有：P→α1P→α2P→αn為書寫方便，可將這些有相同左部的產生式合并為一個，即縮寫成P→α1∣α2∣…∣αn其中，每個αi(i=1,2,…,n)稱為P的一個候選式，直豎“∣”讀為“或”，它與“→”一樣是用來描述文法的元語言符號(即不屬于Σ的字符)。例3.1試構造產生標識符的文法。[解答]首先，標識符是以字母開頭的字母數字串，我們用L表示“字母”類非終結符，用D表示“數字”類非終結符，而用T表示“字母或數字”類非終結符，則有：L→a∣b∣…∣zD→0∣1∣…∣9T→L∣D其次，如果用S表示“字母數字串”類，則T是一字母或數字，ST也是字母數字串，即有S→T∣ST其中，產生式S→T∣ST是一種左遞歸形式，由它可以產生一串T。最后，作為“標識符”的非終結符I，它或者是一單個字母，或者為一字母后跟字母數字串，即I→L∣LS因此，產生標識符的文法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寫一文法，使其語言是奇數集合，但不允許出現以0打頭的奇數。[解答]根據題意，我們可以將奇數劃分為如圖3–1所示的三個部分，即最高位允許出現1～9，用非終結符B表示；中間部分可以出現任意多位數字0～9，每一位用非終結符D表示；最低位只允許出現1、3、5、7、9等奇數，用A表示。圖3–1奇數劃分示意由于中間部分可出現任意位，所以另引入了一個非終結符M，它包括最高位和中間位部分。假定開始符為N，則可得到文法G[N]為：G=({0,1,…,9},{N,A,M,B,D},N,ξ)ξ:N→A∣MA /*一位數字│多位數字*/M→B∣MD /*僅兩位數字(無中間位)│多于兩位數字*/A→1∣3∣5∣7∣9B→1∣2∣3∣4∣5∣6∣7∣8∣9D→0∣B3．文法產生的語言設文法G=(VT,VN,S,ξ)且α、β∈(VT∪VN)*，如果存在產生式A→δ(δ∈(VT∪VN)*)，則稱αAβ可直接推出αδβ，即αAβαδβ其中“”表示直接推導出，是應用產生規(guī)則進行推導的記號。注意“”與“→”不同，“→”是產生式中的定義記號。直接推導是對文法符號串αAβ中的非終結符A用相應的產生式A→δ的右部δ來替換，從而得到αδβ。我們給出推導的說明如下：(1)如果α1可直接推出α2，α2可直接推出α3，…，αn-1可直接推出αn，即存在一個自α1至αn的推導序列：α1α2α3…

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

1型文法的另一種定義方法是文法G的每一個產生式具有下列形式：αAδ→αβδ其中，α、δ∈V*，A∈VN，β∈V+；顯然它滿足前述定義的長度限制，但它更明確地表達了上下文有關的特性，即A必須在α、δ的上下文環(huán)境中才能被β所替換。3．2型文法與2型語言(對應下推自動機，程序設計語言)文法G的每一個產生式具有下列形式：A→α其中，A∈VN，α∈V*，則稱文法G為2型文法或上下文無關文法，記為CFG。2型文法相應的語言稱為2型語言或上下文無關語言，它的識別系統(tǒng)是下推自動機。4．3型文法與3型語言(對應有限自動機)文法G的每個產生式具有下列形式：A→a或A→aB其中，A、B∈VN，a∈VT*，則文法G稱為3型文法、正規(guī)文法或右線性文法，記為RG。3型文法相應的語言為3型語言或正規(guī)語言，它的識別系統(tǒng)是有限自動機。3型文法還可以呈左線性形式：A→a或A→Ba5．四類文法的關系與區(qū)別由四類文法的定義可知，從0型文法到3型文法逐漸增加限制。1～3型文法都屬于0型文法，2、3型文法均屬于1型文法，3型文法屬于2型文法。四類文法的區(qū)別如下：(1)1型文法中不允許有形如“A→ε”的產生式存在，而2、3型文法則允許形如“A→ε”的產生式存在；(2)0、1型文法的產生式左部存在含有終結符號的符號串或兩個以上的非終結符，而2型和3型文法的產生式左部只允許是單個的非終結符號。例3.3試判斷下列產生式集所對應的文法和產生的語言：(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型文法產生的0型語言為L0(G)={a2n∣n>0}。例如：當n=2時，句子a2×2=aaaa,(2)該1型文法產生的1型語言為L1(G)={anbncn∣n≥1}。例如，當n=2時，句子a2b2c2=aabbcc是通過下列推導得到的：(3)該2型文法產生的2型語言為L2(G)={anbncm∣m、n≥1}。例如當n=2、m=3時，句子a2b2c3=aabbccc是通過下列推導得到的：(4)該3型文法產生的3型語言為L3(G)={ambnck∣m、n、k≥1}。例如當m=2、n=3、k=4時，句子a2b3c4=aabbbcccc是通過下列推導得到的：由例3.3可知：{anbncn∣n≥1}{anbnc