第二章文法和語(yǔ)言的基本知識(shí)(編輯修改稿)
2024-08-28 13:02 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 }, {a, b}, P, A ) P={ A→aa | bb | Aaa | Abb } 對(duì)于文法 G來(lái)說(shuō)，它所產(chǎn)生的有些符號(hào)串，如 aabb， bbaa， …… 不屬于語(yǔ)言 L， 即 設(shè)計(jì)的文法超出了所定義語(yǔ)言的范圍 。 文法的形式定義 P={ A→aa | bb | Aaa | Abb } 文法的形式定義 例 2 試設(shè)計(jì)一個(gè)表示所有 標(biāo)識(shí)符的文法 分析 題意是用 文法定義標(biāo)識(shí)符，必須確定 P中規(guī)則。為了設(shè)計(jì)出一組規(guī)則， 首先應(yīng)搞清楚集合中串的結(jié)構(gòu)特征 。 文法的形式定義 用 I代表標(biāo)識(shí)符； L代表字母；D代表數(shù)字 。 則定義標(biāo)識(shí)符的文法為： 字母 字母或數(shù)字串 標(biāo)識(shí)符的結(jié)構(gòu)可用下圖表示 : 文法的形式定義 G=(VN， VT， P， S) 其中： VN={I, L, D} VT={a,b,c, … x,y,z,0,1,2,… ,9} P={ I→L S=I L→a | b | c | … | x | y | z D→0 | 1 | 2 | 3 | … | 9 } | I L | I D 文法的形式定義 若將定義標(biāo)識(shí)符的文法設(shè)計(jì)成： 其中 VN， VT ， S 同上 G=(VN， VT， P， S ) P={ I→L | I D L→a | b | c | … |x|y|z D→0 | 1 | 2 | 3 | … |9 } 文法的形式定義 該文法不能定義 ab， abc … 僅由字母串組成的標(biāo)識(shí)符， 縮小了所定義語(yǔ)言的范圍。 P={ I→L | I D L→a | b | c | … |x|y|z D→0 | 1 | 2 | 3 | … |9 } 文法的形式定義 用 I代表標(biāo)識(shí)符； L代表字母；D代表數(shù)字； T代表字母數(shù)字串；則 定義標(biāo)識(shí)符的文法還可寫(xiě)為： 字母 字母或數(shù)字串 文法的形式定義 P: I→L | LT T→L | D | LT | DT L→a | b | c | … |x|y|z D→0 | 1 | 2 | 3 | … | 9 字母 字母或數(shù)字串 定義標(biāo)識(shí)符的文法比較 P: I→L | LT T→L | D | LT | DT L→a | b | c | … |x|y|z D→0 | 1 | 2 | 3 | … | 9 P={ I→L L→a | b | c | … | x | y | z D→0 | 1 | 2 | 3 | … | 9 } | I L | I D 文法的形式定義 例 3 用文法定義一個(gè)含＋、 *的算術(shù)表達(dá)式，定義用下述自然語(yǔ)言描述： 變量是一個(gè)表達(dá)式； 若 E1和 E2是算術(shù)表達(dá)式 , 則 E1＋ E E1*E (E1) 也是算術(shù)表達(dá)式。 文法的形式定義 分析 算術(shù)表達(dá)式的定義用自然語(yǔ)言描述，這是對(duì)算術(shù)表達(dá)式的非形式定義， 題意用文法來(lái)定義算術(shù)表達(dá)式，即是用形式化的 方法定義表達(dá)式。定義算術(shù)表達(dá)式的文法為： G=({E},{ i, +, *, (, ) }, P, E ) 其中 P為： E→i | E+E | E *E | (E) 文法的形式定義 P為： E→i | E+E | E *E | (E) { i, i+i, i*i, i+i*i, (i+i), … } 注意：是符號(hào)串的集合 文法的形式定義 例 4 設(shè)字母表 Σ={ a, b } , 試設(shè)計(jì)一個(gè)文法，描述語(yǔ)言 L={ abna | n≥0 } 分析 該 語(yǔ)言中串的結(jié)構(gòu)特征 是 當(dāng) n＝ 1 L={ aba } …… L={ aa, aba, abba, …… } 當(dāng) n＝ 2 L={ abba } 當(dāng) n＝ 0 L={ aa } (b0=ε) 文法的形式定義 所以 定義語(yǔ)言的文法為： G=( {A, B}, {a, b}, P, A ) P={ A→aBa B→Bb | ε } L={ aa, aba, abba, …… } 文法的形式定義 例 5 設(shè)字母表 ∑={ (, ) } ,試設(shè)計(jì)一個(gè)文法描述語(yǔ)言 L={ (n )n | n≥0} 分析 該 語(yǔ)言中串的結(jié)構(gòu)特征 是 當(dāng) n=0 L={ ε } 注 : (0 )0= ε 當(dāng) n=1 L={ ( ) } 當(dāng) n=2 L={ (( )) } …… L={ ε, ( ), (( )), ((( ))), … } 文法的形式定義 P: S→ ε | ( S ) 所以 定義語(yǔ)言的文法為： L={ (n )n | n≥0} 語(yǔ)言的形式定義 1. 直接推導(dǎo) 令 G是一文法，我們稱 xAy直接推導(dǎo)出 xαy ， 即 xAy?xαy 僅 A→ α 是 G 的一條規(guī)則 , 且 x, y?(VN∪ VT)*。 也就是說(shuō)從符號(hào)串 xAy 直接推導(dǎo)出 xαy 僅使用一次規(guī)則 。 語(yǔ)言的形式定義 例如，設(shè)有文法 G[S]: S?01 使用規(guī)則 S?01 此時(shí) x＝ ?， y＝ ? P為： S→ 0 1 | 0 S 1 有如下直接推導(dǎo)： S?0S1 使用規(guī)則 S?0S1 此時(shí) x＝ ?， y＝ ? 語(yǔ)言的形式定義 0S1?0011 使用規(guī)則 S?01
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1