資源描述：
《《上下文無關(guān)文法》PPT課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第2章上下文無關(guān)文法研究內(nèi)容上下文無關(guān)文法概述下推自動(dòng)機(jī)非上下文無關(guān)語言2021/9/161上下文無關(guān)文法的應(yīng)用上下文無關(guān)文法的重要性如下表達(dá)能力強(qiáng)大足于表示大多數(shù)程序設(shè)計(jì)語言語法可以構(gòu)造有效的分析算法以檢驗(yàn)一個(gè)給定的字符串是否由某個(gè)上下文無關(guān)文法產(chǎn)生上下文無關(guān)語言在實(shí)踐中的重要意義定義程序設(shè)計(jì)語言：例如BNF范式描述文檔格式：例如XML，HTML使語法分析概念形式化簡化程序設(shè)計(jì)語言的翻譯：例如設(shè)計(jì)語法分析器2021/9/162上下文無關(guān)文法的應(yīng)用語法分析程序語法分析程序生成器超文本標(biāo)記語言可擴(kuò)展標(biāo)記語言2021/9/163文法的形式定義文法G是一個(gè)
2、四元組：G=(VN,VT,P,Z)，其中：VN是非終結(jié)符的有窮集合，也稱為語法單元、語法成分或語法范疇，可分解為若干非終結(jié)符或終結(jié)符VT是終結(jié)符的有窮集合，是基本符號(hào)，不能再分解V=VN∪VT稱為字匯表(字母表)，VN∩VT=Ф。Z是開始符，Z∈VN，P是規(guī)則式（產(chǎn)生式）有窮集合規(guī)則式形如：x→y，其中x∈V*VNV*,稱為規(guī)則式的左部；y∈V*稱為右部。2021/9/164文法的類型Chomsky將文法分為四種類型：０型文法（短語結(jié)構(gòu)文法，可壓縮的上下文有關(guān)文法），最一般的文法，對規(guī)則無限制u→wu∈V*VNV*w∈V*（可為ε）相應(yīng)的自動(dòng)機(jī)是圖靈
3、機(jī)１型文法（上下文有關(guān)文法,不可壓縮的上下文有關(guān)文法），對規(guī)則有些限制xuy→xwyx和y就是上下文，x,y∈V*，u∈V*∪VN,w∈V+（不可為ε），這些限制也可以寫成：u→w
4、u
5、≤
6、w
7、意為串的長度不可壓縮相應(yīng)的自動(dòng)機(jī)是線性界限自動(dòng)機(jī)2021/9/165文法的類型２型文法（上下文無關(guān)文法，簡單短語結(jié)構(gòu)文法），對規(guī)則的限制A→wA∈VNw∈V*（可為ε）２型文法與字典定義形式相近（一個(gè)字用另一些字定義），與人們習(xí)慣一致。相應(yīng)的自動(dòng)機(jī)是下推自動(dòng)機(jī)，與BNF等價(jià)。左部均為非終結(jié)符2021/9/166文法的類型３型文法（正規(guī)文法，正則文法），規(guī)則是線
8、性的，其中左線性：A→BaA→a右線性：A→aBA→aA，B∈VN,a∈VT相應(yīng)的自動(dòng)機(jī)是有限自動(dòng)機(jī)。在程序設(shè)計(jì)語言中，單詞符號(hào)用３型文法定義。2021/9/167上下文無關(guān)文法概述上下文無關(guān)文法是把變量轉(zhuǎn)化為原語符號(hào)串的一組規(guī)則，即變量?變量或原語符號(hào)組成的串上下文無關(guān)文法最早被用來描述自然語言的一些規(guī)則，在計(jì)算機(jī)語言學(xué)中，Backus范式可以用來表示一種程序設(shè)計(jì)語言的各種規(guī)定，例如字符集、標(biāo)識(shí)字符集、標(biāo)識(shí)符以及各種語句的格式等2021/9/168上下文無關(guān)文法概述文法G=(V，?，R，S)被稱為是上下文無關(guān)文法或2型文法。如果對于?α?β∈R，均
9、有
10、β
11、≥
12、α
13、，并且α∈V成立。關(guān)鍵：對于?A∈V，如果A?β∈P，則無論A出現(xiàn)在句型的任何位置，我們都可以將A替換成β，而不考慮A的上下文。L(G)叫做2型語言(type2language)或者上下文無關(guān)語言(contextfreelanguage,CFL)。2021/9/169上下文無關(guān)文法(例子)構(gòu)造上下文無關(guān)文法G，它所產(chǎn)生的語言為字母表{0,1}上所有回文全體，即L(G)={w∈{0,1}*
14、w=wR}G=({S},{0,1};R,S)，其中R：S??
15、1
16、0；S?OSO
17、1S1分別構(gòu)造如下三個(gè)語言的上下文無關(guān)文法L1={anbn
18、n≥1
19、}；L2={anbncmdm
20、n,m≥1}L3={anbmcmdn
21、n,m≥1}G1=({S},{a,b};R1,S)，其中R1：S?aSb
22、abG2=({S,A,B},{a,b,c,d};R2,S)，其中R2：S?AB，A→aAb
23、ab，B?cBd
24、cdG2=({S,A},{a,b,c,d};R3,S)，其中R2：S?aSd
25、aAd，A→bAc
26、bc2021/9/1610上下文無關(guān)文法的形式化定義定義2.1上下文無關(guān)文法是一個(gè)4元組G=(V,?,R,S)V:一個(gè)有窮集，稱為變元集?:一個(gè)有窮集，稱為終結(jié)符集，(V??=?)R:有窮規(guī)則集，V?(V?
27、?)*S?V:起始變元文法G的語言可以表示為L(G)={w??*
28、S?*w}規(guī)則左邊是單個(gè)變元符號(hào)，右邊的所有符號(hào)屬于集合V∪?2021/9/1611上下文無關(guān)文法的推導(dǎo)和派生設(shè)u，v和ω是由變元及終結(jié)符構(gòu)成的字符串，A?ω是文法的一條規(guī)則，稱uAv生成uωv，記作uAv?uωv。如果u=v，或者存在序列u1，u2，?，uk，使得u?u1?u2???uk?v其中k≥0，則稱u派生v，記作u?*v。該文法的語言是{ω∈∑*
29、S?*ω}2021/9/1612上下文無關(guān)文法的形式化定義在描述一個(gè)文法時(shí)，通常只寫出它的規(guī)則出現(xiàn)在規(guī)則左邊的符號(hào)都是變元，其余的
30、符號(hào)都是終結(jié)符，按照慣例，起始變元是第一條規(guī)則左邊的變元2021/9/1613上下文無關(guān)文法舉例例題2.2：
