Flex：匹配 signed int 与 addition/subtraction

Question

我有一个 flex 文件，它 return 根据输入文件向我发送令牌。我目前将它设置为 return 当我在 flex 中看到一个带符号的 int 时，它是一个标记 INT，当我看到一个加法或减法时，它是一个标记 ADD 或 SUB。

我在 flex 中为 signed int 定义了一个宏

signedint = [+-]?[0-9]+

当 flex 看到此模式时，它 return 是一个 INT 令牌。

但是，我运行遇到了能够区分带符号整数与加法或减法的问题。例如，

5 + 2

returns 3 个标记：INT、ADD、INT。这很好。

但是，当缺少空格时，我运行遇到了麻烦：

5+2
5 +2

其中任何一个 return 只是两个标记（2 个整数），因为 flex 将 5 视为一个有符号整数（正确地）并且 returns 它，然后看到 '+2' 并看到另一个signed int（它没有 return 任何空格）。

关于如何让它区分 signed int 和 addition/subtraction 的任何想法？

Answer 1

signedint = \s*[+-]?\s*[0-9]+\s*

这应该有效

Answer 2

在词汇层面解决这个问题的难度是许多语言甚至不尝试的原因。解析器可以轻松区分一元前缀 + 或 - 运算符和具有相同拼写的二元中缀运算符，除了一个极端情况 (见下文），-2 被视为前缀减号后跟整数常量，与 -2 被视为单个标记之间没有真正的语义差异。在解析器中，如果您不希望运算符出现在 AST 中，可以使用常量折叠来计算常量 sub-expressions。

只有通过维护词法状态才能在词法扫描期间区分中缀和前缀运算符，这有效地将部分解析算法复制到词法扫描器中的hand-built状态机中。在普通算术表达式的情况下，它只是解析算法的一小部分，但即便如此它也不漂亮并且使 lexer/parser 组合正确性的验证变得复杂。

撇开此处不相关的运算符优先级和结合性，算术表达式的语法可以简化为如下内容：

expr: term
    | expr INFIX term
term: CONSTANT | VARIABLE
    | '(' expr ')'
    | PREFIX term

（省略后缀运算符，包括函数调用和数组下标，但原理不受影响。）

根据该语法，很容易导出 FIRST、LAST 和 FOLLOW 集。 term 只能以终端开头，而 expr 只能以 term 开头，所以它们都有相同的 FIRST 集合：

FIRST(expr) = FIRST(term) = { (, PREFIX, CONSTANT, VARIABLE }

通过类似的推理，最后一组 term 和 expr 也相同：

LAST(expr) = LAST(term) = { ), CONSTANT, VARIABLE }

最后，non-terminals 的 FOLLOW 集基于 term 仅出现在 expr 末尾的观察，而 expr要么在输入的末尾，要么出现在语法中后跟一个终端：

FOLLOW(term) = FOLLOW(expr) = { ), INFIX, $ }

（其中 $ 是 end-of-input 标记。）

所有这些让我们可以计算终端的 FOLLOW 集，使用观察结果，对于 non-terminal V 的 LAST 中的每个终端 A 只能跟随 FOLLOW(V) 中的终端。（在某些语法中可能会高估 FOLLOW 集，但在这种情况下无关紧要。）最终给我们：

 terminal           can be followed by
 --------           ------------------
 INFIX              PREFIX, (, CONSTANT, VARIABLE
 (                  PREFIX, (, CONSTANT, VARIABLE
 PREFIX             PREFIX, (, CONSTANT, VARIABLE
 )                  INFIX, ), $
 CONSTANT           INFIX, ), $
 VARIABLE           INFIX, ), $

简而言之，PREFIX 和 INFIX 永远不会出现在同一上下文中。如果先前的标记是 INFIX、PREFIX 或 (（或没有先前的标记），则运算符必须是 PREFIX。否则，运算符必须是 INFIX。我们可以在flex 使用两个开始条件：一个用于我们可能看到 CONSTANT 的情况，另一个用于我们不能合法地看到 CONSTANT 的情况。第一个是 INITIAL 状态。

这转化为以下小的 flex 描述：

%x FINAL
%%

<INITIAL>[-+]?[[:digit:]]+  {
                              BEGIN(FINAL); return CONSTANT;
                            }
<INITIAL>[[:alpha:]][[:alnum:]]* {
                              BEGIN(FINAL); return VARIABLE;
                            }
<INITIAL>[(]                  return yytext[0];
<INITIAL>[-]                  return PREFIX_MINUS;
<INITIAL>[+]                  return PREFIX_PLUS;

<FINAL>[)]                    return yytext[0];
<FINAL>[-+*/] BEGIN(INITIAL); return yytext[0];

<*>.                          /* Signal invalid token */

当然，这还不完整。它省略了 yylval 的设置和不属于表达式的输入处理（包括换行符和其他空格）。

尽管此解决方案有效，但很容易看出为什么首选将问题留给解析器：

%%
[-+*/()]                 return yytext[0];
[[:digit:]]+             return CONSTANT;
[[:alpha:]][[:alnum:]]*  return VARIABLE;

但有一个特殊情况需要小心处理。在 N-bit 2 的补码表示中，可以表示 -2^N 但它是无法表示 +2^N，因为最大正数是 2^N−1。如果有符号整数作为表达式延迟到解析器，那么允许整数 2^N 是至关重要的，即使它不适合正在使用有符号整数类型。

这可以通过使用无符号整数类型将整数值传递给解析器来实现，这反过来意味着解析器将需要检测溢出情况。

碰巧，不是 C 处理这种情况的方式，这导致了一个有趣的异常。在 C 中（如上所述），整型常量不包含符号； -2 是两个令牌。但是整数常量确实包括一个（隐式）类型，在十进制整数的情况下，它是可以保存常量值的最小 signed 整数类型。由于一元否定保留类型，结果是在 32 位机器上，-2147483648 是类型 long（或 long long），即使它可以表示为 int .这有时会引起混淆。

Flex：匹配 signed int 与 addition/subtraction

Flex: matching signed int vs addition/subtraction

regex

flex-lexer