级别： 初级 Peter Seebach (developerworks@seebs.plethora.net), 自由作家
2004 年 9 月 24 日 本文是由两部分构成的系列文章的第二篇，将研究更高级的 lex/yacc 开发，并介绍基本的问题诊断技术。留心在您眼前解析的电子邮件标题！对含义模糊的错误消息感到惊奇！观察计算机确实在进行计算！
在由两部分构成的系列文章的
第 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 能够只在一些时候去匹配某些规则。它使用的两个声明的名称为
BODY 和
HEADER 。
HEADER 声明用来解析给定的名称/值对中的值部分，而不是
用来解析整个消息的标题。使用
HEADER 和
BODY
规则的原因是，确保 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 例程将对您大有帮助。随着语法越来越复杂，
更重要的是要为遇到的错误作出清晰而且有意义的诊断。
参考资料
关于作者
对本文的评价
| 
