1、编译原理第四章第四章 语法分析语法分析自上而下分析自上而下分析第四章第四章 语法分析语法分析自上而下分析自上而下分析n本章主要介绍本章主要介绍语法分析语法分析的处理的处理n要进行语法分析，必须对语言的要进行语法分析，必须对语言的语法结构语法结构进行描述。进行描述。采用采用正规式和有限自动机正规式和有限自动机可以描述和识别语言可以描述和识别语言的的单词符号单词符号；用用上下文无关文法上下文无关文法来描述来描述语法规则语法规则。n上下文无关文法上下文无关文法的定义：的定义： 一个上下文无关文法一个上下文无关文法G G是一个四元式是一个四元式 G=(VG=(VT T，V VN N，S S，P)P)，
2、其中，其中V VT T：终结符终结符集合集合( (非空非空) )V VN N：非终结符非终结符集合集合( (非空非空) )，且，且V VT T V VN N= =S S：文法的：文法的开始符号开始符号，S S V VN NP P：产生式产生式集合集合( (有限有限) )，每个产生式形式为每个产生式形式为A A， A A V VN N， ( (V VT T V VN N) )* *开始符开始符S S至少必须在某个产生式的左部出现一次。至少必须在某个产生式的左部出现一次。n例，定义只含例，定义只含+，*的算术表达式的文法的算术表达式的文法 G=， 其其中，中，P由下列产生式组成：由下列产生式组成：
3、E iE E+EE E*EE (E)n如果如果 1 2 n，则我们称这个序，则我们称这个序列是从列是从 1到到 n的一个的一个推导推导。若存在一个从。若存在一个从 1到到 n的推导，则称的推导，则称 1可以可以推导推导出出 n 。n例：对文法例：对文法(1)E (E) (E+E) (i+E) (i+i)n通常，用通常，用 表示：从表示：从 1 1出发，经过出发，经过一步或若干步一步或若干步，可以推出，可以推出 n n。n1n*1 用用 表示：从表示：从 1 1出发，经过出发，经过0 0步或步或若干步若干步，可以推出，可以推出 n n。* 所以所以 ： 即即 或或,|)(*TV SGLq定义：假
4、定定义：假定G G是一个文法，是一个文法，S S 是它的开始符号。是它的开始符号。如果如果 ，则，则 称是一个称是一个句型句型。仅含终结符。仅含终结符号的句型是一个号的句型是一个句子句子。文法。文法G G所产生的句子的全所产生的句子的全体是一个体是一个语言语言，将它记为，将它记为 L(G)L(G)。*S第四章第四章 语法分析语法分析自上而下分析自上而下分析n语法分析器的功能语法分析器的功能n自上而下分析面临的问题自上而下分析面临的问题nLL(1)LL(1)分析法分析法n递归下降分析程序构造递归下降分析程序构造n预测分析程序预测分析程序4.1 语法分析器的功能语法分析器的功能n语法分析的任务语法
5、分析的任务是分析一个文法的句子是分析一个文法的句子结构。结构。n语法分析器的功能语法分析器的功能：按照文法的产生式按照文法的产生式( (语言的语法规则语言的语法规则) )，识别输入符号串是，识别输入符号串是否为一个句子。否为一个句子。n这里所说的输入串是指由单词符号（文法的终结符）这里所说的输入串是指由单词符号（文法的终结符）组成的有限序列。组成的有限序列。n对一个文法，当给你一串符号时，怎样知道它是不是对一个文法，当给你一串符号时，怎样知道它是不是该文法的一个句子（程序）呢？该文法的一个句子（程序）呢？n这就要判断，这就要判断，源程序源程序单词符号单词符号取下一单词取下一单词.语法分语法分析
6、树析树词法分词法分析器析器语法分语法分析器析器符号表符号表编译程序编译程序后续部分后续部分n语法分析的方法语法分析的方法：自下而上分析法自下而上分析法(Bottom-up)(Bottom-up)n基本思想：从输入串开始，逐步进行基本思想：从输入串开始，逐步进行“归约归约”，直到文法的开始符号。即从树末端开始，构造直到文法的开始符号。即从树末端开始，构造语法树。语法树。所谓归约所谓归约，是指根据文法的产生式规，是指根据文法的产生式规则，把产生式的右部替换成左部符号。则，把产生式的右部替换成左部符号。n算符优先分析法：算符优先分析法：按照算符的优先关系和结合按照算符的优先关系和结合性质进行语法分析
7、。适合分析表达式。性质进行语法分析。适合分析表达式。nLRLR分析法：分析法：规范归约规范归约n语法分析的方法：语法分析的方法：n基本思想：基本思想：它从文法的开始符号出发，反复它从文法的开始符号出发，反复使用各种产生式，寻找使用各种产生式，寻找 匹配匹配 的的推导推导。n递归下降分析程序：递归下降分析程序：对每一语法变量对每一语法变量( (非终非终结符结符) )构造一个相应的子程序，每个子程序构造一个相应的子程序，每个子程序识别一定的语法单位；通过子程序间的相互识别一定的语法单位；通过子程序间的相互调用实现对输入串的识别。调用实现对输入串的识别。n预测分析程序预测分析程序F优点：直观、简单和
8、宜于手工实现。优点：直观、简单和宜于手工实现。第四章第四章 语法分析语法分析自上而下分析自上而下分析n语法分析器的功能语法分析器的功能n自上而下分析面临的问题自上而下分析面临的问题nLL(1)LL(1)分析法分析法n递归下降分析程序构造递归下降分析程序构造n预测分析程序预测分析程序4.2 自上而下分析面临的问题自上而下分析面临的问题n自上而下就是从文法的开始符号出发，向自上而下就是从文法的开始符号出发，向下下推导推导，推出句子。，推出句子。p对任何输入串，试图用一切可能的办法，对任何输入串，试图用一切可能的办法，从文法开始符号从文法开始符号(根结点根结点)出发，自上而下出发，自上而下地为输入串
9、建立一棵地为输入串建立一棵语法树语法树。p或者说，为输入串寻找一个最左推导。或者说，为输入串寻找一个最左推导。n例例3.4.1 假定有文法假定有文法G(S): (1) SxAy (2) A*|* 分析分析输入串输入串x*y(记为记为 )。Sx*yIPSx*yIPAxySx*yIPAxySx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*（1 1）当某个非终结符有）当某个非终结符有多个产生式候选多个产生式候选时，时，在在分析过程中，当一个非终结符用某一个候选匹分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的配成功时，这种匹配可能是暂时的。出错时出
10、错时，不得不不得不“回溯回溯”。（2 2）文法左递归问题：文法左递归问题：一个文法是含有左递归一个文法是含有左递归的，如果存在非终结符的，如果存在非终结符P PPP自上而下分析面临的问题自上而下分析面临的问题左递归左递归例：下面是描述算术表例：下面是描述算术表达式的算法达式的算法 S ES E EE+T|T EE+T|T TT TT* *F|FF|F F(E)|id F(E)|id 含有左递归的文法将使自上而下的分含有左递归的文法将使自上而下的分析陷入无限循环析陷入无限循环。为句子为句子idid* *id+idid+id构造分析树构造分析树 S S E E E + T E + T E + T
11、E + TE + TE + T：第四章第四章 语法分析语法分析自上而下分析自上而下分析n语法分析器的功能语法分析器的功能n自上而下分析面临的问题自上而下分析面临的问题nLL(1)LL(1)分析法分析法n递归下降分析程序构造递归下降分析程序构造n预测分析程序预测分析程序4.3 LL(1)分析法分析法n构造不带回溯的自上而下分析算法构造不带回溯的自上而下分析算法要消除文法的左递归性要消除文法的左递归性克服回溯克服回溯4.3.1 左递归的消除左递归的消除n直接消除见诸于产生式中的左递归：假直接消除见诸于产生式中的左递归：假定关于非终结符定关于非终结符P的规则为的规则为PP | 其中其中 不以不以P开
12、头开头。 我们可以把我们可以把P的规则等价地改写为如下的的规则等价地改写为如下的非直接左递归形式：非直接左递归形式：P P P P | 左递归变右递归PP P n一般而言，假定一般而言，假定P关于的全部产生式是关于的全部产生式是PP 1 | P 2 | | P m | 1 | 2| n其中，每个其中，每个 都不等于都不等于 ，每个，每个 都不以都不以P开头开头 那么，消除那么，消除P的直接左递归性就是把这些规的直接左递归性就是把这些规则改写成：则改写成： P 1P | 2P | | nP P 1P | 2P | | mP | 左递归变右递归4.3.1 左递归的消除左递归的消除n例例 文法文法G
13、(E):EET | TTT*F | FF(E) | i经消去直接左递归后变成：经消去直接左递归后变成： ETE E +TE | TFT T *FT | F(E) | i(4.2)PP 1 | P 2 | | P m | 1 | 2| nP 1P | 2P | | nP P 1P | 2P | | mP | n例如文法例如文法G(S):SQc|cQRb|bRSa|a (4.3)虽没有直接左递归，但虽没有直接左递归，但S、Q、R都是左递归的都是左递归的SQcRbcSabc消除一个文法的一切左递归的条件：消除一个文法的一切左递归的条件：（1）不含以）不含以 为右部的产生式为右部的产生式（但改写后的文
14、法可能但改写后的文法可能含以含以 为右部的产生式为右部的产生式）（2）不含回路）不含回路。PPn消除左递归的算法消除左递归的算法:1. 把文法把文法G的所有非终结符按任一种顺序排列成的所有非终结符按任一种顺序排列成P1，P2，Pn；按此顺序执行；按此顺序执行；2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如把形如PiPj 的规则改写成的规则改写成 Pi 1 | 2 | k ; (其中其中Pj 1| 2| k是关于是关于Pj的所有规则的所有规则) 消除关于消除关于Pi规则的直接左递归性规则的直接左递归性 END3. 化简由化简由2所得的文法。去除那
15、些从开始符号出发永所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。远无法到达的非终结符的产生规则。n例例 考虑文法考虑文法G(S)SQc|cQRb|bRSa|an令它的非终结符的排序为令它的非终结符的排序为R、Q、S。n对于对于R，不存在直接左递归。，不存在直接左递归。n把把R代入到代入到Q的有关候选后，把的有关候选后，把Q的规则的规则变为变为 QSab | ab | bn例例 考虑文法考虑文法G(S)SQc|cQRb|bRSa|an令它的非终结符的排序为令它的非终结符的排序为R、Q、S。nQ的规则变为的规则变为 QSab | ab | bn现在的现在的Q不含直接左递归，把
16、它代入到不含直接左递归，把它代入到S的有关候选后，的有关候选后，S变成变成SSabc | abc | bc | cn例例 考虑文法考虑文法G(S)SQc|cQRb|bRSa|anS变成变成SSabc | abc | bc | cn消除消除S的直接左递归后：的直接左递归后：SabcS | bcS | cS S abcS | QSab |ab | bRSa|an例例 考虑文法考虑文法G(S)SQc|cQRb|bRSa|an消除消除S的直接左递归后：的直接左递归后：SabcS | bcS | cS S abcS | QSab |ab | bRSa|an关于关于Q和和R的规则已是多余的，化简为：的规则
17、已是多余的，化简为：SabcS | bcS | cS S abcS | (4.4)n注意，由于对非终结符排序的不同，最注意，由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但后所得的文法在形式上可能不一样。但不难证明，它们都是等价的。不难证明，它们都是等价的。n例如，若对文法例如，若对文法(4.3)的非终结符排序选的非终结符排序选为为S、Q、R，那么，最后所得的无左递，那么，最后所得的无左递归文法是：归文法是：SQc | cQRb | bRbcaR | caR |a R (4.5)R bca R | n文法文法(4.4)和和(4.5)的等价性是显然的。的等价性是显然的。小结小结n自
18、上而下分析面临的问题自上而下分析面临的问题 文法的左递归性文法的左递归性 回溯回溯n消除文法的左递归消除文法的左递归 直接左递归的消除直接左递归的消除 间接左递归的消除间接左递归的消除4.3.2 消除回溯、提左因子消除回溯、提左因子n为了为了消除回溯消除回溯就必须保证：对文法的任就必须保证：对文法的任何非终结符，当要它去匹配输入串时，何非终结符，当要它去匹配输入串时，能够能够根据它所面临的输入符号根据它所面临的输入符号准确地指准确地指派派它的一个候选它的一个候选去执行任务，并且此候去执行任务，并且此候选的工作结果应是确信无疑的。选的工作结果应是确信无疑的。nA 1 | 2 | | nSa.IP
19、A.n令令G是一个不含左递归的文法，对是一个不含左递归的文法，对G的所的所有非终结符的每个候选有非终结符的每个候选 定义它的终结首定义它的终结首符集符集FIRST( )为：为：.,|=)(*TVaaaFIRST 特别是，若特别是，若 ，则规定，则规定FIRST( )。*如果非终结符如果非终结符A的所有候选首符集两两不相交，的所有候选首符集两两不相交，即即A的任何两个不同候选的任何两个不同候选 i和和 jFIRST( i)FIRST( j) 当要求当要求A匹配输入串时，匹配输入串时，A就能根据它所面临的就能根据它所面临的第一个输入符号第一个输入符号a，准确地指派某一个候选前去，准确地指派某一个候
20、选前去执行任务。这个候选就是那个终结首符集含执行任务。这个候选就是那个终结首符集含a的的 。n思考：思考： nFIRST( i)FIRST( j) 很好处理，但是很好处理，但是如果如果 的终结首符集有共同的部分怎么办？的终结首符集有共同的部分怎么办？nA 1 | 2 | | nn可提取其可提取其公共左因子公共左因子n提取公共左因子提取公共左因子: 假定关于假定关于A的规则是的规则是 A 1 | 2 | | n | 1 | 2 | | m (其中，每个其中，每个 不以不以 开头开头) 那么，可以把这些规则改写成那么，可以把这些规则改写成A A | 1 | 2 | | mA 1 | 2 | | n
21、n经过反复提取左因子，就能够把每个非终经过反复提取左因子，就能够把每个非终结符结符(包括新引进者包括新引进者)的所有候选首符集变的所有候选首符集变成为两两不相交。成为两两不相交。n ETE E +TE | TFT T *FT | F(E) | in i + i4.3.3 LL(1)分析条件分析条件n当一个文法当一个文法不含左不含左递归递归，并且满足每，并且满足每个非终结符的所有个非终结符的所有候选首符集两两不候选首符集两两不相交相交的条件，是不的条件，是不是就一定能进行有是就一定能进行有效的自上而下分析效的自上而下分析了呢？了呢？i + i IPEnG(E): ETE E +TE | TFT
22、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 IPETEFTi nG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEnG(E
23、): 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): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEFTi nG(E):
24、ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEFTi nG(E): ETE E +TE | TFT T *FT | F(E) | in思考：思考：当非终结符当非终结符A面临输入符号面临输入符号a，且，且a不属于不属于A的任意候选的任意候选首符集，首符集，但但A的某个候选首符集包含的某个候选首符集包含 时，是否就一定可以使时，是否就一定可以使A自动匹配（自动匹配（ A ）呢？）呢？n需要做判断：需要做判断：有当有当a是是允许在文法的某个句型中允许在文法的某个句型中跟在跟在A后面的终结符后面的终结符时，才可能允许时，才可能允许A自动匹配，自动匹
25、配，否则，否则，a在这里的出现就是一个语法错误。在这里的出现就是一个语法错误。i + i IPETEFTi +TEFTi nG(E): ETE E +TE | TFT T *FT | F(E) | iS T+能否用能否用AA 自动匹配，需要判断自动匹配，需要判断当前输入符号当前输入符号是否在是否在紧跟在紧跟在A A后面的终结符集后面的终结符集FOLLOW(A)FOLLOW(A)中。中。n假定假定S是文法是文法G的开始符号，对于的开始符号，对于G的任何的任何非终结符非终结符A，我们定义，我们定义.,.|)(*TVaAaSaAFOLLOWAS*特别是，若特别是，若 ，则规定，则规定 FOLLOW(
26、A)4.3.3 LL(1)分析条件分析条件n构造构造不带回溯不带回溯的自上而下分析的文法条件的自上而下分析的文法条件1. 文法不含左递归，文法不含左递归，2. 对于文法中每一个非终结符对于文法中每一个非终结符A的各个产生式的各个产生式的候选首符集两两不相交。即，若的候选首符集两两不相交。即，若A 1| 2| n 则则 FIRST( i)FIRST( j) (i j)3. 对文法中的每个非终结符对文法中的每个非终结符A，若它存在某个，若它存在某个候选首符集包含候选首符集包含 ，则，则FIRST( i)FOLLOW(A)= i=1,2,.,n如果一个文法如果一个文法G满足以上条件，则称该文法满足以
27、上条件，则称该文法G为为LL(1)LL(1)文法文法。第一个第一个L：从左到右扫描输入串：从左到右扫描输入串第二个第二个L：最左推导：最左推导1：分析时每一步只需向前查看一个符号：分析时每一步只需向前查看一个符号n对于一个满足上述条件的文法，可以对其输对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假入串进行有效的无回溯的自上而下分析。假设要用非终结符设要用非终结符A进行匹配，面临的输入符进行匹配，面临的输入符号为号为a，A的所有产生式为的所有产生式为A 1 | 2 | | n1. 若若a FIRST( i)，则指派，则指派 i执行匹配任务；执行匹配任务；2. 若若a
28、不属于任何一个候选首符集，则：不属于任何一个候选首符集，则： (1) 若若 属于某个属于某个FIRST( i )且且 a FOLLOW(A)， 则则让让A与与 自动匹配自动匹配。 (2) 否则，否则，a的出现是一种语法错误。的出现是一种语法错误。求求FIRST(X)的算法如下：的算法如下：p80若若X VT，则，则FIRST(X)X。若若X VN，且有产生式，且有产生式Xa， a VT则把则把a加入到加入到FIRST(X)中；中；若若X VN ，X ，则，则 FIRST(X)中。中。对每个文法符号对每个文法符号X VT VN ，连续使用下连续使用下面的规则，直至每个面的规则，直至每个FIRST
29、(X)不再增大为不再增大为止：止：.,|=)(*TVaaaFIRST b) 当当Y1 ，Y2， ，Yi-1都都= , (1 i n) , 则则FIRST( Y1 )-, FIRST( Y2 )-, , FIRST( Yi )- 都包含在都包含在FIRST（X）中）中 c) 当当Y1 ，Y2， ，Yk都都= ,则则 FIRST(X)，此时，此时FIRST(X)= FIRST( Y1 ) FIRST( Y2 ) FIRST( Yk ) 若若X ，Y1 ，Y2， ，Yk VN ，且有产生式且有产生式 X Y1 Y2 Yk： a) 当当Y1 不能不能= ，则，则FIRST(Y1 )中的所有符号中的所有
30、符号都在都在FIRST（X）中）中n对每个非终结符对每个非终结符A，连续使用下面的规则，连续使用下面的规则，直至每个直至每个FOLLOW(A)不再增大为止：不再增大为止： 对于文法的开始符号对于文法的开始符号S，置，置于于FOLLOW(S)中；中； 对于对于A B 的的产生式，则把产生式，则把FIRST( )- 加至加至FOLLOW(B)中；中；对于对于A B或或A B ，其中，其中 ， 则把则把FOLLOW(A)加至加至FOLLOW(B)中。中。求求FOLLOW(A)的算法如下：的算法如下：p82 注意：注意： 永远不进永远不进follow集！集！.,.|)(*TVaAaSaAFOLLOWn
31、例例4.6 对于文法对于文法G(E)ETE E +TE | TFT T *FT | F(E) | i构造每个非终结符的构造每个非终结符的FIRST和和FOLLOW集合：集合： FIRST(E) =(,iFIRST(E )=+, FIRST(T) =(,iFIRST(T )=*, FIRST(F) =(,i FOLLOW(E) =),#FOLLOW(E )=),#FOLLOW(T) =+,),#FOLLOW(T )=+,),#FOLLOW(F) =*,+,),#4.4 递归下降分析递归下降分析程序构造程序构造n构造不带回溯的自上而下分析程序构造不带回溯的自上而下分析程序要消除文法的左递归性要消除
32、文法的左递归性克服回溯克服回溯n主要思路：主要思路： 分析程序由一组递归过程组成，对文法的每一分析程序由一组递归过程组成，对文法的每一个个非终结符非终结符（语法变量）构造一个（语法变量）构造一个相应的子程相应的子程序，序，识别对应的语法单位；识别对应的语法单位； ； 这样的分析程序称为这样的分析程序称为递归下降分析器递归下降分析器。( (因为文因为文法的定义通常是递归的法的定义通常是递归的) )n几个全局过程和变量：几个全局过程和变量：ADVANCE，把，把输入串指示器输入串指示器IP指向下一个指向下一个输入符号，即读入一个单字符号输入符号，即读入一个单字符号SYM，IP当前所指的输入符号当前
33、所指的输入符号ERROR，出错处理子程序，出错处理子程序注意：注意：n每个每个非终结符非终结符有有对应的子程序对应的子程序的定义的定义n在分析过程中，当在分析过程中，当需要从某个非终结符需要从某个非终结符出发出发进行语法树展开进行语法树展开( (推导推导) )时时，就调用，就调用这个非终结符这个非终结符对应的子程序对应的子程序。n子程序的名字可与对应的非终结符的名子程序的名字可与对应的非终结符的名字相同字相同n例：例：ATE | BC| ATE | BC| 对应的递归下降子程序为：对应的递归下降子程序为：PROCEDURE A；BEGINIF SYM FIRST(TE) THEN BEGIN
34、T；E END；/先调用先调用T子程序子程序,再调用再调用EELSE IF SYM FIRST(BC) THEN BEGIN B；C END； /先调用先调用B子程序子程序,再调用再调用CELSE IF SYM FOLLOW(A) THEN BEGIN END；ELSE ERRORENDELSE IF SYM / FOLLOW(A) THEN ERRORn例例: :文法文法G(E):G(E):ETE E +TE | TFT T *FT | F(E) | in对应的递归下降子程序为对应的递归下降子程序为: : PROCEDURE F； IF SYM=i THEN ADVANCE ELSE IF
35、SYM=( THEN BEGIN ADVANCE; E； IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR;n例例: :文法文法G(E):G(E):ETE E +TE | TFT T *FT | F(E) | in对应的递归下降子程序为对应的递归下降子程序为: : PROCEDURE E；BEGIN T；E END；PROCEDURE E ； IF SYM=+ THEN BEGINADVANCE； T；E ENDPROCEDURE E ； IF SYM=+ THEN BEGINADVANCE； T；E END ELSE IF SYM# AND SY
36、M) THEN ERROR / FOLLOW(E )=),#PROCEDURE T；BEGIN F；T ENDPROCEDURE T ；IF SYM=* THENBEGIN ADVANCE； F；T END；n例例: :文法文法G(E):G(E):ETE E +TE | TFT T *FT | F(E) | in对应的递归下降子程序为对应的递归下降子程序为: : 主程序主程序:PROGRAM PARSER;BEGIN ADVANCE; E; IF SYM # THEN ERROREND;n在元符号在元符号“”和和“|”的基础上，扩充的基础上，扩充几个元语言符号：几个元语言符号：1. 用用花括号
37、花括号 表示表示闭包运算闭包运算 *。2. 用表示用表示 0n可任意可任意重复重复0次至次至n次次。3. 用用方括号方括号 表示表示 01 ，即表示，即表示 的出现的出现可可有可无有可无(等价于等价于 | )。 引入上述元符号的文法亦称引入上述元符号的文法亦称扩充的巴科扩充的巴科斯范式斯范式。文法的另一种表示法和转换图文法的另一种表示法和转换图n例如，通常的例如，通常的“实数实数”可定义为：可定义为： decimalsigninteger.digitexponent exponentEsigninteger integerdigitdigit sign + | -n用用扩充的巴科斯范式扩充的巴
38、科斯范式来来描述语法描述语法，直观易直观易懂懂，便于表示左递归消去和因子提取。，便于表示左递归消去和因子提取。n例例4.5 文法文法ET | E+TTF | T*FFi | (E)可表示成可表示成ET+TTF*FFi | (E) (4.6)n ET+TTF*FFi | (E) (4.6)n可以用语法图来表示语言的文法。可以用语法图来表示语言的文法。T+ETF*TFi)FE(n ET+TTF*FFi | (E) (4.6)n可构造一组递归下降分析程序：可构造一组递归下降分析程序：PROCEDURE E；BEGIN T； WHILE SYM=+ DO BEGIN ADVANCE； T ENDEND
39、；PROCEDURE T；BEGIN F； WHILE SYM=* DO BEGIN ADVANCE； F ENDEND；n ET+TTF*FFi | (E) (4.6)n可构造一组递归下降分析程序：可构造一组递归下降分析程序：n ET+TTF*FFi | (E) (4.6)n可构造一组递归下降分析程序：可构造一组递归下降分析程序：PROCEDURE F； IF SYM=i THEN ADVANCE ELSE IF SYM=( THEN BEGIN ADVANCE; E； IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR; 1. 文法不含左递归，文
40、法不含左递归，2. 对于文法中每一个非终结符对于文法中每一个非终结符A的各个产生式的各个产生式的候选首符集两两不相交。即，若的候选首符集两两不相交。即，若A 1| 2| n 则则 FIRST( i)FIRST( j) (i j)3. 对文法中的每个非终结符对文法中的每个非终结符A，若它存在某个，若它存在某个候选首符集包含候选首符集包含 ，则，则FIRST( i)FOLLOW(A)= i=1,2,.,n如果一个文法如果一个文法G满足以上条件，则称该文法满足以上条件，则称该文法G为为LL(1)LL(1)文法文法。回顾：回顾：LL(1)文法条件文法条件nLL(1)分析法分析法假设要用非终结符假设要用
41、非终结符A进行匹配，进行匹配，面临的输入符号为面临的输入符号为a，A的所有产生式为的所有产生式为 ： A 1 | 2 | | n 1.若若a FIRST（ i），），则指派则指派 i执行匹配任务；执行匹配任务；2.若若a不属于任何一个候选首符集，则：不属于任何一个候选首符集，则：（1）若）若 属于某个属于某个FIRST（ i）且）且a FOLLOW(A),则让则让A与与 自动匹配。自动匹配。（2）否则，）否则，a的出现是一种语法错误。的出现是一种语法错误。回顾：回顾：LL(1)分析法分析法n分析程序由一组递归过程组成，文法中每分析程序由一组递归过程组成，文法中每个非终结符对应一个过程；所以这样
42、的分个非终结符对应一个过程；所以这样的分析程序称为析程序称为递归下降分析器递归下降分析器。( (因为文法因为文法的定义通常是递归的的定义通常是递归的) )n每个非终结符有对应的子程序的定义，首每个非终结符有对应的子程序的定义，首先在分析过程中，当需要从某个非终结符先在分析过程中，当需要从某个非终结符出发进行展开出发进行展开( (推导推导) )时，就调用这个非终时，就调用这个非终结符对应的子程序。结符对应的子程序。回顾：回顾：构造不带回溯的自上而下分构造不带回溯的自上而下分析器析器特征特征 根据根据当前当前输入符号输入符号，为当前要处，为当前要处 理的非终结符理的非终结符选择产生式选择产生式要求
43、要求文法是文法是LL(1)LL(1)的的4.5 预测分析程序预测分析程序预测分析器模型预测分析器模型总控程序总控程序X#输入串输入串分析栈分析栈STACKa1a2.ai#输出输出 预测分析表预测分析表M预测分析器模型预测分析器模型总控程序总控程序X#输入串输入串分析栈分析栈STACKa1a2.ai#输出输出 预测分析表预测分析表M分析栈分析栈 STACK 用于用于存放文法符号存放文法符号。分析开。分析开始时，栈底先放一个始时，栈底先放一个#，然后放进文法开，然后放进文法开始符号。始符号。# Sa1a2.ai#预测分析器模型预测分析器模型总控程序总控程序X#输入串输入串分析栈分析栈STACKa1
44、a2.ai#输出输出 预测分析表预测分析表M预测分析表是一个预测分析表是一个 MA，a形式的矩阵形式的矩阵，A VN ， a VT 是终结符或是终结符或；矩阵元素矩阵元素MA，a中存放着一条关于中存放着一条关于A的产生式的产生式，指出当，指出当A面面临输入符号临输入符号a时所采用的候选。时所采用的候选。 MA，a中也可能存放一个中也可能存放一个“出错标志出错标志”，指出，指出A根本不该面临输入符号根本不该面临输入符号a。某文法的某文法的LL(1)预测分析表预测分析表 预测分析器模型预测分析器模型总控程序总控程序X#输入串输入串分析栈分析栈STACKa1a2.ai#输出输出 预测分析表预测分析表
45、M总控程序总控程序在任何时候都是按在任何时候都是按STACK栈顶符号栈顶符号X和当前的输入符号和当前的输入符号a行事；它总是执行下述行事；它总是执行下述三种可能的动作之一：三种可能的动作之一：1. 若若Xa，则宣布分析成功，则宣布分析成功，停止分析。停止分析。2. 若若Xa ，则把，则把X从从STACK栈顶栈顶逐出，让逐出，让a指向下一个输入符号。指向下一个输入符号。匹配成功q总控程序总控程序根据现行根据现行栈顶符号栈顶符号X和当前输入和当前输入符号符号a，执行下列三种动作之一，执行下列三种动作之一:3. 若若X是一个非终结符，则查看分析表是一个非终结符，则查看分析表M。 若若MX，a中存放着
46、关于中存放着关于X的一个产生的一个产生式，把式，把X逐出逐出STACK栈顶，栈顶，把产生式把产生式的右部符号串按反序一一推进的右部符号串按反序一一推进STACK栈栈(若右部符号为若右部符号为 ，则意味不推什么东，则意味不推什么东西进栈西进栈)。在把产生式的右部符号推进。在把产生式的右部符号推进栈的同时应做这个产生式相应的语义栈的同时应做这个产生式相应的语义动作（目前暂且不管）。动作（目前暂且不管）。 若若MX，a中存放着中存放着“出错标志出错标志”，则调用出错诊察程序则调用出错诊察程序ERROR。推导n预测分析程序的总控程序：预测分析程序的总控程序：BEGIN 首先把首先把然后把文法开始符号推
47、进然后把文法开始符号推进STACK栈；栈； 把第一个输入符号读进把第一个输入符号读进a； FLAG:=TRUE; WHILE FLAG DOBEGIN 把把STACK栈顶符号上托出去并放在栈顶符号上托出去并放在X中；中； IF X VT THEN IF X= a THEN 把下一输入符号读进把下一输入符号读进a ELSE ERROR 匹配成功 ELSE IF X=# THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF MX,a=XX1X2XkTHEN 把把Xk,Xk-1,X1一一推进一一推进STACK栈栈 /* 若若X1X2Xk= ，不推什么进栈，不
48、推什么进栈 */ ELSE ERROR END OF WHILE;STOP /*分析成功，过程完毕分析成功，过程完毕*/END分析成功推导n例例4.6 对于文法对于文法G(E)ETE E +TE | TFT T *FT | F(E) | i输入串为输入串为i1*i2+i3，利用分析表进行预测分析：，利用分析表进行预测分析：i+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)步骤步骤符号栈符号栈输入串输入串所用产生式所用产生式0#Ei1*i2+i3#1#E Ti1*i2+i3# ETE 2#E T Fi1*i2+i3# TFT 3#
49、E T ii1*i2+i3# Fii+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)步骤步骤符号栈符号栈输入串输入串所用产生式所用产生式3#E T ii1*i2+i3# Fi4#E T *i2+i3#5#E T F*i2+i3# T *FT 6#E T F i2+i3#7#E T ii2+i3# Fii+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)步骤步骤符号栈符号栈输入串输入串所用产生所用产生7#E T ii2+i3# Fi 8#E T +i3#9#E +i3
50、# T 10#E T+i3# E +TE 11#E Ti3#i+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)步骤步骤符号栈符号栈输入串输入串所用产生所用产生11#E Ti3#12#E T F i3# TFT 13#E T ii3# Fi14#E T #15#E # T 16# E i+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)预测分析表预测分析表MA，a的构造的构造q构造与文法构造与文法G有关的集合有关的集合FIRST和和FOLLOWq构造分析表构造分析表M
