编译原理课程第5讲.ppt

中国科大 温故知新 第三章 语法分析 本章内容 上下文无关文法 自上而下分析和自下而上分析 围绕分析器的自动生成展开 3.1 上下文无关文法 3.1.1 上下文无关文法的定义 正规式来定义一些简单的语言，能表示给定结构的固定次数的重复或者没有指定次数的重复。 例：a (ba)5, a (ba)* 正规式不能用于描述配对或嵌套的结构 例：配对括号串的集合， {wcw | w是a和b的串} 3.1 上下文无关文法 上下文无关文法是四元组（VT , VN , S, P） VT : 终结符集合(非空有限集合，记号名是其同意词) VN : 非终结符集合（非空有限集合, ） S : 开始符号(非终结符) P : 产生式集合， 产生式形式:A ? ? , 例 ( {id, +, *, ?, (, )}, {expr, op}, expr, P ) expr ? expr op expr expr ? (expr) expr ? ? expr expr ? id op ? + op ? * 3.1 上下文无关文法 简化表示方法 3.1 上下文无关文法 例 ( {id, +, *, ?, (, )}, {expr, op}, expr, P ) expr ? expr op expr expr ? (expr) expr ? ? expr expr ? id op ? + op ? * 简化表示 E ? E A E | (E ) | ?E | id A ? + | * 3.1 上下文无关文法 上下文无关文法 E ? E A E | (E ) | ?E | id A ? + | * 3.1 上下文无关文法 3.1.2 推导 把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替。 例 E ? E + E | E * E | (E ) | ? E | id E ? ?E ? ?(E) ? ?(E + E) ? ?(id + E)? ?(id + id) 记号 S ?*?、 S ?+ w 概念 句型、句子、上下文无关语言、等价的文法 3.1 上下文无关文法 E ? E + E | E * E | (E ) | ? E | id E ? ?E ? ?(E) ? ?(E + E) 最左推导 E ? lm ?E ? lm ?(E) ? lm ?(E + E) ? lm ?(id + E) ?lm ?(id + id) 最右推导（规范推导） E ? rm ?E ? rm ?(E) ? rm ?(E + E) ? rm ?(E + id) ?rm ?(id + id) 3.1 上下文无关文法 3.1.3 分析树 3.1 上下文无关文法 3.1.3 二义性 E ? E * E E ? E + E ? id * E ? E * E +E ? id * E + E ? id * E + E ? id * id + E ? id * id + E ? id * id + id ? id * id + id 3.2 语言和文法 上下文无关文法的优点 文法给出了精确的，易于理解的语法说明 自动产生高效的分析器 可以给语言定义出层次结构 以文法为基础的语言的实现便于语言的修改 上下文无关文法的缺点 文法只能描述编程语言的大部分语法 3.2 语言和文法 3.2.1 正规式和上下文无关文法的比较 正规式 (a|b)*ab 文法 A0 ? a A0 | b A0 | a A1 A1 ? b A2 A2 ? ? 3.2 语言和文法 3.2.1 正规式和上下文无关文法的比较 NFA?上下文无关文法 确定终结符集合 为每个状态引入一个非终结符Ai 如果状态i有一个a转换到状态j,引入产生式Ai?aAj,如果i是接受状态，则引入Ai? ? 3.2 语言和文法 3.2.2 分离词法分析器理由 为什么要用正规式定义词法 词法规则非常简单，不必用上下文无关文法。 对于词法记号，正规式描述简洁且易于理解。 从正规式构造出的词法分析器效率高。 3.2 语言和文法 把词法分析从语法分析中分离出来的理由 简化设计 编译器的效率会改进 编译器的可移植性加强 便于编译器前端的模块划分 3.2 语言和文法 3.2.3 验证文法产生的语言 G : S ? (S ) S | ? L(G) = 配对的括号串的集合 3.2 语言和文法 3.2.3 验证文法产生的语言 G : S ? (S ) S | ?