Part2高級語言及其語法描述課件

Part2

高級語言及其語法描述授課：胡靜Part2

高級語言及其語法描述內(nèi)容提要預(yù)備知識——形式語言基礎(chǔ)文法和語言的定義（語法定義、語義定義）術(shù)語和概念文法的表示：正則表達式和語法樹文法和語言的分類內(nèi)容提要預(yù)備知識——形式語言基礎(chǔ)預(yù)備知識預(yù)備知識更多的概念和一些約定A,B,C,…用來表示非終結(jié)符a,b,c,…表示終結(jié)符…,X,Y,Z可以用來表示終結(jié)符或者非終結(jié)符…,w,x,y,z表示終結(jié)符號串α,β,γ,δ,…表示由終結(jié)符或非終結(jié)符構(gòu)成的符號串在產(chǎn)生式A→α中，A是產(chǎn)生式的左邊(lefthandside,LHS)α是產(chǎn)生式的右邊(righthandside,RHS)A→α1|…|αn

表示產(chǎn)生式A→α1,…,A→αn更多的概念和一些約定A,B,C,…用來表示非終結(jié)符符號串和符號串集合的運算符號串和符號串集合的運算符號串和符號串集合的運算符號串和符號串集合的運算Part2高級語言及其語法描述課件Part2高級語言及其語法描述課件將字符看做符號，則單詞就是符號串，單詞集合就是符號串的集合將單詞看做符號，則句子就是符號串，而所有句子的集合（語言）就是符號串的集合Part2高級語言及其語法描述課件文法的直觀概念文法的直觀概念Part2高級語言及其語法描述課件規(guī)則、字母表均為有限集合句子長度是有限的生成的句子個數(shù)是無限的Part2高級語言及其語法描述課件Part2高級語言及其語法描述課件Part2高級語言及其語法描述課件Part2高級語言及其語法描述課件語法樹語法（推導(dǎo)）樹來描述一個句子的語法結(jié)構(gòu)識別符號語法樹語法（推導(dǎo)）樹來描述一個句子的語法結(jié)構(gòu)識別符號關(guān)于文法的定義定義3.1文法G定義為四元組（VN,VT,P,S）。其中VN為非終結(jié)符號（或語法實體，或變量）集；VT為終結(jié)符號集；P為產(chǎn)生式（也稱規(guī)則）的集合；VN,VT和P是非空有窮集。S稱做識別符號或開始符號，是一個非終結(jié)符（S∈VN），至少要在一條規(guī)則中作為左部出現(xiàn)。VN和VT不含公共元素，即VN∩VT=Φ。通常V表示VN∪VT，V稱為文法G的字母表或字匯表。例3.1文法G=（VN，VT，P，S）

VN={S},VT={0,1} P={S→0S1,S→01} S為開始符號文法可以簡寫，只需要指出開始符號和產(chǎn)生式即可。關(guān)于文法的定義定義3.1關(guān)于文法的定義（續(xù)）定義3.2如α→β是文法G=(VN,VT,P,S)的規(guī)則(或說是P中第一個產(chǎn)生式)，γ和δ是V*中的任意符號串，若有符號串v，w滿足：v=γαδ，w=γβδ，則說v（應(yīng)用規(guī)則α→β）直接產(chǎn)生w，或說w是v的直接推導(dǎo)。（v=>w）例：G[S]：S→0S1，S→01S0S100S11000S11100001111G關(guān)于文法的定義（續(xù)）定義3.2G關(guān)于文法的定義（續(xù)）定義3.3如果存在直接推導(dǎo)的序列：v=w0=>w1=>w2…=>wn=w，(n>0)，則稱v推導(dǎo)出（產(chǎn)生）w（推導(dǎo)長度為n）。記做v=>+w。定義3.4若有v=>+w，或v=w，則記做v=>*w。規(guī)范推導(dǎo)（最右推導(dǎo)）最左推導(dǎo)：若規(guī)則右端符號串中有兩個以上的非終結(jié)符時，先推導(dǎo)左邊的。最右推導(dǎo)：若規(guī)則右端符號串中有兩個以上的非終結(jié)符時，先推導(dǎo)右邊的。關(guān)于文法的定義（續(xù)）定義3.3關(guān)于文法的定義（續(xù)）定義3.5設(shè)G[S]是一文法，如果符號串x是從識別符號推導(dǎo)出來的，即有S=>*x，則稱x是文法G[S]的句型。若x只由終結(jié)符號組成，則稱x為G[S]的句子。定義3.6文法G所產(chǎn)生的語言定義為集合{x|S=>*x，其中S為文法的開始符號，且x∈VT

*}?？捎肔(G)表示該集合。例：G：S→0S1，S→01S0S100S11000S11100001111L(G)={0n1n|n≥1}關(guān)于文法的定義（續(xù)）定義3.5關(guān)于文法的定義（續(xù)）定義3.7若L(G1)=L(G2)，則稱文法G1和G2是等價的。例1：如文法G1[A]：A→0R與G2[S]： S→0S1等價

