优化 flex 字符串文字解析
Optimizing flex string literal parsing
我开始为我的编程语言编写词法分析器。
此语言中的字符串文字以 " 开头，并在遇到未转义的 " 时结束。内部的所有内容（包括换行符）都被保留，除了转义序列（通常的 \ns、\ts、\"s 等加上使用其 ASCII 代码转义字符的方法，例如7 或 </code>).</p>
<p>这是我到目前为止编写的代码：</p>
<pre><code>%{
#include <iostream>
#define YY_DECL extern "C" int yylex()
std::string buffstr;
%}
%x SSTATE
%%
\" {
buffstr.clear();
BEGIN(SSTATE);
}
<SSTATE>\[0-9]{1,3} {
unsigned code = atoi(yytext + 1);
if (code > 255) {
std::cerr << "SyntaxError: decimal escape sequence larger than 255 (" << code << ')' << std::endl;
exit(1);
}
buffstr += code;
}
<SSTATE>\a buffstr += '\a';
<SSTATE>\b buffstr += '\b';
<SSTATE>\f buffstr += '\f';
<SSTATE>\n buffstr += '\n';
<SSTATE>\r buffstr += '\r';
<SSTATE>\t buffstr += '\t';
<SSTATE>\v buffstr += '\v';
<SSTATE>\\ buffstr += '\';
<SSTATE>\\" buffstr += '\"';
<SSTATE>\. {
std::cerr << "SyntaxError: invalid escape sequence (" << yytext << ')' << std::endl;
exit(1);
}
<SSTATE>\" {
std::cout << "Found a string: " << buffstr << std::endl;
BEGIN(INITIAL);
}
<SSTATE>. buffstr += yytext[0];
. ;
%%
int main(int argc, char** argv) {
yylex();
}
它运行完美，但如您所见，它并没有特别优化。
它为正在解析的字符串文字中的每个字符将一个字符附加到 std::string 一次，这并不理想。
我想知道是否有更好的方法，例如存储指针并增加长度，然后使用 std::string(const char* ptr, size_t lenght).
构建字符串
有吗？会是什么？
可能的情况是，所提供的代码对于所有实际用途而言都足够快，并且在您实际观察到它成为瓶颈之前，您不应该担心优化它。词法扫描，即使是低效的扫描，也很少对编译时间做出重要贡献。
但是，一些优化是straight-forward。
最简单的方法是观察大多数字符串不包含转义序列。因此，应用通常的 low-lying 水果优化技术，我们首先在一个模式中处理没有转义序列的字符串，甚至不通过单独的词法状态。 [注1]
\"[^"\]*\" { yylval.str = new std::string(yytext + 1, yyleng - 2);
return T_STRING;
}
(F)lex 提供 yyleng，这是它找到的标记的长度，因此从来没有任何理由用 strlen 重新计算长度。在这种情况下，我们不希望字符串中包含双引号，因此我们从第二个字符开始 select yyleng - 2 个字符。
当然，我们需要处理转义码；我们可以使用类似于您的开始条件来执行此操作。当我们在字符串文字中找到转义字符时，我们只会进入这个开始条件。 [注 2] 为了捕捉这种情况，我们依赖于 (f)lex 实现的 maximal munch 规则，即具有最长匹配的模式击败任何其他恰好匹配的模式在相同的输入点匹配。 [注意 3] 由于我们已经匹配了任何以 " 开头且在结束 " 之前不包含反斜杠的标记，我们可以添加一个没有结束引号的非常相似的模式，它只会在第一条规则不匹配的情况下匹配，因为与结束引号的匹配要长一个字符。
\"[^"\]* { yylval.str = new std::string(yytext + 1, yyleng - 1);
BEGIN(S_STRING);
/* No return, so the scanner will continue in the new state */
}
在S_STRING状态下，我们仍然可以匹配不包含反斜杠的序列（不仅仅是单个字符），从而显着减少动作执行和字符串追加的次数：
（开始条件中的支撑模式列表是 flex extension。）
<S_STRING>{
[^"\]+ { yylval.str->append(yytext, yyleng); }
\n { (*yylval.str) += '\n'; }
/* Etc. Handle other escape sequences similarly */
\. { (*yylval.str) += yytext[1]; }
\\n { /* A backslash at the end of the line. Do nothing */ }
\" { BEGIN(INITIAL); return T_STRING; }
/* See below */
}
当我们最终找到一个未转义的double-quote，它将匹配最后一个模式时，我们首先重置词法状态，然后return已经完全构造的字符串。
模式 \\n 实际上匹配行末尾的反斜杠。完全忽略这个反斜杠和换行符是很常见的，以允许长字符串在多个源代码行上继续。如果您不想提供此功能，只需将 \. 模式更改为 \(.|\n).
如果我们没有找到未转义的 double-quote 怎么办？也就是说，如果不小心省略了结束双引号怎么办？在这种情况下，我们将以 S_STRING 开始条件结束，因为字符串没有以引号结尾，因此回退模式将匹配。在 S_STRING 模式中，我们需要添加两种可能性：
<S_STRING>{
// ... As above
<<EOF>> |
\ { /* Signal a lexical error */ }
}
这些规则中的第一个捕获简单的未终止字符串错误。第二个捕获反斜杠后面没有跟合法字符的情况，考虑到其他规则，只有反斜杠是程序中具有未终止字符串的最后一个字符时才会发生这种情况。虽然不太可能，但它可能会发生，所以我们应该抓住它。
进一步的优化相对简单，但我不推荐它，因为它主要只是使代码复杂化，而且好处是无穷小的。 （正是出于这个原因，我没有包含任何示例代码。）
在开始条件下，反斜杠（几乎）总是导致将单个字符附加到我们正在累积的字符串中，这意味着我们可能会调整字符串的大小以执行此附加操作，即使我们只是调整了大小它附加 non-escaped 个字符。相反，我们可以在与 non-escape 字符匹配的操作中向字符串添加一个额外的字符。 （因为 (f)lex 将输入缓冲区修改为 NUL-terminate 标记，标记后面的字符将始终为 NUL，因此将追加的长度增加 1 会将此 NUL 而不是反斜杠插入到字符串中.不过那不重要。)
然后处理转义字符的代码需要替换字符串中的最后一个字符，而不是将单个字符附加到字符串，从而避免一次追加调用。当然，在我们不想插入任何东西的情况下，我们需要将字符串的大小减少一个字符，如果有一个转义序列（例如unicode转义）增加一个以上的字节到字符串，我们需要做一些其他的杂技。
简而言之，我认为这是一种破解而非优化。但不管怎样，我以前也做过这样的事情，所以我也不得不承认过早优化的指控。
备注
你的代码只打印出令牌，这让人很难知道你将字符串传递给 p 的设计是什么浏览器。我在这里假设一个或多或少的标准策略，其中语义值 yylval 是一个联合，其成员之一是 std::string* (not a std::string).我没有解决由此产生的内存管理问题，但是 %destruct 声明会有很大帮助。
在此答案的原始版本中，我建议通过使用与反斜杠匹配的模式作为尾随上下文来捕捉这种情况：
\"[^"\]*/\ { yylval.str = new std::string(yytext + 1, yyleng - 1);
BEGIN(S_STRING);
/* No return, so the scanner will continue in the new state */
}
但是使用最大咀嚼规则更简单也更通用。
如果多个模式具有相同的最长匹配，则扫描仪描述中的第一个模式获胜。
我开始为我的编程语言编写词法分析器。
此语言中的字符串文字以 " 开头，并在遇到未转义的 " 时结束。内部的所有内容（包括换行符）都被保留，除了转义序列（通常的 \ns、\ts、\"s 等加上使用其 ASCII 代码转义字符的方法，例如7 或 </code>).</p>
<p>这是我到目前为止编写的代码：</p>
<pre><code>%{
#include <iostream>
#define YY_DECL extern "C" int yylex()
std::string buffstr;
%}
%x SSTATE
%%
\" {
buffstr.clear();
BEGIN(SSTATE);
}
<SSTATE>\[0-9]{1,3} {
unsigned code = atoi(yytext + 1);
if (code > 255) {
std::cerr << "SyntaxError: decimal escape sequence larger than 255 (" << code << ')' << std::endl;
exit(1);
}
buffstr += code;
}
<SSTATE>\a buffstr += '\a';
<SSTATE>\b buffstr += '\b';
<SSTATE>\f buffstr += '\f';
<SSTATE>\n buffstr += '\n';
<SSTATE>\r buffstr += '\r';
<SSTATE>\t buffstr += '\t';
<SSTATE>\v buffstr += '\v';
<SSTATE>\\ buffstr += '\';
<SSTATE>\\" buffstr += '\"';
<SSTATE>\. {
std::cerr << "SyntaxError: invalid escape sequence (" << yytext << ')' << std::endl;
exit(1);
}
<SSTATE>\" {
std::cout << "Found a string: " << buffstr << std::endl;
BEGIN(INITIAL);
}
<SSTATE>. buffstr += yytext[0];
. ;
%%
int main(int argc, char** argv) {
yylex();
}
它运行完美，但如您所见，它并没有特别优化。
它为正在解析的字符串文字中的每个字符将一个字符附加到 std::string 一次，这并不理想。
我想知道是否有更好的方法，例如存储指针并增加长度，然后使用 std::string(const char* ptr, size_t lenght).
有吗？会是什么？
可能的情况是，所提供的代码对于所有实际用途而言都足够快，并且在您实际观察到它成为瓶颈之前，您不应该担心优化它。词法扫描，即使是低效的扫描，也很少对编译时间做出重要贡献。
但是，一些优化是straight-forward。
最简单的方法是观察大多数字符串不包含转义序列。因此，应用通常的 low-lying 水果优化技术，我们首先在一个模式中处理没有转义序列的字符串，甚至不通过单独的词法状态。 [注1]
\"[^"\]*\" { yylval.str = new std::string(yytext + 1, yyleng - 2);
return T_STRING;
}
(F)lex 提供 yyleng，这是它找到的标记的长度，因此从来没有任何理由用 strlen 重新计算长度。在这种情况下，我们不希望字符串中包含双引号，因此我们从第二个字符开始 select yyleng - 2 个字符。
当然，我们需要处理转义码；我们可以使用类似于您的开始条件来执行此操作。当我们在字符串文字中找到转义字符时，我们只会进入这个开始条件。 [注 2] 为了捕捉这种情况，我们依赖于 (f)lex 实现的 maximal munch 规则，即具有最长匹配的模式击败任何其他恰好匹配的模式在相同的输入点匹配。 [注意 3] 由于我们已经匹配了任何以 " 开头且在结束 " 之前不包含反斜杠的标记，我们可以添加一个没有结束引号的非常相似的模式，它只会在第一条规则不匹配的情况下匹配，因为与结束引号的匹配要长一个字符。
\"[^"\]* { yylval.str = new std::string(yytext + 1, yyleng - 1);
BEGIN(S_STRING);
/* No return, so the scanner will continue in the new state */
}
在S_STRING状态下，我们仍然可以匹配不包含反斜杠的序列（不仅仅是单个字符），从而显着减少动作执行和字符串追加的次数：
（开始条件中的支撑模式列表是 flex extension。）
<S_STRING>{
[^"\]+ { yylval.str->append(yytext, yyleng); }
\n { (*yylval.str) += '\n'; }
/* Etc. Handle other escape sequences similarly */
\. { (*yylval.str) += yytext[1]; }
\\n { /* A backslash at the end of the line. Do nothing */ }
\" { BEGIN(INITIAL); return T_STRING; }
/* See below */
}
当我们最终找到一个未转义的double-quote，它将匹配最后一个模式时，我们首先重置词法状态，然后return已经完全构造的字符串。
模式 \\n 实际上匹配行末尾的反斜杠。完全忽略这个反斜杠和换行符是很常见的，以允许长字符串在多个源代码行上继续。如果您不想提供此功能，只需将 \. 模式更改为 \(.|\n).
如果我们没有找到未转义的 double-quote 怎么办？也就是说，如果不小心省略了结束双引号怎么办？在这种情况下，我们将以 S_STRING 开始条件结束，因为字符串没有以引号结尾，因此回退模式将匹配。在 S_STRING 模式中，我们需要添加两种可能性：
<S_STRING>{
// ... As above
<<EOF>> |
\ { /* Signal a lexical error */ }
}
这些规则中的第一个捕获简单的未终止字符串错误。第二个捕获反斜杠后面没有跟合法字符的情况，考虑到其他规则，只有反斜杠是程序中具有未终止字符串的最后一个字符时才会发生这种情况。虽然不太可能，但它可能会发生，所以我们应该抓住它。
进一步的优化相对简单，但我不推荐它，因为它主要只是使代码复杂化，而且好处是无穷小的。 （正是出于这个原因，我没有包含任何示例代码。）
在开始条件下，反斜杠（几乎）总是导致将单个字符附加到我们正在累积的字符串中，这意味着我们可能会调整字符串的大小以执行此附加操作，即使我们只是调整了大小它附加 non-escaped 个字符。相反，我们可以在与 non-escape 字符匹配的操作中向字符串添加一个额外的字符。 （因为 (f)lex 将输入缓冲区修改为 NUL-terminate 标记，标记后面的字符将始终为 NUL，因此将追加的长度增加 1 会将此 NUL 而不是反斜杠插入到字符串中.不过那不重要。)
然后处理转义字符的代码需要替换字符串中的最后一个字符，而不是将单个字符附加到字符串，从而避免一次追加调用。当然，在我们不想插入任何东西的情况下，我们需要将字符串的大小减少一个字符，如果有一个转义序列（例如unicode转义）增加一个以上的字节到字符串，我们需要做一些其他的杂技。
简而言之，我认为这是一种破解而非优化。但不管怎样，我以前也做过这样的事情，所以我也不得不承认过早优化的指控。
备注
你的代码只打印出令牌，这让人很难知道你将字符串传递给 p 的设计是什么浏览器。我在这里假设一个或多或少的标准策略，其中语义值
yylval是一个联合，其成员之一是std::string*(not astd::string).我没有解决由此产生的内存管理问题，但是%destruct声明会有很大帮助。在此答案的原始版本中，我建议通过使用与反斜杠匹配的模式作为尾随上下文来捕捉这种情况：
\"[^"\]*/\ { yylval.str = new std::string(yytext + 1, yyleng - 1); BEGIN(S_STRING); /* No return, so the scanner will continue in the new state */ }但是使用最大咀嚼规则更简单也更通用。
如果多个模式具有相同的最长匹配，则扫描仪描述中的第一个模式获胜。