编译原理语法分析

1、第四章第四章 语法分析语法分析 贵州大学贵州大学 计算机科学与信息学院计算机科学与信息学院 第四章第四章 语法分析语法分析 v本章内容本章内容 自顶向下自顶向下分析和自底向上分析分析和自底向上分析 围绕语法分析器的自动生成展开围绕语法分析器的自动生成展开 第四章第四章 语法分析语法分析 v4.1 4.1 语法分析器概述语法分析器概述 v4.2 4.2 书写文法书写文法 v4.3 4.3 自顶向下分析自顶向下分析 v4.4 4.4 自底向上分析概述自底向上分析概述 v4.5 4.5 算符优先分析法算符优先分析法 v4.6 LR4.6 LR分析器分析器 v4.7 4.7 二义文法的应用二义文法的应

2、用 语法分析器语法分析器 中间代码中间代码 单词符号单词符号 语法单位语法单位 中间代码中间代码 目标代码目标代码 词法分析器词法分析器 语义分析与中间代码语义分析与中间代码 生成器生成器 代码优化器代码优化器 源程序源程序 表表 格格 管管 理理 出出 错错 处处 理理 目标代码生成器目标代码生成器 4.1 4.1 语法分析器概述语法分析器概述 v 语法分析器是编译器语法分析器是编译器前端前端的重要组成部分，许多编的重要组成部分，许多编 译器，特别是由自动生成工具构造的编译器，往往其译器，特别是由自动生成工具构造的编译器，往往其 前端的中心部件就是语法分析器。前端的中心部件就是语法分析器。

3、语法分析器在编语法分析器在编 译器中的位置和作用如下：译器中的位置和作用如下： 词词 法法 分析器分析器 记记 号号 取下一个取下一个 记号记号 源程序源程序 分析分析 树树 前端的前端的 其余部分其余部分 分析器分析器 中间中间 表示表示 符号表符号表 语法分析器概述语法分析器概述 v语法分析器的主要作用有两点：语法分析器的主要作用有两点： 检查词法分析器输出的单词序列是否是源语言中检查词法分析器输出的单词序列是否是源语言中 的句子，亦即是否符合源语言的语法规则的句子，亦即是否符合源语言的语法规则 检查输入中的语法（可能包括词法）错误，并调检查输入中的语法（可能包括词法）错误，并调 用出错处

