China-pub.com 下载 第4章自顶向下的分析 本章要点 ·使用递归下降分析算法进行自顶向下的分析 ·TNY语言的递归下降分析程序 LL()分析 ·自顶向下分析程序中的错误校正 ·First集合和Follow集合 自顶向下(toP-down)的分析算法通过在最左推导中描述出各个步骤来分析记号串输入。 之所以称这样的算法为自顶向下是由于分析树隐含的编号是一个前序编号，而且其顺序是由根 到叶（参见第3章的3.3节）。自顶向下的分析程序有两类：回湖分析程序(backtracking parser) 和预测分析程序(predictive parser)。预测分析程序试图利用一个或多个先行记号来预测出输 入串中的下一个构造，而回溯分析程序则试着分析其他可能的输入，当一种可能失败时就要求 输入中备份任意数量的字符。虽然回溯分析程序比预测分析程序强大许多，但它们都非常慢， 般都在指数的数量级上，所以对于实际的编译器并不合适。本书将不研究回湖程序（但读者 可查看“注意与参考”部分以及练习以得到一些关于这个主题的提示)。 本章要学习的两类自顶向下分析算法分别是递归下降分析(recursive-descent parsing) 和LL(1)分析(LL(1)parsing)。递归下降分析很常用，且它对于手写的分析程序最为适合， 所以我们最先学习它。之后再来学习LL(1)分析，由于在实际中并不常用到它，所以只是将 其作为一个带有显式栈的简单实例来学习，它是下一章更强大（但也更复杂）的自底向上算 法的前奏。它对于将出现在递归下降分析中的一些问题形式化也有帮助。LL(1)分析方法是 这样得名的：第1个“L”指的是由左向右地处理命入（一些旧式的分析程序惯于自右向左地 处理输入，但现在已不常用了)。第2个“L”指的是它为输入串描绘出一个最左推导。括号 中的数字1意味着它仅使用输入中的一个符号来预测分析的方向(“LL(k)分析”也是有可能 的 一它利用向前看的k个符号，本章后面将简要地介绍到它，但是向前看的一个符号是最 为常见的)。 弟归下降程序分析和LL(1)分析一般地都要求计算先行集合，它们分别称作F「s伟合和 Follow集合O。由于无需显式地构造出这些集合就可以构造出简单的自顶向下的分析程序，所 以在基本算法的介绍之后我们再讨论它们。之后我们还要谈到一个由递归下降分析构造的 TNY分析程序，本章的最后是自项向下的分析中的错误校正。 4.1使用递归下降分析算法进行自顶向下的分析 4.1.1递归下降分析的基本方法 递归下降分析的概念极为简单：将一个非终结符A的文法规则看作将识别A的一个过程的 定义。A的文法规则的右边指出这个过程的代码结构：一个选择中的终结符与非终结符序列与 日下一章将要研究的自底向上的分析算法有一些也需要这些集合
下载 第4章 自顶向下的分析 本章要点 • 使用递归下降分析算法进行自顶向下的分析 • TINY语言的递归下降分析程序 • LL(1)分析 • 自顶向下分析程序中的错误校正 • First 集合和F o l l o w集合 自顶向下（t o p - d o w n）的分析算法通过在最左推导中描述出各个步骤来分析记号串输入。 之所以称这样的算法为自顶向下是由于分析树隐含的编号是一个前序编号，而且其顺序是由根 到叶（参见第3章的3 . 3节）。自顶向下的分析程序有两类：回溯分析程序（ backtracking parser） 和预测分析程序（predictive parser）。预测分析程序试图利用一个或多个先行记号来预测出输 入串中的下一个构造，而回溯分析程序则试着分析其他可能的输入，当一种可能失败时就要求 输入中备份任意数量的字符。虽然回溯分析程序比预测分析程序强大许多，但它们都非常慢， 一般都在指数的数量级上，所以对于实际的编译器并不合适。本书将不研究回溯程序（但读者 可查看“注意与参考”部分以及练习以得到一些关于这个主题的提示）。 本章要学习的两类自顶向下分析算法分别是递归下降分析（ recursive-descent parsing） 和L L ( 1 )分析（LL(1) parsing）。递归下降分析很常用，且它对于手写的分析程序最为适合， 所以我们最先学习它。之后再来学习 L L ( 1 )分析，由于在实际中并不常用到它，所以只是将 其作为一个带有显式栈的简单实例来学习，它是下一章更强大（但也更复杂）的自底向上算 法的前奏。它对于将出现在递归下降分析中的一些问题形式化也有帮助。 L L ( 1 )分析方法是 这样得名的：第 1个“L”指的是由左向右地处理输入（一些旧式的分析程序惯于自右向左地 处理输入，但现在已不常用了）。第2个“L”指的是它为输入串描绘出一个最左推导。括号 中的数字1意味着它仅使用输入中的一个符号来预测分析的方向（“L L ( k )分析”也是有可能 的——它利用向前看的 k个符号，本章后面将简要地介绍到它，但是向前看的一个符号是最 为常见的）。 递归下降程序分析和 L L ( 1 )分析一般地都要求计算先行集合，它们分别称作 F i r s t集合和 F o l l o w集合 。由于无需显式地构造出这些集合就可以构造出简单的自顶向下的分析程序，所 以在基本算法的介绍之后我们再讨论它们。之后我们还要谈到一个由递归下降分析构造的 T I N Y分析程序，本章的最后是自顶向下的分析中的错误校正。 4.1 使用递归下降分析算法进行自顶向下的分析 4.1.1 递归下降分析的基本方法 递归下降分析的概念极为简单：将一个非终结符 A的文法规则看作将识别 A的一个过程的 定义。A的文法规则的右边指出这个过程的代码结构：一个选择中的终结符与非终结符序列与 下一章将要研究的自底向上的分析算法有一些也需要这些集合
106 编译原理及实践 China-pub.co 下载 相匹配的输入以及对其他过程的调用相对应，而选择与在代码中的替代情况(case语句和i语 句)相对应。 例如，考虑前一章的表达式文法： exp-exp addop termterm addop→+l- term-term mulop factor factor mlop→* factor一(ep)|number 及ac1or的文法规则，识别actor并用相同名称进行调用的递归下降程序过程可用伪代码编写 如下： procedure factor begin case token of （:match(); exp: match()) number match (number); else error end case; end factor; 在这段伪代码中，假设有一个在输入中保存当前下一个记号的token变量（以便这个例子使用 先行的一个符号)。另外还假设有一个mach过程，它用它的参数匹配当前的下一个记号。如果 成功则前移，如果失败就表明错误： procedure match expectedToken ) begin if token expectedToken then getToken else error end if; end match 现在脱离开在match和actor中被调用的未指定的eror过程。可以假设它会打印出一个出错信息 并退出。 请注意，在match()调用和factor中的match(number)调用中，我们知道expectedToken利 token是一样的。但是在match()调用中，不能将1oken假设为一个右括号，所以就需要有一个 测试。factort的代码也假设已将过程exp定义为可以调用。在表达式文法的递归下降分析中， exp过程将调用1em,erm过程将调用actor,而factori过程将调用exp,所以所有的这些过程都 必须能够互相调用。不幸的是，为表达式文法中的其余规则编写递归下降程序过程并不像为 factor编写一样简单，而且它需要使用EBNF,下面就介绍这一点
相匹配的输入以及对其他过程的调用相对应，而选择与在代码中的替代情况（ c a s e语句和i f语 句）相对应。 例如，考虑前一章的表达式文法： exp → exp addop term | t e r m addop → + | - term → term mulop factor | f a c t o r mulop → * factor → ( exp ) | n u m b e r 及factor 的文法规则，识别factor 并用相同名称进行调用的递归下降程序过程可用伪代码编写 如下： p ro c e d u re factor ; b e g i n case token of ( : m a t c h( () ; exp ; m a t c h( ) ) ; number : match (n u m b e r) ; else e rro r ; end c a s e ; end f a c t o r ; 在这段伪代码中，假设有一个在输入中保存当前下一个记号的 t o k e n变量（以便这个例子使用 先行的一个符号）。另外还假设有一个m a t c h过程，它用它的参数匹配当前的下一个记号。如果 成功则前移，如果失败就表明错误： p ro c e d u re match ( e x p e c t e d Token ) ; b e g i n if token = e x p e c t e d Token t h e n g e t Token ; e l s e e rror ; end if ; end match ; 现在脱离开在m a t c h和f a c t o r中被调用的未指定的e rro r过程。可以假设它会打印出一个出错信息 并退出。 请注意，在match (()调用和f a c t o r中的match (n u m b e r) 调用中，我们知道e x p e c t e d To k e n和 t o k e n是一样的。但是在match ())调用中，不能将t o k e n假设为一个右括号，所以就需要有一个 测试。f a c t o r的代码也假设已将过程 e x p定义为可以调用。在表达式文法的递归下降分析中， e x p过程将调用t e r m，t e r m过程将调用f a c t o r，而f a c t o r过程将调用e x p，所以所有的这些过程都 必须能够互相调用。不幸的是，为表达式文法中的其余规则编写递归下降程序过程并不像为 f a c t o r编写一样简单，而且它需要使用E B N F，下面就介绍这一点。 1 0 6 编译原理及实践 下载
China-pub.com 第4章自顶向下的分析 107 下载 4.1.2重复和选择：使用EBNF 例如，一个i语句（简化了的）文法规则是： if-stmt一iE(exp）statement if(exp statement else statement 可将它翻译成以下过程 procedure ifSimt; begin match match (( match ()) statement if roken else then match (else): statement end ifStmt 在这个例子中，不能立即区分出文法规则右边的两个选择（它们都以记号1￡开始）。相反地。 我们必须直到看到输入中的记号else时，才能决定是否识别可选的else部分。因此，if语句的 代码与EBNF ifstmt(exp)statement [else statement] 匹配的程度比与BNF的匹配程序要高，上面的EBNF的方括号被翻译成ifStmt的代码中的一个测 试。实际上，EBNF表示法是为更紧密地映射递归下降分析程序的真实代码而设计的，如果使 用的是递归下降程序，就应总是将文法翻译成EBNF。另外还需注意到即使这个文法有二义性 (参见前一章)，编写一个每当在输入中遇到e1se记号时就立即匹配它的分析程序也是很自然 的。这与最近嵌套的消除二义性的规则精确对应。 现在考虑一下BNF中简单算术表达式文法中的exp情况： expexp addop termterm 如要根据我们的计划试着将它变成一个递归的x知过程，则首先应做的是调用xp本身，而这将 立即导致一个无限递归循环。由于ep和em可以以相同的记号开头（一个数或左括号），所以 要想测试使用哪个选择(exp一exp addop term或ep一term)就会出现问题了。 解决的办法是使用EBNF规则 ep→term{addop term} 花括号表示可将重复部分翻译到一个循环的代码中，如下所示： procedure exp; begin term; while token =+or token =-do
4.1.2 重复和选择：使用E B N F 例如，一个i f语句（简化了的）文法规则是： if-stmt → i f ( exp ) s t a t e m e n t | i f ( exp ) statement e l s e s t a t e m e n t 可将它翻译成以下过程 p ro c e d u re ifStmt ; b e g i n match (i f) ; match (() ; exp ; match ( )) ; statement ; i f token = e l s e t h e n m a t c h (e l s e) ; statement ; end if ; end ifStmt ; 在这个例子中，不能立即区分出文法规则右边的两个选择（它们都以记号 i f开始）。相反地， 我们必须直到看到输入中的记号 e l s e时，才能决定是否识别可选的 e l s e部分。因此，i f语句的 代码与E B N F if-stmt → if ( exp ) statement [ e l s e statement ] 匹配的程度比与B N F的匹配程序要高，上面的E B N F的方括号被翻译成i f S t m t的代码中的一个测 试。实际上，E B N F表示法是为更紧密地映射递归下降分析程序的真实代码而设计的，如果使 用的是递归下降程序，就应总是将文法翻译成 E B N F。另外还需注意到即使这个文法有二义性 （参见前一章），编写一个每当在输入中遇到 e l s e记号时就立即匹配它的分析程序也是很自然 的。这与最近嵌套的消除二义性的规则精确对应。 现在考虑一下B N F中简单算术表达式文法中的e x p情况： exp → exp addop term | t e r m 如要根据我们的计划试着将它变成一个递归的 e x p过程，则首先应做的是调用e x p本身，而这将 立即导致一个无限递归循环。由于 e x p和t e r m可以以相同的记号开头（一个数或左括号），所以 要想测试使用哪个选择（exp → exp addop term或exp → t e r m）就会出现问题了。 解决的办法是使用E B N F规则 exp → term { addop term } 花括号表示可将重复部分翻译到一个循环的代码中，如下所示： p ro c e d u re exp ; b e g i n term ; while token = + or token = - do 第 4章 自顶向下的分析 1 0 7 下载
108 编译原理及实践 China-pub.co 下载 match (token); term; end while; end exp; 相似地，term的EBNF规则： em一factor{mulop factor】 就变成代码 procedure term; begin factor; while token =do natch(token）: factor; end while; end term; 在这里当分隔过程时，删去了非终结符addop和mulop,这是因为它们仅有匹配算符功能 addop→+- mulop→* 这里所做的是ep和1erm中的匹配。 这个代码有一个问题：由花括号（和原始的BNF中的显式）表示的左结合是否仍然保留。 例如，假设要为本书中简单整型算术的文法编写一个递归下降程序计算器，就可通过在循环 中轮转来完成运算，从而就保证了该运算是左结合（现在假设分析过程是返回一个整型结果 的函数)： function exp:integer var temp:integer; begin temp:=term; while token =+or token =-do case token of +match (+ temp:=temp +term -match (-) temp :temp-term; end case; end while; return temp; end exp; trm与之也类似。我们已利用这种方法创建了一个可运行的简单计算器，程序清单4-1中有它
match (t o k e n) ; term ; end while ; end exp ; 相似地，t e r m的E B N F规则： term → factor { mulop factor } 就变成代码 p ro c e d u re term ; b e g i n factor ; while token = * d o match (t o k e n) ; factor ; end while ; end term ; 在这里当分隔过程时，删去了非终结符 addop 和m u l o p，这是因为它们仅有匹配算符功能： addop → + | - mulop → * 这里所做的是e x p和t e r m中的匹配。 这个代码有一个问题：由花括号（和原始的 B N F中的显式）表示的左结合是否仍然保留。 例如，假设要为本书中简单整型算术的文法编写一个递归下降程序计算器，就可通过在循环 中轮转来完成运算，从而就保证了该运算是左结合（现在假设分析过程是返回一个整型结果 的函数）： function exp : integer ; var temp : integer ; b e g i n temp := term ; while token = + or token = - do case token o f + : match (+) ; temp := temp + term ; - : match (-) ; temp := temp - term ; end case ; end while ; return temp ; end exp ; t e r m与之也类似。我们已利用这种方法创建了一个可运行的简单计算器，程序清单 4 - 1中有它 1 0 8 编译原理及实践 下载
China-pub.com 第4章自顶向下的分析 109 下载 的C代码。其中并未写出一个完整的扫描程序，而是选择使用了对getchar和scanf的调用来 代替getToken的过程。 程序清单41简单整型算术的递归下降程序计算器 kexp>-sterm>caddop>stern> caddop>->+1- m>-cfactor>cmulop>(factor> cfactor>->(cexp>I Mumber rmputs a line of text from stdin inatadoh char token;/*global token variable/ int term(void) int factor(void) void●rrox(vo1d) Eprintf(stderr,"Error\n"): 0x1t(1) token getchar();/*load token with first character for lookahead/ t for ond of line/ printf("Result din",result) ()trameou chare on line int exp(void) 【1 nt tempterm(i (token)( ae◆：atch+:
的C代码。其中并未写出一个完整的扫描程序，而是选择使用了对 g e t c h a r和s c a n f的调用来 代替g e t T o k e n的过程。 程序清单4-1 简单整型算术的递归下降程序计算器 第 4章 自顶向下的分析 1 0 9 下载
110 编译原理及实践 China-pub.com 下载 break! return tomp int term(void) 【int tomp=factor()i tomp*factor()1 return tomp; int factor(void) int temp ( match(')); gcanf(Nd,stemp): token getchar(); 这个将EBNF中的文法规则转变成代码的办法十分有效，4.4节还将利用它为TINY语言给 出一个完整的分析程序。但是它仍有一些缺点，且须留意在代码中安排的动作。例如：在前面 exp的伪代码中，运算的匹配必须发生在对em的重复调用之前（否则1erm会将一个运算看作是 它的第1个记号，这就会生成一个错误了)。实际上现在必须严格遵循用于保持tokn变量的协 议：必须在分析开始之前先设置token,且对一个记号的测试（将它放在伪代码的ma1ch过程中 一旦成功，就立即调用getToken(或它的等价物)。 在构造语法树中也须注意动作的安排。我们已看到可通过在执行循环时完成计算来保持带 有重复的EBNF的左结合。它再也不能与分析树或语法树中的自顶向下的构造相对应。但相反 地，如考虑表达式3+4+5，其语法树 3 在根节点（表示其与5的和的节点）之前应先建立表示3与4之和的节点。将它翻译为真正的语 法树结构就有了以下的p过程的伪代码：
这个将E B N F中的文法规则转变成代码的办法十分有效， 4 . 4节还将利用它为 T I N Y语言给 出一个完整的分析程序。但是它仍有一些缺点，且须留意在代码中安排的动作。例如：在前面 e x p的伪代码中，运算的匹配必须发生在对t e r m的重复调用之前（否则t e r m会将一个运算看作是 它的第1个记号，这就会生成一个错误了）。实际上现在必须严格遵循用于保持 t o k e n变量的协 议：必须在分析开始之前先设置t o k e n，且对一个记号的测试（将它放在伪代码的m a t c h过程中） 一旦成功，就立即调用g e t To k e n（或它的等价物）。 在构造语法树中也须注意动作的安排。我们已看到可通过在执行循环时完成计算来保持带 有重复的E B N F的左结合。它再也不能与分析树或语法树中的自顶向下的构造相对应。但相反 地，如考虑表达式3 + 4 + 5，其语法树 在根节点（表示其与5的和的节点）之前应先建立表示 3与4之和的节点。将它翻译为真正的语 法树结构就有了以下的e x p过程的伪代码： 1 1 0 编译原理及实践 下载
China-pub.com 第4章自顶向下的分析 111 下载 function exp syntaxTree; var temp,newtemp:syntaxTree; begin fen:■ferm: while token =+or token =-do case token of +match (+) newtemp:=makeOpNode(+); leftChild(newtemp):=temp rightChild(newtemp):=term; femp :newtemp; -match ( newtemp :=makeOpNode(-); leftChild(newtemp):=temp righiChild(newtemp):=term; temp :newtemp; end case; end while; return temp end exp; 或更简单的 function exp:syntaxTree; var femp,newtemp syntaxTree begin temp :term; while token =+or token =-do newtemp:=makeOpNode(token); match (token): lefiChild(newtemp):=temp rightChild(newtemp):=term; temp :newtemp end while; return temp; end exp; 这个代码使用了新函数makeOpNode,它接受作为参数的运算符记号并返回新建的语法树节点 我们还通过写出lefChild():=p或rightChild()=p指出将一个语法树p的赋值作为语法树1的 一个左子树或右子树。有了这个伪代码之后，xp过程实际构造了语法树而不是分析树。这是 因为一个对xp的调用并不总是构造一个新的树节点：如没有运算符，xp则仅仅是传送回从最 初调用到term收到的树来作为它自己的值。也可以写出与1erm和actor相对应的伪代码（参见 练习)
function exp : s y n t a x Tree ; var t e m p, newtemp : s y n t a x Tree ; b e g i n temp := term ; while token = + or token = - d o case token o f + : match (+) ; newtemp := m a k e O p N o d e(+) ; l e f t C h i l d(n e w t e m p) := temp ; r i g h t C h i l d(n e w t e m p) := term ; temp := newtemp ; - : match (-) ; newtemp := m a k e O p N o d e(-) ; l e f t C h i l d(n e w t e m p) := temp ; r i g h t C h i l d(n e w t e m p) := t e r m ; temp := newtemp ; end case ; end while ; return temp ; end exp ; 或更简单的 function exp : s y n t a x Tree ; var t e m p, newtemp : s y n t a x Tree ; b e g i n temp := term ; while token = + or token = - d o newtemp := m a k e O p N o d e(t o k e n) ; match (t o k e n) ; l e f t C h i l d(n e w t e m p) := temp ; r i g h t C h i l d(n e w t e m p) := term ; temp := newtemp ; end while ; return temp ; end exp ; 这个代码使用了新函数m a k e O p N o d e，它接受作为参数的运算符记号并返回新建的语法树节点。 我们还通过写出leftChild (t) := p 或rightChild (t) := p 指出将一个语法树p 的赋值作为语法树t 的 一个左子树或右子树。有了这个伪代码之后， e x p过程实际构造了语法树而不是分析树。这是 因为一个对e x p的调用并不总是构造一个新的树节点；如没有运算符， e x p则仅仅是传送回从最 初调用到t e r m收到的树来作为它自己的值。也可以写出与 t e r m和f a c t o r相对应的伪代码（参见 练习）。 第 4章 自顶向下的分析 1 1 1 下载
112 编译原理及实践 China-pub.com 下载 相反地，递归下降分析程序在严格的自顶向下的风格中可构造出语句的语法树 function ifStatement:syntaxTree; var temp syntaxTree begin match ) match (() temp :makeStmtNode(i) testChild(temp):=exp; natch)）: thenChild(temp):=statement if token=else then match (else): elseChild(temp):=statement; else elseChild(temp):=nil end if; end ifStatement 正因为递归下降分析允许程序设计人员可调整动作的安排，这样它就可以选择手工生成的分析 程序了。 4.1.3其他决定问题 前面描述的递归下降分析虽然非常强大，但它仍有特殊性。若使用的是一个设计精巧的小 型语言（例如TNY,甚至是C),那么对于构造一个完整的分析程序，这些办法是适合的。读 者应注意在复杂情况中还需要更形式的方法。此时还会出现一些问题。首先，将原先在BNF中 编写的文法转变成EBNF格式可能会有些困难。下一节将学习不用EBNF的另一种方法，其中 构造了一个与EBNF基本相等的转变了的BNF。其次，在用公式表达一个用以区分两个或更多 的文法规则选项的测试 A-a1B1... 时，如果α和B均以非终结符开始，那么就很难决定何时使用A→α选项，何时又使用A一B选项。 这个问题就要求计算α和B的Fist集合：可以正规地开始每个串的记号集合。4.3节将详细介绍 这个计算。再次，在写ε产生式的代码 A-8 时，需要了解什么记号可以正规地出现在非终结符A之后，这是因为这样的记号指出A可以恰 当地在分析中的这个点处消失。这个集合被称作A的Foow集合。4.3节中也有这个集合的准确 计算。 最后读者需要注意：人们进行Fist集合和Follow集合的计算是为了对早期错误进行探测。 例如：在程序清单4-1的计算器程序中，假设有输入)3-2)，分析程序在报告错误之前，将从 exp到texm再到factor下降：由于在表达式中，右括号作为第I个字符并不合法，而在ex 中可能早已声明了这个错误。xp的Frst集合将会告诉我们这一点，从而可以进行较早的错误 探测（本章最后将更详细地讨论错误探测和恢复）
相反地，递归下降分析程序在严格的自顶向下的风格中可构造出 i f语句的语法树： function ifStatement : s y n t a x Tree ; var temp : s y n t a x Tree ; b e g i n match (i f) ; match (() ; temp := m a k e S t m t N o d e(i f) ; t e s t C h i l d(t e m p) := exp ; match ( ) ) ; t h e n C h i l d(t e m p) := statement ; i f token = e l s e t h e n match (e l s e) ; e l s e C h i l d(t e m p) := statement ; e l s e e l s e C h i l d(t e m p) := nil ; end if ; end ifStatement ; 正因为递归下降分析允许程序设计人员可调整动作的安排，这样它就可以选择手工生成的分析 程序了。 4.1.3 其他决定问题 前面描述的递归下降分析虽然非常强大，但它仍有特殊性。若使用的是一个设计精巧的小 型语言（例如T I N Y，甚至是C），那么对于构造一个完整的分析程序，这些办法是适合的。读 者应注意在复杂情况中还需要更形式的方法。此时还会出现一些问题。首先，将原先在 B N F中 编写的文法转变成 E B N F格式可能会有些困难。下一节将学习不用 E B N F的另一种方法，其中 构造了一个与E B N F基本相等的转变了的B N F。其次，在用公式表达一个用以区分两个或更多 的文法规则选项的测试 A→a | b | . . . 时，如果a和b均以非终结符开始，那么就很难决定何时使用A→a选项，何时又使用A→b选项。 这个问题就要求计算 a和b的F i r s t集合：可以正规地开始每个串的记号集合。 4 . 3节将详细介绍 这个计算。再次，在写 产生式的代码 A→ 时，需要了解什么记号可以正规地出现在非终结符 A之后，这是因为这样的记号指出 A可以恰 当地在分析中的这个点处消失。这个集合被称作 A的F o l l o w集合。4 . 3节中也有这个集合的准确 计算。 最后读者需要注意：人们进行 F i r s t集合和F o l l o w集合的计算是为了对早期错误进行探测。 例如：在程序清单 4 - 1的计算器程序中，假设有输入 ) 3 - 2 )，分析程序在报告错误之前，将从 e x p到t e r m再到f a c t o r下降；由于在表达式中，右括号作为第 1个字符并不合法，而在 e x p 中可能早已声明了这个错误。 e x p的F i r s t集合将会告诉我们这一点，从而可以进行较早的错误 探测（本章最后将更详细地讨论错误探测和恢复）。 1 1 2 编译原理及实践 下载
China-pub.Com 第4章自顶向下的分析 113 下载 4.2LL(1)分析 4.2.1LL(1)分析的基本方法 LL()分析使用显式栈而不是递归调用来完成分析。以标准方式表示这个栈非常有用，这 样LL()分析程序的动作就可以快捷地显现出来。在这个介绍性的讨论中，我们使用了生成成 对括号的串的简单文法： S-(S)SE (参见第3章的例3.5)。 假设有这个文法和串()，则表4-1给出了自顶向下的分析程序的动作。此表共有4列。第1 列为便于以后参考给每个步骤标上了号码。第2列显示了分析栈的内容，栈的底部向左，栈的 顶部向右。栈的底部标注了一个美元符号，这样一个在顶部包含了非终结符S的栈就是： SS 且将额外的栈项推向右边。表的第3列显示了输入。输入符号由左列向右。美元符号标出了输 入的结束（它与由扫描程序生成的EOF记号相对应）。表的第4列给出了由分析程序执行的动作 的简短描述，它将改变栈和（有可能）输入，如在表的下一行中所示一样。 表41自顶向下的分析程序的分析动作 分析栈 输入 动作 1$S ()s S-(S)5 2SS)St ()s 匹配 3$S)s S s 匹配 55 S- 65 接受 自顶向下的分析程序是从将开始符号放在栈中开始的。在一系列动作之后，它接受一个输 入串，此时栈和输入都空了。因此，成功的自顶向下的分析的一般示意法应是： StartSymbol InputString accept 在上面的例子中，开始符号是S,输入串是)。 自顶向下的分析程序通过将栈顶部的非终结符替换成文法规则中(BNF中)该非终结符的 一个选择来作出分析。其方法是在分析栈的项部生成当前输入记号，在项部它己匹配了输入记 号并将它从找和输入中舍弃掉。这两个动作 1)利用文法选择A→α将栈顶部的非终结符A替换成串α。 2)将栈顶部的记号与下一个输入记号匹配。 是自顶向下的分析程序中的两个基本动作。第1个动作称为生成(generate):通过写出在替换 中使用的BNF选择（它的左边在当前必须是栈顶部的非终结符）来指出这个动作。第2个动作 将栈顶部的一个记号与输入中的下一个记号匹配（并通过取出栈和将输入向前推进而将二者全
4.2 LL(1)分析 4.2.1 LL(1)分析的基本方法 L L ( 1 )分析使用显式栈而不是递归调用来完成分析。以标准方式表示这个栈非常有用，这 样L L ( 1 )分析程序的动作就可以快捷地显现出来。在这个介绍性的讨论中，我们使用了生成成 对括号的串的简单文法： S→(S) S | （参见第3章的例3 . 5 )。 假设有这个文法和串 ( )，则表4 - 1给出了自顶向下的分析程序的动作。此表共有 4列。第1 列为便于以后参考给每个步骤标上了号码。第 2列显示了分析栈的内容，栈的底部向左，栈的 顶部向右。栈的底部标注了一个美元符号，这样一个在顶部包含了非终结符 S的栈就是： $ S 且将额外的栈项推向右边。表的第 3列显示了输入。输入符号由左列向右。美元符号标出了输 入的结束（它与由扫描程序生成的 E O F记号相对应）。表的第4列给出了由分析程序执行的动作 的简短描述，它将改变栈和（有可能）输入，如在表的下一行中所示一样。 表4-1 自顶向下的分析程序的分析动作 分 析 栈 输 入 动 作 1 $ S ( ) $ S → ( S ) S 2 $ S ) S ( ( ) $ 匹配 3 $ S ) S ) $ S → 4 $ S ) ) $ 匹配 5 $ S $ S → 6 $ $ 接受 自顶向下的分析程序是从将开始符号放在栈中开始的。在一系列动作之后，它接受一个输 入串，此时栈和输入都空了。因此，成功的自顶向下的分析的一般示意法应是： $ S t a rt S y m b o l InputString $ . . . . . . . . . . . . $ $ accept 在上面的例子中，开始符号是S，输入串是( )。 自顶向下的分析程序通过将栈顶部的非终结符替换成文法规则中（ B N F中）该非终结符的 一个选择来作出分析。其方法是在分析栈的顶部生成当前输入记号，在顶部它已匹配了输入记 号并将它从栈和输入中舍弃掉。这两个动作 1) 利用文法选择A→a将栈顶部的非终结符A替换成串a。 2) 将栈顶部的记号与下一个输入记号匹配。 是自顶向下的分析程序中的两个基本动作。第 1个动作称为生成（g e n e r a t e）：通过写出在替换 中使用的B N F选择（它的左边在当前必须是栈顶部的非终结符）来指出这个动作。第 2个动作 将栈顶部的一个记号与输入中的下一个记号匹配（并通过取出栈和将输入向前推进而将二者全 第 4章 自顶向下的分析 1 1 3 下载
114 编译原理及实践 China-pub.com 下载 部舍弃掉)这个动作是通过书写单词来指出的。另外还需注意在生成动作中，从BNF中替换 草的串α必须颠倒地压在钱中（这是因为要保证串按自左间右的顺序进到钱的项部）。 例如，在表41的分析的第1步中，栽和抢入分别是 SS ()$ 且用来替换栈顶部的S的规则是S·(S)S,所以将串S)S(压入到栈中得到 SS)S((S 现在已生成了下一个输入终结符，即在栈的顶部的一个左括号，我们还完成了一个匹配以得到 以下的情况： $S)S)$ 表4-1中生成动作的列表与串()最左推导的步骤完全对应： S→(S)S S一(S) =()S [S→e] ) [S+e] 这是自顶向下分析的特征。如果要在分析进行时构造一个分析树，则可当将每个非终结符或终 结符压入到栈中时添加节点来构造动作。因此分析树根节点的构造是在分析开始时进行的（与 开始符号对应)。而在表41的第2步中，当(S)S替换S时，用于4个替换符号中的每个符号的 节点将作为放到栈中的符号来构造，并且作为子节点与在栈中替换的S节点连接。为了使其具 有高效率，就必须修改栈以包括指向这些构造的节点的指针，而不是仅仅是指向非终结符或终 结符本身的指针。另外，读者还将看到如何将这个处理进行修改以生成语法树的结构而非分析 树的结构。 4.2.2LL(1)分析与算法 当非终结符A位于分析栈的顶部时，根据当前的输入记号（先行），必须使用刚刚描述过的 分析办法做出一个决定：当替换栈中的A时应为A选择哪一个文法规则，相反地，当记号位于 栈顶部时，就无需做出这样的决定，这是因为无论它是当前的输入记号（由此就发生一个匹配）， 还是不是输入记号（从而就发生 一个错误)，两者都是相同的。 通过构造一个LL(I)分析表(LL(I)parsing table)就可以表达出可能的选择。这样的表格基本 上是一个由非终结符和终结符索引的二维数组，其中非终结符和终结符包括了要在恰当的分析 步骤（包括代表输入结束的S)中使用的产生式选择。这个表被称为MN,T小，这里的N是文法 的非终结符的集合，T是终结符或记号的集合（为了简便，禁止将$加到T上），M可被认为是 “运动的”表。我们假设表MN,T]在开始时，它的所有项目均为空。任何在构造之后继续为 空的项目都代表了在分析中可能发生的替在错误。 根据以下规则在这个表中添加产生式： )如果4一α是一个产生式选择，且有推导a一*a邱成立，其中a是一个记号，则将A→a添 加到表项目M4,a中。 2)如果4一α是一个产生式选择，且有推导a *e和SS→*BAay成立，其中S是开始符号， a是一个记号（或S),则将A一a添加到表项目M[4,a中。 这个规则的观点是：在规则1中，在输入中给出了记号a,若a可为匹配生成一个a,则希望 挑选规则A→a。在规则2中，若4派生了空串（通过A一α），且如a是一个在推导中可合法地出
部舍弃掉）；这个动作是通过书写单词来指出的。另外还需注意在生成动作中，从 B N F中替换 掉的串a必须颠倒地压在栈中（这是因为要保证串a按自左向右的顺序进到栈的顶部）。 例如，在表4 - 1的分析的第1步中，栈和输入分别是 $ S ( ) $ 且用来替换栈顶部的S的规则是S→ ( S ) S，所以将串S ) S ( 压入到栈中得到 $ S ) S ( ( ) $ 现在已生成了下一个输入终结符，即在栈的顶部的一个左括号，我们还完成了一个匹配以得到 以下的情况： $ S ) S ) $ 表4 - 1中生成动作的列表与串( )最左推导的步骤完全对应： S Þ ( S ) S [S → ( S ) S] Þ ( ) S [S→ ] Þ ( ) [S→ ] 这是自顶向下分析的特征。如果要在分析进行时构造一个分析树，则可当将每个非终结符或终 结符压入到栈中时添加节点来构造动作。因此分析树根节点的构造是在分析开始时进行的（与 开始符号对应）。而在表4 - 1的第2步中，当( S ) S替换S时，用于4个替换符号中的每个符号的 节点将作为放到栈中的符号来构造，并且作为子节点与在栈中替换的 S节点连接。为了使其具 有高效率，就必须修改栈以包括指向这些构造的节点的指针，而不是仅仅是指向非终结符或终 结符本身的指针。另外，读者还将看到如何将这个处理进行修改以生成语法树的结构而非分析 树的结构。 4.2.2 LL(1)分析与算法 当非终结符A位于分析栈的顶部时，根据当前的输入记号（先行），必须使用刚刚描述过的 分析办法做出一个决定：当替换栈中的 A时应为A选择哪一个文法规则，相反地，当记号位于 栈顶部时，就无需做出这样的决定，这是因为无论它是当前的输入记号（由此就发生一个匹配）， 还是不是输入记号（从而就发生一个错误），两者都是相同的。 通过构造一个L L ( 1 )分析表(LL(1) parsing table)就可以表达出可能的选择。这样的表格基本 上是一个由非终结符和终结符索引的二维数组，其中非终结符和终结符包括了要在恰当的分析 步骤（包括代表输入结束的$）中使用的产生式选择。这个表被称为M [N, T ]，这里的N是文法 的非终结符的集合， T是终结符或记号的集合（为了简便，禁止将 $加到T上），M可被认为是 “运动的”表。我们假设表 M [N, T ]在开始时，它的所有项目均为空。任何在构造之后继续为 空的项目都代表了在分析中可能发生的潜在错误。 根据以下规则在这个表中添加产生式： 1) 如果A→a是一个产生式选择，且有推导a Þ *ab成立，其中a 是一个记号，则将A→a添 加到表项目M [A, a] 中。 2) 如果A→a是一个产生式选择，且有推导a Þ * 和S $ Þ *bAag 成立，其中S是开始符号， a是一个记号（或$），则将A→a添加到表项目M [A, a]中。 这个规则的观点是：在规则1中，在输入中给出了记号a，若a可为匹配生成一个a，则希望 挑选规则A→a。在规则2中，若A派生了空串（通过A→a），且如a 是一个在推导中可合法地出 1 1 4 编译原理及实践 下载
