内容


使用 Flex 和 Bison 更好地进行错误处理

构建更加用户友好的编译器和解释器的技巧

Comments

简介

正如 UNIX® 开发人员所了解的那样,Flex 和 Bison 的功能非常强大,非常适合开发词法和语法解析器,尤其是语言编译器和解释器。如果我们不熟悉它们所实现的工具 —— 分别是 Lex 和 Yacc —— 可以参考一下本文 参考资料 一节中有关 Flex 和 Bison 文档的链接,以及其他介绍这两个程序的文章。

本文介绍了更高级的一些主题:用来在编译器和解释器中更好地实现错误处理能力的特性和技术。为了展示这些技术,我使用了一个示例程序 ccalc,它基于 Bison 手册中的计算机实现了一个增强的计算器。我们可以从本文后面 下载 一节下载 ccalc 和相关文件。

增强包括使用了很多变量。在 ccalc 中,变量是通过在初始化中首次使用时定义的,例如 a = 3。如果变量是在初始化之前使用的,那就会产生语义错误,使用值为 0 来创建这个变量,并打印一条消息。

示例源文件

示例源代码中包括 7 个文件:

  • ccalc.c:主程序,以及一些进行输入、输出和错误处理的函数
  • ccalc.h:包括了对所有模块的定义
  • cmath.c:数学函数
  • parse.y:Bison 使用的输入文法
  • lex.l:Flex 的输入
  • makefile:简单的 makefile
  • defs.txt:示例输入文件

这个程序接收两个参数:

  • -debug:产生调试输出
  • filename:输入文件名;默认值为 defs.txt

Bison 使用的设置

为了处理变量名和实际值,Bison 的语义类型必须进行增强:

清单 1. 更好的 Bison 语义类型
/* generate include-file with symbols and types */
%defines
/* a more advanced semantic type */
%union {
  double      value;
  char        *string;
}

