高級語言及其語法描述-資料下載頁
2025-10-07 06:44本頁面
【正文】 i i 圖 2 。 3 語法樹 圖 2。 2與圖 2。 3的不同之處在于從第二代三代過渡開始。對于前者，我們選用規(guī)則 E→E+E, 而后者我們選用 E→E*E 。這里不是同代兄弟生兒子的先后次序的不同而是生什么兒子的不同，后面的這個不同是本質(zhì)上的的差異。這意味著我們可以用兩種完全不同的辦法產(chǎn)生同一個句子。 第二章 高級語言及其語法描述 如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是二義的。也就是說，若一個文法存在某個句子，它有兩個不同的最左（最右 )推導(dǎo)，則這個文法是法是 二義的 。 最后，作為描述程序語言的上下文無關(guān)文法，我們對它有幾點限制。 （ 1）文法中不含任何下面形式的產(chǎn)生式： P→P 因為這種產(chǎn)生式除了產(chǎn)生二義性外沒有任何用處。 第二章 高級語言及其語法描述 （ 2） 每個非終結(jié)符 P必須有用處。這一方面意味著，必須存在含 P的句型；也就是，從開始符號出發(fā)，存在推導(dǎo) S?*?P?. 另一方面意味著，必須存在終結(jié)符串??VT*,使得 P?+?；也就是，對于 P不存在永不終結(jié)的回路。 我們以后所討論的文法均假定滿足上述兩條件。 第二章 高級語言及其語法描述 形式語言鳥瞰： 喬姆斯基把文法分為四種類型即 0型、1型、 2型、 3型。 0行強于 1型， 1行強于 2型， 2型強于 3型。這幾文法的差別在于對產(chǎn)生式施加不同的限制。 我們說 G=(VT ,VN ,S ,?) 是一個 0型文法 ，如果它的每個產(chǎn)生式 ???是這樣的結(jié)構(gòu) ??(VN?VT)* 且至少有一個非終結(jié)符，而 ??(VN?VT)* 。 0型文法也稱短語文法。 第二章 高級語言及其語法描述 如果對 0型文法分別施加以下的第 i條限制，則我們就得到第 i型文法 : (1)G的任何產(chǎn)生式 ??? 均滿足 |?|≤ | ?|（其中 |?|和 |?|分別為 ?和 ?的長度；僅 S??例外，但 S不得出現(xiàn)在任何產(chǎn)生式的右部。 (2） G的任何產(chǎn)生式為 A??, A?VN , ??(VN? VT)* 。 (3) G的任何產(chǎn)生式為 A??B或 A??，其中??VT*， A、 B ? VN 。 其中 1型文法也稱上下文有關(guān)文法。這種文法意味著，對非終結(jié)符進行替換式務(wù)必考慮上下文并且一般不允許替換成空串 ?。 第二章 高級語言及其語法描述 2型文法也稱上下文無關(guān)文法，注意其語言定義： G的任何產(chǎn)生式為 A→ β ， A∈V N， β ∈ （ VN∪V T)* 表明凡出現(xiàn)在產(chǎn)生式左邊的符號都是非終結(jié)符。 3型文法也稱右線性文法。 3型文法還有另一種形式，稱左線性文法：一個文法 G為左線性文法，如果 G的任何產(chǎn)生式為 A→B ? 或 A→ ? ，其中 ?∈ VT* , A、 B ∈ V N 由于 3型文法等價于正規(guī)式所以也稱正規(guī)文法。 第二章 高級語言及其語法描述 例題與習(xí)題解答 [例 ]： 試構(gòu)造生成語言 L={anbnci|n?1, i ?0}的文法 解： G(Z): Z?AB A ?aAb|ab B ?cB|? [例 2。 2]： 已知語言 L={anbbn| n ?1}, 寫出產(chǎn)生 L的文法。 第二章 高級語言及其語法描述 [解 ]： G[S]: S ?aAb A ?aAb|b [例 2。 3]： 已知文法 G=({A,B,C},{a,b,c},A,P) 其中產(chǎn)生式 P由以下組成： A ?abc A ?aBbc Bb ?bB Bc ?Cbcc bC ?Cb aC ?aaB aC ?aa 問：此文法表式的語言是什么？ 第二章 高級語言及其語法描述 [解 ]：由于 A為開始符。 由于 A?aBbc ?abBc ?abCbcc ?aCbbcc ?aabbcc 語言為： {anbn, n0 } [例 2。 4]： 試構(gòu)造語言 L={anbnci | n=1, i=0}的文法。 [解 ]： G(Z): Z ?AB A ?aAb|ab B ?cB|? 第二章 高級語言及其語法描述 [例 2。 5]： 試寫一文法，使其描述的語言L(G) 是能被 5整除的整數(shù)集合。 解： G(Z): Z ?(+| )A(0|5) A ?0|1|2|3|4|5|6|7|8|9|AA [例 2。 6]： 已知語言 L={x | x?{a,b,c}*,且 x重復(fù)排列是對稱的（ aabcbaa,aabbaa,等 ) 寫出該語言的文法。 解： G(Z)： Z ?aZa|bZb|cZc|a|b|c|?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1