4、理器进行适当处理用出错处理器进行适当处理 v两大类分析方法：两大类分析方法： 自顶向下分析自顶向下分析 自底向上分析自底向上分析 存在主要问题存在主要问题: 左递归问题左递归问题 回溯问题回溯问题 主要方法主要方法: 递归子程序法递归子程序法 预测分析法预测分析法 (LL(1) 自顶向下分析算法的基本思想为：自顶向下分析算法的基本思想为： 有符号串有符号串S 若若Z S 则则 S L(GZ) 否则否则 S L(GZ) Gz + 从文法产生语言的角度从文法产生语言的角度 A S aS bSA a a b a aSbAS aabAS aabbaS aabbaa aAS S P: SaAS a A

5、SbA SS ba 句子句子：aabbaa 自底向上分析算法的基本思想为：自底向上分析算法的基本思想为： + 若若Z S 则则 S L(GZ) 否则否则 S L(GZ) Gz 存在主要问题存在主要问题: 句柄的识别问题句柄的识别问题 主要方法主要方法: 算法优先分析法算法优先分析法 LR分析法分析法 从自动机识别语言的角从自动机识别语言的角 度度 A S aS bSA a a b a aAa aSbAa aSbbaa aabbaa aAS S P: SaAS a A SbA SS ba 句子句子：aabbaa 4.2 书写文法书写文法 v定义定义：如果一个文法有非终结符：如果一个文法有非终结符

6、A，对某个串，对某个串，存，存 在推导在推导A +A ，则称该文法是则称该文法是左递归左递归的。形式为的。形式为 AA的产生式引起的左递归称为的产生式引起的左递归称为直接左递归直接左递归。 v直接左递归直接左递归AAa |b 串的特点串的特点 ba . . . a v消除直接左递归消除直接左递归 A b A A a A | 左递归变右左递归变右 递归递归 4.2.1 消除左递归消除左递归 4.2.1 消除左递归消除左递归 v一般而言，假定关于一般而言，假定关于P的全部产生式是的全部产生式是 PP 1 | P 2 | | P m | 1 | 2| n 其中，每个其中，每个 都不等于都不等于 ，每

7、个，每个 都不以都不以P开头开头 那么，消除那么，消除P的直接左递归就是把这些规则改的直接左递归就是把这些规则改 写成：写成： P 1P | 2P | | nP P 1P | 2P | | mP | 左递归变右左递归变右 递归递归 4.2.1 消除左递归消除左递归 v例例 算术表达式文法算术表达式文法 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 | F ( E ) | id 4.2.1 消除左递归消除左递归 v非直接左

8、递归非直接左递归 S Aa | b A Sd | v先变换成直接左递归先变换成直接左递归 S Aa | b A Aad | bd | v再消除左递归再消除左递归 S Aa | b A bd A | A A adA | 4.2.1 消除左递归消除左递归 v例例 考虑文法考虑文法G(S) SQc|c QRb|b (3.1) RSa|a v令它的非终结符的排序为令它的非终结符的排序为R、Q、S。 v对于对于R，不存在直接左递归。，不存在直接左递归。 v把把R代入到代入到Q的有关候选后，把的有关候选后，把Q的的 规则变为规则变为 QSab | ab | b 4.2.1 消除左递归消除左递归 v例例 考

9、虑文法考虑文法G(S) SQc|c QRb|b RSa|a v令它的非终结符的排序为令它的非终结符的排序为R、Q、S。 vQ的规则变为的规则变为 QSab | ab | b v现在的现在的Q不含直接左递归，把它代入到不含直接左递归，把它代入到S的有的有 关候选后，关候选后，S变成变成 SSabc | abc | bc | c 4.2.1 消除左递归消除左递归 v例例 考虑文法考虑文法G(S) SQc|c QRb|b RSa|a vS变成变成 SSabc | abc | bc | c v消除消除S的直接左递归后：的直接左递归后： SabcS | bcS | cS S abcS | QSab |a

10、b | b RSa|a 4.2.1 消除左递归消除左递归 v消除消除S的直接左递归后：的直接左递归后： SabcS | bcS | cS S abcS | QSab |ab | b RSa|a v关于关于Q和和R的规则已是多余的，化简为：的规则已是多余的，化简为： SabcS | bcS | cS S abcS | (3.2) 4.2.1 消除左递归消除左递归 v注意，由于对非终结符排序的不同，最后所得的文注意，由于对非终结符排序的不同，最后所得的文 法在形式上可能不一样。但不难证明，它们都是等法在形式上可能不一样。但不难证明，它们都是等 价的。价的。 v例如，若对文法例如，若对文法(3.1)

11、的非终结符排序选为的非终结符排序选为S、Q、R， 那么，最后所得的无左递归文法是：那么，最后所得的无左递归文法是： SQc | c QRb | b RbcaR | caR |a R (3.3) R bca R | v文法文法(3.2)和和(3.3)的等价性是显然的。的等价性是显然的。 4.2.2 提左因子提左因子 v有左因子的文法有左因子的文法 A 1 | 2 v提左因子提左因子 A A A 1 | 2 4.2.2 提左因子提左因子 v例例 悬空悬空else的文法的文法 stmt if expr then stmt else stmt | if expr then stmt | other v

12、提左因子提左因子 stmtif expr then stmt optional_else_part | other optional_else_part else stmt | 4.3 自顶向下分析自顶向下分析 v自顶向下分析就是从文法的自顶向下分析就是从文法的开始符号开始符号出发，向下出发，向下推推 导导，推出句子。，推出句子。 带带“回溯回溯”的分析方法的分析方法 不带回溯的递归子程序不带回溯的递归子程序( (递归下降递归下降) )分析方法分析方法 v自顶向下分析的主旨：对任何输入串，试图用一切自顶向下分析的主旨：对任何输入串，试图用一切 可能的办法，从文法开始符号可能的办法，从文法开始符

13、号( (根结点根结点) )出发，自上出发，自上 而下、而下、从左到右从左到右地为输入串建立一棵地为输入串建立一棵分析树分析树。或者。或者 说，为输入串寻找一个说，为输入串寻找一个最左推导最左推导。 v分析是一种试探的过程，是反复使用不同产生式谋分析是一种试探的过程，是反复使用不同产生式谋 求与输入序列匹配的过程。求与输入序列匹配的过程。 4.3.1 自顶向下分析的一般方法自顶向下分析的一般方法 v例例 假定有文法假定有文法G(S): (1) SxAy (2) A*|* 分析输入串分析输入串x*y(记为记为 )。 Sx*y IP Axy * Sx*y IPAxy * Sx*y IP Axy *

14、Sx*y IPAxy * Sx*y IPAxy Sx*y IP Axy Sx*y IP 分析成功！分析成功！ 4.3.1 自顶向下分析的一般方法自顶向下分析的一般方法 v困难和缺点：困难和缺点： 不能处理左递归（分析陷入无限循环）不能处理左递归（分析陷入无限循环） 分析过程中，当一个非终结符用某一个候选匹配分析过程中，当一个非终结符用某一个候选匹配 成功时，这种匹配可能是成功时，这种匹配可能是暂时暂时的的。出错时出错时，不得，不得 不不“回溯回溯”。 回溯导致语义工作推倒重来回溯导致语义工作推倒重来 分析器难以报告输入串出错的确切位置分析器难以报告输入串出错的确切位置 效率低，代价高，只有理论

15、意义效率低，代价高，只有理论意义 4.3.2 LL(1)文法文法 v构造不带回溯的自上而下分析算法构造不带回溯的自上而下分析算法 要消除文法的左递归性要消除文法的左递归性 克服回溯克服回溯 v为了消除回溯就必须保证：对文法的任何非为了消除回溯就必须保证：对文法的任何非 终结符，当要用它去匹配输入串时，能够根终结符，当要用它去匹配输入串时，能够根 据它所面临的输入符号准确地指派它的一个据它所面临的输入符号准确地指派它的一个 候选去执行任务，并且此候选的工作结果应候选去执行任务，并且此候选的工作结果应 是确信无疑的。是确信无疑的。 v例例 文法文法G(S): (1) SxAy (2) A*|* v

16、例如例如, 对于下面文法，面临对于下面文法，面临a时不知用什么时不知用什么 规则规则 S A B A a b | B a C C 4.3.2 LL(1)文法文法 v先定义两个和文法有关的函数：先定义两个和文法有关的函数： 令令G是一个不含是一个不含左递归左递归的文法，对的文法，对G的所有非终结符的每个的所有非终结符的每个 候选候选 定义它的终结首符集定义它的终结首符集FIRST( )为：为： 特别是，若特别是，若 * ，则规定，则规定FIRST( ) 如果非终结符如果非终结符A的所有候选首符集两两不相交，即的所有候选首符集两两不相交，即A的任何的任何 两个不同候选两个不同候选 i和和 j FI

17、RST( i)FIRST( j) 当要求当要求A匹配输入串时，匹配输入串时，A就能根据它所面临的第一个输入符就能根据它所面临的第一个输入符 号号a，准确地指派某一个候选前去执行任务。这个候选就是，准确地指派某一个候选前去执行任务。这个候选就是 那个终结首符集含那个终结首符集含a的的 。 v经过经过反复提取左因子反复提取左因子，能够把每个非终结符的所有候选首符集，能够把每个非终结符的所有候选首符集 变成为两两不相交。变成为两两不相交。 .,|=)( * T VaaaFIRST 问题：对文法加什么样的限制可以保证没有回溯？问题：对文法加什么样的限制可以保证没有回溯？ 构造构造FIRST( ) v对

18、文法对文法G的任何符号串的任何符号串 =X1X2Xn构造集合构造集合 FIRST( )。 1. 置置FIRST( )FIRST(X1)； 2. 若对任何若对任何1 j i-1，FIRST(Xj)，则把，则把 FIRST(Xi)加至加至FIRST( )中；特别是，若所有中；特别是，若所有 的的FIRST(Xj)均含有均含有 ，1 j n，则把，则把 也加至也加至 FIRST( )中。显然，若中。显然，若 则则FIRST( ) 。 4.3.2 LL(1)文法文法 例：例： ETE E +TE | TFT T *FT | F(E) | i 分析输入串：分析输入串：i + i i + i IP E n

19、G(E): ETE E +TE | TFT T *FT | F(E) | i i + i IP E TE nG(E): ETE E +TE | TFT T *FT | F(E) | i i + i IP E TE FT nG(E): ETE E +TE | TFT T *FT | F(E) | i i + i IP E TE FT i nG(E): ETE E +TE | TFT T *FT | F(E) | i i + i IP E TE FT i nG(E): ETE E +TE | TFT T *FT | F(E) | i i + i IP E TE FT i nG(E): ETE E

20、+TE | TFT T *FT | F(E) | i i + i IP E TE FT i +TE nG(E): ETE E +TE | TFT T *FT | F(E) | i i + i IP E TE FT i +TE nG(E): ETE E +TE | TFT T *FT | F(E) | i i + i IP E TE FT i +TE FT nG(E): ETE E +TE | TFT T *FT | F(E) | i i + i IP E TE FT i +TE FT i nG(E): ETE E +TE | TFT T *FT | F(E) | i i + i IP E TE

21、 FT i +TE FT i nG(E): ETE E +TE | TFT T *FT | F(E) | i i + i IP E TE FT i +TE FT i nG(E): ETE E +TE | TFT T *FT | F(E) | i i + i IP E TE FT i +TE FT i nG(E): ETE E +TE | TFT T *FT | F(E) | i E T+ 对于对于+ +的匹配只能依赖于在可能的推的匹配只能依赖于在可能的推 导过程中导过程中TT的后面的字符的后面的字符 4.3.2 LL(1)文法文法 v若若FIRST ( i ) 或或 FIRST ( j )含含

22、 ，还需增加条，还需增加条 件件 v假定假定S是文法是文法G的开始符号，对于的开始符号，对于G的任何非的任何非 终结符终结符A的的后继符号后继符号集合是所有在句型中直集合是所有在句型中直 接出现在接出现在A后面的终结符的集合，即后面的终结符的集合，即 FOLLOW (A) = a | S * Aa，a VT 4.3.2 LL(1)文法文法 v构造构造FOLLOW (B ) 的算法归纳为如下三条：的算法归纳为如下三条： 对于文法的开始符号对于文法的开始符号S，令，令$属于属于FOLLOW (S) 如果文法中有形如如果文法中有形如AB的规则，则的规则，则FIRST() 中中非非 元素元素属于属于F

23、OLLOW (B ) 如果文法中有形如如果文法中有形如AB或或AB且且FIRST() 含有含有 元素这样的规则，则元素这样的规则，则FOLLOW (A) 的元素的元素 属于属于FOLLOW (B ) v例例 E TE E + TE | T FT T FT | F (E) | id FIRST(E) = FIRST(T) = FIRST(F) = ( , id FIRST(E ) = +, FRIST(T ) = , FOLLOW(E) = ), $ FOLLOW(E ) = FOLLOW(E) FOLLOW(T) = FIRST(E ) U FOLLOW(E) = +, ), $ FOLLOW

