PythonTip >> 博文 >> 杂项其他

【翻译】通过优先爬山算法解析表达式

zihua 2013-09-26 01:09:55 点击: 1494 | 收藏


摘自 Eli Bendersky’s website

就此问题,我之前讨论过使用递归下降解析器(recursive descent parsers),特别是当一门语言有多级运算优先级时。

有很多方法可以解决这个问题。在维基百科上的一篇文章提到了三种算法:Shunting Yard, top-down operator precedence (TDOP) and 优先爬山(precedence climbing)。今天的主题就是讲解一下第三种算法,因为它在实践中经常被用到。

优先爬山–目的

在了解优先爬山算法前,没有必要对其他表达式解析器算法熟悉。实际上,它是众多算法中最简单的。在详细讲述前,我先简单的说一下此算法欲实现的目的,之后,我再详细讲述,最后,贴出用python实现的代码。

此算法的基本思想是:一个表达式通常是由若干具有低优先级的子表达式构成。

一个简单的例子:

摘自 Eli Bendersky’s website

就此问题,我之前讨论过使用递归下降解析器(recursive descent parsers),特别是当一门语言有多级运算优先级时。

有很多方法可以解决这个问题。在维基百科上的一篇文章提到了三种算法:Shunting Yard, top-down operator precedence (TDOP) and 优先爬山(precedence climbing)。今天的主题就是讲解一下第三种算法,因为它在实践中经常被用到。

优先爬山–目的

在了解优先爬山算法前,没有必要对其他表达式解析器算法熟悉。实际上,它是众多算法中最简单的。在详细讲述前,我先简单的说一下此算法欲实现的目的,之后,我再详细讲述,最后,贴出用python实现的代码。

此算法的基本思想是:一个表达式通常是由若干具有低优先级的子表达式构成。

一个简单的例子:

详细阅读:http://www.ibaiyang.org/2012/08/03/parsing-expression-by-precedence-climbing/

原文链接:http://www.simple-is-better.com/news/929

作者:zihua | 分类: 杂项其他 | 标签: 无 | 阅读: 1494 | 发布于: 2013-09-26 01时 |