第四章 语法分析

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

上下文无关文法 4.1~4.3

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

例 ( {id, +, , , (, )}, {expr, op}, expr, P ) 4.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  

4.1 上下文无关文法 简化表示 expr  expr op expr | (expr) |  expr | id op  + |  E  E A E | (E ) | E | id A  + | 

4.1 上下文无关文法 文法书写上的约定 终结符 非终结符 字母表中的小写字母，如 a，b，c 黑体串，如 id, while 数字 0, 1, … , 9 标点符号，如括号，逗号等 运算符号，如+, -等 非终结符 字母表中的大写字母，如A, B, C 字母S，并且通常代表开始符号 小写字母的名字（斜体），如expr, stmt

4.1 上下文无关文法 文法书写上的约定 字母表中后面的大写字母，如X，Y，Z，可以是终结符或非终结符 字母表中后面的小写字母，如u，v … z 可代表终结符号串 小写希腊字母，如a，b，可代表文法的符号串 对于A  a1，A  a2，... A  an可以写成 A  a1 | a2 | … | an

例 E  E + E | E  E | (E ) |  E | id 4.1 上下文无关文法 4.1.2 推导（自顶向下） 把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替 例 E  E + E | E  E | (E ) |  E | id E  E  (E)  (E + E)  (id + E)  (id + id) 概念 S *、 S + w ，于是  *  * b， 且 b  γ, 则  * γ

4.1 上下文无关文法 4.1.2 推导 概念 上下文无关语言 等价的文法 句型 A→γ, 且a、b是任意符号串，则aAb  aγb 由上下文无关文法生成的语言是上下文无关语言 等价的文法 如果两个文法产生同样的语言，则两个文法等价 句型 文法G的开始符为S，S *， 可能含有非终结符，则叫做文法G的句型。

例 E  E + E | E  E | (E ) |  E | id 最左推导 4.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)

例 E  E + E | E  E | (E ) |  E | id 4.1 上下文无关文法 4.1.3 分析树 例 E  E + E | E  E | (E ) |  E | id E  E ( E ) E + E id id

4.1 上下文无关文法 4.1.4 二义性 id  id + id E  E  E E  E + E  id  E + E  id  E + E  id  id + E  id  id + E  id  id + id  id  id + id 两个不同的最左推导

4.1 上下文无关文法 4.1.4 二义性 id  id + id E  E  E E  E + E  id  E + E  id  E + E  id  id + E  id  id + E  id  id + id  id  id + id 两棵不同的语法树 E * + id

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

4.2 语言和文法 4.2.1 正则式和上下文无关文法的比较 正则式 文法 (a|b)*ab A0  a A0 | b A0 | a A1 开始 a b

4.2 语言和文法 4.2.2 分离词法分析器理由 为什么要用正则式定义词法 词法规则非常简单，不必用上下文无关文法 对于词法记号，正则式描述简洁且易于理解 从正则式构造出的词法分析器效率高

从软件工程角度看，词法分析和语法分析的分离有如下好处 4.2 语言和文法 从软件工程角度看，词法分析和语法分析的分离有如下好处 简化设计 编译器的效率会改进 编译器的可移植性加强 便于编译器前端的模块划分

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

4.2 语言和文法 4.2.3 验证文法产生的语言 G : S  (S) S |  L(G) = 配对的括号串的集合

G : S  (S) S |  L(G) = 配对的括号串的集合 按推导步数进行归纳：推出的是配对括号串 4.2 语言和文法 4.2.3 验证文法产生的语言 G : S  (S) S |  L(G) = 配对的括号串的集合 按推导步数进行归纳：推出的是配对括号串 归纳基础： S   归纳假设：少于n步的推导都产生配对的括号串 归纳步骤：n步的最左推导如下： S  (S)S * (x) S * (x) y

G : S  (S) S |  L(G) = 配对的括号串的集合 按串长进行归纳：配对括号串可由S推出 4.2 语言和文法 4.2.3 验证文法产生的语言 G : S  (S) S |  L(G) = 配对的括号串的集合 按串长进行归纳：配对括号串可由S推出 归纳基础： S   归纳假设：长度小于2n的都可以从S推导出来 归纳步骤：考虑长度为2n(n  1)的w = (x) y S  (S)S * (x) S * (x) y

