第三章语法分析 词法 记号 源程序 分析器 分析、 前端的 中间 分析器 取下一个 其余部分 表示 记号 符号表 ·本章内容 一上下文无关文法 一自上而下分析和自下而上分析 -围绕分析器的自动生成展开
第三章 语法分析 • 本章内容 – 上下文无关文法 – 自上而下分析和自下而上分析 – 围绕分析器的自动生成展开 词 法 分析器 记 号 取下一个 记号 源程序 分析 树 前端的 其余部分 分析器 中间 表示 符号表
3.1上下文无关文法 3.1.1上下文无关文法的定义 正规式能定义一些简单的语言，能表示给定结构 的固定次数的重复或者没有指定次数的重复 例：a(ba)5,a(ba 正规式不能用于描述配对或嵌套的结构 例1：配对括号串的集合 例2：{wcww是a和b的串}
3.1 上下文无关文法 3.1.1 上下文无关文法的定义 –正规式能定义一些简单的语言，能表示给定结构 的固定次数的重复或者没有指定次数的重复 例：a (ba) 5 , a (ba)* –正规式不能用于描述配对或嵌套的结构 例1：配对括号串的集合 例2：{wcw | w是a和b的串}
3.1上下文无关文法 ·上下文无关文法是四元组(V,V,S,P) V: 终结符集合 VN 非终结符集合 S: 开始符号，非终结符中的一个 产生式集合，产生式形式：A→a 例({id,+,*,-,()},{xpr,0p以，xpr,P) eXpr→expr op expr expr→(expr) eXpr→-xpI expr -id 0p→+ 0p→*
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上下文无关文法 ·简化表示 expr->expr op expr (expr)-expr id 0p→+|* 简化表示 E→EAE|(E)|-Elid A→+1*
3.1 上下文无关文法 • 简化表示 expr → expr op expr | (expr) | − expr | id op → + | • 简化表示 E → E A E | (E ) | −E | id A → + |
3.1上下文无关文法 3.1.2推导 把产生式看成重写规则，把符号串中的非终结符 用其产生式右部的串来代替 例E→E+E引E*E引(E)|-EIid E→-E→-(E)→-(E+E)→-(id+E)→-(id+id) 概念 一上下文无关语言、等价的文法、句型 记号 S→*C、S→+w
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)|-EIid 最左推导 E→m-E→m-(E)→m-(E+E) →m-(id+E)→m-(id+id 最右推导（规范推导）》 E→m-E→m-(E)→m-(E+E) →m-(E+id)→m-(id+id
3.1 上下文无关文法 • 例 E → E + E | E E | (E ) | − E | id • 最左推导 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分析树 ·例E→E+E|E*E(E)|-E|id id g-
3.1 上下文无关文法 3.1.3 分析树 • 例 E → E + E | E E | (E ) | − E | id E − E ( E ) E + E id id
3.1上下文无关文法 3.1.4二义性 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.1 上下文无关文法 3.1.4 二义性 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.1上下文无关文法 3.1.4二义性 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 两棵不同的语法树 E E id id id id a
3.1 上下文无关文法 3.1.4 二义性 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 E 两棵不同的语法树 E E * + E E id id id E E id E * + E E id id
3.2语言和文法 文法的优点 文法给出了精确的，易于理解的语法说明 自动产生高效的分析器 可以给语言定义出层次结构 以文法为基础的语言的实现便于语言的修改 文法的问题 文法只能描述编程语言的大部分语法，不能描述 语言中上下文有关的语法特征
3.2 语言和文法 • 文法的优点 –文法给出了精确的，易于理解的语法说明 –自动产生高效的分析器 –可以给语言定义出层次结构 –以文法为基础的语言的实现便于语言的修改 • 文法的问题 –文法只能描述编程语言的大部分语法，不能描述 语言中上下文有关的语法特征