lex和yacc入门（第二部分）
4.88/5 (23投票s)
使用lex和yacc为项目创建解析器。
引言
在本系列文章的第一部分中，我讨论了使用 lex 创建词法分析器（标记识别器）和 yacc 创建解析器的基本知识。在本系列的第二部分，我将介绍如何使用这些工具来创建能够读取 Visual Studio 6 资源文件的解析器。第二部分（本文）将重点关注词法分析器。
然而，考虑到这两种工具之间紧密的联系，有必要在解析器和词法分析器之间来回切换。
项目下载文件中包含词法分析器和解析器的源代码。
Lex 201
正如在第一篇文章中所讨论的，词法分析器负责从某个地方读取输入流并将其分解为标记流。每个标记代表一个最低级别的构建块，表示字符串、数字或关键字等内容。词法分析器通过将输入数据与一组正则表达式（规则）进行匹配来实现这一点。当它找到与特定规则的匹配时，它会执行程序员编写的一些操作代码，然后向解析器返回一个标记，指示匹配了哪个规则。它还可能返回与该规则相关联的一些数据。例如，正则表达式
/* Decimal numbers */
-?[0-9]+ {
yylval.ival = atoi(yytext);
return NUMBER;
}
匹配由一个或多个十进制数字组成，并且可以选择性地前面有一个减号的序列。（关于正则表达式的格式和含义的讨论，请参阅 http://www.monmouth.com/~wstreett/lex-yacc/flex_1.html 并搜索“Patterns”）。当它看到匹配时，它会调用 atoi，并将字符串 yytext 传递给它，而 yytext 恰好是匹配该规则的文本字符串。atoi 的返回值又被赋值给解析器定义的 yylval 联合体的 ival 成员。然后，操作返回 NUMBER 标记给解析器并终止。与大多数正则表达式匹配器一样，lex 是“贪婪”的。它会尝试匹配尽可能长的输入字符串到规则。当然，这正是你所期望的。给定数字输入 123，你希望它匹配 123，只返回一个 NUMBER 标记，而不是返回一个 1、一个 2、一个 3，分别返回三个 NUMBER 标记，每个数字一个。但有时这会带来问题。假设你尝试编写一个规则来识别如下的字符串
/* Strings */
\".*"\" {
yylval.pcs = new CString(yytext);
return STRING;
}
你说，当 lexer 看到一个双引号时，它应该消耗所有输入（.*），直到看到一个闭合的双引号。它也会这样做。不幸的是，它也会愉快地消耗双引号字符，直到遇到输入中的最后一个。 “贪婪”算法确保了这一点。这时，你可能会想尝试编写一个更复杂的正则表达式来考虑这一点。也许是这样的
/* Strings */
\"[^"]*\" {
yylval.pcs = new CString(yytext);
return STRING;
}
此规则将在开头的双引号后的第一个双引号处停止。但它无法让你嵌入转义的双引号。在某个时候，你必须决定你的正则表达式要多复杂，或者是否编写一些 c/c++ 代码来帮助 lexer 会更简单（且更易于维护）。不要忘记，你可能在六个月后还在看这些正则表达式。我选择了后一种方法。所以我的字符串匹配器看起来是这样的
/* Strings */
\" {
/* Seen start of a string */
int ch;
BOOL bExit = FALSE;
yylval.pcs = new CString;
while (!bExit && (ch = yyinput()))
{
switch (ch)
{
case '\\':
switch (ch = yyinput())
{
case 'r':
ch = '\r';
break;
case 'n':
ch = '\n';
break;
case 't':
ch = '\t';
break;
}
break;
case '"':
bExit = TRUE;
continue;
}
*yylval.pcs += ch;
}
return STRING;
}
这种正则表达式和过程代码的组合巧妙地解决了“贪婪”问题，并允许将转义序列转换为它们所代表的字符。yyinput() 函数只是从输入流中获取下一个字符供 lex 使用。Lex 202
Visual Studio 6 资源脚本使用大量的关键字和看起来像关键字的项。有DIALOG 和 MENU 等关键字，然后有 WS_TABSTOP 或 WS_BORDER 等窗口样式，它们也看起来像关键字。我的 lext 脚本的第一个草稿是为了解析一个非常简单的 DIALOG 模板，其中只有一个或两个窗口样式。为每个窗口样式编写一个正则表达式并为每个窗口样式返回一个标记，这是有意义的（而且快速而粗糙）。
在解析器基础工作后，我开始从其他项目中复制粘贴其他 DIALOG 模板到我的测试文件中。每添加一个新模板，我都会注意到解析器遇到的错误，并为新的窗口样式向 lex 添加另一个规则。它开始看起来像这样
WS_TABSTOP { return L_WS_TABSTOP; }
WS_BORDER { return L_WS_BORDER; }
.
.
.
TCS_OWNERDRAWFIXED { return L_TCS_OWNERDRAWFIXED; }
TCS_RAGGEDRIGHT { return L_TCS_RAGGEDRIGHT; }
TCS_RIGHT { return L_TCS_RIGHT; }
TCS_RIGHTJUSTIFY { return L_TCS_RIGHTJUSTIFY
.
.
.
// more styles...
你数过各种 Platform SDK 头文件中定义的窗口样式有多少吗？我数了大约有 225 个窗口样式，另外还有大约 40 个扩展样式。这总共需要大约 265 个正则表达式，仅用于处理窗口和扩展窗口样式。
除了在这里定义的样式外，我还必须在解析器源文件中为每个样式定义一个标记，并添加另一个解析器规则来处理该标记。所有这些加起来都是大量的复制粘贴，并且很快就变成了一个维护噩梦（更不用说因为频繁的鼠标操作而导致的腕管综合征）。
这时我意识到，窗口样式看起来与标识符完全一样。我已经有一个规则在 lexer 中识别标识符（如 IDOK 和 IDCANCEL）。
// Identifiers
[[:alpha:]_][[:alnum:]_]* {
yylval.pcs = new CString(yytext);
return IDENTIFIER;
}
因此，定义两个静态窗口样式表（一个用于常规样式，一个用于扩展样式），然后动态地构建映射来关联窗口样式的名称和值，这并不是一个很大的步骤。完成之后，我将标识符规则修改为如下：// Identifiers
[[:alpha:]_][[:alnum:]_]* {
DWORD data;
// Check if it's actually a predefined style or extended
// style.
if (m_styleMap.Lookup(yytext, data))
{
yylval.dval = data;
return STYLE;
}
else if (m_extStyleMap.Lookup(yytext, data))
{
yylval.dval = data;
return EXTENDEDSTYLE;
}
// Nope, none of the above, so return the string and
// let the parser sort it out...
yylval.pcs = new CString(yytext);
return IDENTIFIER;
}
这给我带来了几点好处。首先，解析器本身得到了简化。它不再需要 265 个标记，而是只需要 2 个标记：一个用于 STYLE，一个用于 EXTENDEDSTYLE，其中确切的样式作为与标记相关联的数据传递。我可以根据需要添加新的窗口样式（或当我意识到它们的存在时），只需将它们添加到静态表中，而无需对解析器源文件进行任何更改。顺便说一句，我出于性能原因使用了动态创建的映射（在创建 lexer 时创建）。虽然在当今的超级奔腾处理器上，对 265 个条目表的线性搜索可能不会花费太长时间，但在解析典型资源脚本时，时间确实会累加，而且无论如何，都没有理由编写效率低下的代码。
此更改还将 lex 处理源文件并创建输出 c++ 文件所需的时间从大约 20 秒缩短到不到 1 秒。我的时间也很重要。
第三，此更改将 lex 生成的文件大小从 12000 多行缩减到大约 2000 行。这对编译时间和编译后可执行文件的大小都产生了显著影响。
最后，词法分析器本身在运行时也显著加快了速度。
Lex 203
此解析器的全部目的是解析 Visual Studio 6 资源脚本中的对话模板。我想让我的解析器能够处理 AppStudio 创建和维护的 .rc 文件，而无需进行任何其他处理。这意味着它必须能够处理 AppStudio 编辑的任何数据结构。另一方面，我的项目对MENU、TOOLBAR、STRINGTABLE 或 .rc 文件中存在的许多其他内容不特别感兴趣。为了避免编写能够处理资源脚本中所有内容的解析器规则，我使用了 lex 的一项功能，该功能允许我们在 lex 脚本中创建子词法分析器。
当词法分析器开始运行时，它处于所谓的 INITIAL 状态。然而，它可以在任何时候切换到另一个状态，从而遵循不同的规则集。例如。
%exclusive comment
%% // End of first section of the lext script
// Lex rules start...
"/*" BEGIN comment;
<comment>"*/" BEGIN INITIAL;
<comment>. |
<comment>\n { ; }
这组简单的规则允许词法分析器在看到 /* 序列时切换到 comment 状态。一旦进入 comment 状态，它将匹配所有以 <comment> 为前缀的规则。起始状态可以是排他的，也可以是非排他的。如果是排他的，则使用 %exclusive 关键字；否则，在 lex 脚本的第一部分使用 %start 关键字。当使用排他起始状态时，输入只会与为该状态定义的规则进行匹配。非排他状态将输入与没有 <state> 前缀的规则以及与相应起始状态相关的规则进行匹配。在前面的代码片段中，如果词法分析器处于 INITIAL 状态并且看到 /* 序列，它会匹配该规则并执行操作。此操作将词法分析器状态更改为 comment 并继续读取输入。然而，现在词法分析器只考虑以 <comment> 开头的规则（因为我们将 comment 状态声明为排他的）。如果输入不是 */，则输入将被丢弃。但是，当词法分析器输入包含 */ 时，它会匹配该规则，词法分析器会切换回 INITIAL 状态。显而易见！但请注意，comment 状态中的任何操作都不会返回任何内容给解析器。由于它们不向解析器返回任何标记，因此解析器看不到注释开始和结束之间的任何内容。对于解析器来说，注释有效地从输入流中消失了。
如果我们能让注释从输入中消失，还有什么能消失呢？那么在 #ifdef 块中，当符号未定义时，代码会怎么样？这有点难做到，因为代码决定 #ifdef 条件是否满足，这应该由解析器来完成。但也不是那么难。考虑解析器中的这段代码片段。
ifdef : L_IFDEF IDENTIFIER
{
if (!m_symbols.IsDefined(*$2))
{
LEXER->m_ifNesting++;
LEXER->yybegin(ifnest);
}
delete $2;
}
;
在这里，解析器看到 #ifdef 的标记和一个 IDENTIFIER。它检查 IDENTIFIER 是否在它的符号表中，如果不在，它会将词法分析器移入 ifnest 状态。它还会增加词法分析器中的 m_ifNesting 计数器。现在看看 lexer 中 ifnest 状态的规则。// Rules when inside #ifdef nesting. Basically ignore everything until
// we've closed the outer #ifdef with an #endif. This does require us to
// count #ifdefs inside the block even when the condition wasn't met.
// Note that we're only in this state if the #if/#ifdef/#ifndef condition
// wasn't
// met
<ifnest>#ifdef |
<ifnest>#if |
<ifnest>#ifndef { m_ifNesting++; }
<ifnest>#endif {
m_ifNesting--;
if (m_ifNesting == 0)
BEGIN INITIAL;
}
<ifnest>. |
<ifnest>\n { ; }
首先，ifnest 状态被声明为排他的。其次，ifnest 状态需要计算它忽略了多少个 #if(def) 语句。这是为了能够处理例如#if !defined(AFX_RESOURCE_DLL) || defined(AFX_TARG_ENU)
#ifdef _WIN32
LANGUAGE 9, 1
#pragma code_page(1252)
#endif //_WIN32
#include "res\Prober.rc2" // non-Microsoft Visual C++ edited resources
#include "afxres.rc" // Standard components
#endif
其中，如果第一个 #if 失败，它将一直保持在 ifnest 状态，直到遇到最后一个 #endif 语句（位于 #include "afxres.rc" 语句之后）。这些构造的净效应是，一旦解析器确定它对某个输入流不感兴趣，它就会将忽略直到达到指定状态的所有后续输入的责任交给词法分析器。一旦责任移交，解析器在达到结束状态之前就不会看到任何标记。
我使用相同的方法来允许解析器忽略资源脚本中的 MENU 语句等内容。解析器依赖于 MENU 语句由一个 IDENTIFIER、然后是 MENU 关键字、然后是一些内容、然后是 BEGIN 关键字，然后是更多内容，最后以 END 关键字结束的知识。在 MENU 语句中可能嵌套 BEGIN/END 块。通过计算 BEGIN 和 END 关键字对，我们可以确定 MENU 语句何时结束。
资源文件中的许多其他构造也遵循类似的模式，并以相同的方式被忽略。
Lex 204
资源脚本文件使用#include 语句在 #include 语句出现的地方包含另一个文件的内容。实现此功能需要一点技巧（以及对 lexer 获取输入的精确方法的了解）。很容易确定 lexer 调用某个函数来获取其输入。通常，该输入来自文件，因此您需要将该文件句柄存储在某处，替换一个新句柄，然后返回给 lexer。然后，当 lexer 在新替换的文件句柄上遇到文件结尾时，您关闭该文件并恢复原始文件句柄。这就是理论。具体如何操作取决于您使用的 lexer。我将 Pargen（见下文说明）用作我的 lexer，所以我这样做了。首先，解析器需要识别有一个 #include 语句需要处理。include : L_INCLUDE STRING
{
DoInclude(*$2);
delete $2;
}
| L_INCLUDE BRACESTRING
{
DoInclude(*$2);
delete $2;
}
;
BRACESTRING 是一个识别文件名形式为 <filename.ext> 的标记。DoInclude() 的作用是void YYPARSERNAME::DoInclude(LPCTSTR szFileName)
{
ASSERTSTRING(szFileName);
#ifdef NDEBUG
try
#endif
{
FILE *f = fopen(szFileName, "rb");
if (f != (FILE *) NULL)
{
if (yydebug)
TRACE("#including '%s'\n", szFileName);
sInclude *include = new sInclude;
include->file = LEXER->yyin;
include->line = LEXER->yylineno;
LEXER->m_csCurrentFile = include->m_csFileName = szFileName;
m_includeStack.AddHead(include);
LEXER->yyin = f;
LEXER->yylineno = 0;
LEXER->yyreset();
}
}
#ifdef NDEBUG
catch(...)
{
CString csMessage;
csMessage.Format(_T("Error processing %s\nin #include"), szFileName);
AfxMessageBox(csMessage, MB_OK);
}
#endif
}
如果这段代码成功打开文件，它会分配一个新的 sInclude 结构，并保存 lexer 的 yyin 成员中存储的现有输入文件句柄。它还会保存当前行号和文件名。然后，它将新文件句柄替换为 lexer 中的现有句柄，将行号重置为零（您希望错误报告显示当前文件的正确行号），并重置 lexer。我们还将 sInclude 结构添加到堆栈中。然后返回到正常解析。注意我说是如果这段代码成功打开文件。这里没有包含路径逻辑。就我的项目而言，我对 Microsoft 提供的目录中定义的符号或对话模板不感兴趣。因此，如果尝试 #include 文件失败，我不会认为这是一个错误——我只会忽略这种情况，并在下一行继续解析。
在 lexer 中，我们继续像往常一样读取输入。最终，lexer 会遇到文件结尾，并调用 yywrap() 函数。
int YYLEXERNAME::yywrap()
{
// We get here when EOF on the current input file is reached. This
// code checks the parser include stack and pops the previous file
// (the one that included the file that's just hit EOF) off. It then
// resets the line number back to the new current file and continues
// reading input from the previous file.
sInclude *include;
if (!PARSER->m_includeStack.IsEmpty())
{
fclose(yyin);
include = (sInclude *) PARSER->m_includeStack.RemoveHead();
if (PARSER->yydebug)
TRACE("Popping parser include stack '%s'\n",
include->m_csFileName);
yyin = include->file;
yylineno = include->line;
m_csCurrentFile = include->m_csFileName;
delete include;
// Keep on lexing...
return 0;
}
// No more input from anywhere, tell the lexer so...
return 1;
}
这对于我们简单的解析器来说效果很好。对于更复杂的解析器，它可能无法正常工作。问题在于，lexer 可能需要很远的向前查找才能确定匹配哪个规则，并且如果它无法匹配某个规则，可能还需要很远的向后回溯。如果您的语法要求 lexer 在文件边界执行此操作，则此技术将不起作用。幸运的是，资源文件足够简单，不太可能出现这种情况。关于示例文件的说明
该项目是使用 http://www.bumblebeesoftware.com 的 Parser Generator 开发的，它提供了 lex 和 yacc（实际上称为 alex 和 ayacc）的版本，可以生成 c++ 类。我不期望经典的 lex 和 yacc 或 flex 和 bison 或 flex++ 或 bison++ 能够编译源文件。但是，Bumble-bee Software 提供 Parser Generator 的 30 天试用版（我在这 30 天的大部分时间里都用于开发和调整此项目）。我非常喜欢它，以至于认为 60 美元的许可证非常划算。我还重建了 Bumble-Bee 提供的库，使用经典的 c 风格 FILE 指针而不是 c++ iostreams。您不必关心我这样做，除了实现 #include 的代码使用了 FILE 指针。如果您尝试使用 Parser Generator 重新构建我的项目文件，您需要将我的代码更改为使用 c++ iostreams，或者重建他们的库以使用 FILE 指针。
文件包括我编写了解析器的项目的第一个草稿。它目前只有最基本的功能。要尝试代码，请打开一个新项目并选择一个 .rc 文件。它应该解析脚本并显示对话框列表。双击对话框名称应该会启动该对话框。
正如下面的第一个评论中所指出的——该项目无法编译。好吧，实际上是可以编译的，但我没有想到指出，除了使用通过 Parser Generator alex 和 ayacc 传递的文件外，它还链接了 Parser Generator 提供的样板库和头文件。我没有分发这些文件的许可，因此它们不包含在内。您可以从上面的链接下载并安装 Parser Generator 的评估版本来获取您自己的副本。