A→01 S→01 R→A1例2：G1[E]:E→i 與 G2[E]：E→T|E+T等價

E→E+E T→F|T*F E→E*E F→（E）|i E→(E)關(guān)于文法的定義（續(xù)）定義3.7Part2高級語言及其語法描述課件文法的類型Chomsky將文法分為四種類型：0型文法：對任一產(chǎn)生式α→β，都有α∈(VN∪VT)+，β∈(VN∪VT)*1型文法：對任一產(chǎn)生式α→β，都有|β|≥|α|，僅僅S→ε除外2型文法：對任一產(chǎn)生式α→β，都有α∈VN

，β∈(VN∪VT)*3型文法：任一產(chǎn)生式α→β的形式都為A→aB或A→a，其中A∈VN

，B∈VN

，a∈VT。上述叫做右線性文法，另有左線性文法，二者等價。文法的類型Chomsky將文法分為四種類型：文法的類型舉例1型（上下文有關(guān)）文法文法G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bDL(G)={ww|w∈{a,b}*}文法的類型舉例1型（上下文有關(guān)）文法文法的類型舉例2型（上下文無關(guān)）文法文法G[S]： S→aB|bA A→a|aS|bAA B→b|bS|aBB

文法G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0文法的類型舉例2型（上下文無關(guān)）文法文法的類型舉例定義標識符的3型（正規(guī)）文法文法G[I]： I→lT I→l T→lT T→dT T→l T→d文法的類型舉例定義標識符的3型（正規(guī)）文法文法和語言0型文法0型文法（短語文法）的能力相當于圖靈機，可以表征任何遞歸可枚舉集，而且任何0型語言都是遞歸可枚舉的1型文法（上下文有關(guān)文法）產(chǎn)生式的形式為α1Aα2→α1βα2，即只有A出現(xiàn)在α1和α2的上下文中時，才允許β取代A。其識別系統(tǒng)是線性界限自動機。2型文法（上下文無關(guān)文法）產(chǎn)生式的形式為A→β，β取代A時與A的上下文無關(guān)。其識別系統(tǒng)是不確定的下推自動機。3型文法（正則文法）產(chǎn)生的語言是有窮自動機（FA）所接受的集合文法和語言0型文法上下文無關(guān)文法上下文無關(guān)文法有足夠的能力描述現(xiàn)今程序設(shè)計語言的語法結(jié)構(gòu)算術(shù)表達式語句賦值語句條件語句讀語句……文法G=({E},{+,*,I,(,)},P,E} <條件語句>→if<條件>then<語句>

P: E→i |if<條件>then<語句>else<語句> E→E+E E→E*E E→(E)上下文無關(guān)文法上下文無關(guān)文法有足夠的能力描述現(xiàn)今程序設(shè)計語言上下文無關(guān)文法的語法樹用于描述上下文無關(guān)文法的句型推導(dǎo)的直觀方法

例:G[S]: S→aAS A→SbA A→SS S→a A→baSaASSbAba句型aabbaa的語法樹（推導(dǎo)樹）葉子結(jié)點：樹中沒有子孫的結(jié)點。

從左到右讀出推導(dǎo)樹的葉子標記，所得的句型為推導(dǎo)樹的結(jié)果。也把該推導(dǎo)樹稱為該句型的語法樹。aa上下文無關(guān)文法的語法樹用于描述上下文無關(guān)文法的句型推導(dǎo)的直觀上下文無關(guān)文法的語法樹推導(dǎo)過程中施用產(chǎn)生式的順序

例:G[S]: S→aAS A→SbA A→SS S→a A→baSaASSbA