高級(jí)程序設(shè)計(jì)語言-編譯原理-資料下載頁
2025-08-07 11:08本頁面
【正文】 二義性 ? 形式語言分類 第二章 高級(jí)語言及其語法描述 例 1 已知文法 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 問：此文法是哪種文法？它所描述的語言有何特點(diǎn)？ 習(xí) 題 第二章 高級(jí)語言及其語法描述 [解 ]：由于 A為開始符。 由于 A ? aBbc ? abBc ? abCbcc ? aCbbcc ? aabbcc 語言為： {anbn, n0 } 第二章 高級(jí)語言及其語法描述 例 2 文法 G[N]為： N→D|ND D→0|1|2|3|4|5|6|7|8|9 G[N]的語言是什么？ 解： N ? ND ? NDD.... ? NDDDD...D ? D......D 所以 G[N]的語言是允許 0開頭的非負(fù)整數(shù)。 第二章 高級(jí)語言及其語法描述 例 3 為只包含數(shù)字、加號(hào)和減號(hào)的表達(dá)式，例如 92＋ 5， 31，７等構(gòu)造一個(gè)文法。 解： G[S]: S → S+D|S D|D D → 0|1|2|3|4|5|6|7|8|9 第二章 高級(jí)語言及其語法描述 例 2 文法 G[N]為： N→D|ND D→0|1|2|3|4|5|6|7|8|9 G[N]的語言是什么？ 解： N ? ND ? NDD.... ? NDDDD...D ? D......D 所以 G[N]的語言是允許 0開頭的非負(fù)整數(shù)。 第二章 高級(jí)語言及其語法描述 解：偶數(shù)的組成和特點(diǎn)：可以是一位偶數(shù)，例如 2， 4， 6， 8，可以是多位偶數(shù)，首位不能為 0，末位只能是 0， 2， 4， 6， 8，中間為任意 G(Z): F?A|CND N ? NE|E| ? E ? 0|C D ? 0|A C ? A|B B ? 1|3|5|7|9 A ? 2|4|6|8 例 4 試構(gòu)造文法，該文法可以生成所有不能以 0開頭的偶數(shù)。 第二章 高級(jí)語言及其語法描述 解：奇數(shù)的組成和特點(diǎn)：可以是一位奇數(shù)：例如 1， 3， 5， 7，9，可以是多位奇數(shù)：首位不能為 0，末位只能是 1， 3， 5， 7，9 ，中間為任意。 例 5 試構(gòu)造文法，該文法可以生成所有不能以 0開頭的奇數(shù)。 G(Z): F?B|CNB N ? NE|E|? E ? 0|C C ? A|B B ? 1|3|5|7|9 A ? 2|4|6|8 第二章 高級(jí)語言及其語法描述 解：奇數(shù)的組成和特點(diǎn)：可以是一位奇數(shù)：例如 1， 3， 5， 7，9，可以是多位奇數(shù)：首位不能為 0，末位只能是 1， 3， 5， 7，9 ，中間為任意。 例 5 試構(gòu)造文法，該文法可以生成所有不能以 0開頭的奇數(shù)。 G(Z): F?B|CNB N ? NE|E|? E ? 0|C C ? A|B B ? 1|3|5|7|9 A ? 2|4|6|8 第二章 高級(jí)語言及其語法描述 例 7 證明下述文法 G[〈 表達(dá)式 〉 ]是二義的。 表達(dá)式 ? a|(表達(dá)式 )|表達(dá)式 運(yùn)算符 表達(dá)式 運(yùn)算符 ? +||*|/ 解：可為句子 a+a*a 構(gòu)造兩個(gè)不同的最右推導(dǎo) : 最右推導(dǎo) 1： 〈 表達(dá)式 〉 ? 〈 表達(dá)式 〉〈 運(yùn)算符 〉〈 表達(dá)式 〉 ? 〈 表達(dá)式 〉 〈 運(yùn)算符 〉 a ? 〈 表達(dá)式 〉 * a ? 〈 表達(dá)式 〉〈 運(yùn)算符 〉〈 表達(dá)式 〉 * a ? 〈 表達(dá)式 〉〈 運(yùn)算符 〉 a * a ? 〈 表達(dá)式 〉 + a * a ? a + a * a 第二章 高級(jí)語言及其語法描述 例 7 證明下述文法 G[〈 表達(dá)式 〉 ]是二義的。 表達(dá)式 ? a|(表達(dá)式 )|表達(dá)式 運(yùn)算符 表達(dá)式 運(yùn)算符 ? +||*|/ 解：可為句子 a+a*a 構(gòu)造兩個(gè)不同的最右推導(dǎo) : 最右推導(dǎo) 2： 〈 表達(dá)式 〉 ? 〈 表達(dá)式 〉〈 運(yùn)算符 〉〈 表達(dá)式 〉 ? 〈 表達(dá)式 〉〈 運(yùn)算符 〉〈 表達(dá)式 〉〈 運(yùn)算符 〉〈 表達(dá)式 〉 ? 〈 表達(dá)式 〉〈 運(yùn)算符 〉〈 表達(dá)式 〉〈 運(yùn)算符 〉 a ? 〈 表達(dá)式 〉〈 運(yùn)算符 〉〈 表達(dá)式 〉 * a ? 〈 表達(dá)式 〉〈 運(yùn)算符 〉 a * a ? 〈 表達(dá)式 〉 + a * a ? a + a * a 第二章 高級(jí)語言及其語法描述 例 9 考慮下面上下文無關(guān)文法： S→SS*|SS+|a (1)表明通過此文法如何生成串 aa+a*，并為該串構(gòu)造語法樹。 (2)G[S]的語言是什么？ 解： (1)此文法生成串 aa+a*的最右推導(dǎo)如下 S ? SS* ? SS* ? Sa* ? SS+a* ? Sa+a* ? aa+a* (2)該文法生成的語言是： *和 +的后綴表達(dá)式，即逆波蘭式 第二章 高級(jí)語言及其語法描述 例 10 文法 S→S(S)S| ε (1) 生成的語言是什么？ (2) 該文法是二義的嗎？說明理由。 解： (１ )嵌套的括號(hào) (２ )是二義的，因?yàn)閷?duì)于（）（）可以構(gòu)造兩棵不同的語法樹。 第二章 高級(jí)語言及其語法描述 例 11 給出生成下述語言的上下文無關(guān)文法： （ 1） { anbnambm| n， m=0} （ 2） { 1n0m1m0n| n， m=0} （ 3） {WaWr|W 屬于 {0|1}*， Wr 表示 Wa的逆 } 解： （１） S→AA A→aAb| ε （２） S→1S0|A A→0A1| ε （３） S→0S0|1S1|0|1| ε 第二章 高級(jí)語言及其語法描述 例 12 給出生成下述語言的三型文法： (1){an|n=0 } (2){anbm|n,m=1 } (3){anbmck|n,m,k=0 } 解： (1) S→aS| ε (2) S→aA A→aA|B B→bB|b (3) A→aA|B B→bB|C C→cC| ε 第二章 高級(jí)語言及其語法描述 第二章 高級(jí)語言及其語法描述 第二章 高級(jí)語言及其語法描述 第二章 高級(jí)語言及其語法描述 句型 第二章 高級(jí)語言及其語法描述 第二章 高級(jí)語言及其語法描述 作業(yè) ? 課本 P36： 7
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1