编译原理语法分析

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语法分析器的主要作用有两点：语法分析器的主要作用有两点： 检查词法分析器输出的单词序列是否是源语言中检查词法分析器输出的单词序列是否是源语言中的句子，亦即是否符合源语言的语法规则的句子，亦即是否符合源语言的语法规则 检查输入中的语法（可能包括词法）错误，并调检查输入中的语法（可能包括词法）错误，并调用出错处理器进行适当处理用出错处理器进行适当处理v两大类分析方法：两大类分析方法：自顶向下分析自顶向下分析自底向上分析自底向

4、上分析存在主要问题存在主要问题: 左递归问题左递归问题 回溯问题回溯问题 主要方法主要方法: 递归子程序法递归子程序法 预测分析法预测分析法 (LL(1)自顶向下分析算法的基本思想为：自顶向下分析算法的基本思想为：有符号串有符号串S若若Z S 则则 S L(GZ) 否则否则 S L(GZ) Gz+从文法产生语言的角度从文法产生语言的角度ASaSbSAaaba aSbAS aabAS aabbaS aabbaa aAS SP: SaAS a A SbA SS ba句子句子：aabbaa自底向上分析算法的基本思想为：自底向上分析算法的基本思想为：+若若Z S 则则 S L(GZ) 否则否则 S L

5、(GZ) Gz存在主要问题存在主要问题: 句柄的识别问题句柄的识别问题主要方法主要方法: 算法优先分析法算法优先分析法 LR分析法分析法从自动机识别语言的角从自动机识别语言的角度度ASaSbSAaaba aAa aSbAa aSbbaa aabbaa aAS SP: SaAS a A SbA SS ba句子句子：aabbaa4.2 书写文法书写文法v定义定义：如果一个文法有非终结符：如果一个文法有非终结符A，对某个串，对某个串，存，存在推导在推导A +A ，则称该文法是则称该文法是左递归左递归的。形式为的。形式为AA的产生式引起的左递归称为的产生式引起的左递归称为直接左递归直接左递归。v直接左

6、递归直接左递归AAa |b 串的特点串的特点 ba . . . av消除直接左递归消除直接左递归A b A A a A | 左递归变右左递归变右递归递归4.2.1 消除左递归消除左递归4.2.1 消除左递归消除左递归v一般而言，假定关于一般而言，假定关于P的全部产生式是的全部产生式是 PP 1 | P 2 | | P m | 1 | 2| n其中，每个其中，每个 都不等于都不等于 ，每个，每个 都不以都不以P开头开头 那么，消除那么，消除P的直接左递归就是把这些规则改的直接左递归就是把这些规则改写成：写成： P 1P | 2P | | nP P 1P | 2P | | mP | 左递归变右左递

7、归变右递归递归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 ) | id4.2.1 消除左递归消除左递归v非直接左递归非直接左递归S Aa | b A Sd | v先变换成直接左递归先变换成直接左递归S Aa | bA Aad | bd | v再消除左递归再消除左递归S Aa | bA bd A | A A adA | 4.2.1 消除左递归消

8、除左递归v例例 考虑文法考虑文法G(S)SQc|cQRb|b (3.1)RSa|av令它的非终结符的排序为令它的非终结符的排序为R、Q、S。v对于对于R，不存在直接左递归。，不存在直接左递归。v把把R代入到代入到Q的有关候选后，把的有关候选后，把Q的的规则变为规则变为 QSab | ab | b4.2.1 消除左递归消除左递归v例例 考虑文法考虑文法G(S)SQc|cQRb|bRSa|av令它的非终结符的排序为令它的非终结符的排序为R、Q、S。vQ的规则变为的规则变为 QSab | ab | bv现在的现在的Q不含直接左递归，把它代入到不含直接左递归，把它代入到S的有的有关候选后，关候选后，S

