資源描述：
《ch3文法和語(yǔ)言(張素琴)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、1文法和語(yǔ)言的形式定義文法的類型上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù)上下文無(wú)關(guān)文法的句型分析有關(guān)文法實(shí)用中的一些說(shuō)明第三章文法和語(yǔ)言語(yǔ)言的詞法和語(yǔ)法描述工具，用有窮規(guī)則描述語(yǔ)言的無(wú)窮句子。3.1文法的直觀概念采用巴克斯范式BNF，規(guī)則的集合來(lái)描述元符號(hào)::=,→,
2、,<>,{}例子p32<句子>::=<主語(yǔ)><謂語(yǔ)>2高級(jí)語(yǔ)言都是由句子(程序)的集合組成C語(yǔ)言是字母表上定義的，按照一定規(guī)則構(gòu)成的字母表上基本符號(hào)串（C源程序）的集合。字母表：是某語(yǔ)言基本符號(hào)的集合，如if是字母表中的一個(gè)元素，保留關(guān)鍵字、標(biāo)示符、運(yùn)算符、字母、
3、數(shù)字和一些專用符號(hào)，如/*，；等。符號(hào)串：字母表中符號(hào)組成的任何有窮序列。如字母表?={0,1}上的符號(hào)串0011003.2符號(hào)和符號(hào)串符號(hào)串的頭尾z=xy是符號(hào)串，x是z的頭，y是z的尾。x非空，y是固有尾；y非空，x是固有頭例子z=abc,頭?,a,ab,abcz=x…符號(hào)串的方冪x是符號(hào)串，將自身鏈接n次的符號(hào)串z=xxx…=xn,設(shè)x=ab,則x0=?,x1=ab,x2=abab,xn=xn-1x符號(hào)串的集合若集合A中所有元素都是某字母表上字符串。4符號(hào)串集合的乘積-笛卡爾乘積集合A和B的乘積AB={xy
4、
5、x?A,y?B}A={a,b},B={c,d},AB={ac,ad,bc,bd},{?}A=A{?}=A字母表集合的閉包?*定義在字母表?上的所有有窮長(zhǎng)字符串的集合。?*=?0??1??2…?n=?0??+正閉包?+=?1??2…?n=??*例子：?={0,1}，?*={?,0,1,00,01,10,11,000,…}無(wú)窮?+={0,1,00,01,10,11,000,…}563.3文法和語(yǔ)言的形式定義如何來(lái)描述一種語(yǔ)言？如果語(yǔ)言是有窮的（只含有有窮多個(gè)句子），可以將句子逐一列出來(lái)表示如果語(yǔ)言是無(wú)窮的，找出語(yǔ)言
6、的有窮表示。語(yǔ)言的有窮表示有兩個(gè)途經(jīng)：生成方式（文法）：語(yǔ)言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來(lái)構(gòu)造。識(shí)別方式（自動(dòng)機(jī)）：用一個(gè)過(guò)程，當(dāng)輸入的一任意串屬于語(yǔ)言時(shí)，該過(guò)程經(jīng)有限次計(jì)算后就會(huì)停止并回答“是”；若不屬于，要么能停止并回答“不是”，要么永遠(yuǎn)繼續(xù)下去。7語(yǔ)言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來(lái)構(gòu)造。規(guī)則：也稱重寫(xiě)規(guī)則、產(chǎn)生式或生成式，是形如?→?或?∷=?的(?，?)有序?qū)?，其?是字母表V的正閉包V+中的一個(gè)符號(hào)，?是V*中的一個(gè)符號(hào)。?稱為規(guī)則的左部，?稱作規(guī)則的右部。文法的定義推導(dǎo)的概念句型、句子和語(yǔ)言的
7、定義8文法定義文法G定義為四元組(VN，VT，P，S)其中VN:非終結(jié)符號(hào)(或語(yǔ)法實(shí)體，或變量)集；VT:終結(jié)符號(hào)集；P:規(guī)則的集合；VN，VT和P是非空有窮集。S:稱作識(shí)別符號(hào)或開(kāi)始符號(hào)的一個(gè)非終結(jié)符，它至少要在一條產(chǎn)生式中作為左部出現(xiàn)。VN和VT不含公共的元素，即VN∩VT=φ用V表示VN∪VT，稱為文法G的字母表或字匯表9文法的定義例文法G=（VN，VT，P，S）VN={S},VT={0,1}P={S→0S1,S→01}S為開(kāi)始符號(hào)例文法G=（VN，VT，P，S）VN={標(biāo)識(shí)符，字母，數(shù)字}VT={a,b,
8、c,…x,y,z,0,1,…,9}P={<標(biāo)識(shí)符>→<字母><標(biāo)識(shí)符>→<標(biāo)識(shí)符><字母><標(biāo)識(shí)符>→<標(biāo)識(shí)符><數(shù)字><字母>→a…<字母>→z<數(shù)字>→0…<數(shù)字>→9}S=<標(biāo)識(shí)符>11文法的寫(xiě)法元符號(hào):→,∷=,
9、,<>習(xí)慣大寫(xiě)字母表示非終結(jié)符小寫(xiě)字母表示終結(jié)符(1)G：S→aAbA→abA→aAbA→ε(2)G[S]：A→abA→aAbA→εS→aSb(3)G[S]:A→ab
10、aAb
11、εS→aSb描述文法的規(guī)則成為巴克斯范式BNF。也可以用語(yǔ)法圖來(lái)表示。見(jiàn)第2章p13-15.12推導(dǎo)的定義直接推導(dǎo)“?”
12、α→β是文法G的產(chǎn)生式，若有v,w滿足：v=γαδ,w=γβδ,其中γ∈V*,δ∈V*則稱v直接推導(dǎo)到w,記作v?w也稱w直接歸約到v例：G：S→0S1，S→010S1?00S1100S11?000S111000S111?00001111S?0S113推導(dǎo)<程序>?<分程序>.(<程序>?<分程序>.)<分程序>.?<變量說(shuō)明部分><語(yǔ)句>.(<分程序>?<變量說(shuō)明部分><語(yǔ)句>)VAR<標(biāo)識(shí)符>;BEGINREAD(<標(biāo)識(shí)符>)END.?VARA;BEGINREAD(<標(biāo)識(shí)符>)END.(<標(biāo)識(shí)符>?A)VAR
13、A;BEGINREAD(<標(biāo)識(shí)符>)END.?VARA;BEGINREAD(A)END.(<標(biāo)識(shí)符>?A)14推導(dǎo)的定義若存在v=w0?w1?...?wn=w,(n>0)則記為v=>+w，稱作v推導(dǎo)出w，或w歸約到v若有v=>+w或v=w，則記為v=>*w15例：G：S→0S1，S→010S1?00S1100S11?000S111000S111?00001111S?0S1
