chaper 4 - 语词法分析 2019-2.pdf

4.6 LR语法分析技术 • LR(k)语法分析概念 – L表示对输入串进行从左到右扫描，R表示最右推导的逆过程； – k表示最多向前看k个符号； • 当k的数量增大时，语法分析器的规模将急剧增大； – k=0：向前看符就是当前输入符。 – k=1，向前看符多了FOLLOW(A)。 FOLLOW(A)：向前看符号。针对文法，而不是针对输入串。 4.6 LR语法分析技术介绍：SLR技术文法： E→ E + T | T T→ T * F | F F→ (E) | id 栈：＄ E→ E + T E→ T T→ T * F T→ F F→ (E) F→ id 规约：栈顶的句柄从栈中弹出，然后将对应产生式的头部压入栈中因此入栈的符号既有终结符id，*，+，（，），也有非终结符E，T，F，对每个产生式，我们来跟踪栈中句柄的满足程度。开始时，栈为空增广文法 E→ E + T E→ T T→ T * F T→ F F→ (E) F→ id E E +T E + T F T F id F id id 对文法的开始符号S，加一个产生式：S' S。只有发生这个规约，才说进入接受状态。原因在于出现E并不代表树生成完毕。为什么EE+T这个规约并不代表进入接受状态，因为id+id+id, 就会有两次EE+T规约，然后才进入接受状态。 E'E 移入-规约决策问题研究的切入点 ——LR(0)项目  在LR分析中，每一次归约都以一条产生式为依据。  对于产生式：AXYZ ，从时间概念上看，要X，Y，Z依次进栈，最终紧挨，在栈顶。  为了区分不同的时间点，可在文法G的每个产生式的右部添加一个圆点，称为文法G的LR(0)项目。  圆点前面代表“历史”（已识别的串），圆点后面代表“期待”  对产生式：AXYZ，共有四个LR(0)项目： AXYZ， AXYZ， AXYZ， AXYZ LR(0)项目的闭包——项集 E→ E + T E→ T T→ T * F T→ F F→ (E) F→ id 项集I0 E'→E ：当E'→E归约要发生时，语法分析完成。 E'→E E→ E + T E→ T E'→E E→ E + T E→ T T→ T * F T→  F E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) F→ id 闭包：直接关系，间接关系，所有可能的情形。 E'→E：期待E的出现。加进来的这些LR(0)项目，都会助推E的出现。推广：项集I的闭包。CLOSURE(I). 对LR(0)项目的闭包的理解项集I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) F→ id 期待E的出现。E的出现，又取决于T的出现。T的出现，又取决于F 的出现。F的出现，又要首先出现（或者id。再倒过来，id出现，就可规约出F。F的出现，就可规约出T。T的出现，就可规约出E。E的出现，就可能规约出E'. 项集I的GOTO函数: GOTO(I，X) 对一个项集合I，当一个符号X（终结符，和非终结符）进栈时，该项集发生的变迁。项集I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) F→ id GOTO(I0，E) = E'→E E→ E + T 的闭包 GOTO(I0，T) = E→ T T→ T * F 的闭包 GOTO(I0，（) = F→ (E) 的闭包 GOTO(I0，id) = F→ id 的闭包 GOTO(I0，F) = T→ F 的闭包 LR(0)自动机(DFA)的构建项集I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) F→ id 项集族内核项非内核项 I1 = GOTO(I0，E) = E'→E E→ E + T 的闭包 I2 =GOTO(I0，T) = E→ T T→ T * F 的闭包 I3 =GOTO(I0，F) = T→ F 的闭包 I4 =GOTO(I0，（) = F→ (E) 的闭包 I5 =GOTO(I0，id) = 的闭包 F→ id LR(0)自动机(DFA)的构建内核项项集I1 E'→E E→ E + T I6 = GOTO(I1，+) = E→ E + T 注意：求项集I1的闭包，不会增加新的非内核项非内核项的闭包 E→ E + T T→ T * F T→  F F→ (E) F→ id LR(0)自动机(DFA)的构建内核项项集I6 E→ E + T T→ T * F T→  F F→ (E) F→ id 非内核项 I9=GOTO(I6，T) = E→ E + T T→ T * F 的闭包 GOTO(I6，F) = T→ F =I3 GOTO(I6，( ) = F→ (E) =I4 GOTO(I6，id) = F→ id =I5 LR(0)自动机(DFA)的构建项集I2 E→ T T→ T * F 内核项 I7 = GOTO(I2，*) = T→ T * F 非内核项的闭包 T→ T * F F→ (E) F→ id LR(0)自动机(DFA)的构建项集I7 T→ T * F F→ (E) F→ id 内核项非内核项 I10 = GOTO(I7，F) = T→ T * F 的闭包 GOTO(I7，（) = F→ (E) =I4 GOTO(I7，id) = =I5 F→ id LR(0)自动机(DFA)的构建内核项项集I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ (E) F→ id I8=GOTO(I4，E) = F→ (E) E→ E + T 非内核项的闭包 GOTO(I4，T) = E→ T T→ T * F =I2 GOTO(I4，F ) = T→ F =I3 GOTO(I4，( ) = F→ (E) =I4 GOTO(I4，id) = =I5 F→ id LR(0)自动机(DFA)的构建项集I8 F→ (E) E→ E + T 内核项 I11=GOTO(I8，）) = F→ (E) GOTO(I8，+) = E→ E+ T 非内核项的闭包 =I6 I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) F→ id E I1 E'→E E→ E + T T I2 E→T T→ T * F T id I5 F→ id id ( ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ (E) F→ id F I3 T→ F  + * id id E ( T I6 E→ E + T T→ T * F T→  F + F→ (E) F→ id * I7 T→ T * F F→ (E) F→ id I8 F→ (E ) E→ E + T ) I9 E→ E + T T→ T * F F I10 T→ T * F  I11 F→ (E)  ( F LR(0)自动机有哪些规律特征？观察分析LR(0)的DFA，然后思考和总结出7个规律特征得出了LR(0)的DFA，我们来观察与分析，看有什么规律和特征。 E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) F→ id I1 E'→E E→ E + T + $ Accept T I2 E→T T→ T * F T id I5 F→ id * id id id ( ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  E ( T I6 E→ E + T T→ T * F T→  F + F→ (E) F→ id I7 T→ T * F F→ (E) F→ id ) I8 F→ (E ) E→ E + T * I9 E→ E + T T→ T * F F I10 T→ T * F  I11 F→ (E)  ( F 移入状态句柄尚未形成 E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) F→ id I1 E'→E E→ E + T + $ Accept T I2 E→T T→ T * F T id I5 F→ id * id id ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  E ( * I7 T→ T * F F→ (E) F→ id id ( T I6 E→ E + T T→ T * F T→  F + F→ (E) F→ id I8 F→ (E ) E→ E + T ) I9 E→ E + T T→ T * F F I10 T→ T * F  I11 F→ (E)  ( F 归约状态句柄已形成 E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) F→ id I1 E'→E E→ E + T + $ Accept T I2 E→T T→ T * F T id * id id I5 F→ id ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  E ( ( F * I7 T→ T * F F→ (E) F→ id id ( T I6 E→ E + T T→ T * F T→  F + F→ (E) F→ id I8 F→ (E ) E→ E + T ) I9 E→ E + T T→ T * F F I10 T→ T * F  I11 F→ (E)  既有移入，又有归约的状态自然也是有冲突的状态 E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) F→ id I1 E'→E E→ E + T + $ Accept T I2 E→T T→ T * F T id I5 F→ id * id id ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  E ( ( F * I7 T→ T * F F→ (E) F→ id id ( T I6 E→ E + T T→ T * F T→  F + F→ (E) F→ id I8 F→ (E ) E→ E + T ) I9 E→ E + T T→ T * F F I10 T→ T * F  I11 F→ (E)  LR(0)自动机不同的状态，在某个变迁符驱动下，变迁到同一状态 E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) F→ id I1 E'→E E→ E + T + $ Accept T I2 E→T T→ T * F T id * id id I5 F→ id ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  E ( * I7 T→ T * F F→ (E) F→ id id ( T I6 E→ E + T T→ T * F T→  F + F→ (E) F→ id I8 F→ (E ) E→ E + T ) I9 E→ E + T T→ T * F F I10 T→ T * F  I11 F→ (E)  ( F FIRST(E) = {（, id }; E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) F→ id I1 E'→E E→ E + T + $ Accept T I2 E→T T→ T * F T id * id id I5 F→ id ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  E ( * I7 T→ T * F F→ (E) F→ id id ( T I6 E→ E + T T→ T * F T→  F + F→ (E) F→ id I8 F→ (E ) E→ E + T ) I9 E→ E + T T→ T * F F I10 T→ T * F  I11 F→ (E)  ( F FIRST(T) =？ E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) F→ id I1 E'→E E→ E + T + $ Accept T I2 E→T T→ T * F T id * id id I5 F→ id ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  E ( * I7 T→ T * F F→ (E) F→ id id ( T I6 E→ E + T T→ T * F T→  F + F→ (E) F→ id I8 F→ (E ) E→ E + T ) I9 E→ E + T T→ T * F F I10 T→ T * F  I11 F→ (E)  ( F FIRST(F) =？ E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) F→ id I1 E'→E E→ E + T + $ Accept T I2 E→T T→ T * F T id * id id I5 F→ id ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  E ( * I7 T→ T * F F→ (E) F→ id id ( T I6 E→ E + T T→ T * F T→  F + F→ (E) F→ id I8 F→ (E ) E→ E + T ) I9 E→ E + T T→ T * F F I10 T→ T * F  I11 F→ (E)  ( F FOLLOW(E) = {), +, $}; E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) F→ id I1 E'→E E→ E + T + $ Accept T I2 E→T T→ T * F T id * id id I5 F→ id ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  E ( * I7 T→ T * F F→ (E) F→ id id ( T I6 E→ E + T T→ T * F T→  F + F→ (E) F→ id I8 F→ (E ) E→ E + T ) I9 E→ E + T T→ T * F F I10 T→ T * F  I11 F→ (E)  ( F FOLLOW(T) = ？来自2方面: {*} + FOLLOW(E); E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) F→ id I1 E'→E E→ E + T T + I2 E→T T→ T * F T id I5 F→ id * id id ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  E ( * I7 T→ T * F F→ (E) F→ id id ( T I6 E→ E + T T→ T * F T→  F + F→ (E) F→ id I8 F→ (E ) E→ E + T ) I9 E→ E + T T→ T * F F I10 T→ T * F  I11 F→ (E)  ( F CLOSURE(核心项), 对应于求了FIRST( )，还扩充了非终结符 E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) F→ id I1 E'→E E→ E + T + $ Accept T I2 E→T T→ T * F T id * id id I5 F→ id ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  E ( ( F * I7 T→ T * F F→ (E) F→ id id ( T I6 E→ E + T T→ T * F T→  F + F→ (E) F→ id I8 F→ (E ) E→ E + T I9 E→ E + T T→ T * F F ) I10 T→ T * F  I11 F→ (E)  在一个状态的核心项中，如果某个非终结符号的产生式多于一项，说明其有左公因子文法的LR(0)项集构成的DFA E I0 E'→E E→ E + E E→ E*E E→ (E) E→ id I1 E'→E E→ E + E E→ E*E + $ accept * id I3 E→ id id ( I2 F→ (E) E→ E + E E→ E*E E→ (E) E→ id I5 E→ E*E E→ E + E E→ E*E E→ (E) E→ id + + + * E * * I7 E→ E + E E→ E + E E→ E*E I8 E→ E * E E→ E + E E→ E*E E ( ( I6 F→ (E ) E→ E + E E→ E*E EE+E EE*E E(E) Eid I1，I6，I7，I8的核心项中，E的产生式多于一项， id id ( E I4 E→ E + E E→ E + E E→ E*E E→ (E) E→ id 说明有左公因子！ ) I9 E→ (E)  LR与LL的对比 因此LL和LR没有本质区别，只是过程和形式不同而已。 LR的DFA表达了历史和过程，自然体现出了左公因子，和左递归; 没有提取左公因子和消除左递归的问题；但引入了建立DFA的过程； LR比LL的优点是什么？基于状态为LR(0)项集的DFA的语法分析例子文法： E→ E + T | T T→ T * F | F F→ (E) | id 输入串： id + id *id E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) T F→ id I1 E'→E E→ E + T + I6 E→ E + T T→ T * F T→  F F→ (E) + F→ id Accept I2 T E→T T→ T * F id I5 F→ id id ( ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  * id id E I7 T→ T * F F→ (E) F→ id I8 F→ (E ) E→ E + T T * F ) I9 E→ E + T T→ T * F 起始状态：输入串： id + id *id$ I10 T→ T * F  状态栈： 0 I11 F→ (E)  id + id *id$ ( 状态栈： 05 F 第1步：移入 ( E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) T F→ id I1 E'→E E→ E + T + I6 E→ E + T T→ T * F T→  F F→ (E) F→ id Accept I2 T E→T T→ T * F id I5 F→ id id ( ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  * id id E ( I7 T→ T * F F→ (E) F→ id T * F I9 E→ E + T T→ T * F I10 T→ T * F  状态栈： 05 归约 0 I8 F→ (E ) E→ E + T ) F I11 F→ (E)  GOTO 03 ( F 第2步：归约 E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) T F→ id I1 E'→E E→ E + T + I6 E→ E + T T→ T * F T→  F F→ (E) F→ id Accept I2 T E→T T→ T * F id I5 F→ id id ( ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  * id id E ( I7 T→ T * F F→ (E) F→ id T * F I9 E→ E + T T→ T * F I10 T→ T * F  状态栈： 03 归约 0 I8 F→ (E ) E→ E + T ) T I11 F→ (E)  GOTO 02 ( F 第3步：归约 E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) T F→ id I1 E'→E E→ E + T I2 T E→T T→ T * F id I5 F→ id id ( ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  + I6 E→ E + T T→ T * F T→  F F→ (E) F→ id * id id E ( I7 T→ T * F F→ (E) F→ id T * F I9 E→ E + T T→ T * F I10 T→ T * F  状态栈： 02 归约 0 I8 F→ (E ) E→ E + T ) E I11 F→ (E)  GOTO 01 ( F 第4步：归约 E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) T F→ id I1 E'→E E→ E + T I2 T E→T T→ T * F id I5 F→ id id ( ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  + I6 E→ E + T T→ T * F T→  F F→ (E) F→ id * id id E ( ( F I7 T→ T * F F→ (E) F→ id I8 F→ (E ) E→ E + T T I9 E→ E + T T→ T * F id + id *id$ * F I10 T→ T * F  状态栈： 016 第5步：移入 ) I11 F→ (E)  id + id *id$ 状态栈： 0165 第6步：移入 E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) T F→ id I1 E'→E E→ E + T I2 T E→T T→ T * F id I5 F→ id id ( ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  + I6 E→ E + T T→ T * F T→  F F→ (E) F→ id * id id E ( I7 T→ T * F F→ (E) F→ id T * F I9 E→ E + T T→ T * F I10 T→ T * F  状态栈： 0165 归约 016 I8 F→ (E ) E→ E + T ) F I11 F→ (E)  GOTO 0163 ( F 第7步：归约 E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) T F→ id I1 E'→E E→ E + T + I6 E→ E + T T→ T * F T→  F F→ (E) F→ id Accept I2 T E→T T→ T * F id I5 F→ id id ( ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  * id id E ( I7 T→ T * F F→ (E) F→ id T * F I9 E→ E + T T→ T * F I10 T→ T * F  状态栈： 0163 归约 016 I8 F→ (E ) E→ E + T ) T I11 F→ (E)  GOTO 0169 ( F 第8步：归约 E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) T F→ id I1 E'→E E→ E + T I2 T E→T T→ T * F id I5 F→ id id ( ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  + I6 E→ E + T T→ T * F T→  F F→ (E) F→ id * id id E ( ( F I7 T→ T * F F→ (E) F→ id I8 F→ (E ) E→ E + T T I9 E→ E + T T→ T * F id + id *id$ * F I10 T→ T * F  状态栈： 01697 第9步：移入 ) I11 F→ (E)  id + id *id$ 状态栈： 016975 第10步：移入 E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) T F→ id I1 E'→E E→ E + T I2 T E→T T→ T * F id I5 F→ id id ( ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  + I6 E→ E + T T→ T * F T→  F F→ (E) F→ id * id id E ( I7 T→ T * F F→ (E) F→ id I8 F→ (E ) E→ E + T T * F ) I9 E→ E + T T→ T * F I10 T→ T * F  状态栈： 016975 归约 01697 F I11 F→ (E)  GOTO 0169710 ( F 第11步：归约 E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) T F→ id I1 E'→E E→ E + T I2 T E→T T→ T * F id I5 F→ id id ( ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  + I6 E→ E + T T→ T * F T→  F F→ (E) F→ id * id id E ( ( F I7 T→ T * F F→ (E) F→ id T I9 E→ E + T T→ T * F * F 状态栈： 0169710 归约 I10 T→ T * F  016 T I8 F→ (E ) E→ E + T ) I11 F→ (E)  GOTO 0169 第12步：归约归约的右部有3个符号，因此要弹出3个状态 E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) T F→ id I1 E'→E E→ E + T I2 T E→T T→ T * F id I5 F→ id id ( ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  + I6 E→ E + T T→ T * F T→  F F→ (E) F→ id * id id E ( ( F I7 T→ T * F F→ (E) F→ id T * F I9 E→ E + T T→ T * F 状态栈： 0169 归约 I10 T→ T * F  0 E I8 F→ (E ) E→ E + T ) I11 F→ (E)  GOTO 01 第13步：归约归约的右部有3个符号，因此要弹出3个状态 E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) T F→ id I1 E'→E E→ E + T + I6 E→ E + T T→ T * F T→  F F→ (E) F→ id $ Accept I2 T E→T T→ T * F id I5 F→ id id ( ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  * id id E ( ( F I7 T→ T * F F→ (E) F→ id I8 F→ (E ) E→ E + T T * F I9 E→ E + T T→ T * F I10 T→ T * F  01 Accept ) I11 F→ (E)  E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) F→ id I1 E'→E E→ E + T + $ Accept T I2 E→T T→ T * F T id * id id I5 F→ id ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  E ( * I7 T→ T * F F→ (E) F→ id id ( T I6 E→ E + T T→ T * F T→  F + F→ (E) F→ id I8 F→ (E ) E→ E + T ) I9 E→ E + T T→ T * F F I10 T→ T * F  I11 F→ (E)  ( F FOLLOW(T) = ？来自2方面: {*} + FOLLOW(E); 4.6.3 LR语法分析算法 • LR语法分析器的结构输入串 sm sm-1 a1 a1 .... ai .... an ＄ LR语法分析程序分析程序根据栈顶状态、当前输入符、分析表确定语法分析动作输出 ... s0 ＄状态栈 ACTION GOTO 文法 LR语法分析表 E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) T F→ id I1 E'→E E→ E + T + I6 E→ E + T T→ T * F T→  F F→ (E) F→ id $ Accept I2 T E→T T→ T * F id I5 F→ id id ( ( F I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  * id id E ( ( I7 T→ T * F F→ (E) F→ id T * F I9 E→ E + T T→ T * F I10 T→ T * F  ACTION(si , a) T si：状态id； 0169 a：当前输入符  移入状态sj；  规约Aβ；  接受； I8 F→ (E ) E→ E + T ) I11 F→ (E)   报错；归约之后： GOTO(si , A)=sj F A：非终结符移入与归约冲突的解决 E I0 E'→E E→ E + T E→ T T→ T * F T→  F T F→ (E) F→ id id I6 T E→ E + T T→ T * F T→  F F→ (E) F→ id * I7 F T→ T * F F→ (E) id F→ id id + I1 E'→E E→ E + T $ ACCEPT I2 E→T * T T→ T * F I5 F→ id id I4 ( F→ (E) ( E→ E + T E→ T T→ T * F T→  F F→ id F F I3 T→ F  E ( ( F ) I8 F→ (E ) E→ E + T I9 E→ E + T T→ T * F id + id *id$ I10 T→ T * F  第9步：移入? 还是归约？状态栈： 0169 FOLLOW(E)={),+,$} I11 F→ (E)  现在当前输入符为'*', 因此不能归约；移入的话，须要当前输入符为'*', 现正是。特征发现 E→ E + T | T 文法： T→ T * F | F F→ (E) | id 输入串： id + id *id 当前输入符仅仅只有在要规约时，当前输入符才关联上规约产生式左部符号的FOLLOW( ) 对于格局：E+T *id 因为：FOLLOW(E)={+,), $} 所以，按E→ E + T归约不行，按E→ T归约也不行只好移入 E+T* id 句柄 SLR(1)语法分析与SLR(1)文法在LR(0)项集的DFA基础上，再补充利用 FOLLOW( )来解决冲突问题（移入与规约的冲突，规约与规约的冲突）：简单LR(1)语法分析，简称为SLR(1)。 E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) T F→ id T I6 E→ E + T T→ T * F + T→  F F→ (E) F→ id * I7 * T→ T * F F + I1 E'→E E→ E + T $ Accept I2 E→T T T→ T * F id ( ( F I5 F→ id id I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  id id E ( I9 E→ E + T T→ T * F ) I8 F→ (E ) E→ E + T F 对于移入与归约冲突: FOLLOW(E) = ｛ ),+, $｝ FOLLOW(T) = ｛*, ), +, $｝ FOLLOW(F) = ｛*, ), +, $｝ ① E→ E + T ② E→ T ③ T→ T * F ④ T→F ⑤ F→ (E) ⑥ F→ id I10 T→ T * F  F→ (E) F→ id ( 文法： I11 F→ (E)  3 1 3 1 3 1 SLR(1)语法分析表 ACTION 状态 0 1 2 3 4 5 6 7 id s5 s5 s5 s5 + * s6 r2 r4 s7 r4 r6 r6 ( s4 s4 s4 s4 GOTO ) ＄ acc r2 r2 r4 r4 r6 r6 E 1 T 2 F 3 8 2 3 9 3 10 文法G的SLR(1)语法分析表文法G： ① E→ E + T ② E→ T ③ T→ T * F ④ T→F ⑤ F→ (E) ⑥ F→ id ACTION 状态 id 0 + * s5 ( GOTO ) ＄ s4 1 s6 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 6 FOLLOW(E) = ｛ ),+, $｝ 7 FOLLOW(T) = ｛*, ), +, $｝ FOLLOW(F) = ｛*, ), +, $｝ 8 9 s4 r6 T F 1 2 3 8 2 3 9 3 acc s5 5 E r6 r6 s5 s4 s5 s4 s6 r6 10 s11 r1 s7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 FOLLOW( )在SLR(1)和LL(1)中应用对比都是解决选择问题。 在SLR(1)中是解决冲突（归约与移入冲突，归约与归约冲突）的问题； 在LL(1)中是解决A与A的选择问题；概念与关系  由ACTION和GOTO函数组成的语法分析表叫文法G的 SLR(1)分析表；  使用G的SLR(1)分析表的LR语法分析器叫G的SLR(1) 语法分析器；  一个具有SLR(1)语法分析表的文法叫做SLR(1)文法；  每个SLR(1)文法都是无二义的，但反过来不成立。 SLR(1)语法分析程序 ① 令a为输入串w＄的第一个符号； ② 栈为＄0； ③ while （true） { ④ 令s是栈顶状态； ⑤ if (ACTION（s,a) = 移入状态t） { ⑥ 将状态t压入栈中； ⑦ 令a为下一个输入符号； ⑧ } else if (ACTION（s,a) = 归约Aβ） { ⑨ 从栈中弹出｜β｜个符号； ⑩ 令t为当前的栈顶状态； ⑪ 将GOTO(t, A)压入栈中； ⑫ 输出产生式Aβ； ⑬ } else if (ACTION（s,a) = 接受） ⑭ break; ⑮ else 调用错误恢复例程； ⑯ } E I0 E'→E E→ E + T E→ T T→ T * F T→  F F→ (E) T F→ id + I1 E'→E E→ E + T I2 T E→T T→ T * F id ( ( F I5 F→ id id I4 F→ (E) E→ E + T E→ T T→ T * F T→  F F→ id F I3 T→ F  输入串: id*id+id$ 格局： T*F +id$ * id id E ( T I6 E→ E + T T→ T * F T→  F F→ (E) F→ id * I7 T→ T * F F I9 E→ E + T T→ T * F ) I8 F→ (E ) E→ E + T I11 F→ (E)  F→ (E) F→ id I10 T→ T * F  ( F 栈中也可以是DFA的状态号 0-2-7-10 +id$ 可行前缀 E→ E + T | T 文法： T→ T * F | F F→ (E) | id 输入串： (id + id) *id 句柄 (E )*id (E+ id)*id (E+id )*id (E+F )*id (E+T )*id 归约移入移入规约规约归约 (E) *id 移入规约移入 F *id (E)* id 对于出现在栈顶的句柄： (E+E )*id 该归约时，必须归约；而且必须正确归约否则，栈中内容就不叫可行前缀，进而在栈顶就无法形成有效项。该文法是不是SLR(1)的文法？  赋值语句文法：实例： 1) id=id; 2) *id=id; 3) id=*id; 4) id =**id 5) **id=id 6) id 7) *id S→ L=R ｜R L→ * R ｜id R→ L S L = R id L R * L * R L id 求FOLLOW(R) I0 S'→S S→ L=R S→ R L→ * R L→ id R→ L S L id I1 S'→S I2 S→ L=R R→ L I5 L→ id id * * R I4 L→ * R R→ L L→ * R L→ id I3 S→ R $ = id R Accept I6 S→ L=R R→ L L→ * R L→ id R I7 L→ * R  * L I8 R→ L L I9 S→ L=R 文法: S→ L=R S→ R L→ * R L→ id R→ L I2状态存在移入与规约冲突，能不能利用 FOLLOW(R)来解决？求FOLLOW(R)：产生式右边的产生式体中包含R，但R不是出现在最右端：无 R是出现在最右端：有三种情形： S→ L=R  FOLLOW(R)+= FOLLOW(S) S→ R  FOLLOW(R)+= FOLLOW(S) L→ * R  FOLLOW(R)+= FOLLOW(L) 求FOLLOW()  求FOLLOW(S)和 FOLLOW(L) I0 S'→S S→ L=R S→ R L→ * R L→ id R→ L S L id I1 S'→S I2 S→ L=R R→ L I5 L→ id id * * R I4 L→ * R R→ L L→ * R L→ id I3 S→ R $ = id R Accept I6 S→ L=R R→ L L→ * R L→ id R I9 S→ L=R 文法: S→ L=R S→ R L→ * R L→ id R→ L I7 L→ * R  * L I8 R→ L L 求FOLLOW(S)：产生式右边的产生式体中包含S，但S不是出现在最右端：无 S是出现在最右端： S'→S  FOLLOW(S)+= {$} 求FOLLOW(L) I0 S'→S S→ L=R S→ R L→ * R L→ id R→ L S L id I1 S'→S I2 S→ L=R R→ L I5 L→ id id * * R I4 L→ * R R→ L L→ * R L→ id I3 S→ R $ = id R Accept I6 S→ L=R R→ L L→ * R L→ id R I9 S→ L=R 文法: S→ L=R S→ R L→ * R L→ id R→ L I7 L→ * R  * L I8 R→ L L 求FOLLOW(L)：产生式右边的产生式体中包含L，但L不是出现在最右端： S→ L=R  FOLLOW(L)+= {=} 是出现在最右端： R→L  FOLLOW(L) += FOLLOW(R) 不是SLR(1)的无二义文法 I0 S'→S S→ L=R S→ R L→ * R L→ id R→ L S L id I1 S'→S I2 S→ L=R R→ L I5 L→ id id * * R I4 L→ * R R→ L L→ * R L→ id I3 S→ R $ = id R 文法: Accept I6 S→ L=R R→ L L→ * R L→ id R I7 L→ * R  I8 R→ L S→ L=R S→ R L→ * R L→ id R→ L FOLLOW(R) = ｛=，$｝ * L I9 S→ L=R L I2状态存在的归约与移入冲突，不能用FOLLOW（R）解决。 FOLLOW(R)是所有可能，即各种情况下的并集；对上述案例不是SLR(1)文法问题的观察和思考对于某个非终结符R，FOLLOW(R)是所有可能，即各种情况下的并集；实际情况却是：在不同的产生式中，R的FOLLOW( )可能是不同的。右部含E的产生式有三个，具体化其 FOLLOW( ) 文法： E→ E + T | T T→ T * F | F F→ (E) | id 输入串： (id + id)*id$ E 对于产生式：E'→ E FOLLOW(E)=FOLLOW(E')='$'; 对于产生式： F→ (E) FOLLOW(E) = ')' 对于产生式： E→ E + T FOLLOW(E)='+' T T F * （ E ) E T F T F id + id F id 把栈与输入串联接—— 进行观察 E→ E + T | T 文法： T→ T * F | F F→ (E) | id 输入串： (id + id) *id 只有在要规约时，当前输入符才关联规约产生式头部符号的FOLLOW() 句柄 (E +id)*id (E+ id)*id (E+id )*id (E+F )*id (E+T )*id (E )*id 移入移入移入规约规约 F *id T *id (E) *id T*F $ E $ 移入规约规约规约规约对LR(1)项目的理解：具体化非终结符的 FOLLOW( ) 由S'→S  FOLLOW(S)= FOLLOW(S') =$。 I0 S'→S, $ S→ L=R, $ S→ R, $ L→ * R, = L→ id, = R→ L, $ FOLLOW(S') =$，显而易见由S→ R  FOLLOW(R)= FOLLOW(S) =$ 由R→ L  FOLLOW(L)= FOLLOW(R) =$ L→ * R , $ L→ id, $ 对LR(1)项目的理解：具体化非终结符的 FOLLOW( ) 当一旦规约出这个L，它的FOLLOW() = {=} 扩展这个L，这个L的FOLLOW()= {=} I0 S'→S, $ S→ L=R, $ S→ R, $ L→ * R, = L→ id, = R→ L, $ L→ * R , $ L→ id, $ 消除二义性——对每个产生式的当前期待符号(前有圆点)，具体化其FOLLOW( ) 这个L不是处在产生式体的最右端，当归约出这个 L时，它的FOLLOW是'=': I0 S'→S, $ S→ L=R, $ S→ R, $ 。 L→ * R, = L→ id, = R→ L, $ L→ * R , $ L→ id, $ 位于产生式体的最右端，因此它的FOLLOW就是头部符号的FOLLOW: 传递而来对LR(0)项目，在其后附带上它(指产生式头部符号)的FOLLOW，就变成了LR(1)项目 I0 S'→S S→ L=R S→ R L→ * R L→ id R→ L LR(0)项集 I0 S'→S, $ S→ L=R, $ S→ R, $ L→ * R ,= L→ id,= R→ L, $ L→ * R ,$ L→ id,$ LR(1)项集 I0 S'→S, $ S→ L=R, $ S→ R, $ L→ * R ,=|S L→ id,=|$ R→ L, $ LR(1)项集的GOTO——实现了文法的无二义性 I0 S'→S S→ L=R S→ R I2 L L→ * R S→ L=R L→ id R→ L R→ L FOLLOW(R) ={=,$} I0 S'→S, $ S→ L=R, $ I2 L S→ R, $ S→ L=R, $ L→ * R ,=|S R→ L, $ L→ id,=|$ R→ L, $ 表明只有当前输入符为$时，才要归约 SLR(1)在处理FOLLOW上，没有看到具体性，笼统地以总体概念来断定局部问题 4.7 更强大的LR语法分析器 ——规范LR方法和LALR方法  SLR方法中，当一个项集中，当包含至少两个核心项，存在移入/归约(归约/归约)冲突时，如果移入符号和归约后头部非终结符（R)的FOLLOW(R)不存在交集，那么就解决了冲突。  但是FOLLOW(R)是所有可能，即各种情况下的并集。在某种具体情形下，可能紧跟其后的符号，也与移入符号不存在交集，也可以解决冲突问题。对DFA状态中的项集，当内核项中有归约项时，找出一种办法去跟踪得出可能紧跟其后的符号——motivation 4.7 LR(1)和LALR(1)语法分析器  规范LR方法（或直接称LR方法）：对于项AX YZ时，把期望的向前看符号（即A的具体化的FOLLOW)也加入项中。  向前看符号与当前输入符号的区别与联系：只有要归约时，才与当前输入符关联起来。  这个做法可以充分利用向前看符号，但是状态增多。  向前看LR（LALR方法） – 基于LR(0)项集族。但是每个LR(0)项都带有向前看符号。 – 分析能力强于SLR方法，且分析表和SLR分析表一样大,状态比LR(1)少很多 – LALR已经可以适应大部分的程序设计语言。 LR(1)项集(DFA中的状态)的GOTO(I，X）函数 I0 S'→S, $ S→ L=R, $ S→ R, $ L→ * R ,= L→ id,= R→ L, $ L→ * R ,$ L→ id,$ I 2 L S→ L=R, $ R→ L, $ LR(1)项集的DFA I0 S’S, $ SL=R, ＄ SR, ＄ RL, $ L*R, =|$ Lid, =|$ S L R I1 S’S, $ Accept = I2 SL=R, ＄ RL, $ I3 SR, ＄ I6 SL=R, ＄ RL, ＄ L*R, $ Lid, $ L I9 RL, $ R I10 SL=R, ＄ * id * id I4 L*R, =|$ RL, = RL, $ L*R, =|$ Lid, =|$ id I5 Lid, =|$ L R * I7 RL, =|$ I8 L*R, =|$ I11 L*R, $ RL, $ L*R, $ Lid, $ I12 Lid, $ L R I13 L*R, $ * id I2状态的冲突，得到了解决. I2中的RL, $ 项目表明，只有当前输入符为$时，才归约，为'='时不能归约。相应的LR(0)项集的DFA I0 S'→S S→ L=R S→ R L→ * R L→ id R→ L S L id I1 S'→S I2 S→ L=R R→ L I5 L→ id id * * R I4 L→ * R R→ L L→ * R L→ id I3 S→ R Accept = id R I6 S→ L=R R→ L L→ * R L→ id R I7 L→ * R  文法: I9 S→ L=R S→ L=R S→ R L→ * R L→ id R→ L FOLLOW(R) = ｛=，$｝ * L I8 R→ L L I2状态存在归约与移入冲突。 LR(1)DFA与LR(0)DFA的对比观察 I0 S’S, $ SL=R, ＄ SR, ＄ RL, $ L*R, = L*R, $ Lid, = Lid, $ S L R * id I1 S’S, $ Accept = I2 SL=R, ＄ RL, $ I3 SR, ＄ I4 L*R, = L*R, $ RL, = RL, $ L*R, $ Lid, $ L*R, = Lid, = id I5 Lid, = Lid, $ I6 SL=R, ＄ RL, ＄ L*R, $ Lid, $ L I9 RL, $ R I10 SL=R, ＄ * id L R * I7 RL, = RL, $ I8 L*R, = L*R, $ I11 L*R, $ RL, $ L*R, $ Lid, $ I12 Lid, $ L R I13 L*R, $ * id 有用的仅只有I2，解决了冲突。新增加的状态I9,I11,I12,I13在解决冲突中都没有任何作用—— 引出LALR(1)：减少R(1)DFA 中的状态数。将LR(1)项集的DFA中的状态进行合并 ——变成LALR(1)项集的DFA I0 S’S, $ SL=R, ＄ SR, ＄ RL, $ L*R, =|＄ Lid, =|＄ S L R * id I1 S’S, $ $ I2 SL=R, ＄ RL, $ = Accept I9 RL, $ L I6 SL=R, ＄ RL, ＄ L*R, $ Lid, $ R I10 SL=R, ＄ * I11 L*R, $ RL, $ L*R, $ Lid, $ I3 SR, ＄ I4 L*R, =|＄ RL, =|＄ L*R, =|＄ Lid, =|＄ id I5 Lid, =|＄ * L R * id I7 RL, =|＄ I8 L*R, =|＄ L id L * id I12 Lid, $ R I13 L*R, $ I11合并到I4，I9合并到I7，I12合并到I5，I13合并到I8，减少了状态数 LALR(1)项目的向前看符号的传递与自发生成 I0 S’S, $ SL=R, ＄ SR, ＄ RL, $ L*R, = | $ Lid, = | $ S L R * id I1 S’S, $ Accept = I2 SL=R, ＄ RL, $ I3 SR, ＄ I4 L*R, =|＄ RL, =|＄ L*R, =|＄ Lid, =|＄ id I5 Lid, =|＄ I6 SL=R, ＄ RL, ＄ L*R, $ Lid, $ R I10 SL=R, ＄ id L R id I9 RL, $ * * * L I7 RL, =|＄ L I11 L*R, $ RL, $ L*R, $ Lid, $ L * id I12 Lid, $ R I13 L*R, $ I8 L*R, =|＄  传递  自发生成 LALR(1)项集的DFA I0 S’S, $ SL=R, ＄ SR, ＄ RL, $ L*R, = | $ Lid, = | $ S L R * id I1 S’S, $ Accept = I2 SL=R, ＄ RL, $ I3 SR, ＄ I4 L*R, =|＄ RL, =|＄ L*R, =|＄ Lid, =|＄ id I5 Lid, =|＄ R I6 SL=R, ＄ RL, ＄ L*R, $ Lid, $ I10 SL=R, ＄  自发生成 * L R * id I7 RL, =|＄ I8 L*R, =|＄ L  传递和LR(0)DFA有相同的状态数。状态合并，在有些文法中，可能带来冲突不能处理。各种文法的关系无二义的文法：是指自底向上语法分析中，无规约与移入冲突，无规约与规约冲突的文法，包括：  LR(0)文法；  SLR(1)文法； DFA中的状态数是一样的  LALR(1)文法  LR(1)文法，或者叫规范LR(1)文法；各种文法的关系无二义的文法规范LR(1)文法 LALR(1)文法 SLR(1)文法 LR(0)文法另外一个文法的LR(1)项集的DFA I0 S’S, $ SCC, ＄ CcC, c|d Cd, c|d S C I1 S’S, $ I2 SCC, ＄ CcC, ＄ Cd, ＄ Accept C c I5 SCC, ＄ I6 CcC, ＄ CcC, ＄ Cd, ＄ d d c I3 CcC, c|d CcC, c|d Cd, c|d d d I4 Cd, c|d C c C I9 CcC, ＄ c I7 Cd, ＄ I8 CcC, c|d 这个DFA告诉我们什么信息？ LR(1)项集的DFA的特征（1） I0 S’S, $ SCC, ＄ CcC, c|d Cd, c|d S C I1 S’S, $ I2 SCC, ＄ CcC, ＄ Cd, ＄ Accept C c I5 SCC, ＄ I6 CcC, ＄ CcC, ＄ Cd, ＄ d d c I3 CcC, c|d CcC, c|d Cd, c|d d d I4 Cd, c|d C c I7 Cd, ＄ I8 CcC, c|d C c I9 CcC, ＄ LR(1)项集的DFA的特征（2） I0 S’S, $ SCC, ＄ CcC, c|d Cd, c|d S C I1 S’S, $ I2 SCC, ＄ CcC, ＄ Cd, ＄ Accept C c I5 SCC, ＄ I6 CcC, ＄ CcC, ＄ Cd, ＄ d d c I3 CcC, c|d CcC, c|d Cd, c|d d d I4 Cd, c|d C c I7 Cd, ＄ I8 CcC, c|d C c I9 CcC, ＄ LR(0)项集的DFA I0 S’S SCC CcC Cd S C I1 S’S I2 SCC CcC Cd Accept C I5 SCC c c I3 CcC CcC Cd d d I4 Cd C c d I6 CcC LR(1)项集的DFA与LR(0)项集的DFA对比 I0 S’S, $ SCC, ＄ CcC, c|d Cd, c|d S C I1 S’S, $ I2 SCC, ＄ CcC, ＄ Cd, ＄ Accept C c I5 SCC, ＄ I6 CcC, ＄ CcC, ＄ Cd, ＄ d d c I3 CcC, c|d CcC, c|d Cd, c|d d d I4 Cd, c|d C c I7 Cd, ＄ I8 CcC, c|d C c I9 CcC, ＄规范LR(1)语法分析表 I0 S’S, $ SCC, ＄ CcC, c|d Cd, c|d S C I1 S’S, $ I2 SCC, ＄ CcC, ＄ Cd, ＄ Accept C c I5 SCC, ＄ I6 CcC, ＄ CcC, ＄ Cd, ＄ d d c I3 CcC, c|d CcC, c|d Cd, c|d d d I4 Cd, c|d C c I7 Cd, ＄ I8 CcC, c|d C c 规范LR(1) 语法分析表 I9 CcC, ＄状态 0 1 2 3 4 5 6 7 8 9 ACTION c s3 d s4 s6 s3 r3 s7 s4 r3 s6 s7 r2 r2 ＄ acc r1 r3 r2 GOTO S 1 C 2 5 8 9 ccdccd$ 基于规范LR(1)的语法分析，输入串： I0 S’S, $ SCC, ＄ CcC, c|d Cd, c|d S C I1 S’S, $ I2 SCC, ＄ CcC, ＄ Cd, ＄ C -I5 SCC, ＄ c I6 CcC, ＄ CcC, ＄ Cd, ＄ d I7 Cd, ＄ d c d 0-3-3-4 c-c-d I3 CcC, c|d CcC, c|d Cd, c|d d I4 Cd, c|d 0-3-3 +C 状态栈： Accept C 0-2 ccd$ C I9 CcC, ＄ c 0-2-6-9 $ 0-2-5 $ I8 CcC, c|d 0-1 c $ Accept d 0-3-3-8 0-2-6-6-7 $ 0-3 +C 0-3-8 0 +C LALR(1)项目的FOLLOW（） I0 S’S, $ SCC, ＄ CcC, c|d Cd, c|d S I1 S’S, $ C I2 SCC, ＄ CcC, ＄ Cd, ＄ C c Accept  自发生成 I5 SCC, ＄  传递 I6 CcC, ＄ CcC, ＄ Cd, ＄ d d c c d I3 CcC, c|d CcC, c|d Cd, c|d d I4 Cd, c|d C c d I7 Cd, ＄ I8 CcC, c|d C c I9 CcC, ＄规范LR(1)与LALR(1)在错误诊断上对比 I0 S’S, $ SCC, ＄ CcC, c|d Cd, c|d S C c d I1 S’S, $ I2 SCC, ＄ CcC, ＄ Cd, ＄ c I3 CcC, c|d CcC, c|d Cd, c|d d I4 Cd, c|d Accept C c d C I5 SCC, ＄ I6 CcC, ＄ CcC, ＄ Cd, ＄ d I7 Cd, ＄ C I9 CcC, ＄ c I8 CcC, c|d |＄ c d 规范LR(1)中状态栈： 0334 然后报错，因为在4状态，向前看符号只有为c|d才能归约。输入串：ccd 出错时的栈状态 LALR(1)中状态栈： 02 停下，因此时才发现错。 4.8 规范LR(1)与LALR(1)的区别和联系  规范LR的状态多，立即发现错误，不会做错误归约；  LALR的状态少，有错时，可能会归约，而且可能发生多步归约，但是不会再发生移入操作。因此不能立即发现错误，但是可行。  代价  收益。规范LR(1)与LALR(1)的代价与收益 I0 S’S, $ SCC, ＄ CcC, c|d |＄ Cd, c|d |＄ S C c d I1 S’S, $ I2 SCC, ＄ CcC, ＄ Cd, ＄ c I3 CcC, c|d |＄ CcC, c|d |＄ Cd, c|d | ＄ d I4 Cd, c|d |＄   Accept C c d C 自发生成传递 I5 SCC, ＄ I6 CcC, ＄ CcC, ＄ Cd, ＄ d I7 Cd, ＄ C I9 CcC, ＄ c 输入串： ccd I8 CcC, c|d |＄ c d 规范LR(1)中状态栈： 0334 然后报错，因为在4状态，向前看符号只有为c|d才能归约。 LALR(1)中状态栈： 02 停下，因此时才发现错。 4.8 二义性文法的使用  二义性文法都不是LR的。  某些二义性文法是有用的： – 可以简洁地描述某些结构； – 隔离某些语法结构，对其进行特殊处理。  对于某些二义性文法 – 可以通过消除二义性规则来达到无二义性。 – 可以在LR分析器中实现这个规则。 4.8 二义性文法的驾驭 E→ E + T | T T→ T * F | F F→ (E) | id 3个非终结符 6个产生式消除左递归提取左公因子 E→ TE' E' → +TE' | ε T→ FT ' T '→ * F T ' | ε F→ (E) | id 5个非终结符 8个产生式  引入了新的非终结符；  引入了新的产生式 EE + E E E * E E(E) | id 1个非终结符 4个产生式  减少了非终结符；  减少了产生式；  丢失了优先级信息；  二义性文法；文法的不同表达方式的特性 E→ E + T | T T→ T * F | F F→ (E) | id E→ TE' E' → +TE' | ε T→ FT ' T '→ * F T ' | ε F→ (E) | id EE + E E E * E E(E) | id 输入串：id + id * id E E E E + T T T * F F id id 次之(5层) F id E + E id E * id E' T E F T' + id id ε 简洁高效(4层) T F E' T' ε id * F T' id ε 复杂(6层) 自底向上的语法分析的特性 EE + E E E * E E(E) | id 归约的过程就是树的形成过程，也是计算的过程。输入串：id + id * id 语法分析中并不需要真正搭建树. E5 E1 + id E2 * E3 ① id ② id ③ E1 + E4 E2 * ④ E1 + E3 ⑤ E4 ⑤ 二义性文法例子二义性文法：EE+E | E*E | (E) | id 对应于：EE+T | T; TT*F | F; F (E) | id 二义性文法的优点：  容易修改运算符的优先级和结合性。  简洁：如果有多个优先级，那么无二义性文法将引入太多的非终结符号  高效：不需要处理ET，TF之类的单产生式的归约。优先级/结合性会带来冲突，须要消除。二义性文法的LR(0)项集构成的DFA E I0 E'→E E→ E + E E→ E*E E→ (E) E→ id I1 E'→E E→ E + E E→ E*E + $ accept * id I3 E→ id id ( I2 F→ (E) E→ E + E E→ E*E E→ (E) E→ id I5 E→ E*E E→ E + E E→ E*E E→ (E) E→ id + + + * E * * I7 E→ E + E E→ E + E E→ E*E I8 E→ E * E E→ E + E E→ E*E E ( ( I6 F→ (E ) E→ E + E E→ E*E EE+E EE*E E(E) Eid I7，I8中有冲突，且不可能通过 FOLLOW()解决！ id id ( E I4 E→ E + E E→ E + E E→ E*E E→ (E) E→ id ) I9 E→ (E)  DFA的优势——LR(0)项有物理含义 E I0 E'→E E→ E + E E→ E*E E→ (E) E→ id I1 E'→E E→ E + E E→ E*E + $ Accept * id id I3 E→ id ( I5 E→ E*E E→ E + E E→ E*E E→ (E) E→ id + + + I7 E→ E + E E→ E + E E→ E*E I2 F→ (E) E→ E + E E→ E*E E→ (E) E→ id E ( ( I6 F→ (E ) E→ E + E E→ E*E 利用优先级和结合性来解决移进/ * E I8 E→ E * E E→ E + E E→ E*E ) I9 E→ (E)  * * id id ( E I4 E→ E + E E→ E + E E→ E*E E→ (E) E→ id 归约冲突利用LR(0)项的物理含义解决二义性冲突 + E I4 E→ E + E E→ E + E E→ E*E E→ (E) E→ id * id I5 E→ E*E E→ E + E E→ E*E E→ (E) E→ id + + + I7 E→ E + E E→ E + E E→ E*E 在I7，当前输入符号：如果为*，优先级移入；如果为+，结合性归约。 * E * * I8 E→ E * E E→ E + E E→ E*E 在I8，当前输入符号：如果为*，结合性归约；如果为+，优先级归约。解决移入/归约冲突的方法：利用优先级和结合性：对id1+id2+id3，运算的左结合性：是先算id1+id2：对id1+id2*id3，运算的优先级：先*后+，于是先算id2*id3； DFA的优势——LR(0)项有物理含义 E I0 E'→E E→ E + E E→ E*E E→ (E) E→ id I1 E'→E E→ E + E E→ E*E + $ Accept * id id I3 E→ id ( I5 E→ E*E E→ E + E E→ E*E E→ (E) E→ id + + + I7 E→ E + E E→ E + E E→ E*E I2 F→ (E) E→ E + E E→ E*E E→ (E) E→ id E ( ( I6 F→ (E ) E→ E + E E→ E*E 从优先级和结合性可知，上述三 * E * * I8 E→ E * E E→ E + E E→ E*E 条转换边永久都不会发生。因此失去了其意义，可以删除。 id id ( E I4 E→ E + E E→ E + E E→ E*E E→ (E) E→ id ) I9 E→ (E)  SLR(1)语法分析表 E I0 E'→E E→ E + E E→ E*E E→ (E) E→ id I1 E'→E E→ E + E E→ E*E + $ Accept * id id I3 E→ id ( I5 E→ E*E E→ E + E E→ E*E E→ (E) E→ id + I7 E→ E + E E→ E + E E→ E*E SLR(1)语法分析表 * E * I8 E→ E * E E→ E + E E→ E*E id id ( E I4 E→ E + E E→ E + E E→ E*E E→ (E) E→ id I2 F→ (E) E→ E + E E→ E*E E→ (E) E→ id E ( I6 F→ (E ) E→ E + E E→ E*E ① EE+E ② EE*E ③ E(E) ④ Eid ) I9 E→ (E)  + ACTION * ( s4 s5 r4 r4 s4 r1 r2 r3 s5 s5 r2 r3 状态 0 1 2 3 4 5 6 7 8 9 id s3 s3 s3 s3 s2 ) acc s2 s2 s2 GOTO ＄ E s9 1 6 7 8 r3 ( ACTION：移入(shift),归约(reduce);GOTO:可看作是非终结符的移入语法错误发现 E I0 E'→E E→ E + E E→ E*E E→ (E) E→ id I1 E'→E E→ E + E E→ E*E + I4 E→ E + E E→ E + E E→ E*E E→ (E) E→ id $ Accept * id id I3 E→ id ( I7 E→ E + E E→ E + E E→ E*E E I8 E→ E * E E→ E + E E→ E*E + I2 F→ (E) E→ E + E E→ E*E E→ (E) E→ id E ( ( ① EE+E ② EE*E ③ E(E) ④ Eid * * FOLLOW(E) = {*,+, ), $} 因此，在I3， I7，I8, I9状态 id id ( I5 E→ E*E E→ E + E E→ E*E E→ (E) E→ id E I6 F→ (E ) E→ E + E E→ E*E 规约成E时，检查当前输入 ) I9 E→ (E)  符是否FOLLOW(E)。说明输入串有语法错误。解决冲突之后的SLR(1)分析表 ① EE+E ② EE*E ③ E(E) ④ Eid 这个表使得文法变成了无二义性文法 DFA 语法分析表该文法的SLR(1)语法分析表 ACTION 状态 0 1 2 3 4 5 6 7 8 9 id s3 s3 s3 s3 + * s4 s5 r4 r4 s4 r1 r2 r3 s5 s5 r2 r3 ( s2 s2 s2 s2 GOTO ) ＄ acc r4 s9 r1 r2 r3 E 1 6 7 8 DFA也变得简洁高效: 11个状态9个； 3个非终结符1个 ACTION:归约(reduce)，移入(shift); GOTO E I0 E'→E E→ E + E E→ E*E E→ (E) E→ id I1 E'→E E→ E + E E→ E*E + E→ E + E E→ E*E E→ (E) E→ id $ Accept * id id I3 E→ id ( I5 E→ E*E E→ E + E E→ E*E E→ (E) E→ id I7 E→ E + E E→ E + E E→ E*E + * E * I8 E→ E * E E→ E + E E→ E*E id id ( E I4 E→ E + E I2 F→ (E) E→ E + E E→ E*E E→ (E) E→ id E ( ( I6 F→ (E ) E→ E + E E→ E*E ) I9 E→ (E)  栈顶状态为I7，当前输入符为+：用 ① EE+E归约，要从栈中弹出3个状态。栈顶变成I1或I2，归约得到了一个非终结符E，将它视作当前输入符； GOTO：非终结符的移入。消除悬空else的二义性已知文法G： stmt → if expr then stmt | if expr then stmt else stmt | other 对于串 if E1 then if E2 then S1 else S2 stmt else是与第一个if结合，还是与第二个if结合？定义语法的就近结合原则，来解决冲突。 if expr then E1 stmt E if expr then stmt E ε S1 E2 else stmt S2 语法分析方法对比消除左提取左  递归二义性文法公因子 LL   构建项目集的 DFA 简洁高效归约的过程就是计算的过程方法    LL(1) LR(0)       FoLLO W( ) 具体化     规范LR(1)   LALR(1)  适中 SLR(1) LR 使用 FoLLO W( ) 利用项目的物理含义，来人工处理冲突 LR语法分析中的错误恢复 • LR语法分析器查询GOTO表时不会发现错误。 • 查询ACTION表时发现报错条目： – 假设栈中的符号串为α，当前输入符号为a；报错表示不可能存在终结符号串x使得αax是一个最右句型。应急模式（恐慌模式）的错误恢复应急模式（恐慌模式）的错误恢复策略 – 从栈顶向下扫描，找到状态s，s有一个对应于非终结符号A 的GOTO目标；（s之上的状态被丢弃） – 在输入中读入并丢弃一些符号，直到找到一个可以合法跟在 A之后的符号a（不丢弃a）； – 将GOTO(s,A)压栈；继续进行正常的语法分析。 – 基本思想：假定当前正在试图归约到A且碰到了语法错误。因此设法扫描完包含语法错误的A的子串，假装找到了A的一个实例。短语层次的错误恢复 • 短语层次的恢复 – 检查LR分析表中的每个报错条目，根据语言的特性来确定程序员最可能犯了什么错误，然后构造适当的恢复程序。 – 修改栈顶状态，或者第一个输入符号； – 删除，插入，替换输入符号，或者输入符号换位；对错误恢复部分，学生自己看书！上下文相关文法上下文无关，上下文相关，到底是什么含义？  回文语法：对称性的数字串：例如：1，313， 12344321 currentDigitdigit, PalindromecurrentDigit Palindrome currentDigit | digit 这是一个上下文有关文法。上下文有关语法的例子还有：1）变量先定义，后使用规则，就近归属规则；2）函数调用中的参数个数，顺序，类型的匹配规则；3）变量使用时的类型匹配；通过穷举，使其变成上下文无关文法： Palindrome0 Palindrome 0 | 1 Palindrome 1 | 2 Palindrome 2 | 3 Palindrome 3 | 4 Palindrome 4 | 5 Palindrome 5 | 6 Palindrome 6 | 7 Palindrome 7 | 8 Palindrome 8 | 9 Palindrome 9 | digit C/S也是上下文无关概念。上下文无关性正则表达式(0?0?1)* (0?0?1)* = （1 | 01 | 001)* 其实例： 1 001 01 1 01 001 001 001 01 01 1 1 三个元素，每次在要出现时，都是独立的，与前后的无关第三章与第四章的关系：文法是正则表达式的超集 (a|b)*abb的DFA b b start S0 123 a 1234 b S1,1 a a 1235 b S2,2 1236 S3,2 a 状态的物理含义：所有可能(还没有发生，还在等待发生）一旦发生，来了个a，那就变迁到下一个状态 (a|b)*abb的文法及LR(0)的DFA S I0 S'→S S→ aS S→ bS S→ abb I1 S'→ S 是不是LR(0)文法? SLR(1)? a I2 S→ aS S→ abb a S→ aS S→ bS a a S→ abb a I3 b S→ bS S→ aS S→ bS S→ abb b b S I4 S→ aS I5 S→ abb b S→ bS S→ aS S→ bS S→ abb I7 S→ abb b S→ bS S→ aS S→ bS S→ abb I6 S S→ bS S 观察与分析上述正则表达式中，连一个非终结符号都没有，因此得出的 DFA最简单，只有4个状态，于是效率高，占用内存少。只要增加一个非终结符号，DFA就明显地变得复杂。DFA状态数由4个增加到8个。 (a|b)*的文法及LR(0)的DFA S I0 S'→S S→ aS S→ bS S→ ,$ I1 S'→ S I2 S→ aS S→ aS a S→ bS S→ ,$ I3 b S→ bS S→ aS S→ bS S→ ,$ $ Accept S a $ I4 S→aS,$ a I4 S→ ,$ b $ b S $ I4 S→bS,$ 上下文无关文法总结  表达式文法；  赋值语句文法；（4.49）  控制语句文法;  函数文法： stmtid (expr_list) expr_list expr_list, expr | expr |   数组元素文法： arrayElementid Dimension_list Dimension_list Dimension_list[expr] | [expr] 上下文无关文法总结(cont.)  语句文法： stmtinclude_stmt | declare_stmt | set_stmt | control_stmt | function_call_tmt stmtt_list stmt_list stmt | stmt stmt_block{stmt_block} | stmt_list 本章小结：语法分析知识图语法分析典型语法分析上下文无关文法文法设计推导、语法分析树、语言二义性自顶向下分析递归下降分析 LL(1) 分析消除左递归提左公因子 FIRST LR(0) 分析 FOLL LL（1） OW 分析表自底向上分析 LR分析算符优先分析 SLR(1) 分析 LR(1) 分析 LR(0) 自动机语法分析表 LALR(1) 分析作业 • 4.2.1(1-3)，4.2.2(1-5)，4.2.3(1-3) • 4.3.1 • 4.4.1(1-5)，4.4.3， 4.4.4, • 4.5.1 • 4.6.2, 4.6.5, 4.6.6, • 4.7.4，4.7.5 第三章要掌握的内容  模式的正则表达式表达；  基于组合原则的正则表达式表达  NFA；  正则表达式的三种运算，以及？: 0个或1个  NFA中基于边的状态缩减；  基于子集构造法的NFA  DFA  正则表达式表达  DFA  基于DFA的匹配与识别：输入串是否匹配正则表达式；第四章要掌握的内容  语法的上下文无关文法表达；  正则表达式  上下文无关文法  LL(1)语法分析：消除左递归，提取左公因子（彻底）；  对文法的每个产生式：计算FIRST（）；对每个非终结符号：计算FIRST（），FOLLOW（）；  填写出文法的LL(1)预测分析表；判断文法是否是LL(1)文法；  基于LL(1)预测分析表对输入串做自顶向下的推导过程：每步使用的产生式；判断输入串是否符合文法；第四章要掌握的内容——自底向上  LR(0)项目，LR(1)项目，LALR(1)项目，  文法  DFA（基于LR(0)项集，LR(1)项目）；  文法 DFA  LR语法分析表；  判断文法是否是LR(0)，SLR(1)，规范LR(1)，LALR(1) 文法；  基于文法的DFA或语法分析表，对输入串的移入-归约过程： 1）符号栈，2）状态栈；每步，判断输入串是否符合文法；随堂测试 E I0 E'→E E→ E + E E→ E*E E→ (E) E→ id I1 E'→E E→ E + E E→ E*E + I4 E→ E + E E→ E + E E→ E*E E→ (E) E→ id $ Accept * id id I3 E→ id ( I7 E→ E + E E→ E + E E→ E*E E I8 E→ E * E E→ E + E E→ E*E ) I9 E→ (E)  + + + * * * ① EE+E ② EE*E ③ E(E) ④ Eid id id ( I5 E→ E*E E→ E + E E→ E*E E→ (E) E→ id E I2 F→ (E) E→ E + E E→ E*E E→ (E) E→ id E ( I6 F→ (E ) E→ E + E E→ E*E ( 对输入串：(id+id)*id, 写出其语法分析中每步（移入或归约）后的栈中状态（注：对归约则是写出随后GOTO后的栈中状态）。随堂测试2：已知文法G S → M id | TME | −E | T-id T→E×T|E E → ( id ) M→+|− 画出G的LR(0)项集的自动机(DFA), 判断它是不是SLR(1)文法，说明理由。如果不是，画出LR(1)自动机DFA中I0状态的LR(1) 项集，对每个存在冲突的状态，列出其LR(1)项集。 I0 S'→S S →M id S →TME S →−E S →T-id T →E × T T →E E →( id ) M → + M → − S M T I1 S'→S $ Accept I2 S →M id id I8 S →M id E I3 S →TME S →T-id M → + M → − M I9 S →TME E → ( id ) I13 S →TME I10 S →T-id M → − id I14 S →T-id I11 T → E × T T → E × T T →E E → ( id ) T I15 T → E × T I12 E→ (id) ) I16 E→ (id) - E I4 T → E × T E T →E (  ( I5 E→ (id) id ( + - LR(0)项集的DFA I6 M→ + I7 M→ - + FOLLOW(S)={$}; FOLLOW(T) ={ +, - }; FOLLOW(E)={+, -, ×, $}; FOLLOW(M)={id, ( }; 基于SLR(1)进行分析 I4状态和I10状态存在移入-规约冲突。对于I4状态，规约后得到T。由FOLLOW(T) ={ +, - }可知，如果当前输入符为+或-则规约，如果为×则移入。因此，SLR(1)可解决I4状态的移入-规约冲突。在I10状态，规约后得到M。由FOLLOW(M) ={ id, ( }可知 , 如果当前输入符为id或（则规约。但当前输入符为id，也应该移入。因此，SLR(1)不能解决I10状态的移入-规约冲突。求LR(1)项集I0的CLOSURE() S → M id | TME | −E | T-id T→E×T|E E → ( id ) M→+|− I0 S'→S,$ S'→S,$ S →M id,$ S →TME,$ S →−E,$ S →T-id,$ E → ( id ),  M → +,id M → −,id T → E × T, +|T →E, +|T → E × T, T →E, E → ( id ), +|- LR(1)项集I0到I4状态和I10状态的变迁图 I0 S'→S, $ S →M id, $ S →TME, $ S →−E, $ S →T-id, $ T → E × T,+|T →E,+|E → ( id ), |+|M → +, id M → −, id T E I3 S →TME, $ S →T-id, $ M → +, ( M → −, ( - I10 S →T-id,$ M → −, ( I4 T → E × T, +|T →E, +|- I4状态和I10状态的移入和规约冲突得到了解决。在I4状态，如果当前输入符为+或-则规约，如果为×则移入。在I10状态，如果当前输入符为（则规约，如果为id则移入。结论该文法不是SLR(1)文法，但是规范LR(1)文法。谢谢谢谢！对LR(1)项目的理解：具体化非终结符的 FOLLOW( ) 由S'→S  FOLLOW(S)= FOLLOW(S') =$。 I0 S'→S, $ S→ L=R, $ S→ R, $ L→ * R, = L→ id, = R→ L, $ FOLLOW(S') =$，显而易见由S→ R  FOLLOW(R)= FOLLOW(S) =$ 由R→ L  FOLLOW(L)= FOLLOW(R) =$ L→ * R , $ L→ id, $ 对LR(1)项目的理解：具体化非终结符的 FOLLOW( ) 当一旦规约出这个L，它的FOLLOW() = {=} 扩展这个L，这个L的FOLLOW()= {=} I0 S'→S, $ S→ L=R, $ S→ R, $ L→ * R, = L→ id, = R→ L, $ L→ * R , $ L→ id, $ DFA的优势——LR(0)项有物理含义 E I0 E'→E E→ E + E E→ E*E E→ (E) E→ id I1 E'→E E→ E + E E→ E*E + I4 E→ E + E E→ E + E E→ E*E E→ (E) E→ id $ Accept * id id I3 E→ id ( I7 E→ E + E E→ E + E E→ E*E E I8 E→ E * E E→ E + E E→ E*E + + + * * * id id ( I5 E→ E*E E→ E + E E→ E*E E→ (E) E→ id E I2 F→ (E) E→ E + E E→ E*E E→ (E) E→ id E ( ( I6 F→ (E ) E→ E + E E→ E*E ) I9 E→ (E)  E→ TE' E' → +TE' | ε T→ FT ' T '→ * F T ' | ε F→ (E) | id E→ E + T | T T→ T * F | F F→ (E) | id EE + E E E * E E(E) | id DFA的优势——LR语法分析实用的原因 I4 S→ id = E id I0 P→S S→ {S} S→ if(B) S S→ while(B) S S→ id = E S { { if I3 S→if( B ) S S→ {S} S→ if(B) S S→ while(B) S S→ id = E if I1 P→S I2 S→ {S} S→ SS S→ if(B) S S→ while(B) S S→ id = E I6 S S→if( B ) S I5 S→ {S} S→ SS S S→ if(B) S S→ while(B) S S→ id = E } S I7 S→ {S} I8 S→ SS