编译原理与技术

编译原理与技术 -- 文法和分析 2015/9/17 编译原理与技术 讲义 1

文法和分析 形式语言中若干基本概念 语言 文法 ( 上下文无关文法 ) 分析树与二义性 形式语言分类 乔姆斯基分类 2015/9/17 编译原理与技术 讲义 2

语言 语言 L={ s s 是 上任一字符串 }, s 称为语言 L 的一个句子 字母表 - 符号 / 字符的非空有限集合 e.g. 二进制数的 ={0,1}, 而十进制数的 = {0,1,,9} *- 表示 上所有字符串的集合 ;L * 字符串 - 上若干字符组成的有穷序列 2015/9/17 编译原理与技术 讲义 3

语言 字符串 e.g. ={0,1} 上的 0,1 串 ( 二进制数 ) 如 0111, 10101; ={a,b} 上的 a, b, aa, abab, 空串 -ε, ε *, 串长 - s ={s 中所含字符的个数 }, ε =0 串的连接运算 - 任意串 x,y, 一般地,xy yx, xε= εx 串的前缀 - 任意串 x, 从其第一个字符 ( 最左字符 ) 起的字符序列是其前缀 ε 亦是 e.g. x = abc, 则 ε,a,ab,abc 均是 x 的前缀 2015/9/17 编译原理与技术 讲义 4

语言的运算 描述运算 语言 L 和语言 M 连接 ( 积 ) LM={ xy x L 且 y M } 合并 ( 和 ) L M={x x L 或 x M } 闭包 L*=L 0 L 1 L 2 = 正闭包 L + =L 1 L 2 L 3 = L i= 0 L i= 1 i i 2015/9/17 编译原理与技术 讲义 5

语言 e.g. L={a,b,,z}, D={0,1,,9}, B={ _ } L D = { } LD={ } L*={ } L(L D)*={ } (L B)(L D B)*={ } D + ={} 2015/9/17 编译原理与技术 讲义 6

文法文法 G=(V T,V N,S,P) 定义为一个四元组, 其中 : V T - 终结符号集合 ; V N - 非终结符号集合,V T V N = ; S- 文法开始符号,S V N ; P- 文法产生式集合, 每一产生式形如 α β, 其中 α,β (V T V N )*,α 至少含有一个非终结符, α 称为相应产生式的左部,β 则为产生式的右部 2015/9/17 编译原理与技术 讲义 7

文法是描述语言的语法结构的形式规则, 其中, 终结符号 ( 集合 ) 表示组成语言的基本成份, 如标识符 常数, 算符等 ; 非终结符号 ( 集合 ) 代表语法实体 ( 范畴 ), 如算术表达式 条件语句 过程等 ; 而开始符号作为一特殊的非终结符号则代表着语言中 最大 的语法实体 - 语言的目标 ( 也称为 句子 ), 如 程序 产生式看作定义语法实体的一种书写规则, 通过它, 可以了解较 大 的语法实体如何由较 小 的语法实体 ( 非终结符号 ) 和 / 或语言基本成份 ( 终结符号 ) 来构成的 2015/9/17 编译原理与技术 讲义 8

上下文无关文法 (context-free grammar) 同样定义为四元组 (V T,V N,S,P),P 中的产生式形式为 : A α,α (V T V N )*, 而 A V N ; 开始符号 S 须在产生式的左部出现至少一次 2015/9/17 编译原理与技术 讲义 9

e.g.1 算术表达式 ( 含 +,* 运算 ) 递归定义如下 : 1) 变量是一个算术表达式 ; 2) 若 E 1 和 E 2 是算术表达式, 则 E 1 + E 2, E 1 * E 2 和 (E 1 ) 也是算术表达式 2015/9/17 编译原理与技术 讲义 10

文法 e.g.1 文法 G1=({i,+,*,(,)},{E},E,P), 其中产生式集合 ( 左递归形式 ) P: E E+E E E*E E (E) E i 2015/9/17 编译原理与技术 讲义 11

文法 e.g. 1 文法 G1=({i,+,*,(,)},{E},E,P), 其中产生式集合 P: E E+E P: E E+E E E*E E (E) E i 相同左部的产生式 E*E (E) i 2015/9/17 编译原理与技术 讲义 12

