语法分析 本章内容 语法分析器：把词法分析生成的词法单元流翻译成语法分析树（parse tree） 介绍上下文无关文法、自顶向下和自底向上的分析方法

语法分析器 词 法 分析器 token 源程序 分析树 前端的 其余部分 语 法分析器 中间表示 符号表 词 法 分析器 token getNextToken 源程序 分析树 前端的 其余部分 语 法分析器 中间表示 符号表 实际中，不需要显式地构造出语法分析树，语法分析和前 端的其余部分（类型检查、中间代码生成等）交错完成， 可以用一个模块来实现。

本章回答四个问题： 如何描述一个程序语言的语法结构？ 上下文无关文法（context-free grammar, CFG） 在词法分析中，正则表达式描述了词法结构 如何描述一个程序语言的语法结构？ 上下文无关文法（context-free grammar, CFG） 如何进行语法分析？即，给定CFG和词法单元流， 如何构造分析树？ 自顶向下，自底向上 如何保证生成的分析树唯一？（二义性问题） 给定CFG，如何快速构造语法分析器？ 语法分析器的生成器Yacc

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

上下文无关文法 上下文无关文法是四元组 (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  + | 

上下文无关文法 推导（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 * 不含非终结符的句型 所有句子的集合 生成相同语言

上下文无关文法 例 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)

上下文无关文法 分析树（parse tree）：推导的图形化表示，展 示了语言的层次结构，与推导顺序无关 例 E  E + E | E  E | (E ) |  E | id (id + id)的分析树 E  E ( E ) E + E id id 每棵分析树对应唯一的最左推导及唯一的最右推导！

二义性 例 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  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 两棵不同的分析树

消除二义性 方法一：消二义规则（disambiguating rules）， 如优先级（e.g. *比+具有更高的优先级） 

消除二义性 方法二：重写文法！

例 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（第一种推导）

无二义的文法 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

有二义的文法： 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

有二义的文法： 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

有二义的文法： 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