4.2 语言和文法 4.2.4 适当的表达式文法 用一种层次观点看待表达式 id  id  (id+id) + id  id + id

4.2 语言和文法 4.2.4 适当的表达式文法 用一种层次观点看待表达式 id  id  (id+id) + id  id + id id  id  (id+id) 文法 expr  expr + term | term term  term  factor | factor factor  id | (expr)

4.2 语言和文法 expr  expr + term | term term  term  factor | factor factor  id | (expr) expr id term factor * expr + id factor term * id  id  id 分析树 id + id  id 分析树

句型：if expr then if expr then stmt else stmt 两个最左推导： 4.2 语言和文法 4.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

4.2 语言和文法 无二义的文法 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

4.2 语言和文法 4.2.6 消除左递归 消除左递归 A  A α | β A  β R R  α R | ε

4.2 语言和文法 4.2.6 消除左递归 文法左递归 A+Aa 直接左递归 AAa |b 消除直接左递归 A  b A 串的特点 ba . . . a 消除直接左递归 A  b A A a A | 

4.2 语言和文法 例 算术表达文法 E  E + T | T （ T + T . . . + T ） T  T  F | F （ F  F . . .  F ） F  ( E ) | id 消除左递归后文法 E  TE  E   + TE  |  T  FT  T    F T  | 

4.2 语言和文法 非直接左递归 S  Aa | b A  Sd |  先变换成直接左递归 A  Aad | bd |  再消除左递归 A  bd A | A A  adA | 

4.2 语言和文法 4.2.7 提左因子 有左因子的文法 A 1 | 2 提左因子 A   A A  1 | 2

stmt  if expr then stmt else stmt | if expr then stmt | other 提左因子 4.2 语言和文法 例 悬空else的文法 stmt  if expr then stmt else stmt | if expr then stmt | other 提左因子 stmt  if expr then stmt optional_else_part optional_else_part  else stmt | 

形式语言 ⑴ 0 型语言 由 0型文法定义 又称 无限制文法！ 产生式形式为： ->  又称 上下文有关文法！ ⑴ 0 型语言 由 0型文法定义 又称 无限制文法！ 产生式形式为： ->  又称 上下文有关文法！ ⑵ 1 型语言 由 1型文法定义 产生式形式为：xAy ->xy 又称 上下文无关文法！ ⑶ 2 型语言 由 2型文法定义 产生式形式为：A ->  又称 正规文法！ ⑷ 3 型语言 由 3型文法定义 产生式形式为：A->aB , A->a , A-> 【注】 四类语言为 包含关系，且有 L0 ⊃L1 ⊃ L2 ⊃ L3； 编译处理中，主要应用后两种文法！

乔姆斯基 艾弗拉姆·诺姆·乔姆斯基（英语：Avram Noam Chomsky，1928年12月7日－） 美国哲学家、语言学家、认知学家、逻辑学家、政治评论家。乔姆斯基是麻省理工学院语言学的荣誉退休教授，他的生成语法被认为是20世纪理论语言学研究上的重要贡献。

句法结构 《句法结构》是乔姆斯基介绍转换生成语法的《语言学理论的逻辑结构》一书的精华版。这一理论认为说话的方式（词序）遵循一定的句法，这种句法是以形式的语法为特征的，具体而言就是一种不受语境影响并带有转换生成规则的语法。 儿童被假定为天生具有适用于所有人类语言的基本语法结构的知识。这种与生俱来的知识通常被称作普遍语法。

下面的二义文法描述命题验算公式的语法，为他写一个等价的非二义文法 练习 文法 S->aSbS | bSaS | ε 产生的语言是什么？该文法是否有二义性？ 下面的二义文法描述命题验算公式的语法，为他写一个等价的非二义文法 S->S and S | S or S| not S| p | q | (S)

练习 文法 R->R'|'R | RR | R* | (R) | a | b

建立句子(a,(a,a))和(a,((a,a),(a,a)))的分析树 为（a）的两个句子构造最左推导 为（a）的两个句子构造最右推导 练习 考虑文法 S->(L) | a L->L,S | S 建立句子(a,(a,a))和(a,((a,a),(a,a)))的分析树 为（a）的两个句子构造最左推导 为（a）的两个句子构造最右推导 这个文法产生的语言是什么？