文法 e.g.2 文法 G2=({i,+,*,(,)},{E,T,F},E,P),P: E E + T T T T * F F F ( E ) i 2015/9/17 编译原理与技术 讲义 13

文法 G1,P: E E+E E*E (E) i 文法 G1 和 G2 描述了相同的语言 - 算术表达式 文法 G2,P: E E + T T T T * F F F ( E ) i 2015/9/17 编译原理与技术 讲义 14

文法产生的语言 e.g.3 i + i 是算术表达式, 那么文法 G1 是如何 描述 它的? 文法 G2 呢? 2015/9/17 编译原理与技术 讲义 15

文法产生的语言 e.g.3 G1 的描述 : E E + E i + E i + i G2 的描述 : E E + T T + T F + T i + T i + F i + i 2015/9/17 编译原理与技术 讲义 16

文法产生的语言 e.g.3 G1 的 描述 方式 : 从文法的开始符号 E 出发, 反复用产生式的右部对其左部的非终结符进行替换和展开, 直至 i+i 出现为止 所用产生式的顺序为 : 1) E E+E 2) E i 3) E i 2015/9/17 编译原理与技术 讲义 17

文法产生的语言 e.g.3 G2 的 描述 方式 : 所用产生式的顺序为 : 1) E E+T 5) T F 2) E T 6) F i 3) T F 4) F i 2015/9/17 编译原理与技术 讲义 18

文法产生的语言 我们称上述 描述 为从开始符号 E 到 i+i 的 推导 过程 表示一步 推导 一般地, αaβ 直接推导出 αγβ, 即 αaβ αγβ 仅当 A γ P, α,β,γ (V T V N )* * + 推导序列 - α β, α β 2015/9/17 编译原理与技术 讲义 19

文法产生的语言 * α 是句型, 如果 S α, α (V T V N )* * α 是句子, 如果 S α, 且 α V T * 文法 G 产生的语言 L(G), 定义为, L(G)={ 文法 G 产生的所有句子 } 2015/9/17 编译原理与技术 讲义 20

文法产生的语言 e.g.4 文法 G3 产生的语言是什么? P:S b A A a A a S ba ba S ba baa baa S ba baa baaa baa a L(G3) = { 以 b 开头后跟一个或多个 a 的串 } 2015/9/17 编译原理与技术 讲义 21

e.g.5 文法产生的语言 L(G4)={a m b n m,n 1} L(G5) = {a n b n n 1} G4: S A B A a A a B b B b G5: S a S b ab 2015/9/17 编译原理与技术 讲义 22

e.g.5 文法产生的语言 文法 G4 对句子 aaabb 的推导 : S A B S A B a A B A a A a a A B A a A a a a B A a a a a b B B b B a a a b b B b 2015/9/17 编译原理与技术 讲义 23

e.g.5 文法产生的语言 文法 G5 对句子 aaaabbbb 的推导 : S a S b S a S b a a S b b S a S b a a a S b b b S a S b a a a a b b b b S a b 2015/9/17 编译原理与技术 讲义 24

句型推导时, 总是选择最左出现的非终结符进行替换 最左推导 E E + E i + E i + i 总是选择最右出现的非终结符进行替换, 也称为规范推导 最右推导 E E + E E + i i + i 2015/9/17 编译原理与技术 讲义 25

E i 规范推导 ( 最右推导 ) 和规范归约 ( 最左归约 ) G1 的句子 i+i*i 的规范推导过程 : E 开始符号 E + E 推E E + E 导 E + E * E 方E E * E 向 i + i + i E + E * i E i E + i * i E i 2015/9/17 编译原理与技术 讲义 26

规范推导 ( 最右推导 ) 和规范归约 ( 最左归约 ) G1 的句子 i+i*i 的规范归约过程 : i + i + i E + i * i E + E * i E + E * E E + E E 约方向( 只有 ) 开始符号归E i E i E i E E * E E E + E 2015/9/17 编译原理与技术 讲义 27

