03 编译器原理与技术---语法分析

1 .第 3 章 语法分析 编译原理与技术

2 .上下文无关文法 自上而下分析和自下而上分析 围绕分析器的自动生成展开 3 语法分析 内容提要 词 法 分析器 记 号 取下一个记号 源程序 分析树 前端的 其余部分 语 法 分析器 中间表示 符号表

3 .3.1 上下文无关文法 第 3 章 语法分析 编译原理与技术

4 .3.1.1 上下文无关文法的定义 正规式能定义一些简单的语言，能表示给定结构的固定次数的重复或者没有指定次数的重复 例： a ( ba ) 5 , a ( ba )  正规式不能用于描述配对或嵌套的结构 例 1 ：配对括号串的集合 例 2 ： { wcw | w 是 a 和 b 的串 } 3.1 上下文无关文法

5 .上下文无关文法 是四元组（ V T , V N , S, P ） V T : 终结符 集合 V N : 非终结符 集合 S : 开始 符号，非终结符中的一个 P : 产生 式集合， 产生式形式 : A  α 以下简称“文法” 例 ( {id, +,  , -, (, )}, {expr, op}, expr, P ) expr  expr op expr expr  (expr) expr  - expr expr  id op  + op   3.1 上下文无关文法

6 .终结符 字母表前面的小写字母，如 a, b, c, … 词法分析中约定的记号，如 id, num , if, while, … 数字 0, 1, 2, … , 9 标点符号，如逗号，句号， … 运算符号，如 +, -,  , <, >, =, … 非终结符 字母表前面的大写字母，如 A, B, C, … 字母 S ，通常代表开始符号 小写字母组成的名字，如 expr, op, stmt , … 其它 字母表后面的大写字母，如 X, Y, Z, 代表文法符号，包括非终结符或终结符 字母表后面的小写字母，如 u, v, w, …, z ，代表终结符号串 小写希腊字母，如 α , β , γ , … ，代表文法符号串 3.1 上下文无关文法 符号的约定

7 .expr  expr op expr expr  (expr) expr  - expr expr  id op  + op   简化 表示 expr  expr op expr | (expr) | - expr | id op  + |  简化表示 E  E A E | (E ) | -E | id A  + |  3.1 上下文无关文法

8 .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 上下文无关文法

9 .例如 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 上下文无关文法

10 .3.1.3 分析树 例如 E  E + E | E  E | (E ) | -E | id E  -E  -(E)  -(E + E)  -(id + E)  -(id + id) 3.1 上下文无关文法 E E  ( ) E E E + id id

11 .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 上下文无关文法 E E E  + E E id id id E E id E  + E E id id

12 .3.2 语言和文法 第 3 章 语法分析 编译原理与技术

13 .文法的优点 文法给出了精确的，易于理解的语法说明 自动产生高效的分析器 可以给语言定义出层次结构 以文法为基础的语言的实现便于语言的修改 文法的问题 文法只能描述编程语言的大部分语法，不能描述语言中上下文有关的语法 特征 3.2 语言和 文法

14 .3.2.1 正规式和上下文无关文法的比较 正规 式 ( a|b )  ab 文法（由正规式构造文法） A 0  aA 0 | bA 0 | aA 1 A 1  bA 2 A 2  ε 3.2 语言和文法 1 2 开始 a 0 a b b

15 .3.2.2 分离词法分析器理由 为什么要用正规式定义词法 词法规则非常简单，不必用上下文无关文法 对于词法记号，正规式描述简洁且易于理解 从正规式构造出的词法分析器效率高 从软件工程角度看，词法分析和语法分析的分离有如下好处 简化 设计 编译器的效率会改进 编译器的可移植性加强 便于编译器前端的模块划分 3.2 语言和文法

16 .能否 把词法分析并入到语法分析中，直接从字符流进行语法分析 若 把词法分析和语法分析合在一起，则必须将语言的注解和空白的规则反映在文法中，文法将大大复杂 注解和空白由自己来处理的分析器，比注解和空格已由词法分析器删除的分析器要复杂得多 3.2 语言和文法

