具有不同类型数据的表达式语法

Question

我正在为处理向量的小型语言编写解释器。我正在使用 Flex 和 Bison。

向量使用以下符号声明：

v := <1.4, -2.2, 7>

因此，它们的分量也可以包含负数。这些向量上支持的运算是加法、减法和标量乘法。所以你不能添加一个向量和一个标量，你不能减去一个向量和一个标量，但是你可以将一个向量和一个标量相乘。

由于支持负数，我的词法分析器使用以下正则表达式来匹配数字：

[+-]?[0-9]+([.][0-9]+)? {yylval.somedub = atof(yytext); return NUMBER;}

当要解析如下格式的表达式时出现问题（加号当然是同样的问题）：

v-2*v

应该解析的方式是：vector minus (number times vector)。但是，一旦 flex 看到 -2，它就会将其解释为一个数字，所以我得到 vector (number) times vector，这当然是没有意义的。另一方面，如果你要写 v - 2*v 它工作正常，因为 - 和 2 之间有一个 space。我语法的表达式部分如下所示（我不打算复制整个代码，因为它很大）：

expression:
    expression '+' level_1
    | expression '-' level_1
    | level_1

level_1:
    NUMBER '*' level_1
    | level_1 '*' NUMBER
    | level_2

level_2:
    '(' expression ')'
    | vector //parses the whole <a, b, c, ..> notation, irrelevant for the problem

我还使用

将 +、- 和 * 声明为左关联

%left '+' '-'
%left '*'

那么我该如何解决这个问题呢？我不知道我是否需要以某种方式改变关联性或者重建整个语法。

有什么想法吗？

谢谢。

Answer 1

如果 -2 被识别为单个 NUMBER 标记，这意味着解析器会将 v-2 视为一个名称后跟一个数字，此时，实际上什么都没有你可以做得到你想要的解析。因此 -2 应该被识别为两个标记：一个减号后跟一个数字。

要实现这一点，您只需从数字的正则表达式中删除 [+-]?（我假设您已经有了自己识别 + 和 - 的规则） .

现在您只需要调整语法以允许 - 或 + 后跟一个数字（或者任何表达式，如果您还想允许 -v 或 -(2+3)).

具有不同类型数据的表达式语法

Expression grammar with different types of data

bison

context-free-grammar

flex-lexer