所谓递归下降法 (recursive descent method),是指对文法的每一非终结符号,都根据相应产生式各候选式的结构,为其编写一个子程序 (或函数),用来识别该非终结符号所表示的语法范畴。例如,对于产生式E′→+TE′,可写出相应的子程序如下: exprprime( ) { if (match (PLUS)) { advance( ); term( ); exprprime( ); } } 其中: 函数match()的功能是,以其实参与当前正扫视的符号 (单词)进行匹配,若成功则回送true,否则回送false;函数advance()是一个读单词子程序,其功能是从输入单词串中读取下一个单词,并将它赋给变量Lookahead;term则是与非终结符号T相对应的子程序。诸如上述这类子程序的全体,便组成了所需的自顶向下的语法分析程序。 应当指出,由于一个语言的各个语法范畴 (非终结符号)常常是按某种递归方式来定义的,此种特点也就决定了这组子程序必然以相互递归的方式进行调用,因此,在实现递归下降分析法时,应使用支持递归调用的语言来编写程序。所以,通常也将上述方法称为递归子程序法。 例42对于如下的文法G[statements]: statements→expression; statements |ε expression→term expression′ expression′→+term expression′ |ε term→factor term′ term′→*factor term′ |ε factor→numorid | (expression) 通过对其中各非终结符号求出相应的FIRST集和FOLLOW集 (计算FIRST集和FOLLOW集的方法后面再做介绍),可以验证,此文法为一LL(1)文法,故可写出递归下降语法分析程序如程序41所示(其中,在文件lex.h里,将分号、加号、乘号、左括号、右括号、输入结束符及运算对象分别命名为SEMI,PLUS,TIMES,LP,RP,EOI及NUMORID,并指定了它们的内部码;此外,还对外部变量yytext,yyleng及yylineno进行了说明)。 程序 G\[statements\]的递归下降语法分析程序 1/* Basic parser, shows the structure but there's no code generation */ 2 3#include <stdio.h> 4#include "lex.h" 5 6statements ( ) 7{ 8/* statements → expression SEMI 9 *| expression SEMI statements 10*/ 11 12expression( ); 13 14if (match (SEMI)) 15advance( ); 16else 17fprintf (stderr, "%d: Inserting missing semicolon\n", yylineno); 18 19if (!match (EOI)) 20statements ( );/* Do another statement. */ 21} 22 23expression( ) 24{ 25/* expression → term expression′ */ 26 27term( ); 28exprprime( ); 29} 30 31exprprime( ) 32{ 33/* expression′ → PLUS term expression′ 34 *| epsilon 35 */ 36 37if (match (PLUS)) 38{ 39advance ( ); 40term( ); 41exprprime( ); 42} 43} 44 45term( ) 46{ 47/* term → factor term′ */ 48 49factor( ); 50termprime( ); 51} 52 53termprime( ) 54{ 55/* term′→TIMES factor term′ 56 *| epsilon 57 */ 58 59if (match (TIMES)) 60{ 61advance( ); 62factor( ); 63termprime( ); 64} 65} 66 67factor( ) 68{ 69/* factor → NUMORID 70 *| LP expression RP 71 */ 72 73if (match (NUMORID)) 74advance( ); 75 76else if (match (LP)) 77{ 78advance( ); 79expression( ); 80if (match(RP)) 81advance( ); 82else 83fprintf (stderr, "%d: Mismatched parenthesis\n", yylineno); 84} 85else 86fprintf (stderr, "%d: Number or identifier expected\n", yylineno); 87} 利用程序41进行语法分析时,我们约定,如果当前的输入符号不是应出现的符号 (例如,对于第37行,当前的输入符号不是加号),则用相应的ε产生式进行推导。另外,上述程序有两个比较明显的缺点: 一是频繁的递归调用将使工作效率大为降低;二是缺乏较完善的语法检查和出错处理。这可通过适当改写文法和扩充程序的功能来改善。例如,可将原文法改写为如下的文法G′[statements]: statements→{expression;} expression→term{+term} term→factor{*factor} factor→numorid | (expression) 此时,对一些子程序的递归调用就可用一段代码的重复执行来代替。于是,对于文法G′[statements],可写出改进的递归下降分析程序如程序42所示。 程序 42改进的递归下降语法分析程序 1/* Revised parser */ 2 3#include <stdio.h> 4#include "lex.h" 5 6voidfactor(void); 7voidterm(void); 8voidexpression(void); 9 10statements( ) 11{ 12/* statements → expression SEMI | expression SEMI statements */ 13 14while (!match (EOI)) 15{ 16expression( ); 17 18if (match (SEMI)) 19advance( ); 20else 21fprintf (stderr, "%d: Inserting missing semicolon\n", yylineno); 22} 23} 24 25voidexpression( ) 26{ 27/* expression → term expression′ 28 * expression′ → PLUS term expression′ | epsilon 29 */ 30 31if (!legallookahead (NUMORID, LP,0)) 32return; 33 34term( ); 35while (match (PLUS)) 36{ 37advance( ); 38term( ); 39} 40} 41 42voidterm( ) 43{ 44if (!legallookahead (NUMORID, LP,0)) 45return; 46 47factor( ); 48while (match (TIMES)) 49{ 50advance( ); 51factor( ); 52} 53} 54 55voidfactor( ) 56{ 57if (!legallookahead (NUMORID, LP,0)) 58return; 59 60if (match (NUMORID)) 61advance( ); 62 63else if (match (LP)) 64{ 65advance( ); 66expression( ); 67if (match (RP)) 68advance( ); 69else 70fprintf (stderr, "%d: Mismatched parenthesis\n", yylineno); 71} 72else 73fprintf (stderr, "%d: Number or identifier expected\n", yylineno); 74} 在程序42的expression( )、term( )及factor( )等三个函数中,都调用了一个名为legallookahead的函数。此函数的实参是相应非终结符FIRST集合中的各个元素,并且用一个0作为最后一个实参,其功能是: 检查当前的输入符号是否属于相应非终结符的FIRST集,若是其中的元素,则继续进行语法分析;否则,除报错外,还逐个删除输入串中的符号,直到出现属于该FIRST集中的某个符号为止。 下面,我们列出函数legallookahead的代码如程序43所示。 程序 43函数legallookahead 75#include <stdarg.h> 76 77#defineMAXFIRST16 78#defineSYNCHSEMI 79 80intlegallookahead (firstarg) 81intfirstarg; 82{ 83/* Simple error detection and recovery. Arguments are a 0terminated list of 84 * those tokens that can legitimately come next in the input. If the list is 85 * empty, the end of file must come next. Print an error message if 86 * necessary. Error recovery is performed by discarding all input symbols 87 * until one that's in the input list is found 88 * 89 * Return true if there's no error or if we recovered from the error, 90 * false if we can't recover. 91 */ 92 93valistargs; 94inttok; 95intlookaheads [MAXFIRST], *p=lookaheads, *current; 96interrorprinted=0; 97intrval=0; 98 99vastart (args, firstarg); 100 101if (!firstarg) 102{ 103if(match (EOI)) 104rval =1; 105} 106else 107{ 108*p++=firstarg; 109while ((tok=vaarg(args, int)) && p<&lookaheads[MAXFIRST]) 110*++p=tok; 111 112while (!match (SYNCH)) 113{ 114for (current = lookaheads; current < p; ++currrent) 115if (match (*current)) 116{ 117rval = 1; 118goto exit; 119} 120 121if (!errorprinted) 122{ 123fprintf (stderr, "Line %d: Syntax error\n", yylineno); 124errorprinted = 1; 125} 126 127advance( ); 128} 129} 130 131exit; 132vaend (args) 133return rval; 134} |