有些文法规则可以产生特定的语义类型,这需要像清单 2 中一样对 Bison 进行声明。要获得一个可移植性更好的 Bison 文法版本,我们需要重新定义 +-*/() 符号。下面这个例子没有使用左括号 (,而是使用了结束符符号 LBRACE,这是由词法分析提供的。另外,操作符的优先顺序也必须进行声明。

对于 Flex 来说,所生成的代码通常都依赖于平台所使用的代码页(codepage)。尽管我们可以使用其他代码页,但是必须要对输入进行转换。因此与 Bison 代码不同,Flex 代码尚不能进行移植。

清单 2. Bison 声明
/* terminal symbols */

%token <string>   IDENTIFIER
%token <value>    VALUE
%type <value>     expression

/* operator-precedence
 * top-0: -
 *     1: * /
 *     2: + -
*/

%left ADD SUB
%left MULT DIV
%left NEG

%start program

这段文法与 Bison 手册非常类似,不同之处在于它使用了名字作为终端符号和标识符的简写形式。标识符是在赋值语句中进行定义和初始化的,并且可以在任何允许使用的地方使用。清单 3 给出了一个示例文法:

清单 3. 示例 Bison 文法
program
    : statement SEMICOLON program
    | statement SEMICOLON
    | statement error SEMICOLON program
    ;

statement
    : IDENTIFIER ASSIGN expression
    | expression
    ;

expression
    : LBRACE expression RBRACE
    | SUB expression %prec NEG
    | expression ADD expression
    | expression SUB expression
    | expression MULT expression
    | expression DIV expression
    | VALUE
    | IDENTIFIER
    ;

program 的第三个输出让这个分析程序可以获得错误,从中搜索分号,然后继续执行(通常错误对于解析器来说都是非常严重的)。

为了让这个例子更加有趣,规则体中的真正数学函数都是以单独函数的形式实现的。在进行高级文法分析时,我们要尽量保证规则简短,并使用函数来实现一些不会直接处理解析的过程:

清单 4. 使用单独的函数来实现数学规则
| expression DIV expression
  {
    $$ = ReduceDiv($1, $3);
  }

最后,函数 yyerror() 必须要进行定义。这个函数是在所生成的解析器检测到语法错误时调用的,它又会调用一个小函数 PrintError(),后者会打印增强的错误消息。详细内容请参看源代码。

Flex 的设置

Flex 所生成的词法分析器必须要根据语义类型提供终止符号。清单 5 定义了空格、实际值、标识符和符号所使用的语法。

清单 5. 示例 Flex 规则
[ \t\r\n]+  {
    /* eat up whitespace */
    }

{DIGIT}+  {
    yylval.value = atof(yytext);
    return VALUE;
    }

{DIGIT}+"."{DIGIT}*        {
    yylval.value = atof(yytext);
    return VALUE;
    }

{DIGIT}+[eE]["+""-"]?{DIGIT}*        {
    yylval.value = atof(yytext);
    return VALUE;
    }

{DIGIT}+"."{DIGIT}*[eE]["+""-"]?{DIGIT}*        {
    yylval.value = atof(yytext);
    return VALUE;
    }

{ID}        {
    yylval.string = malloc(strlen(yytext)+1);
    strcpy(yylval.string, yytext);
    return IDENTIFIER;
    }

"+"       { return ADD; }
"-"       { return SUB; }
"*"       { return MULT; }
"/"       { return DIV; }
"("       { return LBRACE; }
")"       { return RBRACE; }
";"       { return SEMICOLON; }
"="       { return ASSIGN; }

为了帮助调试,我们在程序运行的末尾把所有已知的变量及其当前内容都打印了出来。

使用普通错误消息的例子

使用下面的输入(其中稍微进行了排版)来编译并运行这个示例解析器程序 ccalc

清单 6. 数学解析器的示例输入
a = 3;
3 aa = a * 4;
b = aa / ( a - 3 );

输出结果如下所示:

清单 7. 数学解析器的示例输出
Error 'syntax error'
Error: reference to unknown variable 'aa'
division by zero!
final content of variables
   Name------------------ Value----------
   'a                   ' 3
   'b                   ' 3
   'aa                  ' 0

这个输出结果并非非常有用,因为它并没有显示问题到底在什么地方。这在下一节中会进行介绍。

扩展 Bison 可以更好地处理错误消息

Bison 的最主要的特性在 Bison 手册中隐藏的很深,就是它可以通过使用 YYERROR_VERBOSE 宏在产生语法错误的情况下生成更有意义的错误消息。

普通的 'syntax error' 消息如下:

Error 'syntax error, unexpected IDENTIFIER, expecting SEMICOLON'

这条消息对于调试更为合适。

更好的输入函数

使用原来的错误消息,很难判断语义的错误。当然,这个例子非常容易修复,因为我们立即就可以找出有错误的那一行。在更加复杂的语法和对应输入中,这可能并不简单。让我们编写一个输入函数来从文件中读取相应的行。

Flex 具有一个非常有用的宏 YY_INPUT,它负责为符号解释读入数据。我们可以在 YY_INPUT 宏中添加一个对 GetNextChar() 函数的调用,后者从文件中读取数据,并保留了下一个要读取的字符的位置信息。GetNextChar() 使用了一个缓冲区来存放一行输入。这两个变量保存了当前行号和该行中下一个字符的位置:

清单 8. 更好的 Flex YY_INPUT 宏
#define YY_INPUT(buf,result,max_size)  {\
    result = GetNextChar(buf, max_size); \
    if (  result <= 0  ) \
      result = YY_NULL; \
    }

使用这个增强的错误打印函数 PrintError()(在前面讨论过,它可以很好地显示有问题的输入行,完整的 PrintError() 源代码请参看 示例源代码),我们就具有了一个用户友好的消息,它显示了下一个字符的位置:

清单 9. 更好的 Flex 错误:字符位置
       |....+....:....+....:....+....:....+....:....+....:....+
     1 |a = 3;
     2 |3 aa = a * 4;
...... !.....^
Error: syntax error, unexpected IDENTIFIER, expecting SEMICOLON
     3 |b = aa / ( a - 3 );
...... !.......^
Error: reference to unknown variable 'aa'
...... !.................^
Error: division by zero!

这个示例函数可以从其他函数(例如 ReduceDiv())中进行调用,从而打印语义错误,例如 division by zerounknown identifiers

如果我们希望标记一下最后使用的符号,就可以对 Flex 规则进行扩展,并修改错误的打印。函数 BeginToken()PrintError()(二者都可以在示例源代码中找到)是关键:BeginToken() 是由每条规则进行调用的,这样它就可以记住每个符号的开始和结束,每次打印错误时都会调用 PrintError()。这样,我们就可以生成一条有用的消息了,例如:

清单 10. 更好的 Flex 错误:表示确切的符号位置
     2 |3 aa = a * 4;
...... !..^^............
Error: syntax error, unexpected IDENTIFIER, expecting SEMICOLON

缺点

