如何使用 flex/bison 解析 Scala 语法中的新行？

Question

我想用 flex 和 bison 解析 Scala 语法。但是我不知道如何在 Scala 语法中解析换行符。

如果我将换行符解析为标记 T_NL，这里是 Toy.l 例如：

...
[a-zA-Z_][a-zA-Z0-9_]*  { yylval->literal = strdup(yy_text); return T_ID; }
\n                      { yylval->token = T_LN; return T_LN; }
[ \t\v\f\r]             { /* skip whitespaces */ }
...

这里是 Toy.y 例如：

function_def: 'def' T_ID '(' argument_list ')' return_expression '=' expression T_NL
            ;

argument_list: argument
             | argument ',' argument_list
             ;

expression: ...
          ;

return_expression: ...
                 ;

你可以看到我必须在 Toy.y 中的所有其他语句和定义中跳过 T_NL，这真的很无聊。

请教我源代码示例！

Answer 1

这是野牛 push-parsers 有用的明显案例。基本思想是，只有在识别了以下令牌（并且在一个极端情况下，是第二个后续令牌）时才能做出发送 NL 令牌（或多个令牌）的决定。

推送解析器的优势在于它们让我们可以实现这样的策略，其中输入词位和发送到解析器的标记之间不一定存在 one-to-one 关系。我不打算处理设置推送解析器的所有特殊性（尽管这并不困难）；详情请参考 bison manual。 [注1]

首先，仔细阅读 Scala 语言描述很重要。换行处理描述为 in section 2.13:

A newline in a Scala source text is treated as the special token “nl” if the three following criteria are satisfied:

The token immediately preceding the newline can terminate a statement.

The token immediately following the newline can begin a statement.

The token appears in a region where newlines are enabled.

规则1和规则2是简单的查找表，在下面两段中有精确的定义。规则 2 有一个小例外，如下所述：

A case token can begin a statement only if followed by a class or object token.

处理该异常的一种骇人听闻的可能性是添加 case[[:space:]]+class 和 case[[:space:]]+object 作为词位，假设 no-one 将在 case 之间添加注释和 class。（或者您可以使用更复杂的模式，它允许注释和空格。）如果这些词位之一被识别，它可以作为单个（融合）标记发送到解析器，或者可以作为两个发送在词法分析器操作中使用两次 SEND 调用的标记。（就个人而言，我会选择融合令牌，因为一旦识别出这对令牌，将它们分开就没有任何优势；afaik，没有有效的程序可以将 case class 解析为其他任何东西比 case class。但我可能是错的。）

为了应用规则一和规则二，我们需要两个由令牌号索引的查找表：token_can_end_stmt 和 token_cannot_start_stmt。（第二个意思相反，因为大多数标记都可以开始语句；这样做可以简化初始化。）

        /* YYNTOKENS is defined by bison if you specify %token-tables */
        static bool token_can_end_stmt[YYNTOKENS] = {
          [T_THIS] = true, [T_NULL] = true, /* ... */
        };
        static bool token_cannot_start_stmt[YYNTOKENS] = {
          [T_CATCH] = true, [T_ELSE] = true, /* ... */
        };

我们将需要一点持久状态，但幸运的是，当我们使用推送解析器时，扫描器不需要在每次识别令牌时向其调用者return，所以我们可以将持久状态作为扫描循环中的局部变量。（这是 push-parser 架构的另一个优势。）

从上面的描述我们可以看出，在scanner状态下我们需要维护的是：

一些迹象表明遇到了换行符。这需要是一个计数，而不是布尔值，因为我们可能需要发送两个换行符：

if two tokens are separated by at least one completely blank line (i.e a line which contains no printable characters), then two nl tokens are inserted. A simple way to handle this is to simply compare the current line number with the line number at the previous token. If they are the same, then there was no newline. If they differ by only one, then there was no blank line. If they differ by more than one, then there was either a blank line or a comment (or both). (It seems odd to me that a comment would not trigger the blank line rule, so I'm assuming that it does. But I could be wrong, which would require some adjustment to this scanner.) [Note 2]
前一个标记（对于规则 1）。只需要记录token编号，就是一个简单的小整数。
判断我们是否处于“启用换行符的区域”的某种方式（针对规则 3）。我很确定这需要解析器的帮助，所以我在这里这样写。

通过将关于发送换行符的决定集中到一个函数中，我们可以避免大量的代码重复。无论如何，我典型的 push-parser 架构使用 SEND 宏来处理保存语义值、调用解析器和检查错误的样板；在那里添加换行逻辑很容易：

// yylloc handling mostly omitted for simplicity
#define SEND_VALUE(token, tag, value) do {                             \
    yylval.tag = value;                                                \
    SEND(token);                                                       \
} while(0);

