【正文】 G4 = ( {S,A}, {a}, {S?aA|a, A?aS}, S ) 產(chǎn)生，即 L(G3) = L(G4) = L 例如，由奇數(shù)個(gè) a的符號(hào)串構(gòu)成的語(yǔ)言 L可由文法 G3 = ( {S}, {a}, {S?aSa|a}, S ) 或 G4 = ( {S,A}, {a}, {S?aA|a, A?aS}, S ) 產(chǎn)生，即 L(G3) = L(G4) = L )()(,212121GLGLGGGG?當(dāng)且僅當(dāng)?shù)葍r(jià)的是和稱是兩個(gè)文法和設(shè)定義例 設(shè) ?={a,b}, 則產(chǎn)生語(yǔ)言 A的文法如下： (1) A→aBa B→b|Bb (2) A→aBa B→b|bB (3) A→aB B→ba|bB (4) A→aB B→bC C→bC|a }1{ ?? naabA n。則稱為長(zhǎng)度為對(duì)于步推導(dǎo)稱為對(duì)于情況使上的符號(hào)串序列存在或如果產(chǎn)生的推導(dǎo)是符號(hào)串，稱上的兩個(gè)是為一文法設(shè)定義??。如 名詞 、 動(dòng)詞 、 冠詞 的定義規(guī)則可簡(jiǎn)記為： ? 名詞 ::= monkey | banana ? 動(dòng)詞 ::= eat | has ? 冠詞 ::= the | a 語(yǔ)法規(guī)則及其產(chǎn)生的語(yǔ)言 ? 前面的語(yǔ)法規(guī)則可以產(chǎn)生 16個(gè)不同的句子， 由這 16個(gè)句子組成的集合，就是該規(guī)則所定義（或所產(chǎn)生）的 語(yǔ)言 。 注意，一般說(shuō)來(lái)， xy 不等于 yx； 但 ?x = x? = x 方冪 符號(hào)串 x與其自身的 n1次連接稱為 x 的 n 次方冪，記為： nx????? ?011:,......3,2xnxxxxx nn我們約定這里即 符號(hào)串集合的和與積 設(shè) A， B為兩個(gè)符號(hào)串集合，定義： 和： A+B（或 A∪ B） ={w | w?A，或 w?B } 例如，若 A={a,b,c}， B={00,11}，則 A+B={a,b,c,00,11}。 用 BNF（ BackusNaurFormal（范式））對(duì)ALGOL語(yǔ)言進(jìn)行了描述。 ? 此處所說(shuō)的? 遍 ? ,是指對(duì)源程序或其內(nèi)部表示從頭到尾掃視一次 ,并進(jìn)行有關(guān)的加工處理工作。 ? 所以，有人又將語(yǔ)言定義為：? 某一字母表上符號(hào)串（句子）的集合 ? ? 此定義仍需精確化。記為： |aba|=3 空串 不含任何符號(hào)的符號(hào)串，記為 ? 。 ? 每次替換稱為一步（ 直接 ） 推導(dǎo) ，并用符號(hào)? ??表示。另外，在不強(qiáng)調(diào)開(kāi)始符號(hào) S 時(shí)，可將文法 G[S] 簡(jiǎn)記為 G 。 則稱為遞歸文法。稱為則是文法設(shè)定義TTTGVGLVGLGVwwSwGLSG)(,)(},|{)(,][***????例 ： G[A]: A → Bb B → a 例 ： G[S]: S → aB | Bb B → a | b }{])[( abAGL ?},{])[( bbabaaSGL ? 我們看到， L(G[A])和 L(G[S])是由有限的句子組成的。對(duì)于上例有： VT = { monkey, banana, eat, has, the, a } ? ???????TNTNNTNTNVVVVVVSPVVSPVVSGSG??且詞匯表字匯表稱為法的開(kāi)始符號(hào)。 ? ? ::=” 是用于定義語(yǔ)法結(jié)構(gòu)的符號(hào)，其含義（并讀作）? 定義為 ?。 c a b b c a a S A B F 文法