9、变成变成 SSabc | abc | bc | c4.2.1 消除左递归消除左递归v例例 考虑文法考虑文法G(S)SQc|cQRb|bRSa|avS变成变成 SSabc | abc | bc | cv消除消除S的直接左递归后：的直接左递归后：SabcS | bcS | cS S abcS | QSab |ab | bRSa|a4.2.1 消除左递归消除左递归v消除消除S的直接左递归后：的直接左递归后：SabcS | bcS | cS S abcS | QSab |ab | bRSa|av关于关于Q和和R的规则已是多余的，化简为：的规则已是多余的，化简为：SabcS | bcS | cS S a

10、bcS | (3.2)4.2.1 消除左递归消除左递归v注意，由于对非终结符排序的不同，最后所得的文注意，由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但不难证明，它们都是等法在形式上可能不一样。但不难证明，它们都是等价的。价的。v例如，若对文法例如，若对文法(3.1)的非终结符排序选为的非终结符排序选为S、Q、R，那么，最后所得的无左递归文法是：那么，最后所得的无左递归文法是：SQc | cQRb | bRbcaR | caR |a R (3.3)R bca R | v文法文法(3.2)和和(3.3)的等价性是显然的。的等价性是显然的。4.2.2 提左因子提左因子v有左因子的文

11、法有左因子的文法A 1 | 2v提左因子提左因子A A A 1 | 2 4.2.2 提左因子提左因子v例例 悬空悬空else的文法的文法 stmt if expr then stmt else stmt | if expr then stmt | otherv提左因子提左因子stmtif expr then stmt optional_else_part | otheroptional_else_part else stmt | 4.3 自顶向下分析自顶向下分析v自顶向下分析就是从文法的自顶向下分析就是从文法的开始符号开始符号出发，向下出发，向下推推导导，推出句子。，推出句子。带带“回溯回溯”

12、的分析方法的分析方法不带回溯的递归子程序不带回溯的递归子程序( (递归下降递归下降) )分析方法分析方法v自顶向下分析的主旨：对任何输入串，试图用一切自顶向下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号可能的办法，从文法开始符号( (根结点根结点) )出发，自上出发，自上而下、而下、从左到右从左到右地为输入串建立一棵地为输入串建立一棵分析树分析树。或者。或者说，为输入串寻找一个说，为输入串寻找一个最左推导最左推导。v分析是一种试探的过程，是反复使用不同产生式谋分析是一种试探的过程，是反复使用不同产生式谋求与输入序列匹配的过程。求与输入序列匹配的过程。4.3.1 自顶向下分析的

13、一般方法自顶向下分析的一般方法v例例 假定有文法假定有文法G(S): (1) SxAy (2) A*|* 分析分析输入串输入串x*y(记为记为 )。Sx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*Sx*yIPAxySx*yIPAxySx*yIP分析成功！分析成功！4.3.1 自顶向下分析的一般方法自顶向下分析的一般方法v困难和缺点：困难和缺点：不能处理左递归（分析陷入无限循环）不能处理左递归（分析陷入无限循环）分析过程中，当一个非终结符用某一个候选匹配分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是成功时，这种匹配可能是暂时暂时的的。出错出错时时

14、，不得，不得不不“回溯回溯”。回溯导致语义工作推倒重来回溯导致语义工作推倒重来分析器难以报告输入串出错的确切位置分析器难以报告输入串出错的确切位置效率低，代价高，只有理论意义效率低，代价高，只有理论意义4.3.2 LL(1)文法文法v构造不带回溯的自上而下分析算法构造不带回溯的自上而下分析算法要消除文法的左递归性要消除文法的左递归性克服回溯克服回溯v为了消除回溯就必须保证：对文法的任何非为了消除回溯就必须保证：对文法的任何非终结符，当要用它去匹配输入串时，能够根终结符，当要用它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个据它所面临的输入符号准确地指派它的一个候选去执行任务，并且

