Download presentation
Presentation is loading. Please wait.
1
语法分析 本章内容 语法分析器：把词法分析生成的词法单元流翻译成语法分析树（parse tree）
介绍上下文无关文法、自顶向下和自底向上的分析方法
2
语法分析器 词 法 分析器 token 源程序 分析树 前端的 其余部分 语 法分析器 中间表示 符号表
词 法 分析器 token getNextToken 源程序 分析树 前端的 其余部分 语 法分析器 中间表示 符号表 实际中，不需要显式地构造出语法分析树，语法分析和前 端的其余部分（类型检查、中间代码生成等）交错完成， 可以用一个模块来实现。
3
本章回答四个问题： 如何描述一个程序语言的语法结构？ 上下文无关文法（context-free grammar, CFG）
在词法分析中，正则表达式描述了词法结构 如何描述一个程序语言的语法结构？ 上下文无关文法（context-free grammar, CFG） 如何进行语法分析？即，给定CFG和词法单元流， 如何构造分析树？ 自顶向下，自底向上 如何保证生成的分析树唯一？（二义性问题） 给定CFG，如何快速构造语法分析器？ 语法分析器的生成器Yacc
4
文法 文法（grammar）：程序语言的语法（syntax）的 一种精确的、可读的规范描述
上下文无关文法通常用Backus-Naur Form (BNF)书写 产生式 stmt if expr then stmt else stmt expr id | (expr) | expr + expr | expr * expr 终结符、非终结符 if, then, else, +, *, (, ), id; stmt, expr 递归 stmtlist stmt | stmt; stmtlist “or”
5
上下文无关文法 上下文无关文法是四元组 (VT , VN , S, P)
S : 开始符号，非终结符中的一个（S VN ） P : 产生式集合， 产生式形式 : A 例 ( {id, +, , , (, )}, {expr, op}, expr, P ) P = {expr expr op expr, expr (expr), expr expr, expr id, op +, op } 用BNF书写： expr expr op expr | (expr) | expr | id op + |
6
上下文无关文法 推导（derivations） 例 E E + E | E E | (E ) | E | id 记号 概念
把产生式看成重写规则，把符号串中的非终结符用其 产生式右部的串来代替 例 E E + E | E E | (E ) | E | id E E (E) (E + E) (id + E) (id + id) 记号 S *、 S + 概念 句型、句子、上下文无关语言、等价的文法 ，使得 S * 不含非终结符的句型 所有句子的集合 生成相同语言
7
上下文无关文法 例 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)
8
上下文无关文法 分析树（parse tree）：推导的图形化表示，展 示了语言的层次结构，与推导顺序无关
例 E E + E | E E | (E ) | E | id (id + id)的分析树 E E ( E ) E + E id id 每棵分析树对应唯一的最左推导及唯一的最右推导！
9
二义性 例 E E + E | E E | (E ) | E | 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 两个不同的最左推导
10
二义性 例 E E + E | E E | (E ) | E | 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 两棵不同的分析树
11
消除二义性 方法一：消二义规则（disambiguating rules）， 如优先级（e.g. *比+具有更高的优先级）
12
消除二义性 方法二：重写文法！
13
例 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-then-else的优先级高于if-then（第一种推导）
14
无二义的文法 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
15
有二义的文法： E E + E | E E | (E ) | E | id
另一个例子 有二义的文法： E E + E | E E | (E ) | E | id 优先级： () > (unary minus) > * > + 从高优先级到低优先级构造无二义的文法： element ( expr ) | id primary primary | element term term * primary | primary expr expr + term | term 考虑 id + id * id 的最左推导 expr expr + term term + term primary + term primary + term element + term id + term id + term * primary ... * id + id * id
16
有二义的文法： S S and S | S or S | not S | p | q 优先级： not > and > or
第三个例子 有二义的文法： S S and S | S or S | not S | p | q 优先级： not > and > or 从高优先级到低优先级构造无二义的文法： F not F | p | q T T and F | F E E or T | T 考虑 not p and q 的最左推导 E T T and F F and F not F and F not p and F not p and q
17
有二义的文法： S S and S | S or S | not S | p | q 优先级： not > and > or
第三个例子 有二义的文法： S S and S | S or S | not S | p | q 优先级： not > and > or 无二义的文法？ F not E | p | q T T and F | F E E or T | T 考虑 not p and q 的最左推导 E T T and F F and F not E and F not T and F not F and F not p and F not p and q E T F not E not T not T and F
18
第四个例子 设计一个文法：字母表{a, b}上a和b的个数相等的所有串 有二义的文法： S a S b S | b S a S |
S a B | b A | A a S | b A A B b S | a B B 无二义的文法： S a B S | b A S | A a | b A A B b | a B B aabbabab S S aabbabab S S aabbabab B B aabbabab B B aabbabab B B a abb abab B S
19
其他的文法变换 消除左递归（在自顶向下分析中有用） 将 A Aa | b 改写为 A b A A a A |
20
消除左递归 例 算术表达文法 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 |
21
消除左递归 非直接左递归 S Aa | b A Sd | 先变换成直接左递归 A Aad | bd | 再消除左递归
A bd A | A A adA |
22
其他的文法变换 提取左公因子（在自顶向下分析中有用） 将 A 1 | 2 改写为 A A A 1 | 2
23
验证文法产生的语言 G : S (S) S | L(G) = 配对的括号串的集合 按推导步数进行归纳：推出的是配对括号串
归纳假设：少于n步的推导都产生配对的括号串 归纳步骤：n步的最左推导必然如下形式： S (S)S * (x) S * (x) y
24
验证文法产生的语言 G : S (S) S | L(G) = 配对的括号串的集合 按串长进行归纳：配对括号串可由S推出
归纳假设：长度小于2n的都可以从S推导出来 归纳步骤：考虑长度为2n(n 1)的w, 则存在x和y使得 w = (x) y 且x和y是配对括号串。所以可构造推导： S (S)S * (x) S * (x) y
25
语言和文法 文法的优点 文法的问题 文法给出了精确的，易于理解的语法说明 自动产生高效的分析器 可以给语言定义出层次结构
以文法为基础的语言的实现便于语言的修改 文法的问题 文法只能描述编程语言的大部分语法，不能描述语言 中上下文有关的语法特征
26
语言和文法 适当的表达式文法给我们一种层次观点看待表达式 id id (id+id) + id id + id
expr expr + term | term term term factor | factor factor id | (expr)
27
语言和文法 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 分析树
28
正则表达式 vs 上下文无关文法 正则表达式 文法 每个正则语言都是一个上下文无关语言，反之不成立 1 2 start a b
b 正则表达式 (a|b)*ab 文法 A0 a A0 | b A0 | a A1 A1 b A2 A2 （1）为NFA的每个状态i，创建非终结符Ai （2）对于状态转换：加入Ai a Aj 或 Ai Aj （3）若i为接收状态：加入 Ai （4）若i为开始状态：令Ai为文法的开始符号 每个正则语言都是一个上下文无关语言，反之不成立
29
正则表达式 vs 上下文无关文法 正则表达式能定义一些简单的语言，能表示给定 结构的固定次数的重复或者没有指定次数的重复
例：a (ba)5, a (ba)* 正则表达式不能用于描述配对或嵌套的结构 例：配对括号串的集合 每个正则语言都是一个上下文无关语言，反之不成立
30
正则表达式 vs 上下文无关文法 S aSb | ab L ={anbn | n 1} L是不能用正则表达式描述的语言的一个范例
若存在接受L 的DFA D，状态数为k个 设D读完, a, aa, …, ak 分别到达状态s0, s1, …, sk 至少有两个状态相同，例如是si和sj，则ajbi属于L si … f s0 标记为ai的路径 标记为bi的路径 标记为aj i的路径
31
分离词法分析器的理由 为什么要用正则表达式定义词法 词法规则非常简单，不必用上下文无关文法 对于词法记号，正则表达式描述简洁且易于理解
从正则表达式构造出的词法分析器效率高
32
分离词法分析器的理由 从软件工程角度看，词法分析和语法分析的分离 有如下好处 简化设计 编译器的效率会改进 编译器的可移植性加强
便于编译器前端的模块划分
33
分离词法分析器的理由 能否把词法分析并入到语法分析中，直接从字符 流进行语法分析
若把词法分析和语法分析合在一起，则必须将语言的 注解和空白的规则反映在文法中，文法将大大复杂 注解和空白由自己来处理的分析器，比注解和空格已 由词法分析器删除的分析器要复杂得多
34
非上下文无关的语言 L1 = {wcw | w属于(a | b)*} L2 = {anbmcndm | n 0, m 0}
标识符的声明应先于其引用的抽象 L2 = {anbmcndm | n 0, m 0} 形参个数和实参个数应该相同的抽象 方法一：用上下文敏感文法 方法二：不在文法中描述，在语义分析阶段检查
35
语法分析 语法分析器：给定一个句子，构造该句子的推导 语法分析器都从左至右地扫描输入，但有不同的 方式构造分析树 词 法 分析器 token
词 法 分析器 token getNextToken 源程序 分析树 前端的 其余部分 语 法分析器 中间表示 符号表 语法分析器：给定一个句子，构造该句子的推导 语法分析器都从左至右地扫描输入，但有不同的 方式构造分析树 自顶向下：从根节点开始向叶节点构造 自底向上：从叶节点开始向根节点构造
36
自顶向下的语法分析 从文法的开始符号开始，猜测用哪个产生式推导 例 文法 S aCb C cd | c
用下一个输入符号来指导“猜测” 例 文法 S aCb C cd | c 为输入串w = acb建立分析树 S a C b S a C b c d S a C b c 对C用哪个产生式？ 用C的第一个产生式 猜错了！回溯，试第二个产生式
37
自顶向下的语法分析 不能处理左递归 例 算术表达文法 E E + T | T T T F | F F ( E ) | id
例 算术表达文法 E E + T | T T T F | F F ( E ) | id E E + T E + T E + T … … …
38
自顶向下的语法分析 不能处理左递归 复杂的回溯技术 回溯导致语义工作推倒重来 难以报告出错的确切位置 效率低
39
自顶向下的语法分析 对文法加什么样的限制可以保证没有回溯？ LL(k)文法 书上：递归下降分析技术，针对LL(1)文法的预测 分析技术
40
自底向上的语法分析 构造分析树：从叶节点开始向上到根节点 总是构造最右推导 算法：移进-归约（shift-reduce）
将一个串w“归约”为文法开始符号 关键：寻找与某产生式右部相匹配的子串
41
归约 例 S aABe A Abc | b B d
42
归约 例 S aABe A Abc | b B d abbcde（读入ab） a b
43
归约 例 S aABe A Abc | b B d abbcde aAbcde（归约） a b A
44
归约 例 S aABe A Abc | b B d abbcde aAbcde（再读入bc） a b A c
45
归约 例 S aABe A Abc | b B d abbcde aAbcde aAde（归约） a b A c
46
归约 例 S aABe A Abc | b B d abbcde aAbcde aAde（再读入d） a b A d c
47
归约 a 例 S aABe A Abc | b B d abbcde aAbcde aAde aABe（归约） b A d c
48
归约 a 例 S aABe A Abc | b B d abbcde aAbcde aAde aABe(再读入e) e b A
49
归约 a 例 S aABe A Abc | b B d abbcde aAbcde aAde aABe S（归约） S e b
50
归约 a 例 S aABe A Abc | b B d abbcde aAbcde aAde aABe S
S rm aABe rm aAde rm aAbcde rm abbcde S e a b A d c B
51
句柄（Handles） 句型的句柄是和某产生式右部匹配的子串，并且， 把它归约成该产生式左部的非终结符代表了最右 推导的一个反向步骤
S aABe A Abc | b B d S rm aABe rm aAde rm aAbcde rm abbcde 句柄右边的串一定仅含终结符 如果文法二义，那么句柄可能不唯一
52
句柄（Handles） 例 句柄不唯一 E E + E | E E | (E ) | id E rm E E
例 句柄不唯一 E E + E | E E | (E ) | id E rm E E rm E E + E rm E E + id3 rm E id2 + id3 rm id1 id2 + id3 E rm E + E rm E + id3 rm E E + id3 rm E id2 + id3 rm id1 id2 + id3 在句型E E + id3中，句柄不唯一
53
句柄（Handles） 例 E E + T | T T T F | F F ( E ) | id E rm E + T
rm E + F rm E + id3 rm T + id3 rm T F + id3 rm T id2 + id3 rm F id2 + id3 rm id1 id2 + id3 无二义的文法，句柄唯一
54
移进-归约语法分析技术 使用一个栈 移进：将输入符号移进栈中，直到发现一个句柄 归约：对句柄进行归约 接受：栈中包含文法开始符号，无更多输入
报错：语法错误 下面以id1 id2 + id3为例
55
栈 输 入 动 作 $ id1 id2 + id3$
56
栈 输 入 动 作 $ id1 id2 + id3$ 移进
57
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$
58
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约
59
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E
60
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E
61
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$
62
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$
63
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$
64
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$
65
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE
66
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE
67
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$
68
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$
69
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3
70
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3
71
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E
72
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E E+E归约
73
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E E+E归约
74
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E E+E归约 按E EE归约
75
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E E+E归约 按E EE归约
76
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E E+E归约 按E EE归约 接受
77
移进-归约 要想很好地使用移进归约方式，尚需解决一些 问题 如何决策选择移进还是归约 进行归约时，确定右句型中将要归约的子串
进行归约时，如何确定选择哪一个产生式
78
移进-归约分析中的冲突 1、移进归约冲突 E rm E E rm E E + E rm E E + id3
例 E E + E | E E | (E ) | id E rm E E rm E E + E rm E E + id3 rm E id2 + id3 rm id1 id2 + id3 E rm E + E rm E + id3 rm E E + id3 rm E id2 + id3 rm id1 id2 + id3
79
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E EE归约
80
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E EE归约
81
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E EE归约
82
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E EE归约 $E+ id3$
83
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E EE归约 $E+ id3$
84
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E EE归约 $E+ id3$ $E+id3
85
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E EE归约 $E+ id3$ $E+id3
86
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E EE归约 $E+ id3$ $E+id3 $E+E
87
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E EE归约 $E+ id3$ $E+id3 $E+E 按E E+E归约
88
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E EE归约 $E+ id3$ $E+id3 $E+E 按E E+E归约
89
栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E EE归约 $E+ id3$ $E+id3 $E+E 按E E+E归约 接受
90
E rm E E rm E E + E rm E E + id3 rm E id2 + id3
rm id1 id2 + id3 E rm E + E rm E + id3 rm E E + id3 rm E id2 + id3 rm id1 id2 + id3 栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E E+E归约 按E EE归约 接受 栈 输 入 动 作 $ id1 id2 + id3$ 移进 $ id1 id2 + id3$ 按E id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E EE归约 $E+ id3$ $E+id3 $E+E 按E E+E归约 接受
91
移进-归约分析中的冲突 1、移进归约冲突 例 stmt if expr then stmt
| if expr then stmt else stmt | other 如果移进归约分析器处于格局 栈 输入 … if expr then stmt else … $ if-then-else的优先级高于if-then（选择移进）
92
移进-归约分析中的冲突 归约成expr还 是parameter ? 2、归约归约冲突
stmt id (parameter_list) | expr = expr parameter_list parameter_list, parameter | parameter parameter id expr id (expr_list) | id expr_list expr_list, expr | expr 由A(I, J)开始的语句 栈 输入 … id ( id , id )… 归约成expr还 是parameter ?
93
移进-归约分析中的冲突 2、归约归约冲突 stmt id (parameter_list) | expr = expr
parameter_list parameter_list, parameter | parameter parameter id expr id (expr_list) | id expr_list expr_list, expr | expr 由A(I, J)开始的语句(词法分析查符号表,区分第一个id) 栈 输入 … procid ( id , id )… 需要修改上面的文法
94
LR分析 目前最流行的语法分析技术 LR(k)分析：移进-归约分析 特点 L：从左往右扫描输入 R：反向构造一个最右推导序列
k：向前看k个符号（通常k<=1, 缺省为1）以帮助做出 移进或归约的决定 特点 适用于一大类上下文无关文法（LR文法） 效率高
95
所有LR分析器的驱动程序是相同的，分析表可以不同
输入 LR分析程序 输出 栈 action goto sm Xm sm-1 Xm-1 … s0 a1 ai an $ 分析表 所有LR分析器的驱动程序是相同的，分析表可以不同
96
LR分析 Configuration（分析过程中的中间状态） (s0X1s1X2s2…Xmsm, aiai+1ai+2…an$)
分析表：action[s, a]和goto[s, A] Table action[s, a] s: state, a: terminal entries: (1) shift s (2) reduce A (3) accept (4) error Table goto[s, A] s: state, A: non-terminal entries are states 由sm和ai决定下一步是什么 状态 文法符号 终结符
97
LR分析 给定config: (s0X1s1X2s2…Xmsm, aiai+1ai+2…an$) 1）若action[sm, ai]是“shift s”，则进入config (s0X1s1X2s2…Xmsmais, ai+1ai+2…an$) 2）若action[sm, ai]是“reduce A ”，则进入config (s0X1s1X2s2…Xm-rsm-rAs, aiai+1ai+2…an$) 其中 r = ||, = Xm-r+1Xm-r+2…Xm, s = goto[sm-r, A] 3）若action[sm, ai]是“accept”，则完成分析 4）若action[sm, ai]是“error”，则调用错误恢复
98
例 (1) E E + T (2) E T (3) T T F (4) T F
(5) F ( E ) (6) F id 状态 action goto id ( ) $ E T F s s4 1 s acc 2 r2 s r2 r2 3 r4 r r4 r4 4 … （书上149页图4-37）
99
栈 输 入 动 作 id id + id $ 移进 E E + T E T T T F T F F ( E )
状态 action goto id ( ) $ E T F s s4 … 3 r4 r r4 r4 5 r6 r r6 r6 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 id id + id $ 移进
100
栈 输 入 动 作 id id + id $ 移进 0 id 5 id + id $ E E + T E T
状态 action goto id ( ) $ E T F s s4 … 3 r4 r r4 r4 5 r6 r r6 r6 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 id id + id $ 移进 0 id 5 id + id $
101
栈 输 入 动 作 id id + id $ 移进 0 id 5 id + id $ 按F id归约 E E + T
状态 action goto id ( ) $ E T F s s4 … 3 r4 r r4 r4 5 r6 r r6 r6 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 id id + id $ 移进 0 id 5 id + id $ 按F id归约
102
栈 输 入 动 作 id id + id $ 移进 0 id 5 id + id $ 按F id归约 0 F 3
状态 action goto id ( ) $ E T F s s4 … 3 r4 r r4 r4 5 r6 r r6 r6 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 id id + id $ 移进 0 id 5 id + id $ 按F id归约 0 F 3
103
栈 输 入 动 作 id id + id $ 移进 0 id 5 id + id $ 按F id归约 0 F 3
状态 action goto id ( ) $ E T F s s4 … 3 r4 r r4 r4 5 r6 r r6 r6 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 id id + id $ 移进 0 id 5 id + id $ 按F id归约 0 F 3 按T F归约
104
栈 输 入 动 作 id id + id $ 移进 0 id 5 id + id $ 按F id归约 0 F 3
状态 action goto id ( ) $ E T F s s4 … 3 r4 r r4 r4 5 r6 r r6 r6 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 id id + id $ 移进 0 id 5 id + id $ 按F id归约 0 F 3 按T F归约 0 T 2
105
栈 输 入 动 作 0 T 2 id + id $ E E + T E T T T F T F F ( E )
状态 action goto id ( ) $ E T F … 2 r2 s r2 r2 5 r6 r r6 r6 7 s s4 10 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 T 2 id + id $
106
栈 输 入 动 作 0 T 2 id + id $ 移进 E E + T E T T T F T F
状态 action goto id ( ) $ E T F … 2 r2 s r2 r2 5 r6 r r6 r6 7 s s4 10 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 T 2 id + id $ 移进
107
栈 输 入 动 作 0 T 2 id + id $ 移进 0 T 2 7 id + id $ E E + T E T
状态 action goto id ( ) $ E T F … 2 r2 s r2 r2 5 r6 r r6 r6 7 s s4 10 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 T 2 id + id $ 移进 0 T 2 7 id + id $
108
栈 输 入 动 作 0 T 2 id + id $ 移进 0 T 2 7 id + id $ E E + T E T
状态 action goto id ( ) $ E T F … 2 r2 s r2 r2 5 r6 r r6 r6 7 s s4 10 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 T 2 id + id $ 移进 0 T 2 7 id + id $
109
栈 输 入 动 作 0 T 2 id + id $ 移进 0 T 2 7 id + id $ 0 T 2 7 id 5
状态 action goto id ( ) $ E T F … 2 r2 s r2 r2 5 r6 r r6 r6 7 s s4 10 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 T 2 id + id $ 移进 0 T 2 7 id + id $ 0 T 2 7 id 5 + id $
110
栈 输 入 动 作 0 T 2 id + id $ 移进 0 T 2 7 id + id $ 0 T 2 7 id 5
状态 action goto id ( ) $ E T F … 2 r2 s r2 r2 5 r6 r r6 r6 7 s s4 10 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 T 2 id + id $ 移进 0 T 2 7 id + id $ 0 T 2 7 id 5 + id $ 按F id归约
111
栈 输 入 动 作 0 T 2 id + id $ 移进 0 T 2 7 id + id $ 0 T 2 7 id 5
状态 action goto id ( ) $ E T F … 2 r2 s r2 r2 5 r6 r r6 r6 7 s s4 10 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 T 2 id + id $ 移进 0 T 2 7 id + id $ 0 T 2 7 id 5 + id $ 按F id归约 0 T 2 7 F 10
112
栈 输 入 动 作 0 T 2 7 F 10 + id $ E E + T E T T T F T F
状态 action goto id ( ) $ E T F s s4 1 s acc 2 r2 s r2 r2 … 10 r r r3 r3 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 T 2 7 F 10 + id $
113
栈 输 入 动 作 0 T 2 7 F 10 + id $ 按T TF归约 E E + T E T T T F
状态 action goto id ( ) $ E T F s s4 1 s acc 2 r2 s r2 r2 … 10 r r r3 r3 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 T 2 7 F 10 + id $ 按T TF归约
114
栈 输 入 动 作 0 T 2 7 F 10 + id $ 按T TF归约 0 T 2 E E + T E T
状态 action goto id ( ) $ E T F s s4 1 s acc 2 r2 s r2 r2 … 10 r r r3 r3 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 T 2 7 F 10 + id $ 按T TF归约 0 T 2
115
栈 输 入 动 作 0 T 2 7 F 10 + id $ 按T TF归约 0 T 2 按E T归约 E E + T
状态 action goto id ( ) $ E T F s s4 1 s acc 2 r2 s r2 r2 … 10 r r r3 r3 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 T 2 7 F 10 + id $ 按T TF归约 0 T 2 按E T归约
116
栈 输 入 动 作 0 T 2 7 F 10 + id $ 按T TF归约 0 T 2 按E T归约 0 E 1
状态 action goto id ( ) $ E T F s s4 1 s acc 2 r2 s r2 r2 … 10 r r r3 r3 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 T 2 7 F 10 + id $ 按T TF归约 0 T 2 按E T归约 0 E 1
117
栈 输 入 动 作 0 T 2 7 F 10 + id $ 按T TF归约 0 T 2 按E T归约 0 E 1 移进
状态 action goto id ( ) $ E T F s s4 1 s acc 2 r2 s r2 r2 … 10 r r r3 r3 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 T 2 7 F 10 + id $ 按T TF归约 0 T 2 按E T归约 0 E 1 移进
118
栈 输 入 动 作 0 T 2 7 F 10 + id $ 按T TF归约 0 T 2 按E T归约 0 E 1 移进
状态 action goto id ( ) $ E T F s s4 1 s acc 2 r2 s r2 r2 … 10 r r r3 r3 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 T 2 7 F 10 + id $ 按T TF归约 0 T 2 按E T归约 0 E 1 移进 0 E 1 + 6 id $
119
栈 输 入 动 作 0 E 1 + 6 id $ E E + T E T T T F T F F ( E )
状态 action goto id ( ) $ E T F … 3 r4 r r4 r4 5 r6 r r6 r6 6 s s4 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 E 1 + 6 id $
120
栈 输 入 动 作 0 E 1 + 6 id $ 移进 E E + T E T T T F T F F ( E )
状态 action goto id ( ) $ E T F … 3 r4 r r4 r4 5 r6 r r6 r6 6 s s4 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 E 1 + 6 id $ 移进
121
栈 输 入 动 作 0 E 1 + 6 id $ 移进 0 E 1 + 6 id 5 $ E E + T E T T T F
状态 action goto id ( ) $ E T F … 3 r4 r r4 r4 5 r6 r r6 r6 6 s s4 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 E 1 + 6 id $ 移进 0 E id 5 $
122
栈 输 入 动 作 0 E 1 + 6 id $ 移进 0 E 1 + 6 id 5 $ 按F id归约 E E + T E T
状态 action goto id ( ) $ E T F … 3 r4 r r4 r4 5 r6 r r6 r6 6 s s4 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 E 1 + 6 id $ 移进 0 E id 5 $ 按F id归约
123
栈 输 入 动 作 0 E 1 + 6 id $ 移进 0 E 1 + 6 id 5 $ 按F id归约 0 E 1 + 6 F 3
状态 action goto id ( ) $ E T F … 3 r4 r r4 r4 5 r6 r r6 r6 6 s s4 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 E 1 + 6 id $ 移进 0 E id 5 $ 按F id归约 0 E F 3
124
栈 输 入 动 作 0 E 1 + 6 id $ 移进 0 E 1 + 6 id 5 $ 按F id归约 0 E 1 + 6 F 3
状态 action goto id ( ) $ E T F … 3 r4 r r4 r4 5 r6 r r6 r6 6 s s4 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 E 1 + 6 id $ 移进 0 E id 5 $ 按F id归约 0 E F 3 按T F归约
125
栈 输 入 动 作 0 E 1 + 6 id $ 移进 0 E 1 + 6 id 5 $ 按F id归约 0 E 1 + 6 F 3
状态 action goto id ( ) $ E T F … 3 r4 r r4 r4 5 r6 r r6 r6 6 s s4 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 E 1 + 6 id $ 移进 0 E id 5 $ 按F id归约 0 E F 3 按T F归约 0 E T 9
126
栈 输 入 动 作 0 E 1 + 6 T 9 $ E E + T E T T T F T F F ( E )
状态 action goto id ( ) $ E T F s s4 1 s acc … 9 r1 s r1 r1 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 E T 9 $
127
栈 输 入 动 作 0 E 1 + 6 T 9 $ 按E E+T归约 E E + T E T T T F T F
状态 action goto id ( ) $ E T F s s4 1 s acc … 9 r1 s r1 r1 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 E T 9 $ 按E E+T归约
128
栈 输 入 动 作 0 E 1 + 6 T 9 $ 按E E+T归约 0 E 1 E E + T E T T T F
状态 action goto id ( ) $ E T F s s4 1 s acc … 9 r1 s r1 r1 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 E T 9 $ 按E E+T归约 0 E 1
129
栈 输 入 动 作 0 E 1 + 6 T 9 $ 按E E+T归约 0 E 1 接受 E E + T E T
状态 action goto id ( ) $ E T F s s4 1 s acc … 9 r1 s r1 r1 E E + T E T T T F T F F ( E ) F id 栈 输 入 动 作 0 E T 9 $ 按E E+T归约 0 E 1 接受
130
LR分析 最右推导的反向过程 若文法二义，分析表action的某些条目会包含多 个动作：移进-归约冲突，归约-归约冲突
解决冲突：(1) 重写文法 (2) 分析表中只留下一个 动作 LR(k)分析：由状态和接下来的k个输入符号决定 下一步是什么，一般k=0或1 LR(k)文法：LR(k)分析表的每个条目都是唯一的 如何构造LR分析表？ 三个著名变体：SLR(1), LR(1), LALR(1) (具体算法见书)
131
下面文法不是LR(1)的： L M L b | a M M b L a 句子abbb的分析树
132
LR语法分析中的错误恢复（1） LR语法分析器查询goto表时不会发现错误。 但是可能在查询action表时发现报错条目
假设栈中的符号串为α，当前输入符号为a；报错表示不可能存 在终结符号串x使得αax是一个最右句型。 恐慌模式的错误恢复策略 从栈顶向下扫描，找到状态s，s有一个对应于非终结符号A的 goto目标；（s之上的状态被丢弃） 在输入中读入并丢弃一些符号，直到找到一个可以合法跟在A之 后的符号a（不丢弃a）； 将goto(s,A)压栈；继续进行正常的语法分析。 基本思想：假定当前正在试图归约到A且碰到了语法错误。因此 设法扫描完包含语法错误的A的子串，假装找到了A的一个实例 A的选择可能很多
133
LR语法分析中的错误恢复（2） 短语层次的恢复
134
LR分析器的模型 输入 LR分析程序 输出 栈 action goto sm Xm Xm-1 … s0 a1 ai an $ 分析表
这实际上是一个下推自动机（Pushdown Automaton, PDA）
135
下推自动机（PDA） PDA = NFA + a stack read: pop; write: push
136
“Pushdown”
137
PDA CFG是上下文无关语言的描述方法 PDA是上下文无关语言的识别方法 CFG就像正则表达式，PDA就像有限自动机
两种方法证明一个语言是上下文无关语言： 1. 设计CFG，并证明它能产生该语言 2. 构造PDA，并证明它能识别该语言
138
栈带来的好处 栈：类似无限的存储空间 PDA可以识别非正则语言如 {0n1n | n 0} 有限自动机：有限的状态个数
139
识别{anbn | n 0}的PDA 读入输入字符 接受：输入结束，且栈为空 反之报错 每读入一个0，则将它入栈
每读入一个1，则出栈一个0 接受：输入结束，且栈为空 反之报错
140
到目前为止： 如何描述一个程序语言的语法结构？ 上下文无关文法（context-free grammar, CFG）
自顶向下，自底向上 如何保证生成的分析树唯一？（二义性问题） 给定CFG，如何快速构造语法分析器？ 语法分析器的生成器Yacc
141
语法分析器的生成器Yacc Yacc源程序 Yacc y.tab.c translate.y 编译器 C a.out 输出 输入
C语言写的LALR语法分析器 文法规范 Yacc 编译器 Yacc源程序 translate.y y.tab.c C a.out 输入 输出
142
Yacc源程序的结构 声明 翻译规则 辅助性C语言例程 分为可选的两节：第一节放置C声明， 第二节是对词法单元的声明
%% 翻译规则 辅助性C语言程序 声明 分为可选的两节：第一节放置C声明， 第二节是对词法单元的声明 翻译规则 指明产生式及相关联的语义动作 辅助性C语言例程 被直接拷贝到生成的C语言源程序中 可以在语义动作中调用 其中必须包括yylex()，这个函数返回 词法单元，可以由Lex生成
143
C声明、词法单元声明 翻译规则：产生式及相关联的语义动作 辅助性C语言例程
144
Yacc对于冲突的处理 Yacc使用LR分析(LALR)，当文法有二义时，生成 的分析表action将包含冲突 缺省的处理方法
对于归约-归约冲突，选择前面的产生式 对于移进-归约冲突，总是移进（悬空-else的解决） 用户可以声明终结符和产生式的优先级和结合性， 来解决移进-归约冲突
145
Yacc对于冲突的处理 声明终结符的优先级和结合性 %left ‘||’ %left ‘&&’
%noassoc ‘==’ ‘!=’ ‘<’ ‘>’ ‘<=’ ‘>=’ %left ‘+’ ‘’ %left ‘*’ ‘/’ 低优先级 高优先级
146
Yacc对于冲突的处理 产生式的优先级是它的最右终结符的优先级 指定产生式的优先级：%prec 终结符 …… %left ‘+’ ‘’
%right UMINUS %% expr : expr ‘+’ expr {$$ = $1 + $3; } | expr ‘’ expr {$$ = $1 $3; } | ‘’ expr %prec UMINUS {$$ = $2; } UMINUS具有最高优先级 这个产生式的优先级与UMINUS相同 -5+10看成是-(5+10), 还是(-5)+10? 取后者
147
本章小结 文法和语言的基本知识 分析方法：自顶向下，自底向上 二义性问题
Similar presentations
