Flex:匹配有符号整数与加法/减法

在词汇层面解决这个问题的困难是许多语言甚至没有尝试的原因。解析器可以很容易地区分一元前缀 + 或 - 操作符和二元中缀操作符具有相同的拼写,除了一个角大小写(见下文),两者之间没有真正的语义差异 -2 被视为前缀减号,后跟整数常量,以及 -2 被认为是单个令牌。在解析器中,如果不希望运算符出现在AST中,可以使用常量折叠来计算常量子表达式。

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

去掉这里不相关的运算符优先级和关联性,算术表达式的语法可以简化为如下:

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

(这省略了后缀运算符,包括函数调用和数组下标,但原理不受此影响。)

根据该语法,很容易导出FIRST、LAST和FOLLOW集合。 term 只能从终端开始,并且 expr 只能以 学期 ,因此它们都具有相同的FIRST集合:

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

通过类似的推理 学期 和 表达 也相同:

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

最后,根据观察到的 学期 仅出现在 表达 ,和 表达 位于输入的末尾,或出现在语法中,后跟一个终端:

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

(其中 $ 是输入标记的结尾。)

所有这些都让我们计算终端的FOLLOW集合,使用非终端V的LAST中的每个终端A只能跟在FOLLO(V)中的终端后面的观察结果。(在一些语法中,可能会高估FOLLOW集合,但在这种情况下并不重要。)这最终给了我们:

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

简而言之,前缀和INFIX永远不会出现在同一个上下文中。如果上一个令牌是INFIX、PREFIX或 ( (或者没有以前的标记),则运算符必须是前缀。否则,运算符必须是INFIX。我们可以使用两个开始条件在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 -位2的补码表示,可以表示-2 ^N 但不可能表示+2 ^N ,因为最大正数是2 ^N 1.如果有符号整数作为表达式延迟到解析器,那么整数2 ^N 即使它不适合正在使用的带符号整数类型。

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

碰巧 不 C如何处理这种情况,这导致了一个有趣的异常。在C(如上所述)中,整数常数不包括符号; -2 是两个代币。但是整数常量确实包含(隐式)类型,在十进制整数的情况下,该类型是最小的 签署 可以保存常量值的整数类型。由于一元否定保留了类型, -2147483648 属于类型 long (或 long long )即使它可以表示为 int 。这有时会引起混乱。

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

这应该管用