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

我想用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; }
[ tvfr]             { /* 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，这真的很无聊。

请用源代码示例来教育我！

这是bison推送解析器非常有用的一个明显例子。其基本思想是，只有在识别了下一个令牌(在一个角落的情况下，是第二个下一个)时，才能决定发送NL令牌。

推送解析器的优点是，它们允许我们实现这样的策略，其中输入词法和发送到解析器的令牌之间不一定存在一对一的关系。我不打算讨论设置推送解析器的所有特殊性(尽管这并不困难)；有关详细信息，请参阅bison手册。[注1]

首先，仔细阅读Scala语言的描述是很重要的。第2.13:节介绍了新线处理

如果满足以下三个条件，Scala源文本中的换行符将被视为特殊标记"nl"：

紧跟在换行符前面的标记可以终止语句

紧跟在换行符后面的标记可以开始一个语句

该标记显示在启用换行符的区域中

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

case令牌只有在后面跟有class或object令牌时才能开始语句。

处理该异常的一种常见可能性是添加case[[:space:]]+class和case[[:space:]]+object作为词法，假设没有人会在case和class之间添加注释。(或者你可以使用一个更复杂的模式，它允许注释和空白。)如果识别出其中一个词法，它可以作为一个(融合的)令牌发送给解析器，也可以在lexer操作中使用两次SEND调用作为两个令牌发送。(就我个人而言，我会选择融合的令牌，因为一旦识别出这对令牌，将它们拆分就没有任何好处；当然，没有一个有效的程序可以将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, /* ... */
};

我们需要一点持久状态，但幸运的是，当我们使用推送解析器时，扫描仪不需要每次识别令牌时都返回给调用方，因此我们可以在扫描循环中将持久状态作为局部变量。(这是推送解析器体系结构的另一个优势。)

从上面的描述中，我们可以看到，在扫描仪状态下，我们需要维护的是：

一些指示，表明遇到了换行符。这需要是一个计数，而不是布尔值，因为我们可能需要发送两条换行符：
如果两个令牌由至少一个完全空白的行(即不包含可打印字符的行)分隔，则插入两个nl令牌。处理此问题的一种简单方法是简单地将当前行号与上一个标记处的行号进行比较。如果它们是相同的，那么就没有换行符。如果它们只相差一个，那么就没有空行。如果它们相差不止一个，那么要么是空白行，要么是注释(或者两者都有)。(对我来说，评论不会触发空行规则似乎很奇怪，所以我假设它会触发。但我可能错了，这需要对扫描仪进行一些调整。)[注2]
上一个令牌(用于规则1)。只需要记录令牌编号，这是一个简单的小整数。
某种方式来判断我们是否处于"；启用换行符的区域"；(适用于第3条)。我确信这将需要解析器的帮助，所以我在这里就是这样写的。

通过将发送换行符的决策集中到一个函数中，我们可以避免大量代码重复。无论如何，我典型的推送解析器架构使用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)); }

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

大多数规则都可以在lexer中处理，只需保留一堆不同类型的括号，并检查堆栈的顶部：如果堆栈顶部的括号是{，则启用换行符；否则，它们就不是。因此，我们可以使用以下规则：

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

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

因此，更好的方法是将此逻辑放入解析器，使用词法反馈来传达换行区域堆栈的状态，这是上面对yypush_parse的调用中所假设的。具体来说，它们在扫描器和解析器之间共享一个布尔变量(通过向解析器传递指针)。[注意3]然后，解析器在每个规则的MRA中维护该变量的值，该规则匹配具有潜在不同换行性的区域，使用解析堆栈本身作为堆栈。以下是一个(理论)解析器的小摘录：

%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 = $1; }  ']'
CaseClause        :  <boolean>{ $$ = *nl_enabled; *nl_enabled = false; }
"case" Pattern opt_Guard 
{ *nl_enabled = $1; }   "=>" Block
FunDef             : FunSig opt_nl
<boolean>{ $$ = *nl_enabled; *nl_enabled = true; }
'{' Block  
{ *nl_enabled = $3; }   '}'

注意：

Push解析器还有许多其他优点；IMHO他们是选择的解决方案。特别是，使用推送解析器避免了循环头依赖性，这种依赖性阻碍了构建纯解析器/扫描程序组合的尝试。
仍然存在前面和后面都有文字的多行注释的问题：
```
return   /* Is this comment
a newline?       */ 42
```
我不会试图回答那个问题。)
可以在YYLTYPE结构中保留此标志，因为在本例中只使用了yylloc的一个实例。这可能是一个合理的优化，因为它减少了发送到yypush_parse的参数数量。但它似乎有点脆弱，所以我选择了一个更通用的解决方案。

注意：

相关内容

最新更新

热门标签：