最右推导最左归约 * αβδ αaδ,a P A S rm rm αβδ β 如果右句型可以 归约 到右句型 α δ, 仅当存在最右推导序列 * S αβδ β rm rm αaδ,a P 从开始符号 S 出发, 进行最右推导, 用相应产生式右部文法符号串替换展开其左部非终结符号 目标为句子 ( 右句型 ) 从句子 ( 右句型 ) 出发, 用最左归约, 用相应产生式的左部非终结符号替换产生式右部 ( 句柄 ) 目标为开始符号 S 2015/9/17 编译原理与技术 讲义 28

最右推导 推导中, 关键是选择产生式 最左归约 归约中, 关键是确定句柄 而句柄与某产生式的右部相同且有某最右推导序列中的某一步对应 ; 归约过程看成这一步最右推导的逆过程 2015/9/17 编译原理与技术 讲义 29

分析树 分析树看成是 ( 句型 ) 推导的图形表示 ; 反之, ( 句型 ) 推导可理解为分析树的线形表示 分析树所有结点 v( 内部结点和叶子结点 ) 由文法符号或 ε 标记, 即 v (V T V N {ε} ); 根结点由文法开始符号 S 标记 ; 内部结点 A V N, 其所有子结点从左往右排列构成以 A 为左部的某产生式的右部 2015/9/17 编译原理与技术 讲义 30

分析树与推导文法 G1 推导句子 i+i*i ( 最左 ) 推导过程 : 分析树 E E + E E E + E 圆圈内表示新构造的分析 ( 子 ) 树 - 即推导所用产生式 2015/9/17 编译原理与技术 讲义 31

分析树与推导 - 句子 i+i*i ( 最左 ) 推导过程 : 分析树 E E + E i + E E E + E i 2015/9/17 编译原理与技术 讲义 32

分析树与推导 - 句子 i+i*i ( 最左 ) 推导过程 : 分析树 E E + E i + E i + E * E E E + E i E * E 2015/9/17 编译原理与技术 讲义 33

分析树与推导 - 句子 i+i*i ( 最左 ) 推导过程 : 分析树 E E + E i + E i + E * E i + i * E E E + E i E * E i 2015/9/17 编译原理与技术 讲义 34

分析树与推导 - 句子 i+i*i ( 最左 ) 推导过程 : 分析树 E E + E i + E i + E * E i + i * E i + i * i E E + E i E * E i i 1 代结点 2 代结点 3 代结点 4 代结点 2015/9/17 编译原理与技术 讲义 35

二义性文法 文法 G 是二义性文法, 如果它的某个句子有两种不同的最左 ( 或最右 ) 推导 ; 或有两棵不同的分析树 该句子称为文法 G 的二义性句子 二义性语言 语言 L 是二义性的语言, 如果不存在能产生它的非二义性的文法 ; 或者能产生该语言的文法均为二义性文法 2015/9/17 编译原理与技术 讲义 36

- 二义性文法 e.g.8 文法 G1 是二义性文法 这是因为对于句子 i+i*i 有两种不同的最右推导 推导 1: E E + E E + E * E E + E * i E + i * i i + i * i 推导 2: E E * E E * i E + E * i E + i * i i + i * i 2015/9/17 编译原理与技术 讲义 37

- 二义性文法 e.g.9 文法 G1 是二义性文法 这是因为对于句子 i+i*i 有两棵不同的分析树 E E E * E E + E E + E i i E * E i i i i i+i*i 的一棵分析树 i+i*i 的另一棵分析树 2015/9/17 编译原理与技术 讲义 38

- 二义性文法 e.g.10 文法 G1 对于句子 i+i+i 有两棵不同的分析树 E E E + E E + E E + E i i E + E i i i i i+i*i 的一棵分析树 i+i*i 的另一棵分析树 2015/9/17 编译原理与技术 讲义 39

- 二义性文法 e.g.11 文法 G2 是非二义性文法 对于句子 i+i*i 有唯一的最左推导过程 (why?) 推导过程 : E E + T T + T F + T i + T i + T * F i + F * F i + i * F i + i * i 2015/9/17 编译原理与技术 讲义 40

- 二义性文法 e.g.12 E 文法 G2 是非二义性文法 对于句子 i+i*i 有唯一的分析树 E T F + T F T * F i i i 2015/9/17 编译原理与技术 讲义 41

