形式語言理論

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

a,ab,aaca是Α={a?b,c}上的符號(hào)串在符號(hào)串中，符號(hào)是有順序的，順序不同,代表不同的符號(hào)串，如:ab和ba不同不含任何符號(hào)的符號(hào)串稱為空串，用ε表示 注意:{ε}并不等于空集合{}符號(hào)串長(zhǎng)度:符號(hào)串中含有符號(hào)的個(gè)數(shù) 如: |abc|=3 |ε|=0第5頁，課件共49頁，創(chuàng)作于2023年2月符號(hào)串的運(yùn)算符號(hào)串的連接：設(shè)x、y是符號(hào)串,它們的連接是把y的符號(hào)寫在x的符號(hào)之后得到的符號(hào)串xy

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

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

aa…aa例如a1=aa2=aaa0=ε第6頁，課件共49頁，創(chuàng)作于2023年2月符號(hào)串集合：定義:若集合A中所有元素都是某字母表上的符號(hào)串，則稱A為字母表上的符號(hào)串集合。符號(hào)串集合的乘積：符號(hào)串集合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第7頁，課件共49頁，創(chuàng)作于2023年2月符號(hào)串集合的方冪:設(shè)A是符號(hào)串的集合，則稱Ai為符號(hào)串集A的方冪，其中i是非負(fù)整數(shù)。具體定義如下:A0={ε}A1=A,A2=AAAK=AA......A(k個(gè))第8頁，課件共49頁，創(chuàng)作于2023年2月集合的閉包閉包 集合Σ的閉包Σ*定義如下：

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

例：設(shè)有字母表Σ={0，1}

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

即Σ*表示Σ上所有有窮長(zhǎng)的串的集合。第9頁，課件共49頁，創(chuàng)作于2023年2月正閉包Σ+=Σ1∪Σ2∪Σ3∪…稱為Σ的正閉包。

+

表示上的除ε外的所有有窮長(zhǎng)串的集合自反閉包Σ*=Σ0∪Σ+ Σ+=ΣΣ*=Σ*Σ第10頁，課件共49頁，創(chuàng)作于2023年2月2.2文法和語言1、文法定義:文法G(Grammar)定義為四元組（VN，VT，P，S）

VN(Nonternimal)：非終結(jié)符集

VT(Terminal)：終結(jié)符集

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

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

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

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

若有v+w或v=w，則記為v*w，v廣義推導(dǎo)出w，w廣義規(guī)約到v（可以包含0步推導(dǎo)）+*第14頁，課件共49頁，創(chuàng)作于2023年2月三種推導(dǎo)的比較直接推導(dǎo)（）的長(zhǎng)度為1直接推導(dǎo)序列（+）的長(zhǎng)度n≥1廣義推導(dǎo)（*）的長(zhǎng)度≥0第15頁，課件共49頁，創(chuàng)作于2023年2月規(guī)范推導(dǎo)與規(guī)范規(guī)約考慮兩種特殊推導(dǎo)：最左推導(dǎo)和最右推導(dǎo)，即對(duì)于一個(gè)推導(dǎo)序列中的每一步直接推導(dǎo)，都是對(duì)最左（最右）非終結(jié)符進(jìn)行替換。最右推導(dǎo)也稱規(guī)范推導(dǎo)，它的逆過程稱為最左規(guī)約，也稱規(guī)范規(guī)約。

第16頁，課件共49頁，創(chuàng)作于2023年2月2.3文法的分類

Chomsky對(duì)文法中的規(guī)則施加不同限制，將文法和語言分為四大類：0型文法（PSG）0型語言或短語結(jié)構(gòu)語言1型文法（CSG）1型語言或上下文有關(guān)語言2型文法（CFG）2型語言或上下文無關(guān)語言3型文法（RG）3型語言或正則（正規(guī)）語言第17頁，課件共49頁，創(chuàng)作于2023年2月如果對(duì)于某文法G，P中每個(gè)規(guī)則具有下列形式：

α→β其中α∈V+，β∈V*，則該文法G為（Chomsky）0型文法或短語結(jié)構(gòu)文法。相應(yīng)的語言稱為0型語言或短語結(jié)構(gòu)語言。如文法G，其中VN={A,B,S}VT={0,1}P={S→0AB1B→0B→SA|01A1→SB1A0→S0B}0型文法第18頁，課件共49頁，創(chuàng)作于2023年2月1型文法(上下文有關(guān))

它是0型文法的特例, 對(duì)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＋，它表示當(dāng)A的上文為且下文為時(shí)可把A替換成，因此稱1型文法為上下文有關(guān)文法。第19頁，課件共49頁，創(chuàng)作于2023年2月2型文法（上下文無關(guān)文法）

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

