在 Flex/Bison 中实现字符串插值

Question

我目前正在为我设计的语言编写解释器。

lexer/parser (GLR) 是用 Flex/Bison 编写的，主要的解释器是用 D 编写的 - 到目前为止，一切都完美无缺。

我还想添加字符串插值，即识别包含特定模式（例如 "[some expression]"）的字符串文字并转换包含的表达式。我认为这应该在相应的语法操作中在解析器级别完成。

我的想法是 converting/treating 内插字符串就像简单连接后的样子（因为它现在可以工作）。

例如

print "this is the [result]. yay!"

到

print "this is the " + result + ". yay!"

但是，我对如何在 Bison 中做到这一点感到有点困惑：基本上，我如何告诉它重新解析特定的字符串（在构建主 AST 时）？

有什么想法吗？

Answer 1

如果您真的需要，您也可以通过生成 reentrant parser. You would probably want a reentrant scanner 来重新解析字符串，尽管我想您可以使用 flex 的缓冲区堆栈与默认扫描器一起拼凑一些东西。事实上，值得学习如何根据避免不必要的全局变量的一般原则构建可重入解析器和扫描器，无论您是否需要将它们用于此特定目的。

但是你真的不需要重新解析任何东西；您可以一次完成整个解析。您只需要在您的扫描仪中具备足够的智能，以便它了解嵌套插值。

基本思想是让扫描器将带有插值的字符串文字拆分成一系列标记，解析器可以轻松地将其组装成合适的 AST。由于扫描器可能 return 单个字符串文字中的多个标记，因此我们需要引入一个 start condition to keep track of whether the scan is currently inside a string literal or not. And since interpolations can, presumably, be nested we'll use flex's optional start condition stack，启用 %option stack，以跟踪嵌套上下文。

所以这是一个粗略的草图。

如前所述，扫描器有额外的启动条件：SC_PROGRAM，默认值，在扫描器扫描常规程序文本时有效，SC_STRING，在扫描器扫描时有效扫描字符串。 SC_PROGRAM只是需要，因为flex官方没有提供检查启动条件栈是否为空的接口；除了嵌套之外，它与 INITIAL 顶级开始条件相同。起始条件堆栈用于跟踪插值标记（本例中为 [ 和 ]），它是必需的，因为插值表达式可能使用方括号（例如，作为数组下标）或可能甚至包括一个嵌套的内插字符串。由于 SC_PROGRAM 除一个例外外与 INITIAL 相同，我们将其设为包容性规则。

%option stack
%s SC_PROGRAM
%x SC_STRING
%%

由于我们使用单独的开始条件来分析字符串文字，因此我们还可以在解析时规范化转义序列。并非所有应用程序都希望这样做，但这很常见。但由于这不是这个答案的真正重点，所以我省略了大部分细节。更有趣的是嵌入式插值表达式的处理方式，尤其是深度嵌套的表达式。

最终结果将是将字符串文字转换为一系列标记，可能表示嵌套结构。为了避免在扫描器中实际解析，我们不尝试创建 AST 节点或以其他方式重写字符串文字；相反，我们只是将引号字符本身传递给解析器，分隔字符串文字片段的序列：

["]                 { yy_push_state(SC_STRING);    return '"'; }
<SC_STRING>["]      { yy_pop_state();              return '"'; }

一组非常相似的规则用于插值标记：

<*>"["              { yy_push_state(SC_PROGRAM);   return '['; }
<INITIAL>"]"        {                              return ']'; }
<*>"]"              { yy_pop_state();              return ']'; }

上面的第二条规则避免在开始条件堆栈为空时弹出它（因为它将处于 INITIAL 状态）。没有必要在扫描仪中发出错误信息；我们可以将不匹配的右括号传递给解析器，然后解析器将执行任何必要的错误恢复。

要结束 SC_STRING 状态，我们需要 return 字符串片段的标记，可能包括转义序列：

<SC_STRING>{
  [^[\"]+          { yylval.str = strdup(yytext); return T_STRING; }

  \n               { yylval.chr = '\n';           return T_CHAR; }
  \t               { yylval.chr = '\t';           return T_CHAR; }
          /* ... Etc. */
  \x[[:xdigit]]{2} { yylval.chr = strtoul(yytext, NULL, 16);
                                               return T_CHAR; }
  \.               { yylval.chr = yytext[1];      return T_CHAR; }
}

将这样的转义字符返回给解析器可能不是最好的策略；通常我会使用内部扫描器缓冲区来累积整个字符串。但出于说明目的，它很简单。（这里省略了一些错误处理；有各种特殊情况，包括换行处理和程序中最后一个字符是未终止字符串文字中的反斜杠的恼人情况。）

在解析器中，我们只需要为内插字符串插入一个连接节点。唯一的麻烦是我们不想在没有任何插值的情况下为字符串文字的常见情况插入这样的节点，因此我们使用两种语法产生式，一种用于仅包含一个片段的字符串，另一种用于具有两件或更多件：

string : '"' piece '"'                 { $$ = ; }
       | '"' piece piece_list '"'      { $$ = make_concat_node(
                                                prepend_to_list(, ));
                                       }
piece  : T_STRING                      { $$ = make_literal_node(); }  
       | '[' expr ']'                  { $$ = ; }
piece_list
       : piece                         { $$ = new_list(); }
       | piece_list piece              { $$ = append_to_list(, ); }

在 Flex/Bison 中实现字符串插值

Implementing String Interpolation in Flex/Bison

string

yacc

d

bison

string-interpolation