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 下载