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

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

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

尽管这适用于当前项目,但我想拥有一个通用例程,可以用于以后的项目。

为清楚起见进行了编辑:

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

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

语法:

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

语言:

我正在用C进行此操作,但是我对算法感兴趣,而不是对特定语言的解决方案感兴趣。 C足够低,因此如果需要,可以很容易地转换为另一种语言。

代码示例

我在上面发布了我正在谈论的test code for the simple expression parser。项目需求发生了变化,因此我不需要针对性能或空间进行代码优化,因为它没有合并到项目中。它采用原始的冗长形式,应该易于理解。如果我根据运算符优先级对其做任何进一步的处理,我可能会选择the macro hack,因为它简单地匹配了程序的其余部分。但是,如果我在实际项目中使用过它,那么我将寻求一个更紧凑/更快速的解析器。

相关问题


  Smart design of a math parser?


-亚当

最佳答案

艰难的道路

您需要一个recursive descent parser

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

1+11*5


要手动执行此操作,您必须先阅读1,然后查看加号并开始一个以11开头的全新递归解析“会话” ...并确保将11 * 5解析为其自身的因子,生成带有1 + (11 * 5)的解析树。

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

简单(正确)的方式

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

Download 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可能会显得过大,但是当需要进行更改或需要添加功能时,脱离分析器+评估器可能会带来麻烦。您的情况会有所不同,您将需要运用自己的判断力;只是不要punish other people for your sins [2]并构建一个不够完善的工具。

我最喜欢的解析工具

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

笔记:

1理查德·斯托曼(Richard Stallman)在Why you should not use 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

10-07 19:36
查看更多