第四个例子 设计一个文法：字母表{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

其他的文法变换 消除左递归（在自顶向下分析中有用） 将 A  Aa | b 改写为 A  b A A a A | 

消除左递归 例 算术表达文法 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  | 

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

其他的文法变换 提取左公因子（在自顶向下分析中有用） 将 A  1 | 2 改写为 A   A A  1 | 2

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

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

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

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

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

正则表达式 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为文法的开始符号 每个正则语言都是一个上下文无关语言，反之不成立

正则表达式 vs 上下文无关文法 正则表达式能定义一些简单的语言，能表示给定 结构的固定次数的重复或者没有指定次数的重复 例：a (ba)5, a (ba)* 正则表达式不能用于描述配对或嵌套的结构 例：配对括号串的集合 每个正则语言都是一个上下文无关语言，反之不成立

正则表达式 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的路径

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

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

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

非上下文无关的语言 L1 = {wcw | w属于(a | b)*} L2 = {anbmcndm | n  0, m  0} 标识符的声明应先于其引用的抽象 L2 = {anbmcndm | n  0, m  0} 形参个数和实参个数应该相同的抽象 方法一：用上下文敏感文法 方法二：不在文法中描述，在语义分析阶段检查

语法分析 语法分析器：给定一个句子，构造该句子的推导 语法分析器都从左至右地扫描输入，但有不同的 方式构造分析树 词 法 分析器 token 词 法 分析器 token getNextToken 源程序 分析树 前端的 其余部分 语 法分析器 中间表示 符号表 语法分析器：给定一个句子，构造该句子的推导 语法分析器都从左至右地扫描输入，但有不同的 方式构造分析树 自顶向下：从根节点开始向叶节点构造 自底向上：从叶节点开始向根节点构造

自顶向下的语法分析 从文法的开始符号开始，猜测用哪个产生式推导 例 文法 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的第一个产生式 猜错了！回溯，试第二个产生式

自顶向下的语法分析 不能处理左递归 例 算术表达文法 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 … … …

自顶向下的语法分析 不能处理左递归 复杂的回溯技术 回溯导致语义工作推倒重来 难以报告出错的确切位置 效率低

自顶向下的语法分析 对文法加什么样的限制可以保证没有回溯？ LL(k)文法 书上：递归下降分析技术，针对LL(1)文法的预测 分析技术

自底向上的语法分析 构造分析树：从叶节点开始向上到根节点 总是构造最右推导 算法：移进-归约（shift-reduce） 将一个串w“归约”为文法开始符号 关键：寻找与某产生式右部相匹配的子串

归约 例 S  aABe A  Abc | b B  d

归约 例 S  aABe A  Abc | b B  d abbcde（读入ab） a b

归约 例 S  aABe A  Abc | b B  d abbcde aAbcde（归约） a b A

归约 例 S  aABe A  Abc | b B  d abbcde aAbcde（再读入bc） a b A c

归约 例 S  aABe A  Abc | b B  d abbcde aAbcde aAde（归约） a b A c

归约 例 S  aABe A  Abc | b B  d abbcde aAbcde aAde（再读入d） a b A d c

归约 a 例 S  aABe A  Abc | b B  d abbcde aAbcde aAde aABe（归约） b A d c

归约 a 例 S  aABe A  Abc | b B  d abbcde aAbcde aAde aABe(再读入e) e b A

归约 a 例 S  aABe A  Abc | b B  d abbcde aAbcde aAde aABe S（归约） S e b

归约 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

句柄（Handles） 句型的句柄是和某产生式右部匹配的子串，并且， 把它归约成该产生式左部的非终结符代表了最右 推导的一个反向步骤 S  aABe A  Abc | b B  d S rm aABe rm aAde rm aAbcde rm abbcde 句柄右边的串一定仅含终结符 如果文法二义，那么句柄可能不唯一

句柄（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中，句柄不唯一

句柄（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 无二义的文法，句柄唯一

移进-归约语法分析技术 使用一个栈 移进：将输入符号移进栈中，直到发现一个句柄 归约：对句柄进行归约 接受：栈中包含文法开始符号，无更多输入 报错：语法错误 下面以id1  id2 + id3为例

栈 输 入 动 作 $ id1  id2 + id3$

栈 输 入 动 作 $ id1  id2 + id3$ 移进

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约 按E  EE归约

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约 按E  EE归约

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约 按E  EE归约 接受

移进-归约 要想很好地使用移进归约方式，尚需解决一些 问题 如何决策选择移进还是归约 进行归约时，确定右句型中将要归约的子串 进行归约时，如何确定选择哪一个产生式

移进-归约分析中的冲突 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

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E  EE归约

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E  EE归约

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E  EE归约

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E  EE归约 $E+ id3$

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E  EE归约 $E+ id3$

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E  EE归约 $E+ id3$ $E+id3

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E  EE归约 $E+ id3$ $E+id3

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E  EE归约 $E+ id3$ $E+id3 $E+E

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E  EE归约 $E+ id3$ $E+id3 $E+E 按E  E+E归约

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E  EE归约 $E+ id3$ $E+id3 $E+E 按E  E+E归约

栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E  EE归约 $E+ id3$ $E+id3 $E+E 按E  E+E归约 接受

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$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约 按E  EE归约 接受 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE 按E  EE归约 $E+ id3$ $E+id3 $E+E 按E  E+E归约 接受

移进-归约分析中的冲突 1、移进归约冲突 例 stmt  if expr then stmt | if expr then stmt else stmt | other 如果移进归约分析器处于格局 栈 输入 … if expr then stmt else … $ if-then-else的优先级高于if-then（选择移进）

移进-归约分析中的冲突 归约成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 ?

移进-归约分析中的冲突 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 )… 需要修改上面的文法

LR分析 目前最流行的语法分析技术 LR(k)分析：移进-归约分析 特点 L：从左往右扫描输入 R：反向构造一个最右推导序列 k：向前看k个符号（通常k<=1, 缺省为1）以帮助做出 移进或归约的决定 特点 适用于一大类上下文无关文法（LR文法） 效率高

所有LR分析器的驱动程序是相同的，分析表可以不同 输入 LR分析程序 输出 栈 action goto sm Xm sm-1 Xm-1 … s0 a1 ai an $ 分析表 所有LR分析器的驱动程序是相同的，分析表可以不同

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决定下一步是什么 状态 文法符号 终结符

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”，则调用错误恢复

