c - 运行时公式评估

Question

我想评估用户可以为许多数据点输入的公式，因此效率是一个问题。这是一个 Fortran 项目，但到目前为止，我的解决方案一直集中在使用 yacc/bison 语法上，因此我可能会使用 Fortran 的 iso_c_binding 功能来连接 yyparse()。

首选(到目前为止)的解决方案是对 Bison 手册中的经典 mfcalc 计算器示例的一个小扩展，同时使 bison 语法也能识别(单个)变量名(这并不难)。

问题是在可执行语句中做什么。我在那里看到两个选项。

首先，我可以像在 mfcalc 示例中那样简单地计算表达式的解析值。

其次，我可以调用一次 bison 解析器来解析和创建被解析公式的基于堆栈(逆向抛光)的表示，所以2 + 3*x 会被翻译成 2 3 * + (当然，作为相关的数据结构)。

语法的相关部分如下所示:

%union {
    double val;
    char *c;
    int fcn;
  }

%type <val> NUMBER
%type <c> VAR
%type <fcn> Function

/* Tokens and %left PLUS MINUS etc. left out for brevity */

%%
...

Function:
      SIN     { $$=SIN; }
      | COS     { $$=COS; }
      | TAN     { $$=TAN; }
      | SQRT    { $$=SQRT; }

Expression:
      NUMBER { push_number($1); }
      | VAR  { push_var($1); }
      | Expression PLUS Expression { push_operand(PLUS); }
      | Expression MINUS Expression { push_operand(MINUS); }
      | Expression DIVIDE Expression { push_operand(DIVIDE); }
      | MINUS Expression %prec NEG { push_operand(NEG); }
      | LEFT_PARENTHESIS Expression RIGHT_PARENTHESIS;
      | Function LEFT_PARENTHESIS Expression RIGHT_PARENTHESIS { push_function($1); }
      | Expression POWER Expression { push_operand(POWER); }

函数 push_... 会将公式放入一个结构数组中，其中包含一个包含 token 和 yacc union 的结构。

然后 RPN 将使用一个非常简单(并且希望是快速)的解释器进行解释。

所以，问题。

第二种方法有效吗？我认为这是根据我对 bison(或 yacc)处理移位和减少的方式的理解(基本上，这将移动一个数字并减少一个表达式，所以应该保证顺序是正确的RPN)，但我不太确定。

此外，与使用 $$ 构造(第一种方法)简单地评估函数相比，是否值得付出额外的努力？

最后，还有其他更好的解决方案吗？我曾考虑过使用语法树，但我认为额外的努力实际上不值得。此外，我倾向于认为使用树是矫枉过正的，因为数组可以很好地完成 :-)

Answer 1

与 RPN 相比，生成三地址虚拟操作只是稍微困难一点。实际上，RPN 是一个虚拟堆栈机。三地址操作——也可以很容易地进入一个数组——可能解释起来更快，而且从长远来看可能会更灵活。

将表达式解析为某种内部形式的主要优点是，评估内部形式可能比重新解析原始字符串更快。情况可能并非如此，但通常是因为将浮点文字转换为 float (相对而言)相当慢。

还有一种中间情况，将表达式标记化(放入数组)，然后在解析标记流时直接求值。 (实际上，这使 bison 成为您的虚拟机。)

这些策略中哪一个是最好的在很大程度上取决于您的用例的细节，但它们都不难，因此您可以尝试所有这三种策略并进行比较。