#define SEND(token) do {                                               \
    int status = YYPUSH_MORE;                                          \
    if (yylineno != prev_lineno)                                       \
            && token_can_end_stmt[prev_token]                          \
            && !token_cannot_start_stmt[token]                         \
            && in_new_line_region) {                                   \
      status = yypush_parse(ps, T_NL, NULL, &yylloc, &nl_enabled);     \
      if (status == YYPUSH_MORE                                        \
          && yylineno - prev_lineno > 1)                               \
        status = yypush_parse(ps, T_NL, NULL, &yylloc, &nl_enabled);   \
    }                                                                  \
    nl_encountered = 0;                                                \
    if (status == YYPUSH_MORE)                                         \
      status = yypush_parse(ps, token, &yylval, &yylloc, &nl_enabled); \
    if (status != YYPUSH_MORE) return status;                          \
    prev_token = token;                                                \
    prev_lineno = yylineno;                                            \
while (0);

在扫描仪中指定本地状态非常简单；只需将声明和初始化放在扫描仪规则的顶部，缩进即可。第一条规则之前的任何缩进代码都直接插入 yylex，几乎在函数的顶部（因此每次调用执行一次，而不是每个词位执行一次）：

%%
    int nl_encountered = 0;
    int prev_token = 0;
    int prev_lineno = 1;
    bool nl_enabled = true;
    YYSTYPE yylval;
    YYLTYPE yylloc = {0};

现在，个别规则非常简单（case除外）。例如，我们可能有这样的规则：

"while"                     { SEND(T_WHILE); }
[[:lower:]][[:alnum:]_]*    { SEND_VALUE(T_VARID, str, strdup(yytext)); }

这仍然留下了如何确定我们是否处于启用换行符的区域的问题。

大多数规则都可以在词法分析器中处理，只需保留一堆不同类型的左括号，并检查栈顶：如果栈顶的括号是 {，然后启用换行符；否则，他们不是。所以我们可以使用像这样的规则：

[{([]   { paren_stack_push(yytext[0]); SEND(yytext[0]); }
[])}]   { paren_stack_pop(); SEND(yytext[0]); }

然而，这并没有解决在 case 与其对应的 => 之间禁用换行符的要求。我认为不可能将其作为另一种类型的括号来处理，因为 => 的很多用法与 case 不对应，我相信其中一些可以介于 case 对应的是 =>.

所以更好的方法是将此逻辑放入解析器，使用词法反馈来传达 newline-region 堆栈的状态，这是在上面对 yypush_parse 的调用中假定的.具体来说，它们在扫描器和解析器之间共享一个布尔变量（通过将指针传递给解析器）。 [注 3] 然后，解析器使用解析堆栈在每个匹配可能不同换行性的区域的规则中维护 MRA 中此变量的值lf 作为堆栈。这是（理论上的）解析器的一小段摘录：

%define api.pure full
%define api.push-pull push
%locations
%parse-param { bool* nl_enabled; }
/* More prologue */
%%
// ...
/* Some example productions which modify nl_enabled: */

/* The actions always need to be before the token, because they need to take
 * effect before the next lookahead token is requested.
 * Note how the first MRA's semantic value is used to keep the old value
 * of the variable, so that it can be restored in the second MRA.
 */
TypeArgs          :  <boolean>{ $$ = *nl_enabled; *nl_enabled = false; }
                     '[' Types
                     { *nl_enabled = ; }  ']'

CaseClause        :  <boolean>{ $$ = *nl_enabled; *nl_enabled = false; }
                     "case" Pattern opt_Guard 
                     { *nl_enabled = ; }   "=>" Block

FunDef             : FunSig opt_nl
                     <boolean>{ $$ = *nl_enabled; *nl_enabled = true; }
                     '{' Block  
                     { *nl_enabled = ; }   '}'

备注：

推送解析器还有许多其他优点；恕我直言，他们是选择的解决方案。特别是，使用推送解析器避免了困扰尝试构建纯 parser/scanner 组合的循环 header 依赖。
还有多行注释前后有问题：
```
return   /* Is this comment
            a newline?       */ 42
```
我不会尝试回答这个问题。）
可以将此标志保留在 YYLTYPE 结构中，因为在此示例中只使用了一个 yylloc 实例。这可能是一个合理的优化，因为它减少了发送到 yypush_parse 的参数数量。但它似乎有点脆弱，所以我在这里选择了一个更通用的解决方案。

如何使用 flex/bison 解析 Scala 语法中的新行？

How to parse new line in Scala grammar with flex/bison?

scala

bison

flex-lexer

备注：