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

这一节主演讲述的是编译器原理与技术中的语法分析。首先向我们介绍了上下文无关文法,接着讲了语言和文法,然后讲了重要的分析方法--自上而下分析以及自下而上分析,最后向我们介绍了LR分析器以及语法分析器的生成器等。
展开查看详情

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 语言和文法