内容


使用 lex 和 yacc 编译代码,第 2 部分:开发和故障检修

真正开始编译

Comments

在由两部分构成的系列文章的 第 1 部分所涉及的内容基础之上,本文讨论了两个具体的 lex 和 yacc 应用程序,并讨论了一些常见的缺陷。 这两个例子 —— 一个简单的计算器和一个解析电子邮件消息的程序,都很简单。

Lex-only 代码

虽然可以用 lex 来为解析器生成记号序列,但也可以用它来执行简单的输入操作。例如,有很多 将简单的 English 本文转换为方言的程序都是只用 lex 编写的。最有名的可能是在因特网上广为分布 的经典的 Swedish Chef 翻译器。可以通过识别零散的模式并直接作用于它们来完成这些工作。一个好的 lexer 例子会非常有助于学习如何编写断词器(tokenizer)。在本文的 参考资料 部分中,有指向 Swedish Chef 程序的链接(可以得到源代码,所以您可以确切地理解它是如何完成的)。

当然,大部分简单编程项目使用非常普通的 lexer 就可以完成。 在设计一门语言时要多考虑,通过确保不需要知道上下文就能够可靠地识别出记号,可以充分简化编程。 当然,不是所有语言都是这样的;例如,lex 与 C 字符串常量不相容,因为特殊字符会修改其他字符。

小例子:一个计算器

这里是一个简单的示例程序,只需要一页 yacc 代码和半页 lex 代码就可以编写完该程序。它阐明了 一些有趣之处,甚至有一些便利... 有时候。

