Flex: REJECT 一次拒绝一个字符？

Question

我正在解析 C++ 风格的作用域名称，例如 A::B。如果以前声明为类型，我想将这样的名称解析为类型名称的单个标记；否则，我想将其解析为三个标记 A、:: 和 B.

给定：

L             [A-Za-z_]
D             [0-9]
S             [ \f\r\t\v]

identifier    {L}({L}|{D})*
sname         {identifier}({S}*::{S}*{identifier})+

%%

{sname}       {
                if ( find_type( yytext ) )
                  return Y_TYPE_NAME;
                REJECT;
              }

{identifier}  {
                // ...
                return Y_NAME;
              }

然而，对于输入序列：

A::BB -> Not a type; returned as "A", "::", "BB"
(Declare A::B as a type.)
A::BB

调用 A::BB 的第二次解析会发生什么，调用 REJECT 并且 flex 仅丢弃末尾的 1 个字符并尝试匹配 A::B（一个 B）。这与之前在 {sname} 规则中声明的 A::B 相匹配，这是错误的。

我假设 REJECT 所做的是使用相同的输入进行第二最佳匹配规则。因此，我希望它在 {identifier} 中单独匹配 A 并且只将 ::BB 留在输入流中。但是，如图所示，事实并非如此。它从输入的末尾一次剥离一个字符并重新尝试匹配。

添加 yyless() 以切断 ::BB 没有帮助：

{sname}       {
                if ( find_type( yytext ) )
                  return Y_TYPE_NAME;
                char const *const sep = strpbrk( yytext, ": \t" );
                size_t keep_len = (size_t)(sep - yytext);
                yyless( keep_len );
                REJECT;
              }

我发现唯一有效的是：

{sname}       {
                if ( find_type( yytext ) )
                  return Y_TYPE_NAME;
                char const *const sep = strpbrk( yytext, ": \t" );
                size_t keep_len = (size_t)(sep - yytext);
                yyless( keep_len );
                goto identifier;
              }

{identifier}  {
    identifier:
                // ...
                return Y_NAME;
              }

但是这些看起来有点老套。有没有更规范的“灵活方式”来做我想做的事？

尽管有点乱七八糟，但我的解决方案实际上有什么错误吗？也就是说，它在某些情况下不起作用吗？或者在某些版本的 Flex 中不起作用？

是的，我知道，即使它确实按照我想要的方式工作，它也不会解析所有人为设计的 C++ 作用域名称；但已经足够了。

是的，我知道通常解析这些东西应该作为单独的标记来完成，但是类 C 语言很难解析，因为它们不是上下文无关的。知道什么时候你有一个类型真的很有帮助。

是的，我知道 REJECT 会减慢词法分析器的速度。这（主要）用于终端中的交互式命令行工具，因此人是最慢的组件。

我想主要关注代码的手头问题。我的更多问题是关于如何使用 REJECT、yyless() 等来获得所需的行为。谢谢。

Answer 1

REJECT不区分不同的规则；它只是退回到下一个可能的接受模式（如果存在匹配相同标记的优先级较低的规则，它甚至可能不会更短。）这可能是相同模式的较短匹配。（通常，Flex 从正则表达式的可能匹配中选择最长的匹配。对于 REJECT，较短的匹配也会被考虑。）

因此您可以通过使用尾随上下文来避免 A::B 与输入 A::BB 的错误匹配：[注 1]

{sname}/[^[:alnum:]_]  {...}

（在 Flex 中，您不能将尾随上下文放在宏中，因为扩展用括号括起来。）

如果您想尝试所有个可能的 id1::id2::id3::id4 完整前缀，从最长的前缀 (id1::id2::id3::id4) 开始，然后回退，您可以使用该解决方案依次到每个较短的前缀（id1::id2::id3、id1::id2、id1）。尾随上下文防止标识符中间的中间匹配。

不过，我不确定这是否是您要解决的问题。即使是，它也不能真正解决退回到可接受的解决方案后该做什么的问题，因为您可能不想在序列中间重新搜索前缀。换句话说，如果原件是 A::B::A::B，而 A::B 是“已知前缀”，则 returned 的标记应该（大概）是 A::B，::, A, ::, B 而不是 A::B, ::, A::B.

另一方面，您可能不关心以前定义的前缀；只有完整序列是否是已知类型。在这种情况下，A::B::C::D 的可能标记序列是 [TYPENAME(A::B::C::D)] 和 [ID(A)、::、ID(B)、::、ID(C)、ID(D)]。对于这种情况，您不想限制 {sname} 回退；你想消除它们。回退后，您只想尝试不同规则的匹配。

有多种替代解决方案（不使用 REJECT），主要依赖于使用启动条件的可能性。（您仍然需要考虑回退后会发生什么。启动条件对此也很有用。）