24、 (T ) = FOLLOW(T) FOLLOW(F) = FRIST(T ) U FOLLOW(T) = , +，), $ v练习：已知文法练习：已知文法GS: SeTRT T DR RdR D ab (1)FIRST(S)=_, FIRST(T)=_ FIRST(R)=_, FIRST(D)=_ a.d, b.a,b,d,e, c.a,b d.a,b,$ e.a,b, f.$ (2)FOLLOW(S)=_, FOLLOW(T)=_ FOLLOW(R)=_, FOLLOW(D)=_ a.d b.a,b c.a,b,$ d.$ e.d,$ b e ac d d ce 4.3.2 LL(1)文法

25、文法 v构造不带回溯的自上而下分析的文法条件构造不带回溯的自上而下分析的文法条件 1. 文法不含左递归，文法不含左递归， 2. 对于文法中每一个非终结符对于文法中每一个非终结符A的各个产生式的候选首符集的各个产生式的候选首符集 两两不相交。即，若两两不相交。即，若 A 1| 2| n 则则 FIRST( i)FIRST( j) (i j) 3. 对文法中的每个非终结符对文法中的每个非终结符A，若它存在某个候选首符集包，若它存在某个候选首符集包 含含 ，则，则 FIRST( i)FOLLOW(A)= i=1,2,.,n v如果一个文法如果一个文法G满足以上条件，则称该文法满足以上条件，则称该文法

