形式語言理論

形式語言理論第一頁，共四十九頁，編輯于2023年，星期二形式語言Chomsky于1956年提出了一種用來描述語言的數(shù)學系統(tǒng)。人們把用一組數(shù)學符號和規(guī)則來描述語言的方式稱為形式描述，而把所用的數(shù)學符號和規(guī)則稱為形式語言。形式語言，只是從語法上研究語言。它是抽象的數(shù)學系統(tǒng)，用于模擬程序設計語言的語法，或者是并不很成功地模擬自然語言如英語的語法。形式語言理論是編譯理論的重要基礎，它主要研究組成符號語言的符號串的集合及它們的表示法、結構與特性。第二頁，共四十九頁，編輯于2023年，星期二形式語言和編譯理論中的最基本概念——符號串和符號串集合第三頁，共四十九頁，編輯于2023年，星期二2.1字母表和符號串字母表定義:元素的非空有窮集合，記為∑。例：∑={0?1}Α={a?b,c}元素也稱為符號，字母表也稱符號集。程序語言的字母表由字母數(shù)字和若干專用符號組成。第四頁，共四十九頁，編輯于2023年，星期二符號串定義:由字母表中的符號組成的任何有窮序列例：0,00,10是字母表∑={0?1}上的符號串

a,ab,aaca是Α={a?b,c}上的符號串在符號串中，符號是有順序的，順序不同,代表不同的符號串，如:ab和ba不同不含任何符號的符號串稱為空串，用ε表示 注意:{ε}并不等于空集合{}符號串長度:符號串中含有符號的個數(shù) 如: |abc|=3 |ε|=0第五頁，共四十九頁，編輯于2023年，星期二符號串的運算符號串的連接：設x、y是符號串,它們的連接是把y的符號寫在x的符號之后得到的符號串xy

例如x="ST"，y="abu"，則xy="STabu"

顯然εx=xε=x符號串的方冪：把符號串a(chǎn)自身連接n次得到的符號串a(chǎn)n=

aa…aa例如a1=aa2=aaa0=ε第六頁，共四十九頁，編輯于2023年，星期二符號串集合：定義:若集合A中所有元素都是某字母表上的符號串，則稱A為字母表上的符號串集合。符號串集合的乘積：符號串集合A和B的乘積定義為:AB={xy|x∈A且y∈B}，即AB是由A中的串x和B中的串y連接而成的串xy組成的集合。 若集合A=ab,cdeB=0,1

則AB=ab0,ab1,cde0,cde1

顯然{ε}A=A{ε}=A第七頁，共四十九頁，編輯于2023年，星期二符號串集合的方冪:設A是符號串的集合，則稱Ai為符號串集A的方冪，其中i是非負整數(shù)。具體定義如下:A0={ε}A1=A,A2=AAAK=AA......A(k個)第八頁，共四十九頁，編輯于2023年，星期二集合的閉包閉包 集合Σ的閉包Σ*定義如下：

Σ*=Σ0∪Σ1∪Σ2∪Σ3∪…

例：設有字母表Σ={0，1}

則Σ*=Σ0∪Σ1∪Σ2∪… ={ε,0,1,00,01,10,11,000,…}

即Σ*表示Σ上所有有窮長的串的集合。第九頁，共四十九頁，編輯于2023年，星期二正閉包Σ+=Σ1∪Σ2∪Σ3∪…稱為Σ的正閉包。

+

表示上的除ε外的所有有窮長串的集合自反閉包Σ*=Σ0∪Σ+ Σ+=ΣΣ*=Σ*Σ第十頁，共四十九頁，編輯于2023年，星期二2.2文法和語言1、文法定義:文法G(Grammar)定義為四元組（VN，VT，P，S）

VN(Nonternimal)：非終結符集

VT(Terminal)：終結符集

P(Production)：產(chǎn)生式（規(guī)則）集合

S：開始符號或識別符號第十一頁，共四十九頁，編輯于2023年，星期二說明:V=VN∪VT，V稱為文法G的字母表P中產(chǎn)生式形如：α→β,其中α∈V+且至少含一個非終結符，β∈V*VN,VT和P是非空有窮集VN∩VT=φS是一個非終結符，且至少要在一條產(chǎn)生式的左部出現(xiàn)非終結符代表一個語言中的語法成分，如<賦值語句>，它是構成程序的一個語法成分，這個符號本身不會在程序中出現(xiàn)，而終結符是組成程序的具體的符號。第十二頁，共四十九頁，編輯于2023年，星期二2.推導和規(guī)范推導： α→β是文法G的產(chǎn)生式，若有v，w滿足： v=γαδ,w=γβδ,其中γ,δ∈V* 則稱v直接推導出w,也稱w直接歸約到v, 記作vw直接推導就是用產(chǎn)生式的右部替換產(chǎn)生式的左部的過程直接歸約就是用產(chǎn)生式的左部替換產(chǎn)生式的右部的過程第十三頁，共四十九頁，編輯于2023年，星期二2、直接推導序列：或+

