編譯原理第二章高級(jí)語言及其語法描述-資料下載頁
2025-05-13 04:28本頁面
【正文】 → ?例外，但 S不得出現(xiàn)在任何產(chǎn)生式的右部。 2. G為任何產(chǎn)生式為 A→β ， A∈ VN ， β∈ （ VN∪ VT） ＊ 。 3. G的任何產(chǎn)生式為 (1) A→αB 或 A→α (2) A→Bα 或 A→α 其中 α∈ VT＊ ， A、 B∈ VN。 (1)式右線性文法； (2)式左線 性文法 ? 文法說明： – 1型文法也稱上 、 下文有關(guān)文法 。 這種文法意味著 ，對(duì)非終結(jié)符進(jìn)行替換時(shí)務(wù)必考慮上下文 ， 并且 ，一般不允許替換成空串 ε。 例如 ， 假若 αAβ→αγβ 是1型文 G的一個(gè)產(chǎn)生式 ， α和 β都不空 ， 則非終結(jié)符A只有在 α和 β這樣的一個(gè)上下文環(huán)境中才可以把它替換為 γ。 – 2型文法也稱上 、 下文無關(guān)文法 。 – 3型文法也稱線性文法 ， 或稱為正規(guī)文法 。 文法應(yīng)用舉例 ? 例 1：判斷文法 S→aSb|ab 的類型，并推斷文法語言。 – 由于 S →aSb|ab 與 a、 b無關(guān)，則是上下文無關(guān)文法。 – S →aSb|ab ，有 S?aSb ?aaSbb … ?anSbn， 文法對(duì)應(yīng)的語言為： L2={anbn|n?1} ? [例 2]現(xiàn)有文法如下： 語句 → if條件 then 語句 | if條件 then 語句 else 語句 | 其它語句 試判斷文法的二義性和類型？ – 由文法可以推導(dǎo)出下面的二義性句型 If C1 then if C2 then S1 else S2 ， 其中 else 不知與那 個(gè) then 匹配 ， 所以它是二義性文法。 – 由于替換僅在右側(cè)進(jìn)行，且不考慮條件，所以它上下、文無關(guān)的正規(guī)文法。 ? 某些語言是上 、 下文無關(guān)語言 、 但有些語言卻無法用上 、 下無關(guān)文法描述 。 ? 有些語言即不是一個(gè)上 、 下文無關(guān)語言 ，但也不是一個(gè)上下有關(guān)語言 。 ? 作業(yè)：第 6題、第 8題。
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1