中国科学技术大学：《编译原理与技术》课程教学资源（课件讲稿）第3章 语法分析

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  