一个相当通用的解决方案是定义一个开始条件，它排除了您要回退的规则。一旦确定要回退到不同的规则，就更改为排除刚刚匹配的规则的开始条件，然后调用 yyless(0)（没有 returning）。这将导致 Flex 在新的开始条件下从头开始重新扫描当前令牌。（如果你有几个可能匹配的规则，你将需要几个开始条件。这可能会失控，但在大多数情况下，可能的匹配规则集是非常有限的。）

在某些时候，您需要return到之前的开始条件。（如果确定哪个是先前的开始条件并非易事，您可以使用开始条件堆栈。）理想情况下，为了避免错误的内部匹配，您可能希望仅在达到第一场（不正确的）比赛结束。如果您正在跟踪每个令牌的输入位置，这很容易做到；您只需要在调用 yyless(0) 之前保存位置。（您还需要在 yyless 将 yyleng 设置为 0 之前通过减去 yyleng 来更正令牌输入位置。

从令牌的开头重新扫描可能看起来效率低下，但它的效率低于 REJECT 强加的开销。而 REJECT 的开销会影响整个扫描器操作，而重新扫描解决方案基本上是免费的，除了您碰巧重新扫描的令牌。 [注2]

(BEGIN(some_state); yyless(0);) 是一个相当常见的 flex 习语；这不是唯一的用例。另一个是问题的答案“我如何运行一个开始条件，直到我到达一个不消耗该令牌就无法识别的令牌？”）

但我认为在这种情况下有一个更简单的解决方案，使用 yymore 来累积令牌。（这避免了必须自己动态扩展令牌缓冲区。）同样，有两种可能性，具体取决于您是允许初始前缀匹配还是将可能性限制为完整序列或第一个标识符。

但是大纲是一样的：首先匹配最短的有效可能性，记住那个标记有多长，然后使用开始条件启用一个模式将令牌扩展到下一个可能性或序列的末尾，具体取决于您的需要。在继续扫描器循环之前，您调用 yymore() 向 Flex 指示下一个模式扩展令牌而不是替换它。

在每个可能的匹配结束时，您测试它是否真的是一个有效的标记，如果是，记录位置（以及您可能需要回忆的任何其他内容，例如标记类型）。当您到达无法再扩展匹配的点时，您可以使用 yyless 回退到最后一个有效匹配点，并使用 return 令牌。

这比纯 yyless() 解决方案效率稍低，因为它避免了重新扫描 returned 的令牌。（所有这些解决方案，包括 REJECT，如果所选匹配短于可能的最长扩展匹配，则重新扫描所选匹配后的文本。这在理论上是可以避免的，但由于开销不大，因此似乎不值得建立一个复杂的机制来避免它。）同样，您可能希望避免在回退后尝试扩展令牌匹配，直到达到最长范围。这个可以用同样的方法解决，通过记录最长的匹配范围，但是开始条件处理稍微简单一些。

下面是针对更简单问题的一些未经充分测试的代码，其中只有第一个标识符和完全匹配是可能的：

%{
    /* Code to track current token position and the fallback position.
     * It's a simple byte count; line-ends are not dealt with.
     */
    static int token_pos = 0;
    static int token_max_pos = 0;
    /* This is done before every action, even empty actions */
    #define YY_USER_ACTION token_pos += yyleng;
    /* FALLBACK needs to undo YY_USER_ACTION */
    #define FALLBACK(to) do { token_pos -= yyleng - to; yyless(to); } while (0)
    /* SET_MORE needs to pre-undo the next YY_USER_ACTION */
    #define SET_MORE(X) do { token_pos -= yyleng; yymore(); } while(0)
%}

%x EXTEND_ID
ident [[:alpha:]_][[:alnum:]_]*
%%
    int fallback_leng = 0;
    /* The trailing context here is to avoid triggering EOF in
     * the EXTEND_ID state.
     */
{ident}/[^[:alnum:]_] {
              /* In the fallback region, don't attempt to extend the match. */
              if (token_pos <= token_max_pos)
                return Y_IDENT;
              fallback_leng = yyleng;
              BEGIN(EXTEND_ID);
              SET_MORE(yymore);
            }
{ident}     { return find_type(yytext) ? Y_TYPE_NAME : Y_IDENT; }
<EXTEND_ID>{
  ([[:space:]]*"::"[[:space:]]*{ident})*|.|\n {
              BEGIN(INITIAL);
              if (yyleng == fallback_leng + 1)
                FALLBACK(fallback_leng);
              if (find_type(yytext))
                return Y_TYPE_NAME;
              else {
                FALLBACK(fallback_leng);
                return Y_IDENT;
              }
            }
}

注释

至少，我觉得你可以做到。我从未尝试过 REJECT 确实对其他扫描仪功能施加了一些限制。真的，这是一个历史产物，它大大减慢了词法分析的速度，通常应该避免。
在规则的任何地方使用 REJECT 会导致 Flex 切换到另一个模板，其中保留了端点列表，这在时间和 space.另一个结果是 Flex 无法再调整输入缓冲区的大小。

Flex: REJECT 一次拒绝一个字符？

Flex: REJECT rejects one character at a time?

c

flex-lexer

注释