所生成的词法解析器可能会在检测到某个符号之前读入多个字符。因此,这个过程不可能精确地显示确切的位置。它最终取决于为 Flex 所提供的规则。规则越复杂,位置的精确程度就越低。这个例子中的规则可以由 Flex 通过提前查找一个字符来进行处理,这会让位置的预测更加精确。

Bison 的定位机制

下面让我们来看一下 division by zero 这个错误。最后一次符号读取(结束括号)并不是这个错误的根源。表达式 (a-3) 的值就是 0。对于更好的错误消息来说,我们需要知道表达式的位置。要实现这种功能,我们可以在 YYLTYPE 类型的全局变量 yylloc 中提供这个符号的确切位置。使用宏 YYLLOC_DEFAULT(请参看 Bison 文档 中默认的定义),Bison 可以计算出某个表达式的位置。

记住,只有当您在文法中使用位置时才会定义类型。这是一个常见的错误。

默认的位置类型 YYLTYPE 如清单 11 所示。我们可以对这个类型重新进行定义,使其包括更多信息,例如 Flex 所读取的文件名。

清单 11. 默认位置类型 YYLTYPE
typedef struct YYLTYPE
{
  int first_line;
  int first_column;
  int last_line;
  int last_column;
} YYLTYPE;

在上一节中,我们看到了 BeginToken() 函数,它是在新符号开始时调用的。此时就应该存储这个位置了。在我们的例子中,一个符号不能跨越多行,因此 first_linelast_line 是相同的,它们都保存了当前的行号。其他属性有符号的起点(first_column)和终点(last_column),这是通过符号的起点和长度计算出来的。

要使用这个位置,我们必须对规则处理函数进行处理,如清单 12 所示。符号 $3 的位置是通过 @3 进行引用的。为了防止拷贝这个规则中的整个结构,我们生成了一个指针 &@3。这看起来可能有点奇怪,但却是正确的。

清单 12. 记住规则中的位置
| expression DIV expression
  {
    $$ = ReduceDiv($1, $3, &@3);
  }

在处理函数中,我们获得了一个指向保存了位置信息的 YYLTYPE 结构的指针,这样可以生成一条很好的错误消息。

清单 13. 在 ReduceDiv 中使用保存的位置
extern
double ReduceDiv(double a, double b, YYLTYPE *bloc) {
  if (  b == 0  ) {
    PrintError("division by zero! Line %d:c%d to %d:c%d",
                        bloc->first_line, bloc->first_column,
                        bloc->last_line, bloc->last_column);
    return MAXFLOAT;
  }
  return a / b;
}

现在错误消息可以帮助我们来定位问题了。除零操作错误在第 3 行的第 10 列到 18 列之间。

清单 14. 更好的 ReduceDiv() 错误消息
       |....+....:....+....:....+....:....+....:....+....:....+
     1 |a = 3;
     2 |3 aa = a * 4;
...... !..^^...........
Error: syntax error, unexpected IDENTIFIER, expecting SEMICOLON
     3 |b = aa / ( a - 3 );
...... !....^^...............
Error: reference to unknown variable 'aa'
...... !.................^..
 Error: division by zero! Line 3:10 to 3:18
final content of variables
   Name------------------ Value----------
   'a                   ' 3
   'b                   ' 3.40282e+38
   'aa                  ' 0

结束语

Flex 和 Bison 是用来解析文法的一对功能强大的组合。通过使用本文中介绍的技巧,我们可以构建更好的解释器,它们可以生成像您自己喜欢的编译器中一样的有用的、容易理解的错误消息。


下载资源


相关主题

  • 您可以参阅本文在 developerWorks 全球站点上的 英文原文
  • 请在线阅读 Flex 文档
  • 请在线阅读 Bison 文档
  • 有关 Flex 和 Bison 祖先的背景知识,请查看 Lex 和 Yacc 主页
  • 更多有关 Lex 和 Yacc 的内容,请阅读两部分的 developerWorks 系列 Build code with lex and yacc第一部分 介绍了 lex、yacc、flex 和 bison,第二部分 探讨了更高级的开发和故障诊断问题。另外还可以参考这篇 Lex 和 Yacc 入门,它更详细地介绍了有关 Lex 和 Yacc 的使用知识。
  • developerWorks Linux 专区 中可以找到为 Linux 开发人员准备的更多资源。
  • 在您的下一个开发项目中采用 IBM 试用软件,这可以从 developerWorks 上直接下载。

评论

添加或订阅评论,请先登录注册

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=10
Zone=Linux, Open source
ArticleID=156009
ArticleTitle=使用 Flex 和 Bison 更好地进行错误处理
publish-date=08242006