15、此候选的工作结果应候选去执行任务，并且此候选的工作结果应是确信无疑的。是确信无疑的。v例例 文法文法G(S): (1) SxAy (2) A*|*v例如例如, 对于下面文法，面临对于下面文法，面临a时不知用什么时不知用什么规则规则S A BA a b | B a CC 4.3.2 LL(1)文法文法v先定义两个和文法有关的函数：先定义两个和文法有关的函数：令令G是一个不含是一个不含左递归左递归的文法，对的文法，对G的所有非终结符的每个的所有非终结符的每个候选候选 定义它的终结首符集定义它的终结首符集FIRST( )为：为：特别是，若特别是，若 * ，则规定，则规定FIRST( )如果非终结符如

16、果非终结符A的所有候选首符集两两不相交，即的所有候选首符集两两不相交，即A的任何的任何两个不同候选两个不同候选 i和和 j FIRST( i)FIRST( j) 当要求当要求A匹配输入串时，匹配输入串时，A就能根据它所面临的第一个输入符就能根据它所面临的第一个输入符号号a，准确地指派某一个候选前去执行任务。这个候选就是，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含那个终结首符集含a的的 。v经过经过反复提取左因子反复提取左因子，能够把每个非终结符的所有候选首符集，能够把每个非终结符的所有候选首符集变成为两两不相交。变成为两两不相交。.,|=)(*TVaaaFIRST问题：对文

17、法加什么样的限制可以保证没有回溯？问题：对文法加什么样的限制可以保证没有回溯？构造构造FIRST( )v对文法对文法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

18、*FT | F(E) | i 分析输入串：分析输入串：i + ii + i IPEnG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEnG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTnG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTinG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTinG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEF

19、Ti nG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEnG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEnG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEFTnG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEFTinG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEFTinG(E

20、): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEFTi nG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEFTi nG(E): ETE E +TE | TFT T *FT | F(E) | iE T+对于对于+ +的匹配只能依赖于在可能的推的匹配只能依赖于在可能的推导过程中导过程中TT的后面的字符的后面的字符4.3.2 LL(1)文法文法v若若FIRST ( i ) 或或 FIRST ( j )含含 ，还需增加条，还需增加条件件v假定假定S是文法是文法G的开始符号，对于的开

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

22、有 元素这样的规则，则元素这样的规则，则FOLLOW (A) 的元素的元素属于属于FOLLOW (B ) v例例 E TE E + TE | T FT T FT | F (E) | idFIRST(E) = FIRST(T) = FIRST(F) = ( , id FIRST(E ) = +, FRIST(T ) = , FOLLOW(E) = ), $FOLLOW(E ) = FOLLOW(E) FOLLOW(T) = FIRST(E ) U FOLLOW(E) = +, ), $FOLLOW (T ) = FOLLOW(T) FOLLOW(F) = FRIST(T ) U FOLLOW(T

23、) = , +，), $ 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,$beacddce4.3.2 LL(1)文法文法v构造不带回溯的自上而下分析的文法条件构造不带回溯的自上而下分析的文法条件1. 文法不含左递归，文法不含左递归

24、，2. 对于文法中每一个非终结符对于文法中每一个非终结符A的各个产生式的候选首符集的各个产生式的候选首符集两两不相交。即，若两两不相交。即，若 A 1| 2| n 则则 FIRST( i)FIRST( j) (i j)3. 对文法中的每个非终结符对文法中的每个非终结符A，若它存在某个候选首符集包，若它存在某个候选首符集包含含 ，则，则 FIRST( i)FOLLOW(A)= i=1,2,.,nv如果一个文法如果一个文法G满足以上条件，则称该文法满足以上条件，则称该文法G为为LL(1)文法文法。第一个第一个L代表从代表从左向右扫描左向右扫描输入符号串，第二个输入符号串，第二个L代表产生代表产生最

25、最左推导左推导，1代表在分析过程中执行每步推导都要代表在分析过程中执行每步推导都要向前查看一向前查看一个输入符号个输入符号 4.3.2 LL(1)文法文法v例例1：G1A: AaABe B BbbG1A不是不是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 BSDe BSAccD D Se G3S不是不是LL(1)文法，因为文法，因为FIRST(SAc) FOLLOW(B)=a,d 4.3.2