26、G为为LL(1)文法文法。 第一个第一个L代表从代表从左向右扫描左向右扫描输入符号串，第二个输入符号串，第二个L代表产生代表产生最最 左推导左推导，1代表在分析过程中执行每步推导都要代表在分析过程中执行每步推导都要向前查看一向前查看一 个输入符号个输入符号 4.3.2 LL(1)文法文法 v例例1：G1A: AaABe B Bbb G1A不是不是LL(1)文法，因为文法，因为 FIRST(Bb) FIRST(b)=b v例例2：G2A: AaABeBa B dB G2A不是不是LL(1)文法，因为文法，因为 FIRST(aABe) FIRST(Ba)=a v例例3：G3S: SaAbDed A

27、 BSDe BSAccD D Se G3S不是不是LL(1)文法，因为文法，因为 FIRST(SAc) FOLLOW(B)=a,d 4.3.2 LL(1)文法文法 vLL(1)LL(1)文法有一些明显的性质文法有一些明显的性质 没有公共左因子没有公共左因子 不含左递归不含左递归 不是二义的不是二义的 4.3.2 LL(1)文法文法 v对于一个满足上述条件的文法，可以对其输入串进对于一个满足上述条件的文法，可以对其输入串进 行有效的无回溯的自上而下分析。假设要用非终结行有效的无回溯的自上而下分析。假设要用非终结 符符A进行匹配，面临的输入符号为进行匹配，面临的输入符号为a，A的所有产生的所有产生

28、 式为式为 A 1 | 2 | | n 1. 若若a FIRST( i)，则指派，则指派 i执行匹配任务；执行匹配任务； 2. 若若a不属于任何一个候选首符集，则：不属于任何一个候选首符集，则： (1) 若若 属于某个属于某个FIRST( i )且且 a FOLLOW(A)， 则让则让A与与 自动匹配。自动匹配。 (2) 否则，否则，a的出现是一种语法错误。的出现是一种语法错误。 4.3.3 递归的预测分析递归的预测分析 v预测分析预测分析是指能根据当前的输入符号为非终结符确定用哪一是指能根据当前的输入符号为非终结符确定用哪一 个选择个选择,LL(1),LL(1)文法满足此要求文法满足此要求

29、v递归的预测分析是为递归的预测分析是为每一个非终结符每一个非终结符写一个分析过程写一个分析过程, ,这些这些 过程可能是递归的过程可能是递归的 v在处理输入串时在处理输入串时, ,首先执行的是对应开始符号的过程首先执行的是对应开始符号的过程, ,然后根然后根 据产生式右部出现的非终结符据产生式右部出现的非终结符, ,依次调用相应的过程依次调用相应的过程, ,这种逐这种逐 步下降的过程调用序列隐含地定义了输入串的分析树步下降的过程调用序列隐含地定义了输入串的分析树 例例： type simple | id | array simple of type simple integer | char

30、| num dotdot num 4.3.3 递归的预测分析递归的预测分析 一个辅助过程一个辅助过程 procedure match (t : token); begin if lookahead = t then lookahead := nexttoken( ) else error( ) end; proccdure type; begin if lookahead in integer, char, num then simple( ) else if lookahead = then begin match (); match (id) end else if lookahead =

31、 array then begin match (array); match ( ); simple( ); match ( ); match (of ); type( ) end else error( ) end; type simple | id | array simple of type procedure simple; begin if lookahead = integer then match (integer) else if lookahead = char then match (char) else if lookahead = num then begin matc