若存在v=u0u1...un=w,(n>0)

則稱v+w，v推導出w，或w歸約到v（至少有1步推導），這個直接推導序列的長度為n。3、廣義推導：或*

若有v+w或v=w，則記為v*w，v廣義推導出w，w廣義規(guī)約到v（可以包含0步推導）+*第十四頁，共四十九頁，編輯于2023年，星期二三種推導的比較直接推導（）的長度為1直接推導序列（+）的長度n≥1廣義推導（*）的長度≥0第十五頁，共四十九頁，編輯于2023年，星期二規(guī)范推導與規(guī)范規(guī)約考慮兩種特殊推導：最左推導和最右推導，即對于一個推導序列中的每一步直接推導，都是對最左（最右）非終結符進行替換。最右推導也稱規(guī)范推導，它的逆過程稱為最左規(guī)約，也稱規(guī)范規(guī)約。

第十六頁，共四十九頁，編輯于2023年，星期二2.3文法的分類

Chomsky對文法中的規(guī)則施加不同限制，將文法和語言分為四大類：0型文法（PSG）0型語言或短語結構語言1型文法（CSG）1型語言或上下文有關語言2型文法（CFG）2型語言或上下文無關語言3型文法（RG）3型語言或正則（正規(guī)）語言第十七頁，共四十九頁，編輯于2023年，星期二如果對于某文法G，P中每個規(guī)則具有下列形式：

α→β其中α∈V+，β∈V*，則該文法G為（Chomsky）0型文法或短語結構文法。相應的語言稱為0型語言或短語結構語言。如文法G，其中VN={A,B,S}VT={0,1}P={S→0AB1B→0B→SA|01A1→SB1A0→S0B}0型文法第十八頁，共四十九頁，編輯于2023年，星期二1型文法(上下文有關)

它是0型文法的特例, 對P中的任一產(chǎn)生式α→β，都有|β|≥|α|≥1，僅僅S→ε除外,但S不得出現(xiàn)在任何產(chǎn)生式的右部。 例文法G[S]：

S→aSBE S→aBE EB→BE aB→ab bB→bb bE→be eE→ee 1型文法產(chǎn)生式的一般形式是A→，,∈V*，A∈VN,

β∈V＋，它表示當A的上文為且下文為時可把A替換成，因此稱1型文法為上下文有關文法。第十九頁，共四十九頁，編輯于2023年，星期二2型文法（上下文無關文法）

它是1型文法的特例，對任一產(chǎn)生式α→β，都有 α∈VN

，β∈(VN∪VT)*例文法G[S]： S→ABA→BS|0B→SA|12型文法產(chǎn)生式的一般形式是:A→，它表示不管A的上下文如何都可把A替換成，因此被稱為上下文無關文法。通常程序設計語言的文法，可用2型文法來描述，因此我們重點研究2型文法。第二十頁，共四十九頁，編輯于2023年，星期二3型文法(右線性文法和正規(guī)文法)

它是2型文法的特例，任一產(chǎn)生式α→β的形式都為A→aB或 A→a，其中A，B∈VN，a∈VT* 在正規(guī)文法中，任一產(chǎn)生式α→β的形式都為A→aB或 A→a，其中A，B∈VN，a∈VT例如文法G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0在程序設計語言中，正規(guī)文法通常用來描述單詞的結構。第二十一頁，共四十九頁，編輯于2023年，星期二文法類別產(chǎn)生式形式產(chǎn)生的語言說明0型文法(短語文法)α→βα∈V+,且至少含一個非終結符，β∈V*0型語言對產(chǎn)生式基本無限制1型文法(上下文有關文法)α→β，|β|≥|α|1型語言（上下文有關語言）將A替換成時，必須考慮A的上下文2型文法(上下文無關文法)A→β，A∈VN

