具有优先级的方程式（表达式）解析器？

小编典典

具有优先级的方程式（表达式）解析器？

algorithm

我已经开发了一种使用简单堆栈算法的方程式解析器，该算法将处理二进制（+，-，|，＆，*，/等）运算符，一元（！）运算符和括号。

但是，使用此方法会使我拥有所有具有相同优先级的内容-尽管可以使用括号强制执行优先级，但不管运算符如何，它都是从左到右进行求值的。

因此，现在“ 1 + 11 * 5”返回60，而不是人们期望的56。

虽然这适合当前项目，但我希望有一个通用例程，可以用于以后的项目。

为清楚起见进行了编辑：

解析具有优先级的方程的最佳算法是什么？

我对一些易于实现的东西感兴趣，并且了解我可以自己编写代码，以避免可用代码出现许可问题。

语法：

我不懂语法问题-我是用手写的。很简单，我认为不需要YACC或Bison。我只需要使用诸如“ 2 + 3 *（42/13）”之类的方程式来计算字符串。

语言：

我正在用C进行此操作，但是我对算法感兴趣，而不对特定于语言的解决方案感兴趣。C足够低，可以根据需要轻松转换为另一种语言。

代码示例

我在上面发布了简单表达式解析器的测试代码。项目需求发生了变化，因此由于性能或空间没有合并到项目中，因此我不需要优化代码。它采用原始的冗长形式，应该易于理解。如果我根据运算符优先级对其做任何进一步的处理，我可能会选择宏技巧，因为它可以简单地与程序的其余部分匹配。但是，如果我在真实的项目中使用过它，我将寻求一个更紧凑/更快速的解析器。

阅读 362

2020-07-28

共1个答案

小编典典

艰难的道路

您需要递归下降解析器。

要获得优先权，您需要进行递归思考，例如，使用示例字符串，

1+11*5

要手动执行此操作，您必须先阅读1，然后查看加号并从…开始以全新的方式进行递归解析“会话”，11并确保将解析11 * 5为自己的因子，并生成带有的解析树1 + (11 * 5)。

即使尝试解释，这一切都让人感到非常痛苦，尤其是在C变得更加无能为力的情况下。请参见，在解析11之后，如果*实际上是+，则必须放弃尝试创建术语并改为解析C的尝试。11本身就是一个因素。我的头已经爆炸了。递归的体面策略是可能的，但是有更好的方法…

简单（正确）的方式

如果您使用像Bison这样的GPL工具，那么您可能不必担心许可问题，因为bison生成的C代码未包含在GPL中（IANAL，但我敢肯定，GPL工具不会强制GPL在生成的代码/二进制文件；例如，Apple用GCC编译了诸如Aperture之类的代码，他们无需GPL所说的代码就可以出售它）。

下载Bison（或等效的工具，ANTLR等）。

通常有一些示例代码，您可以在其上运行bison并获得所需的C代码，以演示这四个功能的计算器：

http://www.gnu.org/software/bison/manual/html_node/Infix-
Calc.html

查看生成的代码，发现这并不像听起来那样简单。同样，使用像Bison这样的工具的优点是：1）学到一些东西（特别是如果您阅读了Dragon书籍并学习了语法），2）避免了NIH尝试重新发明轮子。使用真正的解析器生成器工具，您实际上希望以后可以扩展，向其他人展示解析器是解析工具的领域。

更新：

这里的人们提供了很多合理的建议。我唯一不跳过解析工具或仅使用Shunting
Yard算法或手推递归递归解析器的警告是，玩具语言1可能有一天会变成具有功能（正弦，余弦，对数）以及变量，条件和条件的大型实际语言。循环。

对于小型，简单的解释器而言，Flex /
Bison可能会显得过大，但是当需要进行更改或添加功能时，脱离分析器+评估器可能会带来麻烦。您的情况会有所不同，您将需要运用自己的判断力；只是不要为自己的罪行惩罚别人
[2]并建立一个不够充分的工具。

我最喜欢的解析工具

世界上最好的工具是Parsec库（用于递归的体面解析器），该库随附了编程语言Haskell。它看起来很像BNF，或者像某种专用工具或领域特定的语言进行解析（示例代码[3]），但实际上它只是Haskell中的一个常规库，这意味着它与其余的编译步骤相同，您可以编写任意的Haskell代码并在解析器中调用它，也可以
在同一代码中 混合和匹配其他所有
库。（顺便说一下，将这样的解析语言嵌入Haskell之外的语言中会导致大量的语法混乱。我在C＃中做到了这一点，并且效果很好，但不是那么简洁。）

笔记：

1
Richard Stallman在“ 为什么不应该使用Tcl”中说

Emacs的主要教训是扩展语言不应该仅仅是“扩展语言”。它应该是一种真正的编程语言，旨在编写和维护大量程序。因为人们会想要这样做！

[2]是的，使用该“语言”让我永远感到害怕。

还要注意，当我提交此条目时，预览是正确的，但是 SO不足以解析我在第一段中的紧密锚标签
，证明解析器不是一件容易的事，因为如果您使用正则表达式和一些hacks， 那么您可能会出现一些细微的错误 。

[3]使用Parsec的Haskell解析器的代码段：一个四函数计算器，扩展了指数，括号，用于乘法的空白和常量（如pi和e）。

aexpr   =   expr `chainl1` toOp
expr    =   optChainl1 term addop (toScalar 0)
term    =   factor `chainl1` mulop
factor  =   sexpr  `chainr1` powop
sexpr   =   parens aexpr
        <|> scalar
        <|> ident

powop   =   sym "^" >>= return . (B Pow)
        <|> sym "^-" >>= return . (\x y -> B Pow x (B Sub (toScalar 0) y))

toOp    =   sym "->" >>= return . (B To)

mulop   =   sym "*" >>= return . (B Mul)
        <|> sym "/" >>= return . (B Div)
        <|> sym "%" >>= return . (B Mod)
        <|>             return . (B Mul)

addop   =   sym "+" >>= return . (B Add) 
        <|> sym "-" >>= return . (B Sub)

scalar = number >>= return . toScalar

ident  = literal >>= return . Lit

parens p = do
             lparen
             result <- p
             rparen
             return result

2020-07-28