17 .3.2.3 验证文法产生的语言 G : S  (S) S | ε L(G) = 配对的括号串的集合 按推导步数进行归纳：推出的是配对括号串 归纳基础： S  ε 归纳假设：少于 n 步的推导都产生配对的括号串 归纳步骤： n 步的最左推导如下： S  (S)S   (x) S   (x) y 按串长进行归纳：配对括号串可由 S 推出 归纳基础： S  ε 归纳假设：长度小于 2n 的都可以从 S 推导出来 归纳步骤：考虑长度为 2n(n ≥ 1) 的 w = (x) y S  (S)S   (x) S   (x) y 3.2 语言和文法

18 .3.2.4 适当的表达式文法 用 一种层次观点看待表达式 id  id  ( id+id ) + id  id + id 文法 expr  expr + term | term term  term  factor | factor factor  id | (expr) 3.2 语言和文法

19 .expr  expr + term | term term  term  factor | factor factor  id | (expr) 3.2 语言和文法 expr id term factor id id term  term factor factor  expr expr + id factor term id id term  term factor factor id + id  id 分析树 id  id  id 分析树

20 .3.2.5 消除二义性 stmt  if expr then stmt | if expr then stmt else stmt | other 句型： if expr then if expr then stmt else stmt 两个最左推导： stmt  if expr then stmt  if expr then if expr then stmt else stmt stmt  if expr then stmt else stmt  if expr then if expr then stmt else stmt 3.2 语言和文法

21 .无二义的文法 stmt  matched _ stmt | unmatched_stmt matched_stmt  if expr then matched_stmt else matched_stmt | other unmatched_stmt  if expr then stmt | if expr then matched_stmt else unmatched_stmt 3.2 语言和文法

22 .下面 的条件语句文法仍存在二义，请证明 stmt  if expr then stmt | matched_stmt matched_stmt  if expr then matched_stmt else stmt | other if  then 　　　　　　　　　　　　　 else  3.2 语言和文法 例题 if  then  else  if  then 

23 .下面 的条件语句文法仍存在二义，请证明 stmt  if expr then stmt | matched_stmt matched_stmt  if expr then matched_stmt else stmt | other if  then 　　　　　　　　　　　　　 else  3.2 语言和文法 例题 if  then  else  if  then 

24 .下面 的条件语句文法仍存在二义，请证明 stmt  if expr then stmt | matched_stmt matched_stmt  if expr then matched_stmt else stmt | other if  then 　　　　　　　　　　　　　 else  3.2 语言和文法 例题 if  then  else  if  then 

25 .下面 的条件语句文法仍存在二义，请证明 stmt  if expr then stmt | matched_stmt matched_stmt  if expr then matched_stmt else stmt | other if  then 　　　　　　　　　　　　　 else  3.2 语言和文法 例题 if  then  else  if  then 

26 .3.2.7 提左因子 有左因子的文法 A  αβ 1 | αβ 2 提左因子 A  α A A  β 1 | β 2 3.2 语言和文法

27 .例 悬空 else 的文法 stmt  if expr then stmt else stmt | if expr then stmt | other 提 左因子 stmt  if expr then stmt optional_else_part | other optional_else_part  else stmt | ε 3.2 语言和文法 例题

28 .3.2.8 非上下文无关的语言构造 L 1 = { wcw | w ∈ ( a | b )  } 标识符的声明应先于其引用的抽象 L 2 = { a n b m c n d m | n ≥ 0, m ≥ 0 } 形参个数和实参个数应该相同的抽象 L 3 = { a n b n c n | n ≥ 0} 早先排版描述的一个现象的抽象 b e g i n ： 5 个字母键， 5 个回退键， 5 个下划线 键 3.2 语言和文法

29 .3.2.8 非上下文无关的语言构造 L 1 = { wcw | w ∈ ( a | b )  } 标识符的声明应先于其引用的抽象 L 2 = { a n b m c n d m | n ≥ 0, m ≥ 0 } 形参个数和实参个数应该相同的抽象 L 3 = { a n b n c n | n ≥ 0} 早先排版描述的一个现象的抽象 b e g i n ： 5 个字母键， 5 个回退键， 5 个下划线 键 3.2 语言和文法