，β∈V*2型語言（上下文無關語言）無需考慮A在上下文中的出現(xiàn)情況3型文法(正規(guī)文法)A→aB或A→a，A,B∈VN，a∈VT3型語言(正規(guī)語言)產(chǎn)生式全部是規(guī)定的形式第二十二頁，共四十九頁，編輯于2023年，星期二四種文法之間的逐級“包含”關系2型文法1型文法3型文法0型文法第二十三頁，共四十九頁，編輯于2023年，星期二2.4．語言和語法1、句型和句子 設有文法G[S]，若符號串α是從開始符推導出來的,即S=>*α

，則稱α是文法G的句型。若α僅由終結符組成,即S=>*α

，且α∈VT*，則稱α是文法G的句子。例文法G[S]：S→0S1，S→01

因為S0S100S11000S11100001111

所以S,0S1,00S11,000S111,00001111都是G的句型,00001111是G的句子

由規(guī)范推導所得的句型稱為規(guī)范句型第二十四頁，共四十九頁，編輯于2023年，星期二2、語言的定義 由文法G生成的語言記為L(G),它是文法G的一切句子的集合,即 L(G)={x|S=>*x，且x∈VT*} 例文法G：S→0S1，S→01 S0S100S1103S13

…0n-1S1n-1

0n1n L(G)={0n1n|n≥1}3、文法和語言的關系： 文法G生成的每個終結符號串都在L(G)中 L(G)中的每個串確實能被G生成第二十五頁，共四十九頁，編輯于2023年，星期二2.語法樹1、定義：語法樹是這樣的一個語法結構，它的結點由符號組成。根結點對應于開始符號。只有非終結符號對應的結點有子結點。并且，一個結點和它的子結點分別對應于文法中的一個規(guī)則的左部和右部。2、引入語法樹的意義：作為識別句子的輔助工具，語法樹可以表示句子的結構。這一點對于其后的語義分析有非常重要的意義。第二十六頁，共四十九頁，編輯于2023年，星期二3、作用:直觀地描述上下文無關文法的句型推導過程。給定文法G=(VN,VT,P,S)，對于G的任何句型都能構造與之關聯(lián)的語法樹第二十七頁，共四十九頁，編輯于2023年，星期二語法樹的相關概念結點：每個樹的結點對應于一個符號。結點的名字就是該符號。邊：兩個結點之間的連線。根結點：沒有邊進入的結點。分支：某個結點向下射出的邊和其結點稱為分支。（父子結點，兄弟結點）子樹：語法樹的某個結點和它向下射出的部分末端結點：沒有向下射出的邊的結點成為末端結點。在相對于句型的語法樹中，末端結點可能是非終結符號。第二十八頁，共四十九頁，編輯于2023年，星期二語法樹的特征給定文法G，G=(VN,VT,P,S)，對于G的任何句型都能構造與之關聯(lián)的語法樹（推導樹）。這棵樹具有下列特征：1、根結點的標記是開始符號S；2、每個結點的標記都是V中的一個符號；3、若一棵子樹的根結點為A，且其所有直接子孫的標記從左向右的排列次序為A1A2…AR，那么A→A1A2..AR一定是P中的一條規(guī)則；4、若一標記為A的結點至少有一個除它以外的子孫，則A∈VN5、若樹的所有葉結點上的標記從左到右排列為字符串w，則w是文法G的句型；若w中僅含終結符號，則w為文法G所產(chǎn)生的句子。第二十九頁，共四十九頁，編輯于2023年，星期二構造語法樹方法：把開始符號做為根結點，對每一個直接推導畫一個分支，分支的名字是直接推導中被替換的非終結符號，直到再無分支可畫結束。例如：推導SABAcBdAccddabccddSBBdbaAcdc第三十頁，共四十九頁，編輯于2023年，星期二語法樹的構造過程SABAcBdAccddabccddSSBASBBdAcSBBdAcdcSBBdbaAcdc（1）（2）（3）（5）（4）第三十一頁，共四十九頁，編輯于2023年，星期二

例：文法G：E→E+T|T T→T×F|FF→（E）|i

句型T+T×F的推導過程與語法樹EET+TFT×E=>E+TEET+TFT×E=>E+T=>E+T×F=>T+T×F=>T+T=>T+T×F從語法樹中看不出句型中的符號被替代的順序從左到右讀出葉子結點得到的符號串，為文法的句型。也把該語法樹稱為該句型的語法樹。第三十二頁，共四十九頁，編輯于2023年，星期二2.5文法和語言的一些特性

1、無用非終結符：某個非終結符不出現(xiàn)在文法的任何一個句型中，并且不能從它推出終結符號串。含有該非終結符的規(guī)則即不可終止。2、不可達文法符號：如果一個非終結符不出現(xiàn)在該文法的任何其他的產(chǎn)生式的右部。該非終結符為不可達文法符號，含有該非終結符的規(guī)則即不可達規(guī)則3、有害規(guī)則：U→U,無用且引起文法的二義4、可空非終結符：