清单 1. 简单计算器的 Lexer
%{
#include "calc.h"
#include "y.tab.h"
%}
NUMBER  [0-9]+
OP	[+-/*]
%%
{NUMBER}	{ yylval.value = strtol(yytext, 0, 10); return NUMBER; }
({OP}|\n)	{ return yytext[0]; }
.		{ ; }

这里要做的全部工作是匹配数字、运算符和换行。数字会返回专门的标记 NUMBER ; 其余的都只是作为普通的字符返回。没有得到匹配的字符则被悄悄忽略掉。

清单 2. 简单计算器的解析器
%{
#include <stdio.h>
#include "calc.h"
%}
%union {
	long value;
}
%type <value> expression add_expr mul_expr
%token <value> NUMBER
%%
input:
	  expression
	| input expression
expression:
	  expression '\n' { printf("%ld\n", $1); }
	| expression '+' add_expr { $$ = $1 + $3; }
	| expression '-' add_expr { $$ = $1 - $3; }
	| add_expr { $$ = $1; }
add_expr:
	  add_expr '*' mul_expr { $$ = $1 * $3; }
	| add_expr '/' mul_expr { $$ = $1 / $3; }
	| mul_expr { $$ = $1; }
mul_expr:
	  NUMBER { $$ = $1; }

该解析器展示了处理优先级和结合性的方法,但不要求显式地使用 %prec 声明来引导 yacc 解决冲突。 如果松绑定(looser-binding)运算符使用紧绑定(tighter-binding)运算符作为操作数表达式, 那么优先级是自动处理的。举例来说,这就是 C 标准定义其形式语法的方式。

注意,当在一个表达式后面发现一个换行时,表达式的值就会被直接打印出来。无需进行长期 存储,也不用修改任何变量。对于敏捷的桌面计算器来说,这就做得够好了。

还要注意向左递归的使用。yacc 选择向左递归。您可以适当地编写“input”的规则:

input: expression
| expression input

不过,如果这样做,那么您写的每一个表达式都将导致在解析器中另一个层次上的递归; 如先前所写的一样,在解析下一个表达式之前,每个表达式都被归约为一个 input 对象。向左递归更有效,而且对较大的输入集来说,这可能是惟一可行的选择。

具体的例子:解析电子邮件

一个可能的任务是,读取包含电子邮件消息的文件,并提取它们的标题和内容。 这是一个有趣的例子,因为读取标题的规则太复杂,这使得对其中一部分使用 start 声明 更为实用。lexer 实际上完成了指出它位于消息中的哪个地方的一些任务,但是解析器仍 将所有内容放在一起。

示例程序可以读取单独的消息或者 Berkeley “mbox”格式的消息。它使用以“From”开头的行 作为消息分隔符;这是可以修改的,但是用它就足够了。

用于此的支持代码相当简单。“sz”类型为代码提供了便利,它是一个字符串库, 隐藏了字符串增长时重新分配所需的全部工作。这个结构是极度简化的,没有被 很好地实现;这是为了让代码更少,更容易读懂。实际的代码应该更全面。

语法通常相当简单。一个文件由一个或多个消息构成。为了归约每个消息之后的规则, 使用的是向左递归。消息包括一个标题、一个空行和一个主体。主体非常简单易读:是一系列的行。 您可能会注意到,主体没有显式的终结符。更确切地说,首先,不属于消息主体的内容必须与下一个可能对象的开头部分相匹配;少许读取内容出现反复,这表明它必定是标题部分。 由于主体中只会出现 LINE 标记,所以出现下一个其他标记,表明这是标题部分 —— 或者是一个语法错。作为一种特殊情况(在 yacc 中是隐式的,没有在语法中声明),0 标记表示不再有任何标记,解析结束。如果已经成功地归约了 start 规则(在这个例子中即 file ),那么可以认为解析是成功的。

标题语法相当复杂,尽管还不是最复杂。标题可以从 headerline 或者 FROMLINE 标记开始。 headerline 是 非终极符(non-terminal),它依次需要有一个标题名称、标题主体以及可选的附加部分。为了保证效率,附加部分的行处理 也是向左递归的。注意,在理论上,这个语法会接受有多个“From”行的标题;这可能是固定的,不过,没有明显的理由去担心它。

该示例中的 lexer 比计算器的更为复杂;复杂得多。它使用了 start 声明 —— 这项功能使 lexer 能够只在一些时候去匹配某些规则。它使用的两个声明的名称为 BODYHEADERHEADER 声明用来解析给定的名称/值对中的值部分,而不是 用来解析整个消息的标题。使用 HEADERBODY 规则的原因是,确保 lexer 在开始退还全部行(解析器必须随后进行分析以决定如何处理它们)之前 识别出标题的名称和附加部分。

这确实意味着 lexer 和解析器都必须明白,是一个空行将标题从主体中分离了出来。与此类似,lexer 必须 明白附加部分的结构;解析器只知道有时它需要将附加的文本添加到标题中。

在这个程序中,解析器使用全局变量来追踪解析的消息列表。这就是测试程序访问消息列表 的方式;对 yyparse() 进行调用返回的只是成功或失败的标志,而 不是它可能已经创建的任何对象。(返回值为零,说明是一次成功的解析,否则返回的是非零值。)

常见问题的故障检修

lex 和 yacc 非常擅长解析相当简单的文件格式。最大的局限在于,yacc 被限定为一个预读标记。 这就意味着,如果 yacc 在知道采取哪个动作之前,必须读取两个标记,那么它将无法解析该语法。

清单 3. 将 Uncle Shelby's ABZ 用作一个 yacc 语法
a_f:
	  'a' 'b' 'c' 'd' 'e' 'f' { printf("alphabet\n"); }
	| 'a' 'b' 'z' 'd' 'e' 'f' { printf("Silverstein\n"); }

在这种情况中,必须采取动作时,yacc 可以断定它解析的是哪个字母表 —— 是规则的那个字母表,还是 Uncle Shelby's ABZ。另一方面,如果这样编写规则,那么该规则将不会生效:

清单 4. 一个不可解析的语法
a_f:
	  'a' { printf("alphabet\n"); } 'b' 'c' 'd' 'e' 'f'
	| 'a' { printf("Silverstein\n"); } 'b' 'z' 'd' 'e' 'f'

在这种情况中,要决定采取两个动作中的哪一个动作,yacc 可以使用的惟一记号是字母“b”,而它 在两个规则中是相同的。该语法是不明确的;所以 yacc 无法指出接下来将做什么。

但是,yacc 可以预读一个字符,所以:

清单 5. 一个可解析的语法
a_f:
	  'a' 'b' { printf("alphabet\n"); } 'c' 'd' 'e' 'f'
	| 'a' 'b' { printf("Silverstein\n"); } 'z' 'd' 'e' 'f'

该版本是可以运行的。当 yacc 获得“c”或“z”时,它所知道的足以确定将使用哪一个规则。对处理相当简单的文件格式来说,这一 灵活性通常就足够了。

冲突的解决

大部分人偶而会遇到移位/归约(shift/reduce)冲突或者归约/归约(reduce/reduce)冲突。第一个问题的问题不大,而第二个问题 通常非常严重。移位/归约冲突最著名的例子是 C 中的“dangling else”的歧义性。

设想一个类似这样的 yacc 语法:

清单 6. Dangling else
statement	  if '(' condition ')' statement
         	| if '(' condition ')' statement else statement
		| printf '(' string ')' ';'

如果稍微简化一下,该语法非常类似于实际的 C 语法。现在,考虑在一个条件语句嵌套在另一个 条件语句中的情况下,会发生什么事情:

清单 7. 嵌套的条件
if (a)
if (b)
printf("a and b\n");
else
printf("--?\n");

else 标记是关联到内部的( if (b) ) 还是外部 if ?不管是哪种情况,都会有一个 if/else 结构实例,以及一个普通的 if。这叫做移位/归约 冲突。当 yacc 发现 else 标记时,它可以将序列(从 if (b) 到分号) 归约为一个 声明(已经将整个 printf 归约到一个声明中),或者它可以将 else 标记 移位到声明之上,使之成为一个更大模式的前半部分。 实际上,yacc 的解释将会如下所示:

清单 8. 判定的 dangling else
if (a)
	if (b)
		printf("a and b\n");
	else
		printf("a and not-b\n");

默认的行为更多是进行移位而不是归约,而且这通常是您最希望看到的。可以通过设置不同模式的 优先级来强制改变这种行为。另一种方法是设计语法来排除这种歧义性:例如,在 perl 中, 如果 if 声明不是可选的,那么就用大括号将主体括起来,这样就 可以简单地告知 else 是内部还是外部 if 声明的一部分。

lexer 也有一些问题。常见的问题是,一个规则匹配太多的文本;更糟糕的是,由于 lex 倾向于匹配它能找到的最长的文本,这可能导致匹配的是一个完全不适当的规则。start 声明 在很大程度上有助于解决此问题。更强大的工具是排他(exclusive)声明,在这个工具中,只有符合排他声明的规则才能被匹配(并不是所有的 lex 版本都支持这项功能,不过所有最新版本 中都应该可以获得该功能)。

如果您的 lex 版本没有排他声明,那么您可以使用声明来限制每一个规则,并在其中进行切换。 使用 %{...%} 块来 BEGIN 您想用作 默认的声明,这样它将生效,而所有其他声明好像都被排除在外一样。

多个解析器和 lexer

以前,在一个程序中使用多个解析器时,需要非常小心地调整 lex 和 yacc 生成的文件。 这一点已经得到了修正,而且更加便利:lex 和 yacc 的最新版本都允许您在生成代码的符号名称上指定一个前缀。就照这样去做吧 —— 这样更简单。在 flex 中,该选项是 -Pprefix ;在最新的 yacc 中,最常见的是 -p prefix 。如果您可以使用的默认的 lex 和 yacc 不支持这项功能,那么您可以随时安排使用 flex 或者 bison。

继续前进

为了深入学习 lex 和 yacc,您最好去编写一些用来消遣的小程序。在因特网上也很容易 找到示例程序:只需稍加搜索就可以找到所有种类的极好材料。文章最后的一些链接可能会对您的起步有所帮助。

只要有可能,请尝试为您的 lexer 和解析器开发单独的测试。当遇到问题时,最重要的是 明白哪里出错了;一个好的出发点是弄明白是标记出错,还是语法中的错误。投入一些精力 编写一个好的 yyerror 例程将对您大有帮助。随着语法越来越复杂, 更重要的是要为遇到的错误作出清晰而且有意义的诊断。


相关主题


评论

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

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=10
Zone=Linux
ArticleID=163251
ArticleTitle=使用 lex 和 yacc 编译代码,第 2 部分:开发和故障检修
publish-date=09242004