编译原理与技术

Size: px

Start display at page:

Download "编译原理与技术"

权平
5 years ago
Views:

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

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

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

4 语言字符串 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

5 语言的运算描述运算语言 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

6 语言 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

7 文法文法 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

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

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

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

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

12 文法 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

13 文法 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

14 文法 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

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

16 文法产生的语言 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

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

18 文法产生的语言 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

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

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

21 文法产生的语言 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

22 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

23 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

24 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

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

26 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

27 规范推导 ( 最右推导 ) 和规范归约 ( 最左归约 ) 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

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

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

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

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

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

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

34 分析树与推导 - 句子 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

35 分析树与推导 - 句子 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

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

37 - 二义性文法 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

38 - 二义性文法 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

39 - 二义性文法 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

40 - 二义性文法 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

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

42 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

43 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

44 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

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

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

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

48 形式语言分类 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

49 形式语言分类 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

50 正规式 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

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

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

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

Microsoft PowerPoint - 2-FormalLang.ppt

Microsoft PowerPoint - 2-FormalLang.ppt 第二章高级语言及其语法描述 2.1 程序设计语言的定义 2.2 高级语言的一般特性 2.3 程序设计语言的语法描述本章目的 : 简要了解高级语言的主要内容及特点 ; 掌握上下文无关文法及语法树作业 : p35-36:1(1)(2)(5),4,6-11 9 号交程序设计语言历史 50 s: Fortran & Lsp 60 s: Algol, PL/1, Smula67 70 s: Pascal,