26、LL(1)文法文法vLL(1)LL(1)文法有一些明显的性质文法有一些明显的性质没有公共左因子没有公共左因子不含左递归不含左递归不是二义的不是二义的4.3.2 LL(1)文法文法v对于一个满足上述条件的文法，可以对其输入串进对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要用非终结行有效的无回溯的自上而下分析。假设要用非终结符符A进行匹配，面临的输入符号为进行匹配，面临的输入符号为a，A的所有产生的所有产生式为式为 A 1 | 2 | | n1. 若若a FIRST( i)，则指派，则指派 i执行匹配任务；执行匹配任务；2. 若若a不属于任何一个候选首符集，则：不

27、属于任何一个候选首符集，则： (1) 若若 属于某个属于某个FIRST( i )且且 a FOLLOW(A)， 则让则让A与与 自动匹配。自动匹配。 (2) 否则，否则，a的出现是一种语法错误。的出现是一种语法错误。4.3.3 递归的预测分析递归的预测分析v预测分析预测分析是指能根据当前的输入符号为非终结符确定用哪一是指能根据当前的输入符号为非终结符确定用哪一个选择个选择,LL(1),LL(1)文法满足此要求文法满足此要求v递归的预测分析是为递归的预测分析是为每一个非终结符每一个非终结符写一个分析过程写一个分析过程, ,这些这些过程可能是递归的过程可能是递归的v在处理输入串时在处理输入串时,

28、,首先执行的是对应开始符号的过程首先执行的是对应开始符号的过程, ,然后根然后根据产生式右部出现的非终结符据产生式右部出现的非终结符, ,依次调用相应的过程依次调用相应的过程, ,这种逐这种逐步下降的过程调用序列隐含地定义了输入串的分析树步下降的过程调用序列隐含地定义了输入串的分析树例例：type simple | id | array simple of typesimple integer | char | num dotdot num4.3.3 递归的预测分析递归的预测分析一个辅助过程一个辅助过程procedure match (t : token);beginif lookahead

29、= t thenlookahead := nexttoken( )else error( )end;proccdure type;beginif lookahead in integer, char, num thensimple( )else if lookahead = then beginmatch (); match (id) endelse if lookahead = array then beginmatch (array); match ( ); simple( ); match ( ); match (of ); type( )endelse error( )end;type

30、 simple | id | array simple of typeprocedure simple;beginif lookahead = integer then match (integer)else if lookahead = char then match (char)else if lookahead = num then begin match (num); match (dotdot); match (num)endelse error( )end;simple integer | char | num dotdot num4.3.4 非递归的预测分析非递归的预测分析v如果

31、显式地维持一个状态栈如果显式地维持一个状态栈, ,而不是隐式地通过递而不是隐式地通过递归调用归调用, ,则可以构造非递归的预测分析器则可以构造非递归的预测分析器v预测分析的关键问题是决定取哪个产生式运用于预测分析的关键问题是决定取哪个产生式运用于非终结符（通过查分析表来决定产生式）非终结符（通过查分析表来决定产生式）v预测分析器组成：输入缓冲区（存放要分析的串，预测分析器组成：输入缓冲区（存放要分析的串，以以$ $作为结束标记）、栈（存放文法符号，栈底符作为结束标记）、栈（存放文法符号，栈底符号是号是$)$)、分析表（两维数组、分析表（两维数组MA,a,AMA,a,A是非终结符，是非终结符，a

32、 a是终结符或是终结符或$)$)和输出流。和输出流。4.3.4 非递归的预测分析非递归的预测分析a + b $输入输入预测分析程序预测分析程序分析表分析表M输出输出 XYZ$栈栈分析器工作过程分析器工作过程v预测分析程序根据现行栈顶符号预测分析程序根据现行栈顶符号X X和当前输入和当前输入符号符号a a，执行下列四种动作之一，执行下列四种动作之一: :1. 1. 若若X Xa a$，则宣布分析成功，停止分析。，则宣布分析成功，停止分析。2. 2. 若若X Xa a $，则把，则把X X从栈顶逐出，推进输入从栈顶逐出，推进输入指针，指向下一个输入符号。指针，指向下一个输入符号。3. 3. 若若X

