编译原理ch2剖析.ppt

* 华东师大计算机科学技术系 * 对文法的二义性讨论（续） 对二义性文法所产生的语言，有的可找到等价的无二义性文法，因此只说文法的二义性，而不说语言的二义性。当然存在这样的语言，不存在它们的无二义性文法。例如：L={aibjck|i=j或j=k,i,j,k?1}。 文法的二义性是不可判定的，即不存在一种算法能在有限步内判定该文法是否是二义性的。 通常的做法是：找出无二义性文法的一个充分条件，即满足条件的一定是无二义性文法 。 * 华东师大计算机科学技术系 * 形式语言分类 2.5 形式语言分类 1956年 Chomsky将文法分成四类：0型、1型、2型和3型 文法G＝（VT，VN，P，S） VN∪VT ＝ V 、 VN∩VT＝φ P中产生式的一般形式是α→β，α?V+,α至少含有一个非终结符，β? V*，β可以是空串。 称文法G为 0型文法（短语结构文法） * 华东师大计算机科学技术系 * 形式语言分类 在0型文法的基础上，再规定：|α|=|β| ∵ α中至少含有一个非终结符 ? β不能为? 称文法G为1型文法（上下文有关文法） 等价定义： wαz→wβz w,z ? V* α? VN ，β? V＋ * 华东师大计算机科学技术系 * 形式语言分类 在0型文法的基础上，再规定： A→α，其中A?VN，α?V* 称文法是2型文法（上下文无关文法） 任何含有U→ε的产生式（称为ε产生式）的文法不是1型文法。但是含有ε产生式的2型文法可以转化为不含ε产生式的2型文法，转化前后的两个文法所生成的语言至多相差一个ε。 * 华东师大计算机科学技术系 * 例1：试将如下的含有?产生式的上下文无关文法 （2型文法）G[S]转换成等价的不含?产生式的 上下文无关文法。 ① S?aAS ② S?b ③ A?cS ④ A?? 解：引入非终结符AN与AY,AN表示不可空， 而AY表示可空。随后消除可空的产生式以及 在产生式的右部去除非终结符AY即可，因此 G[S]可等价表示为： ① S?aANS ①’ S?aAYS ② S?b ③ AN?cS ④ AY?? * 华东师大计算机科学技术系 * 最后得到等价的无?产生式的文法G1[S]为： ①S?aANS ②S?aS ③S?b ④AN?cS 注意：两文法不同，但等价！ ∵ 语言相同。 问题：什么情况下转换前后的二个文法的语言 会 相差?呢？ * 华东师大计算机科学技术系 * 在2型文法的基础上，再规定： 产生式形式是A→x，A→xB， A,B?VN，x?VT* 则称文法是右线性文法。 若规定： x?VT 即A→a，A→bB， A,B?VN，a,b?VT 则称文法是3型文法（正则文法）。 正则文法也可以是左线性文法的特例。 适当地引入新的非终结符可以把一个右线性文法转换为等价的正则文法。 * 华东师大计算机科学技术系 * 例2：试将如下文法G[S]转换为等价的正则文法（3型文法）： ①S?aA ②S?A ③A?abbS ④A?cA ⑤A?a 解：按正则文法的定义，只需对产生式②、③进行等价变换。对产生式③用 A?abbS bbS?bbS bS?bS 来替代。 * 华东师大计算机科学技术系 * 对产生式②则用 S?abbS S?cA S?a 来替代。 因此与G[S]等价的正则文法G1[S]为： S?aA|abbS|cA|a A?abbS|cA|a bbS?bbS bS?bS 其中bbS,bS是新引入的非终结符。 * 华东师大计算机科学技术系 * 实用限制 文法的实用限制 从实用的角度一般规定： 文法中不含任何如下形式的产生式：U→U。 U是可达的，即从开始符号S出发，存在推导S?*αUβ, α、β?V* U是有用的，即存在终结符号串γ?VT*，使得U?*γ。 * 华东师大计算机科学技术系 * 文法与模型 文法与模型 每一类文法都对应数学模型（识别系统）——自动机。 有限状态自动机 3型文法 下推自动机 2型文法 线性界限图灵机 1型文法 图灵机（Turing） 0型文法 编译程序的词法分析程序使用3型文法及其数学模型有限状态自动机。 在句法分析中使用2型文法及其数学模型下推自动机。 * 华东师大计算机科学技术系 * 习题 P30 习题2 2.5 2.6 2.8 2.9 2.11 补充题 考察如下的文法G[S]： S→abcdA A→a 试将其转换成等价的正则文法。 * 华东师大计算机科学