32、h (num); match (dotdot); match (num) end else error( ) end; simple integer | char | num dotdot num 4.3.4 非递归的预测分析非递归的预测分析 v如果显式地维持一个状态栈如果显式地维持一个状态栈, ,而不是隐式地通过递而不是隐式地通过递 归调用归调用, ,则可以构造非递归的预测分析器则可以构造非递归的预测分析器 v预测分析的关键问题是决定取哪个产生式运用于预测分析的关键问题是决定取哪个产生式运用于 非终结符（通过查分析表来决定产生式）非终结符（通过查分析表来决定产生式） v预测分析器组成：输入缓

33、冲区（存放要分析的串，预测分析器组成：输入缓冲区（存放要分析的串， 以以$ $作为结束标记）、栈（存放文法符号，栈底符作为结束标记）、栈（存放文法符号，栈底符 号是号是$)$)、分析表（两维数组、分析表（两维数组MA,a,AMA,a,A是非终结符，是非终结符， a a是终结符或是终结符或$)$)和输出流。和输出流。 4.3.4 非递归的预测分析非递归的预测分析 a + b $ 输入输入 预测分析程序预测分析程序 分析表分析表M 输出输出 X Y Z $ 栈栈 分析器工作过程分析器工作过程 v预测分析程序根据现行栈顶符号预测分析程序根据现行栈顶符号X X和当前输入和当前输入 符号符号a a，执行

34、下列四种动作之一，执行下列四种动作之一: : 1. 1. 若若X Xa a$，则宣布分析成功，停止分析。，则宣布分析成功，停止分析。 2. 2. 若若X Xa a $，则把，则把X X从栈顶逐出，推进输入从栈顶逐出，推进输入 指针，指向下一个输入符号。指针，指向下一个输入符号。 3. 3. 若若X X是终结符但不是是终结符但不是a a，则分析器报告出错，调，则分析器报告出错，调 用错误恢复例程。用错误恢复例程。 分析器工作过程分析器工作过程 4. 4. 若若X X是非终结符，程序访问分析表是非终结符，程序访问分析表 若若MXMX，aa中存放着关于中存放着关于X X的一个产生式，把的一个产生式，

35、把X X逐逐 出出STACKSTACK栈顶，栈顶，把产生式的右部符号串按反序一把产生式的右部符号串按反序一 一推进一推进STACKSTACK栈栈( (若右部符号为若右部符号为 ，则意味不推什，则意味不推什 么东西进栈么东西进栈) )。 若若MXMX，aa中存放着中存放着“出错标志出错标志”，则调用错误，则调用错误 恢复例程。恢复例程。 分析表分析表 非终非终 结符结符 输输 入入 符符 号号 id + . . . E E TE E E +TE T T FT T T T FT F F id 预测分析器接受输入预测分析器接受输入id + id * id的动作的动作 栈栈 输输 入入 输输 出出 $

36、E id + id * id$ 非终非终 结符结符 输输 入入 符符 号号 id + E E TE E E +TE T T FT T T T FT F F id $E Tid + id * id$E TE $E T F id + id * id$ id + id * id$ + id * id$ + id * id$ + id * id$ id * id$ $E T id $E T $E $E T + $E T T FT F id T E +TE 4.3.5 构造预测分析表构造预测分析表 算法算法4.3 (1)对文法的每个产生式对文法的每个产生式A ，执行，执行(2)和和(3) (2)对对FI

37、RST( )的每个终结符的每个终结符a，把，把A 加入加入 MA, a (3)如果如果 在在FIRST( )中，对中，对FOLLOW(A)的每的每 个终结符个终结符b（包括（包括$）, 把把A 加入加入MA, b (4)M 的其它没有定义的条目都是的其它没有定义的条目都是error 例例 E TE E + TE | T FT T FT | F (E) | i FIRST(E) = FIRST(T) = FIRST(F) = ( , i FIRST(E ) = +, FRIST(T ) = , FOLLOW(E) = FOLLOW(E ) = ), $ FOLLOW(T) = FOLLOW (T

38、 ) = +, ), $ FOLLOW(F) = , +，), $ i+*()# EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E) $ 4.3.5 构造预测分析表构造预测分析表 v如果如果G是左递归或二义的，那么，是左递归或二义的，那么，M至少含至少含 有一个有一个多重定义条目多重定义条目。因此，消除左递归和。因此，消除左递归和 提取左因子将有助于获得无多重定义的分析提取左因子将有助于获得无多重定义的分析 表表M。 v可以证明，一个文法可以证明，一个文法G的预测分析表的预测分析表M不含不含 多重定义条目，当且仅当该文法为多重定义条目，当且

39、仅当该文法为LL(1)的。的。 G(S): S iCtS | iCtSeS | a C b 提取左因子之后，改写成：提取左因子之后，改写成： G(S): S iCtSS | a S eS | C b abeit# SSaSiCtSS S S S eS S CCbF (E) 最近匹配原则最近匹配原则 FIRST(S)=i,a FIRST(S)=e, FIRST(C)=b FOLLOW(S)=e,$ FOLLOW(S)=e,$ FOLLOW(C)=t $ 4.3.6 预测分析的错误恢复预测分析的错误恢复 v程序可能的错误程序可能的错误: : 词法错误，如标识符、关键字或算符的拼写错词法错误，如标识

