我已经开发了一种使用简单堆栈算法的方程式解析器,该算法将处理二进制(+,-,|,&,*,/等)运算符,一元(!)运算符和括号。
但是,使用此方法会使我拥有所有具有相同优先级的东西-尽管可以使用括号强制执行优先级,但不管运算符如何,它都是从左到右求值的。
因此,现在“ 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