处理 Flex/Bison 中的新行

Question

我正在尝试使用 Flex/Bison 编写类似 C 的语言。我的问题是我找不到处理新行的正确方法。我必须忽略所有新行，所以我不会 returnt 它们作为 Bison 的标记，因为这会使语法规则很难制定，但在某些规则中我被要求强制更改行。例如：

程序“标识符”-> 强制更改行

函数“标识符”(“参数”) -> 强制更改行

如果我 return \n 作为 flex 的标记，那么我必须在我的所有语法规则中添加新行，这肯定是不切实际的。我试图让一个变量像开关或其他东西一样工作，但它并没有完全起作用。有什么帮助或建议吗？

Answer 1

有一种称为尾随上下文的模式您不能尝试：https://people.cs.aau.dk/~marius/sw/flex/Flex-Regular-Expressions.html

“标识符”/[\n]

“函数标识符”/[\n]

Answer 2

如果所需的换行只是为了美观——也就是说，如果为了避免歧义不需要它——那么执行它的最简单方法通常只是跟踪标记位置（这是bison 和 flex 可以帮助你）这样你就可以检查你的减少操作，两个连续的标记不在同一行：

func_defn: "function" IDENT '(' opt_arg_list ')' body "end" {
    if (@5.last_line == @6.first_line) {
      yyerror("Body of function must start on a new line");
      /* YYABORT; */ /* If you want to kill the parse at this point. */
    }
    // ...
}

Bison 不需要任何声明或选项即可使用位置；如果它注意到您在任何操作中使用 @N（这是您引用令牌位置的方式），它将插入位置支持。但是，有时插入 %locations 声明以强制支持位置是有用的。通常不需要对您的语法进行其他更改。

您必须在词法分析器中插入一些代码才能向解析器报告位置值。位置通过名为 yylloc 的全局变量进行通信，其值的类型为 YYLTYPE。默认情况下，YYLTYPE 是一个包含四个 int 成员的结构：first_line、first_column、last_line、last_column。（有关更多详细信息，请参阅 the Bison manual。）这些字段需要在您的词法分析器中为每个标记设置。幸运的是，flex 允许您定义宏 YY_USER_ACTION，其中包含在每个操作（甚至是空操作）之前执行的代码，您可以使用它来填充 yylloc。这是一个适用于许多简单词法分析器的方法；你可以把它放在你的 flex 文件顶部的代码块中。

/* Simple YY_USER_ACTION. Will not work if any action includes
 * yyless(), yymore(), input() or REJECT.
 */
#define YY_USER_ACTION                                             \
  yylloc.first_line = yylloc.last_line;                            \
  yylloc.first_column = yylloc.last_column;                        \
  if (yylloc.last_line == yylineno)                                \
    yylloc.last_column += yyleng;                                  \
  else {                                                           \
    yylloc.last_line = yylineno;                                   \
    yylloc.last_column = yytext + yyleng - strrchr(yytext, '\n');  \
  }

如果上述简单的位置检查不足以满足您的用例，那么您可以通过所谓的“词法反馈”来完成：一种机制，解析器不仅从词法扫描器收集信息，而且当需要某种词法更改时与词法分析器通信。

通常不鼓励使用词汇反馈，因为它可能很脆弱。记住解析器和扫描器不一定同步是很重要的。解析器经常（但不总是）需要知道当前产生式之后的下一个标记，因此执行产生式动作时的词法状态可能是下一个标记之后的词法状态，而不是最后一个标记之后的状态生产。但它可能不会；许多解析器生成器，包括 Bison，如果发现无论下一个标记如何都会执行相同的操作，都会尝试立即执行操作。不幸的是，这并不总是可以预测的。例如，在 Bison 的情况下，将解析算法从默认的 LALR(1) 更改为 Canonical LR(1) 或 GLR 也可以将特定的缩减操作从立即更改为延迟。