40、符、关键字或算符的拼写错 语法错误，如算术表达式的括号不配对语法错误，如算术表达式的括号不配对 语义错误，如算符作用于不相容的运算对象语义错误，如算符作用于不相容的运算对象 逻辑错误，如无穷的递归调用逻辑错误，如无穷的递归调用 v大多数错误的诊断和恢复集中在语法分析阶段。一个大多数错误的诊断和恢复集中在语法分析阶段。一个 原因是大多数错误是语法错误，另一个原因是语法分原因是大多数错误是语法错误，另一个原因是语法分 析方法的准确性，它们能以非常有效的方法诊断语法析方法的准确性，它们能以非常有效的方法诊断语法 错误。错误。 v在编译的时侯，想要准确诊断语义或逻辑错误有时是在编译的时侯，想要准确诊断

41、语义或逻辑错误有时是 很困难的很困难的 4.3.6 预测分析的错误恢复预测分析的错误恢复 v分析器对错误处理的基本目标分析器对错误处理的基本目标 清楚而准确地报告错误的出现清楚而准确地报告错误的出现 迅速地从每个错误中恢复过来，以便诊断后面迅速地从每个错误中恢复过来，以便诊断后面 的错误，并尽量少出现伪错误的错误，并尽量少出现伪错误 它不应该使正确程序的处理速度降低太多它不应该使正确程序的处理速度降低太多 v非递归预测分析在什么场合下发现错误非递归预测分析在什么场合下发现错误 栈顶的终结符和下一个输入符号不匹配栈顶的终结符和下一个输入符号不匹配 栈顶是非终结符栈顶是非终结符A A，输入符号是，

42、输入符号是a a，而，而M M A A , , a a 是空白是空白 4.3.6 预测分析的错误恢复预测分析的错误恢复 v非递归预测分析：采用紧急方式的错误恢复非递归预测分析：采用紧急方式的错误恢复 发现错误时，分析器每次抛弃一个输入记号，直发现错误时，分析器每次抛弃一个输入记号，直 到输入记号属于某个指定的到输入记号属于某个指定的同步记号同步记号集合为止集合为止 v例：下述两条是有语法错误的语句，其中第一条赋例：下述两条是有语法错误的语句，其中第一条赋 值句结束时忘记加分号，采用紧急恢复方式的可能值句结束时忘记加分号，采用紧急恢复方式的可能 结果如下所示。结果如下所示。 x := a + b

43、 y := c + d; 紧急方式：紧急方式： x := a + b + d; - 丢弃丢弃b之后的若干记号，之后的若干记号， 直到遇到直到遇到同步记号同步记号+为止。为止。 4.3.6 预测分析的错误恢复预测分析的错误恢复 v同步记号一般是定界符，如分号或同步记号一般是定界符，如分号或endend等。等。 v紧急方式的错误恢复的效果依赖于同步记号紧急方式的错误恢复的效果依赖于同步记号 集合的选择：集合的选择： 把把FOLLOW(FOLLOW(A A) )的所有终结符放入非终结符的所有终结符放入非终结符A A的同步的同步 记号集合记号集合 if if expr expr thenthen （t

44、henthen是是exprexpr的一个同步记号）的一个同步记号） 把高层结构的开始符号加到低层结构的同步记号把高层结构的开始符号加到低层结构的同步记号 集合中集合中 a a := := exprexpr ; if ; if （语句的开始符号作为表达式的同步符号，以免遗（语句的开始符号作为表达式的同步符号，以免遗 漏分号时忽略漏分号时忽略ifif语句等一大段程序）语句等一大段程序） 把把FIRST(FIRST(A A) )的终结符加入的终结符加入A A的同步记号集合的同步记号集合 a a := := exprexpr ; , if ; , if （语句的开始符号作为语句的同步符号，以免多（语句

45、的开始符号作为语句的同步符号，以免多 出一个逗号时会把出一个逗号时会把ifif语句忽略了）语句忽略了） 错误处理错误处理 如果非终结符可以产生空串，若出错时栈顶如果非终结符可以产生空串，若出错时栈顶 是这样的非终结符，则可以使用产生空串的是这样的非终结符，则可以使用产生空串的 产生式产生式 错误处理错误处理 v栈顶为栈顶为T ，面临，面临id时出错时出错 非终非终 结符结符 输输 入入 符符 号号 id+ . . . EETE E E +TE TTFT T 出错出错T T FT . . . 错误处理错误处理 vT 可以产生空串，报错并用可以产生空串，报错并用T 非终非终 结符结符 输输 入入

