pratt parser - Githubissues

资料来源

算法本身

对于该top-down 算法，对应于token都有关联的函数，一个称之为nud，另一个称之为led，和2个整数值，称之为lbp和rbp。nud函数在语言构造的右边，led函数则是token出现在语言构造的左边。

def expression(rbp = 0):
    global token
    t = token
    token = next()
    left = t.nud()
    // token的左结合能力大于整个表达式的右结合能力
    // 那么先计算内部优先级高的表达式
    while rbp < token.lbp:
        t = token
        token = next()
        left = t.led(left)
    return left

left变量是表示the left part of the expression，rbp表示作为结合成为右操作数的能力。对于 1 + 2 3， + rbp 小于 *的lbp，对于上面的算法，while rbp < token. lbp这句，表示2 作为 *号的一项，而不是作为 + 号的被加项。上面while语句内循环，针对1 + 2 3的意思是，2*3先计算，然后作为加法运算的另一项。下面的表达式箭头的每一项表示rbp consume token的范围。

对于 1 + 2这个表达式，定义如下几个表达式

class literal_token:
    def __init__(self, value):
        self.value = value
    def nud(self):
        return self.value
class operator_add_token:
    lbp = 10
    def led(self, left):
        right = expression(10)
        return left + right
class end_token:
    lbp = 0
import re
token_pat = re.compile("\s*(?:(\d+)|(.))")
def tokenize(programe):
    if number, operator in token_pat.findall(program):
        if number():
            yield literal_token(number)
        elif operator == "+":
            yield operator_add_token()
        else:
            raise SyntaxError("unknown error")
    yield end_token()
def parse(progame):
    global token, next
    next = tokenize(programe).next
    token = next()
    return expression

我们看到定义了nud和operator_add_token对应的nud和led

BruceChen7 / gitblog

pratt parser #17

资料来源

算法本身