第3章语法分析 记号 源程序 词法 分析器 分 前端的 中间 分析器 取下一个 其余部分 表示 记号 符号表 。本章内容 一上下文无关文法 一自上而下分析和自下而上分析 -围绕分析器的自动生成展开
第3章 语法分析 记 号 词 法 分析器 取下 个 源程序 分析树 前端的 其余部分 分析器 中间 分析器 取下一个 表示 记号 树 其余部分 表示 符号表 • 本章内容 – 上下文无关文法 – 自上而下分析和自下而上分析 – 围绕分析器的自动 围绕分析器的自动 成展开 生
3.1上下文无关文法 3.1.1上下文无关文法的定义 正规式能定义一些简单的语言，能表示给定结构 的固定次数的重复或者没有指定次数的重复 例：a(ba5,a(ba 正规式不能用于描述配对或嵌套的结构 例1：配对括号串的集合 例2：{wcww是a和b的串
3 1. 上下文无关文法 3.1.1 上下文无关文法的定义 –正规式能定义一些简单的语言，能表示给定结构 的固定次数的重复或者没有指定次数的重复 例：a (ba)5 例：a (ba) , a (ba)* –正规式不能用于描述配对或嵌套的结构 例1：配对括号串的集合 例2：{wcw | w是a和b的串}
3.1上下文无关文法 ·上下文无关文法是四元组(Vr,VN,S,P) 终结符集合 非终结符集合 S: 开始符号 P: 产生式集合，产生式形式：A→C 例({id,+,*,-,(,)},{xpr,0p,expr,P) expr→expr op expr expr→(expr) expr→-xp1 epr→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 0叩→+|* 简化表示 E→EAE|(E)|-E|id A>十*
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+ElE*E引(E)|-Eld E→-E→-(E)→-(E+E)→-(id+E)→-(id+id 概念 一上下文无关语言、等价的文法、句型 记号 S→*a、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)|-E|id 。 最左推导 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 ia EId
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+迈 →id*id+E →id*id+id →id*id+id E a E E 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 E * E E + E E + E id id * E E id id id id
3.2语言和文法 ·文法的优点 文法为语言给出了精确的、易于理解的语法规范 -自动产生高效的分析器 -可以给语言定义出层次结构 以文法为基础的语言的实现便于语言的修改 ,文法的问题 文法只能描述编程语言的大部分语法，而不是所 有的语法
3 2. 语言和文法 • 文法的优点 –文法为语言给出了精确的、易于理解的语法规范 –自动产生高效的分析器 –可以给语言定义出层次结构 –以文法为基础的语言的实现便于语言的修改 • 文法的问题 –文法只能描述编程语言的大部分语法，而不是所 有的语法
3.2语言和文法 3.2.1正规式和上下文无关文法的比较 。 正规式 (ab)"ab 开始 ·文法 A0-→aA|bAo|MA1 A1→bA2 A2→ε
3 2. 语言和文法 3.2.1 正规式和上下文无关文法的比较 • 正规式 (a|b)*ab a ( | ) 1 2 开始 a 0 b • 文法 A a A | b A | a A b A0 a A0 | b A0 | a A1 A1 b A2 A2