例 (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 s5 s4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 8 2 3 … （书上149页图4-37）

栈 输 入 动 作 id  id + id $ 移进 E  E + T E  T T  T  F T  F F  ( E ) 状态 action goto id +  ( ) $ E T F s5 s4 1 2 3 … 3 r4 r4 r4 r4 5 r6 r6 r6 r6 E  E + T E  T T  T  F T  F F  ( E ) F  id 栈 输 入 动 作 id  id + id $ 移进

栈 输 入 动 作 id  id + id $ 移进 0 id 5  id + id $ E  E + T E  T 状态 action goto id +  ( ) $ E T F s5 s4 1 2 3 … 3 r4 r4 r4 r4 5 r6 r6 r6 r6 E  E + T E  T T  T  F T  F F  ( E ) F  id 栈 输 入 动 作 id  id + id $ 移进 0 id 5  id + id $

栈 输 入 动 作 id  id + id $ 移进 0 id 5  id + id $ 按F  id归约 E  E + T 状态 action goto id +  ( ) $ E T F s5 s4 1 2 3 … 3 r4 r4 r4 r4 5 r6 r6 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归约

栈 输 入 动 作 id  id + id $ 移进 0 id 5  id + id $ 按F  id归约 0 F 3 状态 action goto id +  ( ) $ E T F s5 s4 1 2 3 … 3 r4 r4 r4 r4 5 r6 r6 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

栈 输 入 动 作 id  id + id $ 移进 0 id 5  id + id $ 按F  id归约 0 F 3 状态 action goto id +  ( ) $ E T F s5 s4 1 2 3 … 3 r4 r4 r4 r4 5 r6 r6 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归约

栈 输 入 动 作 id  id + id $ 移进 0 id 5  id + id $ 按F  id归约 0 F 3 状态 action goto id +  ( ) $ E T F s5 s4 1 2 3 … 3 r4 r4 r4 r4 5 r6 r6 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

栈 输 入 动 作 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 s7 r2 r2 5 r6 r6 r6 r6 7 s5 s4 10 E  E + T E  T T  T  F T  F F  ( E ) F  id 栈 输 入 动 作 0 T 2  id + id $

栈 输 入 动 作 0 T 2  id + id $ 移进 E  E + T E  T T  T  F T  F 状态 action goto id +  ( ) $ E T F … 2 r2 s7 r2 r2 5 r6 r6 r6 r6 7 s5 s4 10 E  E + T E  T T  T  F T  F F  ( E ) F  id 栈 输 入 动 作 0 T 2  id + id $ 移进

栈 输 入 动 作 0 T 2  id + id $ 移进 0 T 2  7 id + id $ E  E + T E  T 状态 action goto id +  ( ) $ E T F … 2 r2 s7 r2 r2 5 r6 r6 r6 r6 7 s5 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  id + id $ 移进 0 T 2  7 id + id $ E  E + T E  T 状态 action goto id +  ( ) $ E T F … 2 r2 s7 r2 r2 5 r6 r6 r6 r6 7 s5 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  id + id $ 移进 0 T 2  7 id + id $ 0 T 2  7 id 5 状态 action goto id +  ( ) $ E T F … 2 r2 s7 r2 r2 5 r6 r6 r6 r6 7 s5 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 $

栈 输 入 动 作 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 s7 r2 r2 5 r6 r6 r6 r6 7 s5 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  id + id $ 移进 0 T 2  7 id + id $ 0 T 2  7 id 5 状态 action goto id +  ( ) $ E T F … 2 r2 s7 r2 r2 5 r6 r6 r6 r6 7 s5 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

栈 输 入 动 作 0 T 2  7 F 10 + id $ E  E + T E  T T  T  F T  F 状态 action goto id +  ( ) $ E T F s5 s4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 … 10 r3 r3 r3 r3 E  E + T E  T T  T  F T  F F  ( E ) F  id 栈 输 入 动 作 0 T 2  7 F 10 + id $

栈 输 入 动 作 0 T 2  7 F 10 + id $ 按T  TF归约 E  E + T E  T T  T  F 状态 action goto id +  ( ) $ E T F s5 s4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 … 10 r3 r3 r3 r3 E  E + T E  T T  T  F T  F F  ( E ) F  id 栈 输 入 动 作 0 T 2  7 F 10 + id $ 按T  TF归约

栈 输 入 动 作 0 T 2  7 F 10 + id $ 按T  TF归约 0 T 2 E  E + T E  T 状态 action goto id +  ( ) $ E T F s5 s4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 … 10 r3 r3 r3 r3 E  E + T E  T T  T  F T  F F  ( E ) F  id 栈 输 入 动 作 0 T 2  7 F 10 + id $ 按T  TF归约 0 T 2

栈 输 入 动 作 0 T 2  7 F 10 + id $ 按T  TF归约 0 T 2 按E  T归约 E  E + T 状态 action goto id +  ( ) $ E T F s5 s4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 … 10 r3 r3 r3 r3 E  E + T E  T T  T  F T  F F  ( E ) F  id 栈 输 入 动 作 0 T 2  7 F 10 + id $ 按T  TF归约 0 T 2 按E  T归约

栈 输 入 动 作 0 T 2  7 F 10 + id $ 按T  TF归约 0 T 2 按E  T归约 0 E 1 状态 action goto id +  ( ) $ E T F s5 s4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 … 10 r3 r3 r3 r3 E  E + T E  T T  T  F T  F F  ( E ) F  id 栈 输 入 动 作 0 T 2  7 F 10 + id $ 按T  TF归约 0 T 2 按E  T归约 0 E 1

栈 输 入 动 作 0 T 2  7 F 10 + id $ 按T  TF归约 0 T 2 按E  T归约 0 E 1 移进 状态 action goto id +  ( ) $ E T F s5 s4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 … 10 r3 r3 r3 r3 E  E + T E  T T  T  F T  F F  ( E ) F  id 栈 输 入 动 作 0 T 2  7 F 10 + id $ 按T  TF归约 0 T 2 按E  T归约 0 E 1 移进

栈 输 入 动 作 0 T 2  7 F 10 + id $ 按T  TF归约 0 T 2 按E  T归约 0 E 1 移进 状态 action goto id +  ( ) $ E T F s5 s4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 … 10 r3 r3 r3 r3 E  E + T E  T T  T  F T  F F  ( E ) F  id 栈 输 入 动 作 0 T 2  7 F 10 + id $ 按T  TF归约 0 T 2 按E  T归约 0 E 1 移进 0 E 1 + 6 id $

栈 输 入 动 作 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 r4 r4 r4 5 r6 r6 r6 r6 6 s5 s4 9 3 E  E + T E  T T  T  F T  F F  ( E ) F  id 栈 输 入 动 作 0 E 1 + 6 id $

栈 输 入 动 作 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 r4 r4 r4 5 r6 r6 r6 r6 6 s5 s4 9 3 E  E + T E  T T  T  F T  F F  ( E ) F  id 栈 输 入 动 作 0 E 1 + 6 id $ 移进

栈 输 入 动 作 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 r4 r4 r4 5 r6 r6 r6 r6 6 s5 s4 9 3 E  E + T E  T T  T  F T  F F  ( E ) F  id 栈 输 入 动 作 0 E 1 + 6 id $ 移进 0 E 1 + 6 id 5 $

栈 输 入 动 作 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 r4 r4 r4 5 r6 r6 r6 r6 6 s5 s4 9 3 E  E + T E  T T  T  F T  F F  ( E ) F  id 栈 输 入 动 作 0 E 1 + 6 id $ 移进 0 E 1 + 6 id 5 $ 按F  id归约

栈 输 入 动 作 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 r4 r4 r4 5 r6 r6 r6 r6 6 s5 s4 9 3 E  E + T E  T T  T  F T  F F  ( E ) F  id 栈 输 入 动 作 0 E 1 + 6 id $ 移进 0 E 1 + 6 id 5 $ 按F  id归约 0 E 1 + 6 F 3

栈 输 入 动 作 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 r4 r4 r4 5 r6 r6 r6 r6 6 s5 s4 9 3 E  E + T E  T T  T  F T  F F  ( E ) F  id 栈 输 入 动 作 0 E 1 + 6 id $ 移进 0 E 1 + 6 id 5 $ 按F  id归约 0 E 1 + 6 F 3 按T  F归约

栈 输 入 动 作 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 r4 r4 r4 5 r6 r6 r6 r6 6 s5 s4 9 3 E  E + T E  T T  T  F T  F F  ( E ) F  id 栈 输 入 动 作 0 E 1 + 6 id $ 移进 0 E 1 + 6 id 5 $ 按F  id归约 0 E 1 + 6 F 3 按T  F归约 0 E 1 + 6 T 9

栈 输 入 动 作 0 E 1 + 6 T 9 $ E  E + T E  T T  T  F T  F F  ( E ) 状态 action goto id +  ( ) $ E T F s5 s4 1 2 3 1 s6 acc … 9 r1 s7 r1 r1 E  E + T E  T T  T  F T  F F  ( E ) F  id 栈 输 入 动 作 0 E 1 + 6 T 9 $

栈 输 入 动 作 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 s5 s4 1 2 3 1 s6 acc … 9 r1 s7 r1 r1 E  E + T E  T T  T  F T  F F  ( E ) F  id 栈 输 入 动 作 0 E 1 + 6 T 9 $ 按E  E+T归约

栈 输 入 动 作 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 s5 s4 1 2 3 1 s6 acc … 9 r1 s7 r1 r1 E  E + T E  T T  T  F T  F F  ( E ) F  id 栈 输 入 动 作 0 E 1 + 6 T 9 $ 按E  E+T归约 0 E 1

栈 输 入 动 作 0 E 1 + 6 T 9 $ 按E  E+T归约 0 E 1 接受 E  E + T E  T 状态 action goto id +  ( ) $ E T F s5 s4 1 2 3 1 s6 acc … 9 r1 s7 r1 r1 E  E + T E  T T  T  F T  F F  ( E ) F  id 栈 输 入 动 作 0 E 1 + 6 T 9 $ 按E  E+T归约 0 E 1 接受

LR分析 最右推导的反向过程 若文法二义，分析表action的某些条目会包含多 个动作：移进-归约冲突，归约-归约冲突 解决冲突：(1) 重写文法 (2) 分析表中只留下一个 动作 LR(k)分析：由状态和接下来的k个输入符号决定 下一步是什么，一般k=0或1 LR(k)文法：LR(k)分析表的每个条目都是唯一的 如何构造LR分析表？ 三个著名变体：SLR(1), LR(1), LALR(1) (具体算法见书)

下面文法不是LR(1)的： L  M L b | a M   M b L a  句子abbb的分析树

LR语法分析中的错误恢复（1） LR语法分析器查询goto表时不会发现错误。 但是可能在查询action表时发现报错条目 假设栈中的符号串为α，当前输入符号为a；报错表示不可能存 在终结符号串x使得αax是一个最右句型。 恐慌模式的错误恢复策略 从栈顶向下扫描，找到状态s，s有一个对应于非终结符号A的 goto目标；（s之上的状态被丢弃） 在输入中读入并丢弃一些符号，直到找到一个可以合法跟在A之 后的符号a（不丢弃a）； 将goto(s,A)压栈；继续进行正常的语法分析。 基本思想：假定当前正在试图归约到A且碰到了语法错误。因此 设法扫描完包含语法错误的A的子串，假装找到了A的一个实例 A的选择可能很多

LR语法分析中的错误恢复（2） 短语层次的恢复

LR分析器的模型 输入 LR分析程序 输出 栈 action goto sm Xm Xm-1 … s0 a1 ai an $ 分析表 这实际上是一个下推自动机（Pushdown Automaton, PDA）

下推自动机（PDA） PDA = NFA + a stack read: pop; write: push

“Pushdown”

PDA CFG是上下文无关语言的描述方法 PDA是上下文无关语言的识别方法 CFG就像正则表达式，PDA就像有限自动机 两种方法证明一个语言是上下文无关语言： 1. 设计CFG，并证明它能产生该语言 2. 构造PDA，并证明它能识别该语言

栈带来的好处 栈：类似无限的存储空间 PDA可以识别非正则语言如 {0n1n | n  0} 有限自动机：有限的状态个数

识别{anbn | n  0}的PDA 读入输入字符 接受：输入结束，且栈为空 反之报错 每读入一个0，则将它入栈 每读入一个1，则出栈一个0 接受：输入结束，且栈为空 反之报错

到目前为止： 如何描述一个程序语言的语法结构？ 上下文无关文法（context-free grammar, CFG） 自顶向下，自底向上 如何保证生成的分析树唯一？（二义性问题） 给定CFG，如何快速构造语法分析器？ 语法分析器的生成器Yacc   

语法分析器的生成器Yacc Yacc源程序 Yacc y.tab.c translate.y 编译器 C a.out 输出 输入 C语言写的LALR语法分析器 文法规范 Yacc 编译器 Yacc源程序 translate.y y.tab.c C a.out 输入 输出

Yacc源程序的结构 声明 翻译规则 辅助性C语言例程 分为可选的两节：第一节放置C声明， 第二节是对词法单元的声明 %% 翻译规则 辅助性C语言程序 声明 分为可选的两节：第一节放置C声明， 第二节是对词法单元的声明 翻译规则 指明产生式及相关联的语义动作 辅助性C语言例程 被直接拷贝到生成的C语言源程序中 可以在语义动作中调用 其中必须包括yylex()，这个函数返回 词法单元，可以由Lex生成

C声明、词法单元声明 翻译规则：产生式及相关联的语义动作 辅助性C语言例程

Yacc对于冲突的处理 Yacc使用LR分析(LALR)，当文法有二义时，生成 的分析表action将包含冲突 缺省的处理方法 对于归约-归约冲突，选择前面的产生式 对于移进-归约冲突，总是移进（悬空-else的解决） 用户可以声明终结符和产生式的优先级和结合性， 来解决移进-归约冲突

Yacc对于冲突的处理 声明终结符的优先级和结合性 %left ‘||’ %left ‘&&’ %noassoc ‘==’ ‘!=’ ‘<’ ‘>’ ‘<=’ ‘>=’ %left ‘+’ ‘’ %left ‘*’ ‘/’ 低优先级 高优先级

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? 取后者

本章小结 文法和语言的基本知识 分析方法：自顶向下，自底向上 二义性问题