因此，如果您要尝试与扫描器通信，您应该尝试以一种无论扫描器是否已被要求提供先行令牌都有效的方式进行通信。一种方法是将与扫描器通信的代码放在 Mid-Rule Action 一个令牌中，该令牌比您要影响的令牌早。 [注1]

为了使换行符“大部分是可选的”，我们需要告诉词法分析器什么时候应该 return 换行符而不是忽略它。一种方法是导出词法分析器可以调用的函数。我们将该函数的定义放入生成的解析器中，并将其声明放入生成的头文件中：

/* Anything in code requires and code provides sections is also
 * copied into the generated header. So we can use it to declare
 * exported functions.
 */
%code requires {
  #include <stdbool.h>
  bool need_nl(void);
}
%%
// ...

/* See [Note 2], below. */

/* Program directive. */
prog_decl: "program" { need_nl_flag = true; } IDENT '\n'

/* Function definition */
func_defn: "function" IDENT
           '(' opt_arg_list { need_nl_flag = true; } ')' '\n'
              body
           "end"

// ...
%%
static bool need_nl_flag = false;

/* The scanner should call this function when it sees a newline.
 * If the function returns true, the newline should be returned as a token.
 * The function resets the value of the flag, so it must not be called for any
 * other purpose. (This interface allows us to set the flag in a parser action
 * without having to worry about clearing it later.)
 */
bool need_nl(void) {
  bool temp = need_nl_flag;
  need_nl_flag = false;
  return temp;
}

// ...

然后我们只需要对扫描仪进行小的调整即可调用该函数。这使用 Flex 的 set difference operator {-} 使字符 class 包含除换行符之外的所有空白。因为我们把这条规则放在第一位，所以第二条规则将只用于包含至少一个换行符的空白。请注意，对于任何空行序列，我们只 return 一个换行符。

([[:space:]]{-}[\n])+  { /* ignore whitespace */ }
[[:space:]]+           { if (need_nl()) return '\n'; }

备注

这也不是你可以不假思索就做的事情：过早更改扫描仪配置也可能是一个错误。在操作中，您可以通过查看 yychar 的值来检查是否已读取前瞻标记。如果 yychar 是 YYEMPTY，则没有读取先行标记。如果它是 YYEOF，则尝试读取先行标记但遇到了输入结束。否则，先行标记已被读取。

使用两种操作似乎很诱人，一种是在您要影响的操作之前的标记之前，另一种是在该标记之前。第一个动作只有在yychar不是YYEMPTY时才会执行，说明lookahead token已经被读取，scanner即将读取你要更改的token，而第二个动作只会执行如果那时 yychar 是 YYEMPTY。但完全有可能对于特定的解析，这两个条件都为真，或者两者都不为真。

Bison 确实有一种配置，您可以使用它来使前瞻决策完全可预测。如果您设置 %define lr.default-reduction accepting，那么 Bison 将始终尝试读取先行符号，并且您可以确定提前放置一个标记的操作将起作用。除非您以交互方式使用解析器，否则启用此选项不会产生实际成本。但它不适用于旧的 Bison 版本或其他解析器生成器，例如 byacc.
对于这个语法，我们可以将中间规则操作放在 '\n' 标记之前，而不是更早的一个标记（只要解析器从未转换为 GLR 或Canonical-LR 解析器）。这是因为在这两个规则中，MRA 将介于两个令牌之间，并且（大概）没有其他规则可能适用于这些令牌中的第一个。在那些情况下，Bison 当然可以知道可以减少 MRA，而无需检查先行标记以查看它是否为 \n：下一个标记是换行符并且需要减少，或者下一个标记不是换行符，这将是一个语法错误。由于 Bison 不保证在缩减动作运行之前检测到语法错误，它可以在知道解析是否成功之前减少 MRA 动作。

处理 Flex/Bison 中的新行

Handling new lines in Flex/Bison

lex

newline

token

bison

备注