，β∈(VN∪VT)*例文法G[S]： S→ABA→BS|0B→SA|12型文法產(chǎn)生式的一般形式是:A→，它表示不管A的上下文如何都可把A替換成，因此被稱為上下文無關(guān)文法。通常程序設(shè)計(jì)語言的文法，可用2型文法來描述，因此我們重點(diǎn)研究2型文法。第20頁，課件共49頁，創(chuàng)作于2023年2月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在程序設(shè)計(jì)語言中，正規(guī)文法通常用來描述單詞的結(jié)構(gòu)。第21頁，課件共49頁，創(chuàng)作于2023年2月文法類別產(chǎn)生式形式產(chǎn)生的語言說明0型文法(短語文法)α→βα∈V+,且至少含一個(gè)非終結(jié)符，β∈V*0型語言對(duì)產(chǎn)生式基本無限制1型文法(上下文有關(guān)文法)α→β，|β|≥|α|1型語言（上下文有關(guān)語言）將A替換成時(shí)，必須考慮A的上下文2型文法(上下文無關(guān)文法)A→β，A∈VN

，β∈V*2型語言（上下文無關(guān)語言）無需考慮A在上下文中的出現(xiàn)情況3型文法(正規(guī)文法)A→aB或A→a，A,B∈VN，a∈VT3型語言(正規(guī)語言)產(chǎn)生式全部是規(guī)定的形式第22頁，課件共49頁，創(chuàng)作于2023年2月四種文法之間的逐級(jí)“包含”關(guān)系2型文法1型文法3型文法0型文法第23頁，課件共49頁，創(chuàng)作于2023年2月2.4．語言和語法1、句型和句子 設(shè)有文法G[S]，若符號(hào)串α是從開始符推導(dǎo)出來的,即S=>*α

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

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

因?yàn)镾0S100S11000S11100001111

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

由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型第24頁，課件共49頁，創(chuàng)作于2023年2月2、語言的定義 由文法G生成的語言記為L(zhǎng)(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、文法和語言的關(guān)系： 文法G生成的每個(gè)終結(jié)符號(hào)串都在L(G)中 L(G)中的每個(gè)串確實(shí)能被G生成第25頁，課件共49頁，創(chuàng)作于2023年2月2.語法樹1、定義：語法樹是這樣的一個(gè)語法結(jié)構(gòu)，它的結(jié)點(diǎn)由符號(hào)組成。根結(jié)點(diǎn)對(duì)應(yīng)于開始符號(hào)。只有非終結(jié)符號(hào)對(duì)應(yīng)的結(jié)點(diǎn)有子結(jié)點(diǎn)。并且，一個(gè)結(jié)點(diǎn)和它的子結(jié)點(diǎn)分別對(duì)應(yīng)于文法中的一個(gè)規(guī)則的左部和右部。2、引入語法樹的意義：作為識(shí)別句子的輔助工具，語法樹可以表示句子的結(jié)構(gòu)。這一點(diǎn)對(duì)于其后的語義分析有非常重要的意義。第26頁，課件共49頁，創(chuàng)作于2023年2月3、作用:直觀地描述上下文無關(guān)文法的句型推導(dǎo)過程。給定文法G=(VN,VT,P,S)，對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹第27頁，課件共49頁，創(chuàng)作于2023年2月語法樹的相關(guān)概念結(jié)點(diǎn)：每個(gè)樹的結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)符號(hào)。結(jié)點(diǎn)的名字就是該符號(hào)。邊：兩個(gè)結(jié)點(diǎn)之間的連線。根結(jié)點(diǎn)：沒有邊進(jìn)入的結(jié)點(diǎn)。分支：某個(gè)結(jié)點(diǎn)向下射出的邊和其結(jié)點(diǎn)稱為分支。（父子結(jié)點(diǎn)，兄弟結(jié)點(diǎn)）子樹：語法樹的某個(gè)結(jié)點(diǎn)和它向下射出的部分末端結(jié)點(diǎn)：沒有向下射出的邊的結(jié)點(diǎn)成為末端結(jié)點(diǎn)。在相對(duì)于句型的語法樹中，末端結(jié)點(diǎn)可能是非終結(jié)符號(hào)。第28頁，課件共49頁，創(chuàng)作于2023年2月語法樹的特征給定文法G，G=(VN,VT,P,S)，對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹（推導(dǎo)樹）。這棵樹具有下列特征：1、根結(jié)點(diǎn)的標(biāo)記是開始符號(hào)S；2、每個(gè)結(jié)點(diǎn)的標(biāo)記都是V中的一個(gè)符號(hào)；3、若一棵子樹的根結(jié)點(diǎn)為A，且其所有直接子孫的標(biāo)記從左向右的排列次序?yàn)锳1A2…AR，那么A→A1A2..AR一定是P中的一條規(guī)則；4、若一標(biāo)記為A的結(jié)點(diǎn)至少有一個(gè)除它以外的子孫，則A∈VN5、若樹的所有葉結(jié)點(diǎn)上的標(biāo)記從左到右排列為字符串w，則w是文法G的句型；若w中僅含終結(jié)符號(hào)，則w為文法G所產(chǎn)生的句子。第29頁，課件共49頁，創(chuàng)作于2023年2月構(gòu)造語法樹方法：把開始符號(hào)做為根結(jié)點(diǎn)，對(duì)每一個(gè)直接推導(dǎo)畫一個(gè)分支，分支的名字是直接推導(dǎo)中被替換的非終結(jié)符號(hào)，直到再無分支可畫結(jié)束。例如：推導(dǎo)SABAcBdAccddabccddSBBdbaAcdc第30頁，課件共49頁，創(chuàng)作于2023年2月語法樹的構(gòu)造過程SABAcBdAccddabccddSSBASBBdAcSBBdAcdcSBBdbaAcdc（1）（2）（3）（5）（4）第31頁，課件共49頁，創(chuàng)作于2023年2月

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