2型文法允許以下產(chǎn)生式

S→ε，該產(chǎn)生式稱為空產(chǎn)生式，S稱為可空非終結符。在消除左遞歸方法中用到空產(chǎn)生式。第三十三頁，共四十九頁，編輯于2023年，星期二

例：文法G[S]：（1）S→Be（2）B→Ce （3）B→Af（4）A→Ae（5）A→e （6）C→Cf（7）D→f

多余規(guī)則為：（6）不可終止（7）不可到達第三十四頁，共四十九頁，編輯于2023年，星期二文法G：E→E+E|E×E|（E）|i句子i×i+i對應的語法樹兩個不同的最左推導：推導1：E

E+EE×E+Ei×E+Ei×i+Ei×i+i推導2：EE×Ei×Ei×E+Ei×i+Ei×i+iiEE+EEE×iiEEE×iEE+ii2.5文法的二義性(Ambiguity)第三十五頁，共四十九頁，編輯于2023年，星期二

如果一個文法存在某個句子對應兩棵不同的語法樹，則說這個文法是二義的。二義性文法存在某個句子,它有兩個不同的最左（右）推導。

第三十六頁，共四十九頁，編輯于2023年，星期二為什么要避免文法產(chǎn)生二義性？二義性的文法將給編譯程序的執(zhí)行帶來問題。當編譯程序?qū)Χx性文法生成的句子結構進行語法分析時，就會產(chǎn)生兩種甚至更多種不同的理解。語法結構上的不確定性，必將導致語義處理上的不確定性。因此，希望描述語言的文法是無二義性的。第三十七頁，共四十九頁，編輯于2023年，星期二如何消除文法的二義性？(1)方法一：不改變文法中原有的語法規(guī)則，僅加進一些語法的非形式規(guī)定。如1：對于文法

G[E]:E→iE→E+EE→E*EE→(E)

規(guī)定運算符優(yōu)先順序和結合律，即*優(yōu)先于+，+、*服從左結合。第三十八頁，共四十九頁，編輯于2023年，星期二如何消除文法的二義性？(2)方法二：構造一個等價的無二義性的文法，即把排除二義性的規(guī)則合并到原有文法中，改寫原有的文法。如文法

G[E]:E→iE→E+EE→E*EE→(E)

將運算符的優(yōu)先順序和結合規(guī)則加到原有文法中，則可構造無二義性的文法

G’[E]:E→T|E+TT→F|T*FF→（E）|i第三十九頁，共四十九頁，編輯于2023年，星期二2.6分析方法簡介對于2型文法,如何識別一個符號串是否為某文法的句型或句子，有兩種分析方法：自頂向下分析法(Top-Downparsing)自底向上分析法(Bottom-Upparsing)第四十頁，共四十九頁，編輯于2023年，星期二2.6.1自頂向下的分析方法1、定義:從文法的開始符號出發(fā)，反復使用文法的產(chǎn)生式，尋找與輸入符號串匹配的推導。2、語法樹的構造：將文法的開始符號作為語法樹的根，向下逐步建立語法樹，使語法樹的末端結點符號串正好是輸入符號串。

第四十一頁，共四十九頁，編輯于2023年，星期二

例文法G：S→cAd

A→ab

A→a

識別輸入串w=cabd是否為該文法的句子S推導過程：cAdab=>cabdS=>cAd第四十二頁，共四十九頁，編輯于2023年，星期二3、自頂向下方法的主要問題對輸入串cabd自上而下構造語法樹的另一過程不成功，不成功的原因是選錯產(chǎn)生式A→a自頂向下分析的主要問題是選擇產(chǎn)生式:假定要被代換的最左非終結符號是B，且有n條規(guī)則：B→A1|A2|…|An，那么如何確定用哪個右部去替代B？只能試探性地構造，如果選錯了產(chǎn)生式，必須退回原來的狀態(tài)，往前回退稱為回溯。ScAda第四十三頁，共四十九頁，編輯于2023年，星期二2.6.2確定的自頂向下的分析方法

當文法的某一個非終結符有幾條產(chǎn)生式、而且每條產(chǎn)生式右部都是終結符時，應保證它們是互不相同的終結符。

第四十四頁，共四十九頁，編輯于2023年，星期二2.6.3自底向上的分析方法1、定義:從輸入符號串開始，在其中尋找句柄