查看原文有更好的格式:
http://www.ibaiyang.org/2012/08/03/parsing-expression-by-precedence-climbing/
摘自 Eli Bendersky’s website
就此问题,我之前讨论过使用递归下降解析器(recursive descent parsers),特别是当一门语言有多级运算优先级时。
有很多方法可以解决这个问题。在维基百科上的一篇文章提到了三种算法:Shunting Yard, top-down operator precedence (TDOP) and 优先爬山(precedence climbing)。今天的主题就是讲解一下第三种算法,因为它在实践中经常被用到。
优先爬山–目的
在了解优先爬山算法前,没有必要对其他表达式解析器算法熟悉。实际上,它是众多算法中最简单的。在详细讲述前,我先简单的说一下此算法欲实现的目的,之后,我再详细讲述,最后,贴出用python实现的代码。
此算法的基本思想是:一个表达式通常是由若干具有低优先级的子表达式构成。
一个简单的例子:
2 + 3 * 4 * 5 - 6
假设(+和-)和(*和/)分别的优先级是1,2【数字越大,优先级越大,故先运算】,那么我们有:
2 + 3 * 4 * 5 - 6
|---------------| : prec 1
|-------| : prec 2
三个数连乘的子表达式有最小的优先级2.整个表达式具有最小优先级1.
给一个稍微复杂的例子,此列中,包含指数运算,令其优先级为3:
2 + 3 ^ 2 * 3 + 4
|---------------| : prec 1
|-------| : prec 2
|---| : prec 3
结合律(Associativity)
二元运算符除了有优先级,同时也有结合律。譬如,同一级运算符中,具有左结合律的二元运算符从左向右运算;具有右结合律的二元操作符从右向左运算。
下面给出一些例子吧,例如加好(+)是左结合律,因此
2 + 3 + 4
和
(2 + 3) + 4
等价;另一方面,如指数运算(^)具有右结合律,因此
2 ^ 3 ^ 4
和
2 ^ (3 ^ 4)
等价。
当然,优先爬山算法能正确的处理结合律。
带有括号的子表达式
最后,我们知道,括号能够任意的组合子表达式,打破运算符号的优先级,例如:
2 * (3 + 5) * 7
爬山算法—如何奏效
首先,我们定义一些术语。元(atoms)可以是数字或则带有括号的子表达式。表达式(expression)是由元(atom)同二元运算符构成。
此算法是运算符驱动的。它基本的步骤就是读取下一个元和查看紧跟其后的运算符。如果后面的运算符优先级小于当前步骤的优先级,此算法返回;否则,他在一个循环中反复的调用自己去处理子表达式。
下面是伪代码:
compute_expr(min_prec):
result = compute_atom()
while cur token is a binary operator with precedence >= min_prec:
prec, assoc = precedence and associativity of current token
if assoc is left:
next_min_prec = prec + 1
else:
next_min_prec = prec
rhs = compute_expr(next_min_prec)
result = compute operator(result, rhs)
return result
每一次递归调用处理具有同一优先级运算符号构成的元的子表达式。
一个例子
让我们通过一个例子,对此算法有一个直观的认识吧。
2 + 3 ^ 2 * 3 + 4
算法从调用compute_expr(1)开始,因为1具有最小的优先级。下面是此例子的调用过程:
* compute_expr(1) # Initial call on the whole expression
* compute_atom() --> 2
* compute_expr(2) # Loop entered, operator '+'
* compute_atom() --> 3
* compute_expr(3)
* compute_atom() --> 2
* result --> 2 # Loop not entered for '*' (prec < '^') * result = 3 ^ 2 --> 9
* compute_expr(3)
* compute_atom() --> 3
* result --> 3 # Loop not entered for '+' (prec < '*') * result = 9 * 3 --> 27
* result = 2 + 27 --> 29
* compute_expr(2) # Loop entered, operator '+'
* compute_atom() --> 4
* result --> 4 # Loop not entered - end of expression
* result = 29 + 4 --> 33
处理优先级
注意到此算法针对每一个二元操作符进行一次递归调用。其中一些生命期非常的短—读取一个元(atom),然后直接返回,因为没有进入while循环(发生在第二步);另一些生命期比较长。初始调用compute_expr 将计算整个表达式。
while循环是一个必要的组成成分。它保证了当前compute_expr 会处理连续的同一优先级的操作符。
处理结合律
我认为,这个算法最吸引人的地方是它非常的简单,并且能够很好的处理结合律。不管什么情况下,此算法总是设置下一次调用的优先级是当前优先级,或则在此基础上加1。
我们举一个例子来看其如何处理的吧
8 * 9 * 10
^
|
箭头所指向的地方是compute_expr 运行到的位置,并且已经进入了while循环,此时prec=2.因为*是左结合律,故next_min_prec=2 + 1。在读入一个数据后,调用
compute_expr(3),看下一个*
8 * 9 * 10
^
|
因为*的优先级是2,然而min_prec等于3,所以没有进入while循环,直接返回。犹如
(8 * 9) * 10
相反,对于以下实例:
8 ^ 9 ^ 10
^的优先级是3,并且其是右结合律,所以min_prec是3,不会加一. 这就意味着在返回调用者之前,还会去读取下一个^运算符,犹如
8 ^ (9 ^ 10)
处理子表达式
伪代码没有解释如何处理带有括号的子表达式。考虑如下表达式:
2000 * (4 - 3) / 100
while循环没有很清楚的告诉如何处理这个问题。当然解决问题的关键是compute_atom。当它读入一个左括号时,它就知道有一个子表达式紧随其后,
所以它调用compute_expr 去处理这个子表达式(直到遇见右括号才返回),然后才将结果作为一个元(atom)返回给compute_atom。所以compute_expr
根本就没有感觉到括号的存在。
python实现
为了简单,它十分的短,你可以很轻松的将其扩展到你实际中的语言中。接下来我讲分几块来呈现这些实现方式。
开始我们需要拥有一个简单的tokenizer类去将文本分为tokens和保持一些状态。语法非常简单:数字,基本的运算符+,-,*,/,^和括号。
- Tok = namedtuple('Tok', 'name value')
-
- class Tokenizer(object):
-
-
-
-
-
- TOKPATTERN = re.compile("\s*(?:(\d+)|(.))")
-
- def __init__(self, source):
- self._tokgen = self._gen_tokens(source)
- self.cur_token = None
-
- def get_next_token(self):
-
-
- try:
- self.cur_token = self._tokgen.next()
- except StopIteration:
- self.cur_token = None
- return self.cur_token
-
- def _gen_tokens(self, source):
- for number, operator in self.TOKPATTERN.findall(source):
- if number:
- yield Tok('NUMBER', number)
- elif operator == '(':
- yield Tok('LEFTPAREN', '(')
- elif operator == ')':
- yield Tok('RIGHTPAREN', ')')
- else:
- yield Tok('BINOP', operator)
接下来,是compute_atom实现方式
- def compute_atom(tokenizer):
- tok = tokenizer.cur_token
- if tok.name == 'LEFTPAREN':
- tokenizer.get_next_token()
- val = compute_expr(tokenizer, 1)
- if tokenizer.cur_token.name != 'RIGHTPAREN':
- parse_error('unmatched "("')
- tokenizer.get_next_token()
- return val
- elif tok is None:
- parse_error('source ended unexpectedly')
- elif tok.name == 'BINOP':
- parse_error('expected an atom, not an operator "%s"' % tok.value)
- else:
- assert tok.name == 'NUMBER'
- tokenizer.get_next_token()
- return int(tok.value)
它处理元信息(在我们的例子中是整数),包括带有括号的子表达式。
然后是,compute_expr 的实现方式,和上面的伪代码十分的相识
-
- OpInfo = namedtuple('OpInfo', 'prec assoc')
-
- OPINFO_MAP = {
- '+': OpInfo(1, 'LEFT'),
- '-': OpInfo(1, 'LEFT'),
- '*': OpInfo(2, 'LEFT'),
- '/': OpInfo(2, 'LEFT'),
- '^': OpInfo(3, 'RIGHT'),
- }
-
- def compute_expr(tokenizer, min_prec):
- atom_lhs = compute_atom(tokenizer)
-
- while True:
- cur = tokenizer.cur_token
- if (cur is None or cur.name != 'BINOP'
- or OPINFO_MAP[cur.value].prec < min_prec):
- break
-
-
- assert cur.name == 'BINOP'
-
-
-
- op = cur.value
- prec, assoc = OPINFO_MAP[op]
- next_min_prec = prec + 1 if assoc == 'LEFT' else prec
-
-
-
- tokenizer.get_next_token()
- atom_rhs = compute_expr(tokenizer, next_min_prec)
-
-
- atom_lhs = compute_op(op, atom_lhs, atom_rhs)
-
- return atom_lhs
唯一不同的一点是这个代码非常明显的处理token信息。基本上是遵循“递归向下调用”原则。每一次递归调用只能获取当前的token,存放在tokenizer.cur_tok里,并且确保读取所有的tokens且被处理(通过不断的调用tokenizer.get_next_token()).
还有额外的一小块没有提到。compute_op 是简单的执行了数字运算:
- def compute_op(op, lhs, rhs):
- lhs = int(lhs); rhs = int(rhs)
- if op == '+': return lhs + rhs
- elif op == '-': return lhs - rhs
- elif op == '*': return lhs * rhs
- elif op == '/': return lhs / rhs
- elif op == '^': return lhs ** rhs
- else:
- parse_error('unknown operator "%s"' % op)
其他的资源
这里还有一些我发现的额外的资料
分享到:
相关推荐
表达式解析表达式解析表达式解析表达式解析表达式解析表达式解析
表达式表达式解析器表达式解析器表达式解析器表达式解析器表达式解析器
说明:网上找了一圈表达式解析引擎实现的功能都不够满足支持业务需求,于是自己造轮子实现了一个,包含了等式,不等式,逻辑运算,参数,函数的支持。功能应该能够满足所有的业务需求了,函数可自行扩展,有需要支持...
Java Cron表达式解析 翻译为中文和英文
开源表达式解析器,开源表达式解析器开源表达式解析器开源表达式解析器
在SourceForge上看到的一个Python写的表达式解析器 目前在研究它的代码
说明:网上找了一圈表达式解析引擎实现的功能都不够满足支持业务需求,于是自己造轮子实现了一个,包含了等式,不等式,逻辑运算,参数,函数的支持。功能应该能够满足所有的业务需求了,函数可自行扩展,有需要支持...
Cron Expression:一个cron表达式解析器
这可能是网上最完整的Cron表达式解析翻译方法。 JavaScript版-解释翻译Cron表达式(代码奉上)。 此方法分为JavaScript版和Java版本,有需要的朋友请根据自己需要下载。 希望我写的方法有帮助到你,不足之处请多多...
用Java写的Cron表达式解析, Java swing编写的简洁界面,表达式到界面,界面到表达式,实现双重解析
一个C#实现的简单表达式解析器,支持算符优先级、括号以及函数。 修正前一个上传版本存在的问题:算符优先级的错误。
VC++表达式解析(计算)工具源代码,由江汉石油学院计算机系的学生所编写。表达式中只能有圆括号、函数名、运算符、常数与变量。一、变量名的命名规则:1、可以是字符、或字符串;2、不能以数字开头;3、不能夹杂有...
delphi 教你如何做表达式解析器 词法分析器 语法分析器
C++实现计算器,最通俗易懂的版本, 支持括号和四则运算 ,功能完整可以直接使用使用波兰表达式进行转化。
很辛苦自己做的。不是很好,但是功能还是蛮强大的
算术表达式解析 逆波兰 递归 算术表达式解析 逆波兰 递归 算术表达式解析 逆波兰 递归
资源为js文件,下载后直接用script标签引入,需要解析时调用该js第一个方法,参数为cron定时器表达式字符串,例如:translateCRONToChinese("0 0 12 */1 * ?");
一个简单java表达式解析的程序,需要的可以参考
可以解析Cron表达式,个人有用希望你也有用。一个是例子,一个是代码实现,需要根据自己实现需求修改。
.net C# Cron表达式解析..可以解析Cron表达式,有例子也有实现,希望能帮助到需要的人,