33、 X是终结符但不是是终结符但不是a a，则分析器报告出错，调，则分析器报告出错，调用错误恢复例程。用错误恢复例程。分析器工作过程分析器工作过程4. 4. 若若X X是非终结符，程序访问分析表是非终结符，程序访问分析表若若MXMX，aa中存放着关于中存放着关于X X的一个产生式，把的一个产生式，把X X逐逐出出STACKSTACK栈顶，栈顶，把产生式的右部符号串按反序一把产生式的右部符号串按反序一一推进一推进STACKSTACK栈栈( (若右部符号为若右部符号为 ，则意味不推什，则意味不推什么东西进栈么东西进栈) )。若若MXMX，aa中存放着中存放着“出错标志出错标志”，则调用错误，则调用错误

34、恢复例程。恢复例程。分析表分析表非终非终结符结符输输 入入 符符 号号 id + . . .E E TE E E +TE T T FT T T T FT F F id 预测分析器接受输入预测分析器接受输入id + id * id的动作的动作 栈栈 输输 入入 输输 出出 $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 *

35、 id$ id * id$E T id$E T $E $E T +$E T T FT F idT E +TE 4.3.5 构造预测分析表构造预测分析表算法算法4.3(1)对文法的每个产生式对文法的每个产生式A ，执行，执行(2)和和(3)(2)对对FIRST( )的每个终结符的每个终结符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) |

36、i FIRST(E) = FIRST(T) = FIRST(F) = ( , i FIRST(E ) = +, FRIST(T ) = , FOLLOW(E) = FOLLOW(E ) = ), $ FOLLOW(T) = FOLLOW (T ) = +, ), $ 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至少含至少含有一个有一个多重定义条目多重定义条目。因此，消除左递归和。

37、因此，消除左递归和提取左因子将有助于获得无多重定义的分析提取左因子将有助于获得无多重定义的分析表表M。v可以证明，一个文法可以证明，一个文法G的预测分析表的预测分析表M不含不含多重定义条目，当且仅当该文法为多重定义条目，当且仅当该文法为LL(1)的。的。G(S):S iCtS | iCtSeS | aC b提取左因子之后，改写成：提取左因子之后，改写成：G(S):S iCtSS | aS eS | C babeit#SSaSiCtSS S S S eSS CCbF (E)最近匹配原则最近匹配原则 FIRST(S)=i,a FIRST(S)=e, FIRST(C)=bFOLLOW(S)=e,$

38、FOLLOW(S)=e,$FOLLOW(C)=t$4.3.6 预测分析的错误恢复预测分析的错误恢复v程序可能的错误程序可能的错误: : 词法错误，如标识符、关键字或算符的拼写错词法错误，如标识符、关键字或算符的拼写错 语法错误，如算术表达式的括号不配对语法错误，如算术表达式的括号不配对 语义错误，如算符作用于不相容的运算对象语义错误，如算符作用于不相容的运算对象 逻辑错误，如无穷的递归调用逻辑错误，如无穷的递归调用v大多数错误的诊断和恢复集中在语法分析阶段。一个大多数错误的诊断和恢复集中在语法分析阶段。一个原因是大多数错误是语法错误，另一个原因是语法分原因是大多数错误是语法错误，另一个原因是语

39、法分析方法的准确性，它们能以非常有效的方法诊断语法析方法的准确性，它们能以非常有效的方法诊断语法错误。错误。v在编译的时侯，想要准确诊断语义或逻辑错误有时是在编译的时侯，想要准确诊断语义或逻辑错误有时是很困难的很困难的4.3.6 预测分析的错误恢复预测分析的错误恢复v分析器对错误处理的基本目标分析器对错误处理的基本目标清楚而准确地报告错误的出现清楚而准确地报告错误的出现迅速地从每个错误中恢复过来，以便诊断后面迅速地从每个错误中恢复过来，以便诊断后面的错误，并尽量少出现伪错误的错误，并尽量少出现伪错误它不应该使正确程序的处理速度降低太多它不应该使正确程序的处理速度降低太多v非递归预测分析在什么场

