第四讲
2.3文法构造与文法简化
• 一、如何由语言构造文法 • 例题3、设L3={ω | ω∈(a，b)*且ω中含有相 同个数的a和b}试构造生成L3的文法G3.
• 例4，设L4={ω | ω∈(0,1)*且ω中1的个数为 偶数}试构造生成L4的文法G4.
• 二、文法的简化 • 1、由于同一语言可以用不同的文法来描述，显然 应当选择产生式个数最少，最符合语言特征的来 描述。 • 2、在文法中有些产生式对推导不起作用，要删除 掉 • 如何某个产生式在推导过程中永远不会被用到， 即由开始符号推导，永远推不到的左部的非终结 符。 • 永远导不出终结符串的产生式。 • 形如PP产生式。
• 3、简化步骤： • 查找有无形如PP的产生式，若有则删除； • 若某个产生式在推导过程中永远不会被用 到，删除； • 若某个产生式在推导过程中不能从重导出 终结符，删除。 • 最后，整理所有剩余产生式，就得到简化 的文法。
• • • • • • • • • •
例题1、化简下面的文法 (0)SBe (1)SEc (2)AAe (3)Ae (4)AA (5)BCe (6)BAf (7)CCF (8)Df
• 三、构造为ε产生式的上下文无关文法 • 1、无ε产生式的上下文无关文法要满足条 件： • P中要么不含有ε产生式，要么只有S ε; • 若S ε,则S不出现在任何产生式右部。
• 2、构造无ε产生式