编译原理第三章.ppt

第3章文法和语言 数计学院宋彩芳 第3章文法和语言 程序设计语言 记号系统 语法 是语言结构的定义 指一组规则 用它可以形成和产生一个合适的程序 描述工具是上下文无关文法 语义 是描述了语言的含义 分为静态语义和动态语义 静态语义是一系列限定规则 并确定哪些合乎语法的程序是合适的 动态语义也称运行语义和执行语义 表明程序要做些什么 要计算什么 语用 语用则是从使用的角度去描述语言 第3章文法和语言 例如赋值语句s 2 3 1416 r r h 的非形式化的描述为 语法 赋值语句由一个变量 后随一个赋值号 再在其后面跟一个表达式构成语义 首先计算语句右部表达式的值 然后把所得结果送给左部变量中 语用 赋值语句可用来计算和保存表达式的值 第3章文法和语言 非形式化描述 不够清晰和准确形式化描述用一整套带有严格规定的符号体系来描述问题的方法 程序语言语法的形式描述是很好用的 形式语言理论 语义的形式描述不那磨好用 但它推动语言理论的发展 形式语义学 第3章文法和语言 3 1文法的直观概念3 2符号和符号串3 3文法和语言的形式定义3 4文法的类型3 5上下文无关文法及语法树3 6句型的分析3 7有关文法实用中的一些说明3 8典型例题及解答 3 1文法的直观概念 文法 形式语言理论的基本概念之一 阐明语法的一个工具是文法 直观定义 定义一系列规则以判别句子结构合法与否的依据 这些规则被看作元语言 只涉及汉语句子的结构描述 3 1文法的直观概念 汉语句子的定义规则 我 你 他 王明 大学生 工人 英语 是 学习 3 1文法的直观概念 我是大学生 的动作过程 我 我 我是 我是 我是大学生 第3章文法和语言 3 1文法的直观概念3 2符号和符号串3 3文法和语言的形式定义3 4文法的类型3 5上下文无关文法及语法树3 6句型的分析3 7有关文法实用中的一些说明3 8典型例题及解答 3 2符号和符号串 元素的非空有穷集合 例如 a b c 1 字母表 根据字母表的定义 是字母表 它由a b c三个元素组成 3 2符号和符号串 是一个字母表 由0 1两个元素组成 注意 例如 0 1 2 字母表中的元素 可以是字母 数字或其他符号 1 字母表中至少包含一个元素 3 2符号和符号串 字母表中的元素称为符号或称为字符 例如 前述例子中 2 符号 字符 a b c是字母表 中的符号 0 1是字母表 中的符号 3 2符号和符号串 例如 设有字母表 a b c 符号的有穷序列称为符号串 符号串总是建立在某个特定字母表上的且只由字母表上的有穷多个符号组成 则有符号串a b ab ba cba abc 3 符号串 字 3 2符号和符号串 说明 符号串中符号的顺序是很重要的 不包含任何符号的符号串 称为空符号串 用 表示 ab和ba是字母表 上的两个不同的符号串 空符号串由0个符号组成 其长度 0 3 2符号串的运算 1 符号串的头尾 固有头和固有尾 例如 z xy x是z的头 y是z的尾如果x是非空的 那么y是固有尾如果y是非空的 那么x是固有头分析 z abc的头 尾 固有头 固有尾 省略写法 z x z x z x 3 2符号串的运算 设x和y是符号串 则串xy称为它们的连结 则XY ABC10A YX 10AABC 注意 对任意一个符号串x 我们有 x x x 2 符号串的连结 例如 设X ABC Y 10A 3 2符号串的运算 3 符号串的方幂 设x是符号串 则x的幂运算定义为 x0 x1 x x2 xx x3 xxx 注意 x0 1 3 2符号串的运算 例如 设x abc则 x0 x1 abc x2 xx abcabc 3 2符号串的运算 符号串的集合若集合A中的一切元素都是某字母表上的符号串 则称A为该字母表上的符号串集合 2 2符号串的运算 4 集合的乘积 设A和B是符号串的集合 则A和B的乘积定义为 集合的乘积是满足于x A y B的所有符号串xy所构成的集合 AB xy x A y B A A A 2 2符号串的运算 例如 设A a b B c d 则AB ac ad bc bd 由于对任意的符号串x 总有 x x x 所以 对任意集合A 我们有 2 2符号串的运算 特别指出的是 是符号串 不是集合 而 表示由空符号串 所组成的集合 但这样的集合不是空集合 2 2符号串的运算 4 集合的幂运算 设A是符号串的集合 则集合A的幂运算定义为 A0 A1 A A2 AA 2 2符号串的运算 例如 设A a b 则 A0 A1 A a b A2 AA aa ab ba bb A3 AAA A2A aaa aab aba abb baa bab bba bbb 2 2符号串的运算 5 集合A的正闭包A 与闭包A 设A是符号串的集合 则A的正闭包A 和A的闭包A 的定义为 A A1 A2 An A A0 A1 A2 An A 2 2符号串的运算 可见 集合A的正闭包表示A上元素a b构成的所有符号串的集合 集合A的闭包比集合A的正闭包多含一个空符号串 例如 设A a b 则 A a b aa ab ba bb aaa aab A a b aa ab ba bb aaa aab 3 2符号和符号串 字母表 符号集 符号串符号串的头尾 固有头和固有尾符号串的连接符号串的方幂符号串集合符号串集合的乘积符号串集合的方幂符号串集合的闭包 第3章文法和语言 3 1文法的直观概念3 2符号和符号串3 3文法和语言的形式定义3 4文法的类型3 5上下文无关文法及语法树3 6句型的分析3 7有关文法实用中的一些说明3 8典型例题及解答 第3 3章文法和语言的形式定义 如何来描述一种语言 如果语言是有穷的 只含有有穷多个句子 可以将句子逐一列出来表示如果语言是无穷的 找出语言的有穷表示 语言的有穷表示有两个途经 生成方式 文法 语言中的每个句子可以用严格定义的规则来构造 识别方式 自动机 用一个过程 当输入的一任意串属于语言时 该过程经有限次计算后就会停止并回答 是 若不属于 要么能停止并回答 不是 要么永远继续下去 3 3文法和语言的形式定义 均表示字母表A上的一个形式语言 由于这三个语言均是有限符号串的集合 因此 可枚举出其全部句子来表示该语言 例如 设有字母表A a b c 则 L1 a b c L2 a aa ab ac L3 c cc 3 3文法和语言的形式定义 例如 设字母表 0 1 则 1 2 3 0 1 00 10 11 01 000 100 当语言为无穷集合时 用文法来描述语言 3 3文法的形式定义 规则是一个符号与一个符号串的有序对 A 通常写作 A 或A 1 规则也称产生式 规则的作用是告诉我们如何用规则中的符号串生成语言中的序列 3 3文法的形式定义 规则中出现的符号分为两类 一类是终结符号 另一类是非终结符号 非终结符号是出现在规则左部能派生出符号或符号串的那些符号 即每个非终结符号表示一定符号串的集合 用大写字母表示或用尖括号把非终结符号括起来 3 3文法的形式定义 终结符号是不属于非终结符号的那些符号 它是组成语言的基本符号 是一个语言的不可再分的基本符号 通常用小写字母表示 3 3文法的形式定义 规则的非空有穷集合 通常表示成四元组 VN是规则中非终结符号的集合 VT是规则中终结符号的集合 P是文法规则的集合 2 文法 G VN VT P S 3 3文法的形式定义 S是一个非终结符号 称为文法的开始符号或文法的识别符号 它至少要在一条规则中作为左部出现 由它开始 识别出我们所定义的语言 由文法定义可知 文法是对语言结构的定义和描述 文法四大要素中关键是规则的集合 3 3文法的形式定义 将它们缩写为 A 1 2 n A 1 A 2 A n 其中每个 i有时也称为是A的一个候选式 为了书写方便 对于若干个左部相同的规则 如 3 3文法的形式定义 例文法G VN VT P S VN S VT 0 1 P S 0S1 S 01 S为开始符号 例文法G VN VT P S VN 标识符 字母 数字 VT a b c x y z 0 1 9 P a z 0 9 S 3 3文法的形式定义 3 3文法的形式定义 我们约定 第一条规则的左部是开始符号 对文法G不用四元式显示表示 仅只将规则写出 习惯大写字母表示非终结符小写字母表示终结符 1 G S aAbA abA aAbA 2 G S A abA aAbA S aSb 3 G S A ab aAb S aSb 3 3文法的形式定义 直接推导 是文法G的产生式 若有v w满足 v w 其中 V V 则称v直接推导到w 记作v w也称w直接归约到v例 G S 0S1 S 010S1 00S1100S11 000S111000S111 00001111S 0S1 3 3文法的形式定义 推导 VAR BEGINREAD END VARA BEGINREAD END A VARA BEGINREAD END VARA BEGINREAD A END A 3 3文法的形式定义 推导的定义 若存在v w0 w1 wn w n 0 则记为v w 称作v推导出w 或w归约到v若有v w或v w 则记为v w 3 3文法的形式定义 例 G S 0S1 S 010S1 00S1100S11 000S111000S111 00001111S 0S1 00S11 000S111 00001111S 00001111S S00S11 00S11 3 3文法的形式定义 句型有文法G S 若S x 则称x是文法G S 的句型 句子有文法G 若S x 且x VT 则称x是文法G的句子 例 G S 0S1 S 01S 0S1 00S11 000S111 00001111G的句型S 0S1 00S11 000S111 00001111G的句子00001111 01 3 3文法的形式定义 例 G E E E T TT T F FF E aE E T T T F T a T a T F a F F a a F a a a句子 用符号a 和 构成的算术表达式 3 3文法的形式定义 文法生成的 语言的定义 由文法G生成的语言记为L G 它是文法G的一切句子的集合 L G x S x 其中S为文法的开始符号 且x VT 例 G S 0S1 S 01L G 0n1n n 1 例文法G S 1 S aSBE 2 S aBE 3 EB BE 4 aB ab 5 bB bb 6 bE be 7 eE eeL G anbnen n 1 G生成的每个串都在L G 中L G 中的每个串确实能被G生成 文法的等价 若L G1 L G2 则称文法G1和G2是等价的如文法G1 A A DB与G2 S S 0S1等价A DES 01E ABD 0B 1 推导和规则的区别 1 形式上的区别 推导用 表示 规则用 表示 2 对文法G中任何规则A 我们有A 即推导的依据是规则 3 3文法和语言的形式定义 文法的形式定义 规则 产生式 文法定义语言的形式定义 推导 直接推导句型 句子语言定义 上节内容回顾 文法 G VT VN S P 产生式语言 推导句型 句子 第3章文法和语言 3 1文法的直观概念3 2符号和符号串3 3文法和语言的形式定义3 4文法的类型3 5上下文无关文法及语法树3 6句型的分析3 7有关文法实用中的一些说明3 8典型例题及解答 3 4文法的类型 通过对产生式施加不同的限制 Chomsky将文法分为四种类型 0型文法 对任一产生式 都有 VN VT 且至少含有一个非终结符 VN VT 1型文法 对任一产生式 都有 仅仅S 除外2型文法 对任一产生式 都有 VN VN VT 3型文法 任一产生式 的形式都为A aB或A a 其中A VN B VN a VT 文法的类型 因为 递归可枚举 的意思就是存在一个图灵机 它可以将一个文法规则能辨认的所有的字符串从短到长 一个一个不带重复的举出来 那么可以构造另一个图灵机 它一个个枚举可辨认的字符串和输入相比较 如果匹配就返回成功 如果枚举字符串长度大于输入就返回失败 总会停机的 故停机可判定 0型文法就是图灵机停机可判定的边界 0型文法再往上的才是停机不可判定的 文法的类型 例 文法G S S CDAb bAC aCABa aBC bCBBb bBAD aDC aBD bDD bAa bD 1型 上下文有关 文法 文法的类型 例 文法G S S ABA BS 0B SA 1 2型 上下文无关 文法 3型 正规 文法 G S S 0A 1B 0A 0A 1B 0SB 1B 1 0 G I I lTI lT lTT dTT lT d 文法的类型 文法的类型 0型文法 四类文法之间的逐级 包含 关系 3型文法 文法和语言 0型文法产生的语言称为0型语言1型文法或上下文有关文法 CSG 产生的语言称为1型语言或上下文有关语言 CSL 2型文法或上下文无关文法 CFG 产生的语言称为2型语言或上下文无关语言 CFL 3型文法或正则 正规 文法 RG 产生的语言称为3型语言正则 正规 语言 RL 文法和语言 四种文法之间的关系将产生式做进一步限制而定义的 语言之间的关系依次 有不是上下文有关语言的0型语言 有不是上下文无关语言的1型语言 有不是正则语言的上下文无关语言 第3章文法和语言 3 1文法的直观概念3 2符号和符号串3 3文法和语言的形式定义3 4文法的类型3 5上下文无关文法及语法树3 6句型的分析3 7有关文法实用中的一些说明3 8典型例题及解答 上下文无关文法及其语法树 上下文无关文法有足够的能力描述程序设计语言的语法结构 语法树 句型推导的直观表示 G E E iE E E E E E 例 G ifthen ifthenelse 语法树 语法树的定义 设G VN VT P S 若一棵树满足下列4个条件 则此树称作G的语法树 推导树 1 根的标记是S2 每个结点都有一个标记 此标记是V的一个符号3 若一结点n至少有一个它自己除外的子孙 并且有标记A 则肯定A VN4 如果结点n有标记A 其直接子孙结点从左到右的次序是n1 n2 nk 其标记分别为A1 A2 Ak 那么A A1A2 Ak一定是P中的一个产生式语法树的结果 从左到右读出叶子的标记而构成的句型 语法树 给定文法G VN VT P S 对于G的任何句型都能构造与之关联的语法树 推导树 定理 G为上下文无关文法 对于 有S 当且仅当文法G有以 为结果的一棵语法树 推导树 根据推导序列 对每步推导画相应分枝 A S a S b S A a a b a aSbAS aabAS aabbaS aabbaa aAS S 二 如何画出分析树 1 自顶向下 根据归约序列 对每步归约画相应分枝 A S a S b S A a a b a aAa aSbAa aSbbaa aabbaa aAS S 二 如何画出分析树 2 自底向上 语法树 例 G S S aASA SbAA SSS aA ba 句型aabbaa的可能语法树 语法树 句型aabbaa的可能推导序列 S aAS aAa aSbAa aSbbaa aabbaaS aAS aSbAS aabAS aabbaS aabbaaS aAS aSbAS aSbAa aabAa aabbaa 最左 最右 推导 在推导的任何一步 其中 是句型 都是对 中的最左 右 非终结符进行替换 最右推导被称为规范推导 由规范推导所得的句型称为规范句型 语法树 结论 一棵语法树表示了一个句型的种种可能的 但未必是所有的 不同推导过程 包括最左 最右 推导 问题 一个句型是否只对应唯一的一棵语法树呢 一个句型是否只有唯一的一个最左 最右 推导呢 语法树 例 G E E iE E EE E EE E EE EE Eiii EE EiE Eii 句型i i i的两个不同的最左推导 推导1 E E E E E E i E E i i E i i i推导2 E E E i E i E E i i E i i i 二义文法 二义文法 若一个文法存在某个句子对应两棵不同的语法树 则称这个文法是二义的若一个文法存在某个句子有两个不同的最左 右 推导 则称这个文法是二义的 文法二义性的消除 1 不改变文法中原有的语法规则 仅加进一些非形式的语法规定 文法二义性的消除 2 构造一个等价的无二义性文法 即把排除二义性的规则合并到原有文法中 改写原有的文法 例如 对于上例文法G E 将运算符的优先顺序和结合规则 优先于 左结合加到原有文法中 可构造出无二义性文法如下 文法二义性的消除 则句子i i i只有唯一一棵语法树 E E T T T T F F F E i 文法二义性的消除 例2定义某程序语言条件语句的文法G为 试证明该文法是二义性的并消除之 分析该文法的句子ifbifbAelseA对应下面两棵不同的语法树 S ifbS ifbSelseS A 其它语句 文法二义性的消除 所以该文法是二义的 S ifbS ifbSelseS A 句子ifbifbAelseA 文法二义性的消除 消除文法的二义性可采用下面两种方法 不改变已有规则 仅加进一非形式的语法规定 else与前面最接近的不带else的if相对 文法G的句子ifbifbAelse只对应唯一的一棵语法树 消除了二义 文法二义性的消除 2 改写文法G为G S S1 S2 S1 ifbS1elseS1 A S2 ifbS ifbS1elseS2 G S ifbS ifbSelseS A 其它语句 G 文法二义性的消除 这是因为通过分析 得知引起二义性的原因是 if else语句的if后可是if型 因此改写文法时规定 if else之间只能是if else语句或其他语句 文法二义性的消除 S S1 S2 S1 ifbS1elseS1 A S2 ifbS ifbS1elseS2 对改写后的文法 句子ifbifbAelseA只对应唯一的一棵语法树 通常我们只说文法的二义性 而不说语言的二义性 这是因为可能有两个不同的文法G和G 而且其中一个是二义性的 另一个是无二义性的 但却有L G L G 即这两个文法所产生的语言是相同的 文法二义性的消除 应该指出的是文法的二义性和语言的二义性是两个不同的概念 文法二义性的消除 将一个语言说成是二义性的 是指对它不存在无二义性的文法 这样的语言称为先天二义性的语言 例如L aibjck i j或j k且i j k 1 便是这种语言 第3章文法和语言 3 1文法的直观概念3 2符号和符号串3 3文法和语言的形式定义3 4文法的类型3 5上下文无关文法及语法树3 6句型的分析3 7有关文法实用中的一些说明3 8典型例题及解答 上下文无关文法 句型的分析 句型分析就是识别一个符号串是否为某文法的句型 是某个推导的构造过程 在语言的编译实现中 把完成句型分析的程序称为分析程序或识别程序 分析算法又称识别算法 从左到右的分析算法 即总是从左到右地识别输入符号串 首先识别符号串中的最左符号 进而依次识别右边的一个符号 直到分析结束 句型的分析算法分类 分析算法可分为 自上而下分析法 从文法的开始符号出发 反复使用文法的产生式 寻找与输入符号串匹配的推导 或者说 为输入串寻找一个最左推导 自下而上分析法 从输入符号串开始 逐步进行归约 直至归约到文法的开始符号 两种方法反映了两种语法树的构造过程 自上而下方法是从文法符号开始 将它做为语法树的根 向下逐步建立语法树 使语法树的结果正好是输入符号串自下而上方法则是从输入符号串开始 以它做为语法树的结果 自底向上的构造语法树 自上而下的语法分析 例 文法G S cAdA abA a识别输入串w cabd是否为该文法的句子 SSScAdcAdab推导过程 S cAdcAd cabd 自下而上的语法分析 例 文法G S cAdA abA a识别输入串w cabd是否该文法的句子 SAAcabdcabdcabd规约过程构造的推导 cAd cabdS cAd 自上而下的语法分析 1 S cAd 2 A ab 3 A a识别输入串w cad是否为该文法的句子 自下而上的语法分析 cabdcAbdaa不是 可规约串 ab是 可规约串 1 S cAd 2 A ab 3 A a识别输入串w cabd是否为该文法的句子 句型分析的有关问题 1 在自上而下的分析方法中如何选择使用哪个产生式进行推导 假定要被代换的最左非终结符号是B 且有n条规则 B A1 A2 An 那么如何确定用哪个右部去替代B 2 在自下而上的分析方法中如何识别可归约的串 在分析程序工作的每一步 都是从当前串中选择一个子串 将它归约到某个非终结符号 该子串称为 可归约串 短语 直接短语和句柄 短语 令G是一个文法 S是文法的开始符号 假定 是文法G的一个句型 如果有 则称 是句型 相对于非终结符A的短语 且A 直接短语 如有A 则称 是句型 相对于规则AA 的直接短语 短语 直接短语和句柄 注意 短语和直接短语的区别在于第二个条件 直接短语中的第二个条件表示有文法规则A 因此 每个直接短语都是某规则右部 短语 直接短语和句柄 句柄 一个句型的最左直接短语称为该句型的句柄 句柄特征 1 它是直接短语 即某规则右部 2 它具有最左性 短语 直接短语和句柄 注意 短语 直接短语和句柄都是针对某一句型的 都是指句型中的哪些符号串能构成短语和直接短语 离开具体的句型来谈短语 直接短语和句柄是无意义的 短语 直接短语和句柄 例如设有文法G S S A B a b P S 其中P为 求句型baSb的全部短语 直接短语和句柄 S AB A Aa bB B a Sb 短语 直接短语和句柄 对文法 首先建立该句型的推导过程 最左推导 最右推导 分析根据短语定义 可以从句型的推导过程中找出其全部短语 直接短语和句柄 句型baSb 短语 直接短语和句柄 句型baSb中的子串Sb 是 相对于非终结符B 句型baSb的短语 且为直接短语 B Sb 句型本身是 相对于非终结符S 句型baSb的短语 根据最左推导 短语 直接短语和句柄 句型baSb中的子串a 是 相对于非终结符B 句型baSb的短语 且为直接短语 句柄 句型baSb中的子串ba 是 相对于非终结符A 句型baSb的短语 B a 根据最右推导 子树 语法树的子树是由某一结点连同所有分枝组成的部分 简单子树 语法树的简单子树是指只有单层分枝的子树 直观解释 句型的短语 直接短语和句柄 短语 子树的末端结点形成的符号串是相对于子树根的短语 直接短语 简单子树的末端结点形成的符号串是相对于简单子树根的直接短语 句柄 最左简单子树的末端结点形成的符号串是句柄 句型的短语 直接短语和句柄 短语 i i i i i 第一个i 第二个i 第三个i 三个i都是直接短语 第一个i是句柄 注意 i i不是句型的短语 句子i i i 句型的短语 直接短语和句柄 前例对文法G S S A B a b P S 其中P为 可用语法树非常直观地求出句型baSb的全部短语 直接短语和句柄 S AB A Aa bB B a Sb 句型的短语 直接短语和句柄 分析首先根据句型baSb的推导过程画出对应的语法树如下 Sb为句型的相对于B的短语 直接短语 baSb为句型的相对于S的短语 ba为句型的相对于A的短语 a句型的相对于B的短语 直接短语和句柄 S AB bBB baB baSb S AB ASb bBSb baSb 由语法树可知 第3章文法和语言 3 1文法的直观概念3 2符号和符号串3 3文法和语言的形式定义3 4文法的类型3 5上下文无关文法及语法树3 6句型的分析3 7有关文法实用中的一些说明3 8典型例题及解答 文法实用中的一些说明 限制化简文法文法中不含有有害规则和多余规则有害规则 形如U U的产生式 会引起文法的二义性多余规则 指文法中任何句子的推导都不会用到的规则文法中不含有不可到达和不可终止的非终结符1 文法中某些非终结符不在任何规则的右部出现 该非终结符称为不可到达 2 文法中某些非终结符 由它不能推出终结符号串 该非终结符称为不可终止 对于文法G S 为了保证任一非终结符A在句子推导中出现 必须满足如下两个条件 1 A必须在某句型中出现即有S A 其中 属于V 2 必须能够从A推出终结符号串t来即A t 其中t VT 化简文法 例 G S 1 S Be2 B CeD为不可到达3 B AfC为不可终止4 A Ae5 A e6 C Cf7 D f产生式2 6 7 为多余规则应去掉 上下文无关文法中的 规则 上下文无关文法中某些规则可具有形式A 称这种规则为 规则因为 规则会使得有关文法的一些讨论和证明变得复杂 有时会限制这种规则的出现如果语言L有一个有穷的描述 则L1 L 也同样有一个有穷的描述 并且可以证明 若L是上下文有关语言 上下文无关语言或正规语言 则L 和L 分别是上下文有关语言 上下文无关语言和正规语言 第3章文法和语言 3 1文法的直观概念3 2符号和符号串3 3文法和语言的形式定义3 4文法的类型3 5上下文无关文法及语法树3 6句型的分析3 7有关文法实用中的一些说明3 8典型例题及解答 3 8典型例题及解答 文法与语言的转换 例题1 5 9 10判断文法类型 0型 1型 2型 3型 构造句型的推导及语法树 例题6 9判断文法的二义性 例题7 8 10寻找文法一句型的短语 直接短语 句柄 例题11 13 1 设计一个文法定义一个已知的语言 1 文法是一个四元组G VN VT P S 文法四大要素中 关键是一组规则 它定义 或描述 了一个语言的结构 从文法定义可知 文法对于程序设计者来说 文法给出了语言的精确定义和描述 本章小结 2 分析已知语言句子的结构特征 设计出相应的一组规则 但不唯一 4 若语言是无穷集合 设计该语言的文法一定是递归的 本章小结 3 设计的文法必须能定义已知的语言 不能超出或缩小所定义语言的范围 分析根据语言句子的结构特征 设计出相应规则 例1 给出语言L2 anbm m n 1 的文法 P2 S AB L2 ab abb abbb aabb aabbb aabbbb aaabbb aabbbb A aAb ab B bB 本章小结 分析根据语言句子的结构特征 设计出相应规则 例2 给出语言L1 a2n 1 n 0 的文法 P1 A aAa a L1 a aaa aaaaa aaaaaaa aaaaaaaaa 本章小结 本章小结 分析根据语言句子的结构特征 设计出相应规则 例3 给出语言L3 anbmck n m k 0 的文法 P3 A aA bB cC P3 A aA B 或 L3 a aa aaa b bb bbb c cc ccc ab abb bc bcc C cC B bB cC C cC B bB C 本章小结 L4 0 2 4 6 8 10 12 14 16 18 20 22 24 26 例4 写一个文法 使其语言是正偶数的集合 每个偶数不以0开头 P4 N E AE N 0 2 4 6 8 BN 或 分析不以0开头的偶数集合中串的结构特征 A D AD E 0 2 4 6 8 D 1 2 3 9 D 0 1 2 3 9 B 1 2 3 9 B0 P4 本章小结 A 0A1 P S 1S0 A 例5 给出语言L 1n0m1m0n n m 0 的文法 分析根据语言句子的结构特征 设计出相应规则 L 01 0011 10 1100 1010 100110 110100 11001100 本章小结 P S a 0S0 1S1 例6 给出语言L WaWt W 0 1 Wt表示W的逆的文法 分析根据语言句子的结构特征 设计出相应规则 L a 0a0 1a1 01a10 10a01 00a00 11a11 101a101 110a011 100a001 W 0 1 01 10 00 11 101 110 100 111 本章小结 2 已知一个文法 确定该文法所定义的语言 2 给定一个文法 可根据语言和推导定义推导出文法的句子 从而确定出该文法所定义的语言 本章小结 自然语言描述 例如 L x x a b 且x中a b个数相同 式子描述 例如L a2nbb n 0 3 语言可用 本章小结 例1文法G A A a b A bA a A 所生成的语言是什么 分析 A bA bbA bbbA bnA bna L G A bna n 0 本章小结 例2文法G N 为 N ND DD 0 1 2 3 4 5 6 7 8 9 1 G N 所生成的语言是什么 2 给出句子0127的最左 最右推导 本章小结 L G N 0 1 2 9 为可带前导0的正整数 为数字串 最