40、合下发现错误非递归预测分析在什么场合下发现错误栈顶的终结符和下一个输入符号不匹配栈顶的终结符和下一个输入符号不匹配栈顶是非终结符栈顶是非终结符A A，输入符号是，输入符号是a a，而，而M M A A , , a a 是空白是空白4.3.6 预测分析的错误恢复预测分析的错误恢复v非递归预测分析：采用紧急方式的错误恢复非递归预测分析：采用紧急方式的错误恢复 发现错误时，分析器每次抛弃一个输入记号，直发现错误时，分析器每次抛弃一个输入记号，直到输入记号属于某个指定的到输入记号属于某个指定的同步记号同步记号集合为止集合为止v例：下述两条是有语法错误的语句，其中第一条赋例：下述两条是有语法错误的语句，

41、其中第一条赋值句结束时忘记加分号，采用紧急恢复方式的可能值句结束时忘记加分号，采用紧急恢复方式的可能结果如下所示。结果如下所示。 x := a + b y := c + d;紧急方式：紧急方式： x := a + b + d; - 丢弃丢弃b之后的若干记号，之后的若干记号，直到遇到直到遇到同步记号同步记号+为止。为止。4.3.6 预测分析的错误恢复预测分析的错误恢复v同步记号一般是定界符，如分号或同步记号一般是定界符，如分号或endend等。等。v紧急方式的错误恢复的效果依赖于同步记号紧急方式的错误恢复的效果依赖于同步记号集合的选择：集合的选择：把把FOLLOW(FOLLOW(A A) )的所

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

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

44、误处理错误处理vT 可以产生空串，报错并用可以产生空串，报错并用T 非终非终结符结符 输输 入入 符符 号号 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用来指示

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

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

47、析不同的方法寻找句柄，就可获得不同的分析方法。方法。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 Ei+ +* *EiiEEEE4.4 自底向上分析自底向上分析4.4.1 归约归约例例S aABe A Abc | bB d所谓所谓归约归约，是指根据，是指根据文法的产生式规则，文法的产生式规则，把产生式的右部替换把产生式的右部替换成左部符号成左部符号4.4.1 归约归约例例S aABe A Abc | bB dabbcdeeabbdc所谓所谓归约归约，是指根据，是指根据文法的产生式规则，文法的产生式规则，把产生式

48、的右部替换把产生式的右部替换成左部符号成左部符号4.4.1 归约归约例例S aABe A Abc | bB dabbcdeaAbcdeeabAbdc所谓所谓归约归约，是指根据，是指根据文法的产生式规则，文法的产生式规则，把产生式的右部替换把产生式的右部替换成左部符号成左部符号4.4.1 归约归约例例S aABe A Abc | bB dabbcdeaAbcdeaAdeeabAbdAc所谓所谓归约归约，是指根据，是指根据文法的产生式规则，文法的产生式规则，把产生式的右部替换把产生式的右部替换成左部符号成左部符号4.4.1 归约归约例例S aABe A Abc | bB dabbcdeaAbcde

49、aAdeaABeeabAbdAcB所谓所谓归约归约，是指根据，是指根据文法的产生式规则，文法的产生式规则，把产生式的右部替换把产生式的右部替换成左部符号成左部符号4.4.1 归约归约例例S aABe A Abc | bB dabbcdeaAbcdeaAdeaABeS SeabAbdAcB所谓所谓归约归约，是指根据，是指根据文法的产生式规则，文法的产生式规则，把产生式的右部替换把产生式的右部替换成左部符号成左部符号4.4.1 归约归约例例S aABe A Abc | bB dabbcdeaAbcdeaAdeaABeS S rm aABe rm aAde rm aAbcde rm abbcdeSe

