第三章文法和語(yǔ)言-在線瀏覽
2024-09-11 12:51本頁(yè)面
【正文】 正閉包表示為 A+ ， 集合 A 的閉包表示為 A* ， A UA UA UA A K1K32 1 U ?? ????? A UA UA UUA A A K0K32 10* U ??????盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 167。 ?V=VN∪ VT，稱為文法 G的字母表（字匯表） 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?例 文法 G=（ VN， VT， P， S），其中 VN = { S }， VT ={ 0, 1 }， P={ S 0S1, S 01 } 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?例 文法 G=（ VN， VT， P， S），其中 ?VN ={標(biāo)識(shí)符，字母，數(shù)字 } ?VT ={a,b,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í)符 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?很多時(shí)候，不用將文法 G的四元組顯式地表示出來(lái)，而 只將產(chǎn)生式寫出 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?一般約定： ?第一條產(chǎn)生式的左部是識(shí)別符 ?用尖括號(hào)括起來(lái)的是非終結(jié)符（或者用大寫字母表示） ?不用尖括號(hào)括起來(lái)的是終結(jié)符（或者用小寫字母表示） ?將 G也寫成 G[S]，其中 S是識(shí)別符 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?推導(dǎo)： 定義 V*中的符號(hào)之間的關(guān)系： ?直接推導(dǎo)： ?長(zhǎng)度為 n(n≥1)的推導(dǎo)： ?長(zhǎng)度為 n(n ≥0)的推導(dǎo)： * + 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?定義 ： 文法 G＝（ VN， VT， P， S）， α β是一條 規(guī)則， γ和 δ是 V*中的任意符號(hào)，若有符號(hào)串 v， w滿 足： v=γαδ， w= γβδ， 則稱 v直接推導(dǎo)到 w， v w， 或 w直接歸約到 v ?例： G： S 0S1， S 01 S 0S1 00S11 000S111 00001111 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?定義 ： 如果存在直接推導(dǎo)的序列： v=w0 w1 w2… wn=w (n0) 則稱 v推導(dǎo)出 w（推導(dǎo)長(zhǎng)度為 n），或稱 w歸約到 V， 記作 + 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?定義 ： 若有 v w，或 v=w，則記作： + * 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?定義 ： 若有 S x，則稱 x是文法 G[S]的 句型 ，若 x僅 由終結(jié)符組成，則稱 x為 G[S]的 句子 * 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?定義 ： 文法 G所產(chǎn)生的語(yǔ)言定義為集合 L(G)=｛ x|S x，其中 S為文法識(shí)別符號(hào)，且 x∈ VT*｝ ?文法描述的語(yǔ)言是該文法一切句子的集合 ?例： G： S 0S1， S 01 L(G)={0n1n|n≥1} * 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 例 文法文法 G[S]： （ 1） S aSBE （ 2） S aBE （ 3） EB BE （ 4） aB ab （ 5） bB bb （ 6） bE be （ 7） eE ee L（ G） ={ anbnen | n≥1 } 思考： a4b4e4怎么推導(dǎo)？ 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?定義 ： 若 L(G1)＝ L(G2)，則稱文法 G1和 G2是等價(jià)的 ?例如文法 G[A]： ?A 0R ?A 01 ?R A1 和文法 G[S]： ? S 0S1 ? S 01 ?等價(jià) L(G)={0n1n|n≥1} 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 167。 上下文無(wú)關(guān)文法及其語(yǔ)法樹 ?上下文無(wú)關(guān)文法有足夠的能力描述現(xiàn)今程序設(shè)計(jì)語(yǔ)言的 語(yǔ)法結(jié)構(gòu)，比如描述算術(shù)表達(dá)式、描述各種語(yǔ)句等 ?例 ： 文法 G=({E},{+,*,i,(,)},P,E)其中 P為： E i E E+E E E*E E (E) ?條件語(yǔ)句 if條件 then語(yǔ)句 | if條件 then語(yǔ)句 else 語(yǔ)句 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?給定文法 G=（ VN， VT， P， S），對(duì)于 G的任何句型都 能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹（推導(dǎo)樹、語(yǔ)法分析樹、分 析樹）。在形式語(yǔ)言中，最右推導(dǎo)被稱為 規(guī)范推導(dǎo) ，由規(guī)范推導(dǎo)所得的句型稱為 規(guī)范句型 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ? 例： G[E]: E i E E+E E E*E E (E) 句型 i*i+i 的兩個(gè)： 推導(dǎo) 1： E ? E+E ? E*E+E ? i*E+E ? i*i+E ? i*i+i 推導(dǎo) 2： E ? E*E ? i*E ? i*E+E ? i*i+E ?i*i+i ?一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹？一個(gè)句型是否只 有唯一的一個(gè)最左（最右）推導(dǎo)？ 不是 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 圖 推導(dǎo) 1的語(yǔ)法樹 圖 推導(dǎo) 2的語(yǔ)法樹 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1