46、符符 号号 id+ . . . EETE E E +TE TTFT T 报错，用报错，用 T T T FT . . . 错误处理错误处理 v如果终结符在栈顶而不能匹配，弹出如果终结符在栈顶而不能匹配，弹出 此终结符此终结符 例例 E TE E + TE | T FT T FT | F (E) | id FOLLOW(E) = FOLLOW(E ) = ), $ FOLLOW(T) = FOLLOW (T ) = +, ), $ FOLLOW(F) = , +，), $ 注：注：synchsynch用来指示从非终结符的用来指示从非终结符的FOLLOWFOLLOW集合中得到集合中得到 的同步记号。

47、的同步记号。 i+*()# EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E) synch synchsynch synch synch synch synch synch synch $ 4.3.6 预测分析的错误恢复预测分析的错误恢复 v如果分析器查找条目如果分析器查找条目MA,aMA,a并发现它是空的，并发现它是空的， 则跳过输入符号则跳过输入符号a a；如果条目是；如果条目是synchsynch，则调，则调 用同步过程并把栈顶的非终结符弹出，恢复用同步过程并把栈顶的非终结符弹出，恢复 分析；如果栈顶的记号不匹配输入符号，则分析；如果

48、栈顶的记号不匹配输入符号，则 从栈顶弹出该记号。从栈顶弹出该记号。 vP136,P136,表表4.44.4 4.4 自底向上分析概述自底向上分析概述 v基本思想：从输入串开始，逐步进行基本思想：从输入串开始，逐步进行“归归 约约”，如果最后能得到文法的如果最后能得到文法的开始符号开始符号，则，则 输入串是合乎语法的句子，否则输入串有语输入串是合乎语法的句子，否则输入串有语 法错误。法错误。即从树末端开始，即从树末端开始，构造分析构造分析树树。 v核心：寻找句型中的核心：寻找句型中的“句柄句柄”进行归约，用进行归约，用 不同的方法寻找句柄，就可获得不同的分析不同的方法寻找句柄，就可获得不同的分析

49、 方法。方法。 G(E)： E i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E E i + + * * E i i E EE E 4.4 自底向上分析自底向上分析 4.4.1 归约归约 例例S aABe A Abc | b B d 所谓所谓归约归约，是指根据，是指根据 文法的产生式规则，文法的产生式规则， 把产生式的右部替换把产生式的右部替换 成左部符号成左部符号 4.4.1 归约归约 例例S aABe A Abc | b B d abbcde eabbdc 所谓所谓归约归约，是指根据，是指根据 文法的产生式规则，文法的产生式规

50、则， 把产生式的右部替换把产生式的右部替换 成左部符号成左部符号 4.4.1 归约归约 例例S aABe A Abc | b B d abbcde aAbcde eab A bdc 所谓所谓归约归约，是指根据，是指根据 文法的产生式规则，文法的产生式规则， 把产生式的右部替换把产生式的右部替换 成左部符号成左部符号 4.4.1 归约归约 例例S aABe A Abc | b B d abbcde aAbcde aAde eab A bd A c 所谓所谓归约归约，是指根据，是指根据 文法的产生式规则，文法的产生式规则， 把产生式的右部替换把产生式的右部替换 成左部符号成左部符号 4.4.1 归

51、约归约 例例S aABe A Abc | b B d abbcde aAbcde aAde aABe eab A bd A c B 所谓所谓归约归约，是指根据，是指根据 文法的产生式规则，文法的产生式规则， 把产生式的右部替换把产生式的右部替换 成左部符号成左部符号 4.4.1 归约归约 例例S aABe A Abc | b B d abbcde aAbcde aAde aABe S S eab A bd A c B 所谓所谓归约归约，是指根据，是指根据 文法的产生式规则，文法的产生式规则， 把产生式的右部替换把产生式的右部替换 成左部符号成左部符号 4.4.1 归约归约 例例S aABe A

52、 Abc | b B d abbcde aAbcde aAde aABe S S rm aABe rm aAde rm aAbcde rm abbcde S eab A bd A c B 所谓所谓归约归约，是指根据，是指根据 文法的产生式规则，文法的产生式规则， 把产生式的右部替换把产生式的右部替换 成左部符号成左部符号 4.4.2 句柄句柄 v定义定义 设设是文法是文法G的一个句型，若的一个句型，若 存在存在 S *A，A +，则，则 称称是句型是句型相对于相对于A的的 短语短语；特别的，若；特别的，若 有有A，则，则 称称是句型是句型 相对于产生式相对于产生式A的的直接短语直接短语（简单短

53、语简单短语）。 一个句型的最左直接短语被称为一个句型的最左直接短语被称为句柄句柄。 4.4.2 句柄句柄 v用分析树求用分析树求短语短语、简单短语简单短语和和句柄句柄的方法：的方法： 1 1）每个句型都有一棵分析树；）每个句型都有一棵分析树； 2 2）每棵分析树的叶（从左到右）组成一）每棵分析树的叶（从左到右）组成一句型句型； 3 3）每个子树的叶（从左到右）组成一）每个子树的叶（从左到右）组成一短语短语； 4 4）每个简单子树的叶（从左到右）组成一）每个简单子树的叶（从左到右）组成一简简 单短语单短语； 5 5）最左简单子树的叶（从左到右）组成一）最左简单子树的叶（从左到右）组成一句句 柄柄