50、abAbdAcB所谓所谓归约归约，是指根据，是指根据文法的产生式规则，文法的产生式规则，把产生式的右部替换把产生式的右部替换成左部符号成左部符号4.4.2 句柄句柄v定义定义 设设是文法是文法G的一个句型，若的一个句型，若 存在存在S *A，A +，则，则 称称是句型是句型相对于相对于A的的短语短语；特别的，若；特别的，若 有有A，则，则 称称是句型是句型相对于产生式相对于产生式A的的直接短语直接短语（简单短语简单短语）。一个句型的最左直接短语被称为一个句型的最左直接短语被称为句柄句柄。4.4.2 句柄句柄v用分析树求用分析树求短语短语、简单短语简单短语和和句柄句柄的方法：的方法：1 1）每个

51、句型都有一棵分析树；）每个句型都有一棵分析树；2 2）每棵分析树的叶（从左到右）组成一）每棵分析树的叶（从左到右）组成一句型句型；3 3）每个子树的叶（从左到右）组成一）每个子树的叶（从左到右）组成一短语短语；4 4）每个简单子树的叶（从左到右）组成一）每个简单子树的叶（从左到右）组成一简简单短语单短语；5 5）最左简单子树的叶（从左到右）组成一）最左简单子树的叶（从左到右）组成一句句柄柄。bdbaceSABAdbaceSABAdaceSABaceSABSS aAcBe A Ab | b B dabbcde规范归约规范归约v定义定义：假定：假定 是文法是文法G的一个句子，我们称序列的一个句子，

52、我们称序列 n， n-1， ， 0 是一个是一个规范归约规范归约（最左归约最左归约），如果此序列满足：），如果此序列满足： 1 n= 2 0为文法的开始符号，即为文法的开始符号，即 0=S 3 对任何对任何i，0 i n， i-1是从是从 i经把经把句柄句柄替换成为替换成为相应产生式左部非终结符而得到的。相应产生式左部非终结符而得到的。v提醒提醒：最左归约最左归约的逆过程是一个的逆过程是一个最右推导最右推导，分别，分别称称最右推导最右推导和和最左归约最左归约为为规范推导规范推导和和规范归约规范归约4.4.3 移进移进 归约分析归约分析v采用采用“移进归约移进归约”思想进行自思想进行自底向底向上

53、分析上分析。v基本思想：用一个寄存符号的栈，基本思想：用一个寄存符号的栈，把输入符把输入符号号按从左到右的顺序一个一个地移进到栈里按从左到右的顺序一个一个地移进到栈里，边移入边分析，边移入边分析，当栈顶形成某个产生式的当栈顶形成某个产生式的句句柄柄（即为某产生式的右部）（即为某产生式的右部）时，即把栈顶的时，即把栈顶的这一部分替换成这一部分替换成( (归约归约为为) )该产生式的左部符该产生式的左部符号号。最终如果栈顶为文法的开始符号，则所最终如果栈顶为文法的开始符号，则所分析的输入符号串为合法的符号串，报告分分析的输入符号串为合法的符号串，报告分析成功析成功, ,否则，是不合格的符号串，报告

54、错误。否则，是不合格的符号串，报告错误。例：设文法例：设文法G(S)： (1) S aAcBe (2) A b (3) A Ab (4) B d试对试对abbcde进行进行“移进归约移进归约”分析。分析。a bbcdeba bcdeAa bcdebAa cdeAa cdecAa dedcAa eabbcdeeBcAa S BcAa e例：考虑文法例：考虑文法G(E)：EE +T |T TT*F | F Fi| (E)并假定输入串为并假定输入串为（i+i)*i，考察自底向上的分析过程。，考察自底向上的分析过程。步骤步骤 分析栈分析栈 输入串输入串 动作动作1 1 $ (i+i)$ (i+i)*