if-then-else 问题 e.g.13 文法 G3 如下 : stmt if expr then stmt if expr then stmt else stmt others G3 是二义性文法, 因为对输入串, if E1 then if E2 then S1 else S2 有两棵不同的分析树 ( 推导 ) 2015/9/17 编译原理与技术 讲义 42

stmt if expr then stmt E1 if expr then stmt else stmt E2 S1 S2 stmt if expr then stmt else stmt E1 S2 if expr then stmt E2 2015/9/17 编译原理与技术 讲义 43 S1

if-then-else 问题 解决 if-then-else 的二义性 stmt matched unmatched matched if expr then matched else matched others unmatched if expr then stmt if expr then matched else unmatched 对输入串, if E1 then if E2 then S1 else S2 仅有惟一的分析树 ( 推导 ) 2015/9/17 编译原理与技术 讲义 44

stmt unmatched if expr then stmt E1 matched if expr then matched else matched E2 S1 S2 2015/9/17 编译原理与技术 讲义 45

if-then-else 下面的文法是否有二义性? stmt if expr then stmt else-part others else-part else stmt endif endif 2015/9/17 编译原理与技术 讲义 46

约化的 CFG CFG 中不含有不可达 或者无法推出终结符串的非终结符 文法 G4 约化后的文法 G5: S A B A a B B b C c S A A a 2015/9/17 编译原理与技术 讲义 47

形式语言分类 0 型文法短语文法 1 型文法 上下文有关文法 2 型文法 上下文无关文法 3 型文法正规文法 α β, α * * VVV N β V * α β, α β 或 αaδ αβδ αδ, V *, β + V A α α V A V *, N A α or A αb α V * T, A,B V N 图灵机 线性有界自动机 下推自动机 有限自动机 2015/9/17 编译原理与技术 讲义 48

形式语言分类 0 型文法 短语文法 L0={ αc α α (a b)* 1 型文法 上下文有关文法 L1={ 2 型文法 上下文无关文法 L2={ 3 型文法 正规文法 L3={ i i i a b c i 1 i i j j a b c i, j 1 a b i c k i, j,k 1 } } } } 2015/9/17 编译原理与技术 讲义 49

正规式 V.S 上下文无关文法 任意正规集可以用一上下文文法来产生 如 : 正规式 (a b)*ab, 则如下的 CFG 产生相同语言集合 ( 正规集 ): a A 0 aa 0 ba 0 aa 1 a b A 0 A 1 A 2 A 1 ba 2 A 2 ε 相应 CFG 的构造规则 : b 正规式 (a b)*ab 对应 FA (1)FA 中若有状态 i 状态 j 且标记为 a 的转换, 则添加产生式 A i aa j,a i 和 A j 为状态 i 和 j 对应的非终结符 (2)FA 中的终态 f, 引入产生式 A f ε 2015/9/17 编译原理与技术 讲义 50

语法分析 高级语言源程序 词法分析 token get_next_ token 语法分析器 分析树 语义分析 符号表 错误处理 2015/9/17 编译原理与技术 讲义 51

有两种通用的语法分析方法 第一种方法, 称为自顶向下的 (top-down) 如果一个分析器从树的顶端 ( 开始符号 ) 开始发现词法记号序列所对应的分析树, 并随后以深度优先的方式 ( 用产生式 ) 对其进行扩展, 则它被认为是自顶向下的 自顶向下的语法分析器对应分析树的前序遍历 自顶向下的语法分析技术本质上是预测性的 (predictive), 因为它们总是在实际匹配开始之前预测将要被匹配的产生式 自顶向下的 (top-down) 预测分析用的产生式对应着最左推导 2015/9/17 编译原理与技术 讲义 52

另一种方法属于自底向上的 (bottom-up) 语法分析器类 自底向上的语法分析器从分析树的底部 ( 树的叶结点, 它们都是终结符号 ) 开始发现其结构, 并确定用来生成叶结点的产生式 随后发现用来生成叶结点的直接父结点的产生式 自底向上的语法分析器对应分析树的后序遍历 自底向上的 (bottomup) 语法分析所识别的产生式对应着最右分析 - 即最左规约 ( 最右推导的严格逆序 ) 2015/9/17 编译原理与技术 讲义 53