lex和yacc入门（第一部分）
4.90/5 (52投票s)
一个关于如何在项目中使用lex和yacc创建解析器的指南。
lex和yacc简介。
我正在开发一个用于处理对话框模板的编辑器。我赶紧补充一下，这不是一个对话框编辑器本身——而是一个可以处理与对话框相关的、但Visual Studio不支持的表格的编辑器。
作为项目的一部分，我想能够像对话框一样加载和显示对话框模板。
要做到这一点，有简单的方法和困难的方法。简单的方法是要求资源脚本已经被编译成.res文件，然后（以某种方式）获取编译后的模板。既然我（大概）正在编写对话框模板，而且它们是我正在进行的项目的一部分，那么假设我能访问.res文件似乎是合理的。这将允许我获得一个对话框模板的句柄并将其传递给CreateDialogIndirect，同时也能让我检查每个控件的特性。但这并不允许人类记忆的错误。如果有一件事我敢肯定，那就是我会在某个地方更改一个对话框模板，然后忘记编译它。
因此，我们有了困难的方法。我决定编写一个解析器，它可以读取Visual Studio 6资源源文件（.rc文件），并向我返回一组已编译的对话框模板。
那么，该如何着手呢？快速查看一下资源模板文件的源代码，就足以告诉我，人生太短暂，不值得去尝试以显而易见的方式去做。资源文件包含许多文本块。有些是注释，有些是工具栏资源，有些是菜单，有些是对话框，还有许多其他类型的块。每种块都有自己的格式。使用常规过程式编程编写一个了解所有这些块的解析器似乎是很多工作。所以我转向了yacc和lex来寻求帮助。
Yacc和Lex 101
Yacc和Lex起源于UNIX世界。Yacc代表“yet another compiler compiler”（又是另一个编译器编译器），Lex是“lexical analyser”（词法分析器）的缩写。哇，这告诉你很多，不是吗！我接触yacc是在1986年左右，当时我正在阅读HPUX 9.x手册，发现了一章关于yacc的内容。它几乎是yacc的标准介绍——它假设你在开始之前就已经了解了整个主题。参见http://dinosaur.compilertools.net/，这是一个很好的例子，展示了描述和解释的程度。
Lex是一个读取来自某处的输入流并将其分解为组成部分的工具。每个组成部分都是一个标记（token）。一个标记可以是关键字、数字、字符串或标点符号。在这种情况下，一个标记是不能再分解成更小部分的东西。它要么是一个关键字，要么是别的东西。如果它是一个字符串，它就是一个字符串，我们不关心字符串的机器表示。数字和标点符号也是如此。
Yacc是一个接收来自某处的标记流并对其施加结构的工具。程序员定义结构并指定在识别出特定结构时要执行的操作。yacc经常从lex获取标记，这并不令人意外。（顺便说一句，我想指出yacc和lex是UNIX程序——在GNU中有flex和bison作为等价物——对yacc来说这是一个相当糟糕的双关语……为了本文的目的，你可以互换使用flex和lex，或者yacc和bison）。
对于yacc，程序员编写一个语法并将其通过yacc处理。输出是一个c文件，然后被编译并链接到你的程序中。lex也是如此。
Yacc和Lex 102
yacc和lex文件的整体结构是相似的。第一部分包含通用的c代码声明和yacc/lex指令，并通过%%行与第二部分分隔。
第二部分包含yacc文件中的yacc语法，或lex文件中的正则表达式。第二部分通过%%行与第三部分分隔。
第三部分包含原始c代码，这些代码将按原样复制到输出文件中。
yacc文件看起来像这样
%{
C declarations
%}
yacc declarations
%%
Grammar rules
%%
Additional C code
lex文件看起来像这样
%{
C declarations
%}
lex declarations
%%
Regular expressions
%%
Additional C code
Yacc和Lex 103
让我们来看一个简单的yacc语法。我们正在尝试编写一个解析器来解释资源脚本文件中的对话框模板。了解你的输入！所以，我们先来看看对话框模板。
IDD_WHISPERWINDOW DIALOG 0, 0, 261, 146 STYLE DS_MODALFRAME |
WS_MINIMIZEBOX | WS_POPUP | WS_VISIBLE | WS_CAPTION | WS_SYSMENU
CAPTION "Whispers"
FONT 8, "MS Sans Serif"
BEGIN
CONTROL"",IDC_EDIT,"RichEdit20A",WS_BORDER | WS_TABSTOP
| 0xc4,7,109,247,12
CONTROL"",IDC_RICHEDIT,"RichEdit20A",WS_BORDER |
WS_VSCROLL | WS_TABSTOP | 0x844,7,7,247,100
END
我们可以将其分解为以下部分
对话框模板由一个ID后跟DIALOG关键字，然后是一些屏幕坐标，然后是STYLE，然后是CAPTION，然后是FONT，最后是一个定义了一些控件的块组成。呼，真是个大 mouthful！
用yacc表达可能看起来像这样
%start dialog
%token L_ID
%token L_STRING
%token L_NUMBER
%token L_DIALOG
%token L_STYLE
%token L_CAPTION
%token L_FONT
%token L_BEGIN
%token L_END
%token L_STYLES
%token L_CONTROL
%token L_NUM
%token L_WS_TABSTOP
%token L_WS_BORDER
more
styles
%%
dialog : L_ID L_DIALOG L_NUM ',' L_NUM ','
L_NUM ',' L_NUM L_STYLEstylescaption L_FONT L_NUM ',' L_STRING
L_BEGIN controls L_END
;
styles : style
| style '|' styles
;
style : L_WS_TABSTOP
| L_WS_BORDER
| L_WS_VSCROLL
| /* more styles */
;
caption : /*empty */
| L_CAPTION L_STRING
;
controls : control
| control controls
;
control : L_CONTROL L_STRING ',' L_ID ',' L_STRING ',' styles
',' L_NUM ',' L_NUM ',' L_NUM ',' L_NUM
;
%%
这个yacc程序的第一部分是%start dialog声明。这告诉解析器，它应该开始假设它正在查找与文件中稍后定义的dialog规则匹配的输入。
然后是定义一系列标记。每个%token是一个标记，是输入的最低级组件。请注意，我们没有定义L_ID看起来是什么样的。我们也没有定义L_STRING看起来是什么样的。我们只是说明yacc解析器识别一个标记，表示在输入流的这一点，我们已经看到了一个L_ID或一个L_STRING。但请记住这一点……
除了显式命名的标记之外，yacc解析器还将单个字符视为标记。你可以在dialog语法的第一行看到这一点。
dialog:L_ID L_DIALOG L_NUM ',' L_NUM ',' L_NUM ',' L_NUM
','是一个标记，代表输入流中的逗号。
接下来是dialog : 行。用yacc的说法，这就是我上面说的：一个对话框模板由一个对话框ID（一个L_ID）后跟'DIALOG'关键字，然后是一些屏幕坐标，然后是STYLE，然后是CAPTION，然后是FONT，最后是一个定义了一些控件的块组成。
冒号(:)左边的部分是一个非终结符符号。这仅仅意味着它不是一个标记，并且它可以被分解成更小的部分（标记）。冒号(:)右边的部分可以是标记（不再可能进行归约）或非终结符符号，这些符号又由更精细的结构组成。左手边（非终结符符号）的定义一直持续到我们遇到分号';'。
惯例规定标记（终结符符号）为大写，非终结符为小写。因此，从上面的例子来看
dialog:L_ID L_DIALOG L_NUM ',' L_NUM ',' L_NUM ',' L_NUM
dialog是一个非终结符符号，定义为L_ID（标记）后跟L_DIALOG（标记）后跟L_NUM（标记）后跟逗号','等等……
当yacc解析器看到这个标记流时，它就知道它在处理某些东西——即，一个对话框模板。
Yacc和Lex 104
现在我们已经定义了一个简单的语法，让我们看看标记流的来源。最基本的是，我们需要一种方法来识别一个字符流是否匹配某个特定模式，并以某种方式向解析器发出信号，表明我们刚刚看到了那个特定的模式。
模式可以是特定关键字，如DIALOG，也可以是字面意义上的模式，如'任何数字串'。
一个能够识别上面示例yacc语法中使用的标记集的基于lex的词法分析器可能看起来像这样……
%%
"DIALOG" { return L_DIALOG; }
"STYLE" { return L_STYLE; }
"CAPTION" { return L_CAPTION; }
"FONT" { return L_FONT; }
"BEGIN" { return L_BEGIN; }
"END" { return L_END; }
"CONTROL" { return L_CONTROL; }
"WS_TABSTOP" { return L_WS_TABSTOP; }
"WS_BORDER" { return L_WS_BORDER; }
more styles
[a-zA-Z_][a-zA-Z0-9_]* { return L_ID; }
-?[0-9]+ { return L_NUM; }
"\".*\"" { return L_STRING; }
%%
lex脚本中的每一行都是一个正则表达式。正则表达式可以是特定的关键字，也可以是lex识别的模式。当lex识别出一个模式时，它会执行与该模式相关的操作（花括号{}之间的内容），然后继续处理后续输入。
请注意，这是不完整的——我还没有指定一种方法让词法分析器（标记器）将与标记相关联的数据返回给解析器。对于像DIALOG这样的简单关键字，无需返回数据——识别出DIALOG关键字的事实本身就是数据。但是对于字符串，你需要同时传递你看到了一个字符串以及这个字符串本身。我们稍后会讲到这个。
Yacc和Lex 105
现在是时候看看词法分析器如何返回数据值以及标记类型了。为了实现这一点，yacc和lex协同工作。Yacc定义了附加到每个标记的数据类型，并定义了一个包含所有可能数据类型的联合体。例如。
%union {
int numVal;
char *stringval;
}
这个声明出现在yacc脚本的第一部分（第一个%%之前的部分）。在联合体声明之后，列出每个需要返回数据类型的标记。并非所有标记都需要返回数据——关键字标记通常不需要，因为看到关键字本身就是足够的数据。标记声明带有数据类型的例子如下
%type <numVal> L_NUM
%type <stringVal> L_STRING L_ID
这说明L_NUM标记附带的数据是数值型的，而L_STRING和L_ID的数据是字符串数据。它还告诉yacc，当它看到L_NUM类型的标记时，它应该使用numVal成员作为int，当它看到L_STRING或L_ID类型的标记时，它应该使用stringVal成员作为char *。numVal成员是什么的？你不用关心——因为你将使用yacc特定的语法来引用数据，并让yacc负责处理数据确切的位置。
在lex脚本中，每个代码片段负责提取相关数据并将其分配给联合体中适当的数据成员。yacc和lex在这种情况下变得非常亲密，因为yacc定义了数据结构，而lex执行对数据结构的赋值。
与lex脚本中识别数字和ID的正则表达式相关的代码片段更改为如下所示：
[a-zA-Z_][a-zA-Z0-9_]* {
yylval.stringVal = strdup(yytext);
return L_ID;
}
-?[0-9]+ {
yylval.numVal = atoi(yytext);
return L_NUM;
}
yytext是匹配规则的文本，yylval是解析器提供的、在联合体语句中定义的数据类型的实例。
如果整数对你的解析器来说足够了，那么可以省略联合体语句。默认情况下，所有标记类型都使用整数。
Yacc和Lex 106
让我们仔细看看yacc语法。假设标记已经定义（按照惯例，所有标记都是大写）。我们现在感兴趣的语法部分是：
%%
dialog : L_ID L_DIALOG L_NUM ',' L_NUM ',' L_NUM
',' L_NUM L_STYLE styles caption L_FONT L_NUM ','
L_STRING L_BEGIN controls
L_END
;
styles : style
| style '|' styles
;
style : L_WS_TABSTOP
| L_WS_BORDER
| L_WS_VSCROLL
| /* more styles */
;
caption : /*empty */
| L_CAPTION L_STRING
;
controls : control
| control controls
;
control : L_CONTROL L_STRING ',' L_ID ',' L_STRING ',' styles
',L_NUM ',' L_NUM ',' L_NUM ',' L_NUM
;
%%
我们已经确定dialog :行定义了对话框模板的轮廓。为了让解析器识别一个对话框模板，冒号（:）和分号（;）之间的每个标记都必须存在。
我们还可以说，一个非终结符符号（“: ”的左边）由这个或那个组成。我们通过在冒号后面立即写出第一个替代项，然后加上一个“|”符号和第二个替代项来实现这一点。一个非终结符符号由这个或那个或这个组成……
看看styles的定义。
styles : style
| style '|' styles
;
这里发生的是，我们说styles由一个style组成，或者一个style后跟一个'|'管道符，后跟styles本身。这是一个右递归规则。这就是我们如何解析类似以下的内容
DS_MODALFRAME | WS_MINIMIZEBOX | WS_POPUP | WS_VISIBLE | WS_CAPTION |
WS_SYSMENU
并期望能够成功。解析器获取一个代表第一个style的标记，DS_MODALFRAME，并看到它后面跟着一个管道符'|'。规则表明，如果它看到一个style后跟一个'|'，它将遵循第二个分支。该分支规定它应该接着查找另一个style，此时它看到了WS_MINIMIZEBOX。依此类推，直到它看到WS_SYSMENU，之后它将看到另一个符号，因此遵循第一个分支，该分支由style单独组成。
现在我们来看看caption的定义。
caption : /*empty */
| L_CAPTION L_STRING
;
这是另一个强大的yacc构造。第一个分支是空的。换句话说，caption是可选的。但如果它存在，它必须由L_CAPTION标记后跟L_STRING标记组成。
Yacc和Lex 107
显然，我上面展示的解析器和词法分析器是不完整的。它们不仅不允许对话框模板的各种变化，而且除了识别遵循有限规则的对话框模板之外，它们不做任何事情。我不会在这篇文章中提供一个完整的对话框模板解析器。你可以在第二部分找到它。但我确实计划向你展示如何让解析器对它解析的内容做一些有用的事情。
所以现在我们来添加一些代码来处理我们匹配的规则。我将使用伪代码来展示，因为在内存中实际创建对话框模板的细节非常复杂。让我们把yacc语法中的dialog部分改为这样（同样，我省略了%token定义以节省空间——假设大写的就是标记）。
dialog : L_ID L_DIALOG
{
gDlgTemplate = new DLGTEMPLATE;
gDlgID = $1;
}
L_NUM ',' L_NUM ',' L_NUM ',' L_NUM
L_STYLE styles caption L_FONT L_NUM ','L_STRING
L_BEGIN controls L_END
;
我们引入了一些新东西。假设我们有一个名为gDlgTemplate的全局变量，它指向一个DLGTEMPLATE结构。一旦我们识别出这是一个对话框模板，我们就创建一个DLGTEMPLATE结构的新实例。然后我们将与L_ID相关联的值赋给一个名为gDlgID的全局整数。
顺带一提，$1指的是右侧的第一个标记。标记从左到右计数，并包括包含在匹配大括号内的动作代码块，因此L_ID是$1，L_DIALOG是$2，动作代码是$3，依此类推……
但是等等！我们之前不是说L_ID是一个字符串吗？是的，它是。但是你已经知道L_ID是在resource.h中定义的符号，并在你的代码中用作数字的方便占位符。那么，我们如何解析一个可能包含数字或符号作为ID的对话框模板呢？我们可以这样做……
dialog : L_ID L_DIALOG
{
gDlgTemplate = new DLGTEMPLATE;
gDlgID = FindSymbol($1);
}
L_NUM ',' L_NUM ',' L_NUM ',' L_NUM
L_STYLE styles caption L_FONT L_NUM ',' L_STRING
L_BEGIN controls L_END
| L_NUM L_DIALOG
{
gDlgTemplate = new DLGTEMPLATE;
gDlgID = $1;
}
L_NUM ',' L_NUM ',' L_NUM ',' L_NUM
L_STYLE styles caption L_FONT L_NUM ',' L_STRING
L_BEGIN controls L_END
;
我们重复语法，一次是为了对话框模板包含ID的情况，另一次是为了对话框模板包含数字的情况。在第一种情况下，我们获取与L_ID标记相关联的数据（实际的标识符文本），并在某个地方定义的符号表中查找它。在第二种情况下，我们已经有了数字，所以我们直接赋值。
这个重复的语法片段会起作用，但不是最好的方法。无论哪种情况，我们都希望第一个标记求值为一个数字。它是一个直接嵌入在对话框资源模板中的数字，还是一个指向别处定义的符号的字符串，这并不重要——我们想要的是一个数字。我们可以替换一个子语法来实现这一点。
dialog : nameID L_DIALOG
{
gDlgTemplate = new DLGTEMPLATE;
gDlgID = $1;
}
L_NUM ',' L_NUM ',' L_NUM ',' L_NUM
L_STYLE styles caption L_FONT L_NUM ',' L_STRING
L_BEGIN controls L_END
;
nameID : L_NUM
{
$$ = $1;
}
| L_ID
{
$$ = FindSymbol($1);
}
;
我们添加了一个新的非终结符符号nameID，它被定义为L_ID或L_NUM。
如果nameID是一个数字（第一条路径），我们将它的值（$1）赋给$$。如果它是L_ID（第二条路径），我们在某个地方查找它的值并将其赋给$$。无论哪种情况，$$都是nameID的值。在任何一种情况下，$1都是词法分析器（标记器）返回的与标记相关联的值。也就是说，如果词法分析器看到了一个数字，它就将该数字作为值赋给并返回L_NUM作为标记。如果相反，词法分析器看到了L_ID，它就将L_ID的文本作为值赋给并返回L_ID作为标记类型。
解析器如何知道nameID规则应该返回一个数字？在语法的%token部分，我们通过%type声明告诉解析器nameID规则有一个数字值，这与我们告诉解析器L_NUM是一个数字的方式完全相同。
%type <numVal> L_NUM nameID
换句话说，%type关键字可以为标记（终结符符号）和非终结符符号分配数据类型。并非所有标记或非终结符符号都需要数据类型，只有那些实际具有与之关联的数据的才需要。
Yacc和Lex 108
不可避免地，你的解析器会遇到错误。我们已经看了对话框资源的结构，知道第一个元素是一个数字ID。假设你正在读取的对话框模板在第一个L_NUM后缺少一个逗号
IDD_WHISPERWINDOW DIALOG 0 0, 261, 146
语法已经解析了IDD_WHISPERWINDOW，DIALOG和0，然后遇到了另一个L_NUM标记。不幸的是，这与预期的输入不匹配。解析器此时期望看到一个逗号。所以解析器检查任何其他可以匹配到目前为止我们看到的内容的规则，但没有找到。错误！
dialog : L_ID L_DIALOG L_NUM ',' L_NUM ',' L_NUM ',' L_NUM
我们可以通过重新定义语法的开始来解决这种情况。与其假设我们只查找匹配dialog规则的输入流，不如查找一个有效的对话框模板，或者允许对输入错误进行优雅处理。现在我们的开始条件看起来是这样的。
start : dialog
| error L_END { yyerrok(); }
;
error是一个预定义的具有特殊含义的标记。每当解析器遇到无法处理的输入时，它就会进入错误状态，并查找包含error标记的规则。解析器还为错误状态附加了一些其他含义。具体来说，它会查找错误符号后面的标记，并丢弃所有其他输入，直到它看到与终止错误条件相匹配的标记。当它看到那个标记时，它就匹配规则并执行与该规则相关的动作。在这种情况下，它只是调用yyerrok()函数并继续。yyerrok所做的只是将解析器重置为“正常”输入模式，并让它继续尝试解析输入，而不是简单地丢弃标记。在实际应用中，你可能希望错误规则做一些更有用的事情，比如通知用户找到了一个错误。
Yacc和Lex 109
好吧，这是简单的错误处理——由意外或无效输入引起的错误。一类更难处理的错误来自模糊的语法。
Yacc实现的是所谓的LALR(1)语法。这意味着它会向前看以查看即将到来的内容。(1)表示它使用一个单标记的向前看。
因此，如果你的语法足够简单，解析器总能根据它已经看到的内容加上一个向前看的标记来决定做什么，那么你的语法就可以始终无歧义地解析。不幸的是，许多有用的语法是模糊的，这给解析器带来了问题——如果在它已经看到的内容加上一个向前看的标记的基础上，它有两个或多个同样有效的分支可供选择，那么解析器必须有其他方式来决定。Yacc通过应用语法文件中出现的第一个规则来解决这个问题。
当yacc在语法中遇到这种歧义时，它会输出一条错误消息警告你。通常你需要仔细检查错误消息和有问题的行，并手动找出解析器在歧义情况下实际会做什么。大多数yacc实现还可以生成一个详细的输出文件，该文件详细显示了解析器在任何给定点的行为。然而，对这些文件的解释超出了本教程的范围。
参考文献
http://www.monmouth.com/~wstreett/lex-yacc/lex-yacc.html 我发现这是对lex/yacc（实际上是flex/bison）最普遍有用的参考。
http://www.eng.usyd.edu.au/tutorial/course1/cplusplus15.html#l188 介绍了flex++和bison++，它们是词法分析器和解析器生成器，可以创建c++类。
工具
网上有很多免费或其他的flex和bison实现可供下载。总的来说，我发现它们使用起来非常麻烦。即使你能找到针对win32平台的编译二进制文件，生成的代码对我来说也几乎是无法阅读的。更糟糕的是，通常的实现使用一个骨架文件，yacc和lex将代码片段和生成的表插入其中。这些骨架文件来自UNIX世界，通常包含#ifdef thismachine #else thatmachine的代码。经常，编译yacc/lex输出文件成功所需的时间比编写语法本身的时间还要长。
最终，我放弃了与免费下载的斗争，花了60美元从http://www.bumblebeesoftware.com/ 获得了一个Pargen的许可证。嗯——如果你购买许可证，我不会因此更富有。