句型T+T×F的推導(dǎo)過程與語法樹EET+TFT×E=>E+TEET+TFT×E=>E+T=>E+T×F=>T+T×F=>T+T=>T+T×F從語法樹中看不出句型中的符號(hào)被替代的順序從左到右讀出葉子結(jié)點(diǎn)得到的符號(hào)串，為文法的句型。也把該語法樹稱為該句型的語法樹。第32頁，課件共49頁，創(chuàng)作于2023年2月2.5文法和語言的一些特性

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

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

S→ε，該產(chǎn)生式稱為空產(chǎn)生式，S稱為可空非終結(jié)符。在消除左遞歸方法中用到空產(chǎn)生式。第33頁，課件共49頁，創(chuàng)作于2023年2月

例：文法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）不可到達(dá)第34頁，課件共49頁，創(chuàng)作于2023年2月文法G：E→E+E|E×E|（E）|i句子i×i+i對(duì)應(yīng)的語法樹兩個(gè)不同的最左推導(dǎo)：推導(dǎo)1：E

E+EE×E+Ei×E+Ei×i+Ei×i+i推導(dǎo)2：EE×Ei×Ei×E+Ei×i+Ei×i+iiEE+EEE×iiEEE×iEE+ii2.5文法的二義性(Ambiguity)第35頁，課件共49頁，創(chuàng)作于2023年2月

如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則說這個(gè)文法是二義的。二義性文法存在某個(gè)句子,它有兩個(gè)不同的最左（右）推導(dǎo)。

第36頁，課件共49頁，創(chuàng)作于2023年2月為什么要避免文法產(chǎn)生二義性？二義性的文法將給編譯程序的執(zhí)行帶來問題。當(dāng)編譯程序?qū)Χx性文法生成的句子結(jié)構(gòu)進(jìn)行語法分析時(shí)，就會(huì)產(chǎn)生兩種甚至更多種不同的理解。語法結(jié)構(gòu)上的不確定性，必將導(dǎo)致語義處理上的不確定性。因此，希望描述語言的文法是無二義性的。第37頁，課件共49頁，創(chuàng)作于2023年2月如何消除文法的二義性？(1)方法一：不改變文法中原有的語法規(guī)則，僅加進(jìn)一些語法的非形式規(guī)定。如1：對(duì)于文法

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

規(guī)定運(yùn)算符優(yōu)先順序和結(jié)合律，即*優(yōu)先于+，+、*服從左結(jié)合。第38頁，課件共49頁，創(chuàng)作于2023年2月如何消除文法的二義性？(2)方法二：構(gòu)造一個(gè)等價(jià)的無二義性的文法，即把排除二義性的規(guī)則合并到原有文法中，改寫原有的文法。如文法

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

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

G’[E]:E→T|E+TT→F|T*FF→（E）|i第39頁，課件共49頁，創(chuàng)作于2023年2月2.6分析方法簡(jiǎn)介對(duì)于2型文法,如何識(shí)別一個(gè)符號(hào)串是否為某文法的句型或句子，有兩種分析方法：自頂向下分析法(Top-Downparsing)自底向上分析法(Bottom-Upparsing)第40頁，課件共49頁，創(chuàng)作于2023年2月2.6.1自頂向下的分析方法1、定義:從文法的開始符號(hào)出發(fā)，反復(fù)使用文法的產(chǎn)生式，尋找與輸入符號(hào)串匹配的推導(dǎo)。2、語法樹的構(gòu)造：將文法的開始符號(hào)作為語法樹的根，向下逐步建立語法樹，使語法樹的末端結(jié)點(diǎn)符號(hào)串正好是輸入符號(hào)串。

第41頁，課件共49頁，創(chuàng)作于2023年2月

例文法G：S→cAd

A→ab

A→a

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

當(dāng)文法的某一個(gè)非終結(jié)符有幾條產(chǎn)生式、而且每條產(chǎn)生式右部都是終結(jié)符時(shí)，應(yīng)保證它們是互不相同的終結(jié)符。

第44頁，課件共49頁，創(chuàng)作于2023年2月2.6.3自底向上的分析方法1、定義:從輸入符號(hào)串開始，在其中尋