55、*i$ i$ 移进移进2 2 $( i+i)$( i+i)* *i$ i$ 移进移进3 3 $(i +i)$(i +i)* *i$ i$ 归约归约4 4 $(F +i)$(F +i)* *i$ i$ 归约归约5 5 $(T +i)$(T +i)* *i$ i$ 归约归约6 6 $(E +i)$(E +i)* *i$ i$ 移进移进7 7 $(E+ i)$(E+ i)* *i$ i$ 移进移进8 8 $(E+i )$(E+i )* *i$ i$ 归约归约9 9 $(E+F )$(E+F )* *i$ i$ 归约归约 步骤步骤 分析栈分析栈 输入串输入串 动作动作10 $(E+T )10 $(E+

56、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$ 移进移进16 $T16 $T* *i $ i $ 归约归约17 $T17 $T* *F $ F $ 归约归约18 $T $ 18 $T $ 归约归约1919 $E $E $ 接受接受移进移进 归约分析归约分析v分析栈上的候选式不一定是句柄。例如，在第分析栈上的候选式不一定是句柄。例如，在第1414步步时栈顶为时栈

57、顶为T T，它是，它是E E的一候选式，但它不是的一候选式，但它不是句柄句柄，不，不能归约成能归约成E E。判定候选式是极为简单的事情，但判。判定候选式是极为简单的事情，但判定句柄就不那么容易。而不同的自底向上方法给出定句柄就不那么容易。而不同的自底向上方法给出不同的判定方法。不同的判定方法。v自底向上方法主要包括以下四个动作：自底向上方法主要包括以下四个动作：移进移进：把下一个输入符号读到分析栈中：把下一个输入符号读到分析栈中归约归约：把分析栈顶的句柄归约为一非终结符：把分析栈顶的句柄归约为一非终结符接受接受：分析成功：分析成功报错报错：处理错误：处理错误移进移进 归约分析归约分析v注意两点

58、：注意两点：（1 1）栈内符号串）栈内符号串+ + 未处理输入符号串未处理输入符号串 = = 当当前前句型句型（2 2）句柄都在）句柄都在栈顶栈顶v这一方法的关键是确定当前句型的句柄这一方法的关键是确定当前句型的句柄v实际上，以上分析过程并未真正解决句柄实际上，以上分析过程并未真正解决句柄的识别问题的识别问题 移进移进 归约分析的冲突归约分析的冲突v有些上下文无关文法不能使用移进有些上下文无关文法不能使用移进归约分析。这归约分析。这些文法的移进些文法的移进归约分析器可能面临两种情况：归约分析器可能面临两种情况：分析器根据栈中的所有内容和下一个输入符号不分析器根据栈中的所有内容和下一个输入符号不

59、能决定是移进还是归约（能决定是移进还是归约（移进移进归约冲突归约冲突）分析器不能决定按哪一个产生式进行归约（分析器不能决定按哪一个产生式进行归约（归归约约归约冲突归约冲突）2021-12-22944.4.4 优先法优先法v根据归约的先后次序为句型中相邻的文法符号根据归约的先后次序为句型中相邻的文法符号规定优先关系规定优先关系句柄内相邻符号同时归约，是同优先的句柄内相邻符号同时归约，是同优先的句柄两端符号的优先级要高于句柄外与之相邻的句柄两端符号的优先级要高于句柄外与之相邻的符号符号va1ai-1 aiai+1aj-1aj aj+1anv定义了这种优先关系之后，语法分析程序就可定义了这种优先关系

60、之后，语法分析程序就可以通过以通过ai-1 ai和和aj aj+1这两个关系来确定句柄这两个关系来确定句柄的头和尾了的头和尾了 2021-12-2295v根据句柄的识别状态（根据句柄的识别状态（句柄是逐步形成的句柄是逐步形成的）用状态来描述不同时刻下形成的那部分句柄用状态来描述不同时刻下形成的那部分句柄因为句柄是产生式的右部，可用产生式来表示句因为句柄是产生式的右部，可用产生式来表示句柄的不同识别状态柄的不同识别状态v例如：例如： SbBB可分解为如下识别状态可分解为如下识别状态S.bBB 移进移进bSbB.B 等待归约出等待归约出BSb.BB 等待归约出等待归约出BSbBB. 归约归约v采用