54、。 b db ace S AB A d b ace S AB A d ace S AB ace S AB S S aAcBe A Ab | b B d abbcde 规范归约规范归约 v定义定义：假定：假定 是文法是文法G的一个句子，我们称序列的一个句子，我们称序列 n， n-1， ， 0 是一个是一个规范归约规范归约（最左归约最左归约），如果此序列满足：），如果此序列满足： 1 n= 2 0为文法的开始符号，即为文法的开始符号，即 0=S 3 对任何对任何i，0 i n， i-1是从是从 i经把经把句柄句柄替换成为替换成为 相应产生式左部非终结符而得到的。相应产生式左部非终结符而得到的。 v

55、提醒提醒：最左归约最左归约的逆过程是一个的逆过程是一个最右推导最右推导，分别，分别 称称最右推导最右推导和和最左归约最左归约为为规范推导规范推导和和规范归约规范归约 4.4.3 移进移进 归约分析归约分析 v采用采用“移进归约移进归约”思想进行自底向上分析。思想进行自底向上分析。 v基本思想：用一个寄存符号的栈，基本思想：用一个寄存符号的栈，把输入符把输入符 号号按从左到右的顺序一个一个地移进到栈里按从左到右的顺序一个一个地移进到栈里， 边移入边分析，当栈顶形成某个产生式的边移入边分析，当栈顶形成某个产生式的句句 柄柄（即为某产生式的右部）时，即把栈顶的（即为某产生式的右部）时，即把栈顶的 这

56、一部分替换成这一部分替换成( (归约归约为为) )该产生式的左部符该产生式的左部符 号号。最终如果栈顶为文法的开始符号，则所。最终如果栈顶为文法的开始符号，则所 分析的输入符号串为合法的符号串，报告分分析的输入符号串为合法的符号串，报告分 析成功析成功, ,否则，是不合格的符号串，报告错误。否则，是不合格的符号串，报告错误。 例：设文法例：设文法G(S)： (1) S aAcBe (2) A b (3) A Ab (4) B d 试对试对abbcde进行进行“移进归约移进归约”分析。分析。 a bbcde b a bcde A a bcde b A a cde A a cde c A a de

57、 d c A a eabbcde e B c A a S B c A a e 例：考虑文法例：考虑文法G(E)：EE +T |T TT*F | F Fi| (E) 并假定输入串为并假定输入串为（i+i)*i，考察自底向上的分析过程。，考察自底向上的分析过程。 步骤步骤 分析栈分析栈 输入串输入串 动作动作 $ (i+i)$ (i+i)* *i$ i$ 移进移进 $( i+i)$( i+i)* *i$ i$ 移进移进 $(i +i)$(i +i)* *i$ i$ 归约归约 $(F +i)$(F +i)* *i$ i$ 归约归约 $(T +i)$(T +i)* *i$ i$ 归约归约 $(E +i

58、)$(E +i)* *i$ i$ 移进移进 $(E+ i)$(E+ i)* *i$ i$ 移进移进 $(E+i )$(E+i )* *i$ i$ 归约归约 $(E+F )$(E+F )* *i$ i$ 归约归约 1 1 步骤步骤 分析栈分析栈 输入串输入串 动作动作 10 $(E+T )10 $(E+T )* *i$ i$ 归约归约 11 $(E )11 $(E )* *i$ i$ 移进移进 12 $(E) 12 $(E) * *i$ i$ 归约归约 13 $F 13 $F * *i$ i$ 归约归约 14 $T 14 $T * *i$ i$ 移进移进 15 $T15 $T* * i$ i$

59、移进移进 16 $T16 $T* *i $ i $ 归约归约 17 $T17 $T* *F $ F $ 归约归约 18 $T $ 18 $T $ 归约归约 $E $ $E $ 接受接受 移进移进 归约分析归约分析 v分析栈上的候选式不一定是句柄。例如，在第分析栈上的候选式不一定是句柄。例如，在第1414步步 时栈顶为时栈顶为T T，它是，它是E E的一候选式，但它不是的一候选式，但它不是句柄句柄，不，不 能归约成能归约成E E。判定候选式是极为简单的事情，但判。判定候选式是极为简单的事情，但判 定句柄就不那么容易。而不同的自底向上方法给出定句柄就不那么容易。而不同的自底向上方法给出 不同的判定

60、方法。不同的判定方法。 v自底向上方法主要包括以下四个动作：自底向上方法主要包括以下四个动作： 移进移进：把下一个输入符号读到分析栈中：把下一个输入符号读到分析栈中 归约归约：把分析栈顶的句柄归约为一非终结符：把分析栈顶的句柄归约为一非终结符 接受接受：分析成功：分析成功 报错报错：处理错误：处理错误 移进移进 归约分析归约分析 v注意两点：注意两点： （1 1）栈内符号串）栈内符号串+ + 未处理输入符号串未处理输入符号串 = = 当当 前前句型句型 （2 2）句柄都在）句柄都在栈顶栈顶 v这一方法的关键是确定当前句型的句柄这一方法的关键是确定当前句型的句柄 v实际上，以上分析过程并未真正解