写篇笔记记录一下对 pratt parsing 的心智模型，这玩意需要的代码量很少，但理解难度上天，给我看了快两三天才稍微有点明白，还是得做点笔记记录一下，这大概是我回炉次数最多的笔记，反反复复调整代码结构和文字描述以保证清晰……最终效果还是比较满意的。感觉应上了那句老话——先把书读厚，再把书读薄。

关于 pratt parsing 的实际业务流程，主要是参考了这篇文章。建立心智模型时部分地采用了这篇文章的 BP 概念，但没有使用 BP 表示结合性，因此要求运算符两边的 BP 是相同的，因此 BP 在这里实际上就是所谓的优先级。另外这篇文章的实现过于难懂了，loop 里面的各种 break 试图搅拌我的脑子，但实际的业务流程是能够更简单地去表示的。

关于 parselet，主要是参考了这篇文章，但并没有上来就引入 parselet 的概念，发现那样操作实在有点让人难懂…而且这篇文章没有提及前缀运算符的优先级。

循序渐进，首先实现对优先级的支持，然后是结合性的支持；然后，依次添加前缀，后缀，括号，取数组，三目的支持；这时代码已经乱成渣滓了，因此进行相应抽象，引入 parselet 的概念，将各运算符的逻辑抽离出来，再次实现之前已经实现的部分；最后另外使用栈去实现一下四则运算表达式的计算，因为其思想和 pratt 是基本一致的，而我之前从来没理解过那玩意是怎么操作。

完整的实现代码在最后。

pratt parsing，即自顶向下算符优先解析法，是一种特别适用于解析表达式的解析法，它能轻易地使用表去表示各算符的优先级和结合性，同时也能够很容易引入各种复杂的算符比如三目，数组索引等。理解 pratt parsing 我感觉有两个关键：

读取任意表达式时，根据 token 出现的位置和 token 的类型，我们马上就能识别出它是什么类型，属于哪个语法树节点，比如1 + 2，读到1后，我们马上就能知道这将是某操作符的左操作数，接下来要读一个中缀操作符（如果没到 EOF 的话）；比如-1 + 2，看到一个-，我们马上就知道这是一个前缀操作符，后面要读一个表达式
（这点是 pratt parsing 的精髓吧？）在尝试获取某操作符的右操作数的时候，对于可能的右操作数，只需要比较它右边的操作符的优先级和该操作符的优先级即可确认它是该操作符的右操作数还是它右边操作符的左操作数。这么说有点晦涩，但这个性质造成的特性是，某操作符的右操作数，是该操作符右边所有优先级高于该操作符的部分，获取这部分后就能为该操作符建立语法树；如果该操作符右边的第一个操作符的优先级比自己低，那右操作数就是下一个 token，马上就可以建立相应的语法树，这是说，1 + 2 * 3 ^ 4 * 5 + 6 = (1 + (2 * 3 ^ 4 * 5)) + 6，而1 * 2 - 1 = (1 * 2) - 1 ，理解这一点，就能够理解下面的第一版 pratt

优先级

先无视结合性，且只考虑中缀操作符。考虑下面的表达式，^为指数运算，优先级比*高：

1	`1 + 2 * 3 ^ 4`

如何解析它呢？作为人类，我们知道，^优先级最高，所以先把3 ^ 4 括起来，* 优先级次之，所以再把2 * (3 ^ 4) 括起来，然后是+，然后是@（假设它优先级比+低），总之添加括号是这个顺序：

1 + 2 * 3 ^ 4 @ 5
1 + 2 * (3 ^ 4) @ 5
1 + (2 * (3 ^ 4)) @ 5
(1 + (2 * (3 ^ 4))) @ 5
((1 + (2 * (3 ^ 4))) @ 5)

但计算机不是人，更擅长从左往右看，模仿计算机该怎样进行操作呢？首先把优先级规定一下，规定@，+，*，^优先级分别为 1，2，3，4，然后把优先级标在操作数和操作符之间：

1 2	`1 + 2 * 3 ^ 4 @ 5 + 6 * 7 2 2 3 3 4 4 1 1 2 2 3 3`

假装自己是计算机，从左往右读，首先看到1和+，马上能够明白，1 是 + 的左操作数，于是，现在的问题是找到 + 的右操作数。

但这里已知1要和+结合，所以这里可以预先加上一个(（别真加！）：

1 2	`(1 + 2 * 3 ^ 4 @ 5 + 6 * 7 2 2 3 3 4 4 1 1 2 2 3 3`

加一个括号表示建立了部分语法树节点，第一个 token 是左操作数，第二个 token 是操作符。

继续读，发现读到一个2，后面跟着一个*。然后这时候就要问，2是+的右操作数吗，或者说，2和+结合吗？不是，*的优先级高于+，所以2将首先和*结合。

ok，知道 2 要和*结合，我们首先可以在+ 的右边加上一个(了：

1 2	`(1 + (2 * 3 ^ 4 @ 5 + 6 * 7 2 2 3 3 4 4 1 1 2 2 3 3`

光看 2 * 3 ^ 4 @ 5，我们已经读到2和*，现在的问题是找到 * 的右操作数。能直接猴急地马上把2 * 3 给括起来吗？不行，这需要首先确认3 要和 * 结合，我们继续读，发现3右边是个^，^优先级高于*，所以 3 和^结合，又得在*的右边再括一个括号了：

1 2	`(1 + (2 * (3 ^ 4 @ 5 + 6 * 7 2 2 3 3 4 4 1 1 2 2 3 3`

光看 3 ^ 4 @ 5，已经读到了3和^，现在的问题是找到 ^ 的右操作数，需要确认4是否是和^结合，能发现4右边是@，优先级比^低，所以4和^结合，我们找到了^的右操作数。

找到了^的左右操作数，我们可以建立^相应的语法树节点了：

1	`(1 + (2 * (3 ^ 4) @ 5 + 6 * 7`

一对括号表示创建了一个完整的语法树节点，在这里我们为3 ^ 4创建了相应语法树节点。

把3 ^ 4 括起来后，我们又发现我们找到了*的右操作数了（即语法树节点3 ^ 4），我们可以建立*相应的语法树节点了：

1	`(1 + (2 * (3 ^ 4)) @ 5 + 6 * 7`

把 2 * (3 ^ 4) 括起来，我们又发现这个节点是+ 的右操作数了。

这就回答了上面的第一个问题——求+ 的右操作数，求了+的右操作数之后，再做什么？当然是再建立+相应的语法树节点了，再括一个：

1	`(1 + (2 * (3 ^ 4))) @ 5 + 6 * 7`

问的第一个问题已经被回答了，但解析还没结束——建立了语法树(1 + (2 * (3 ^ 4)))，但还有 @ 5 + 6 * 7没处理呢。将已经处理完的语法树写作 X（它已经是“原子”的了），现在表达式写作：

1 2	`X @ 5 + 6 * 7 1 1 2 2 3 3`

问题又变为解析该表达式。从左往右读，首先看到 X 和@，我们又开始问问题了，@的右操作数是什么……

再考虑另一个表达式，1 + 2 + 3 + 4，它读到一个 1，给它暂存作为 X：

1
2
3

X + 2 + 3 + 4
  ^
where x = 1

然后继续读，读到一个+，马上明白，X 是+的左操作数，于是问，+的右操作数是什么？往前一看，是2，ok，建立语法树(X + 2)，并再次命名为 X：

1
2
3

X + 3 + 4
  ^
where x = (1 + 2)

然后继续……

1
2
3

X + 4
^
where x = ((1 + 2) + 3)

后面不用描述了，注意这操作和在递归下降法中解析左结合的操作符是基本一样的。

如何理解特定某一趟的行为呢？可以认为，每一次求右操作数时，它把所有高于上一操作符优先级的部分全都给括起来了，然后当成黑箱返回过来：

对于 1 + 2 * 3 ^ 4 @ 5 + 6 * 7 @ 1

          3 ^ 4
     2 * -------         * 7
1 + ------------     + 6
                 @ 5         @ 1

求到右操作数后，建立语法树，把当前结果暂存，继续进行该操作（就像一个循环）：

           * 7
       + 6 ---
X @ 5 --------  @ 1

能发现，在寻找右操作数时，所有优先级比该操作符高的操作符及相关操作数会作为右操作数的一部分，比如1 + 2 * 3 ^ 4 @ 5，能直接发现+的右操作数是(2 * 3 ^ 4)，而对于1 + 2 @ 3，右操作数是 2。

能发现，只需要记住上一个操作符的优先级，我们能从表达式的任意位置开始进行解析。

伪代码表示或许会是这样（假设这里是解析它，因此目标是生成 AST）：

def algo(lexer, lastOp = ZERO_PRECEDENCE_OP):
  x = Expr.Literal(lexer.nextAtom())
  while currentOpPrecedenceHigherThan(lastOp):
    op = lexer.nextOp()
    right = algo(lexer, op)
    x = Expr.Binary(op, x, right)
  return x

algo 的行为是解析表达式中优先级高于特定优先级的部分。lastOp 的缺省值 ZERO_PRECEDENCE_OP 怎么理解呢？约定所有操作符的优先级都大于 0，因此初始的上一个操作符设为 0 就能保证把整个表达式都读进去了，也就是说对于第一趟 algo，while 的条件总为真。

代码实现

为了学习方便，定义一个很糙的 Lexer，规定所有 Token 均为单字符，Atom 形如/[a-zA-Z0-9]/，其它的认为是 Op。

type AtomToken = {type: 'ATOM', value: string}
type OpToken = {type: 'OP', op: string}
type EofToken = { type: 'EOF' }
type Token = AtomToken | OpToken | EofToken

function tokenMatch<T>(token: Token, fn: Partial<{ATOM: (t: AtomToken) => T, OP: (t: OpToken) => T, EOF: (t: EofToken) => T}>) {
  if (!fn[token.type]) {
    throw new Error(`pattern match failed, type: ${token.type}`)
  }
  return (fn[token.type] as any)(token)
}

type Lexer = {
  next(): Token,
  peek(): Token,
  nextAtom(): AtomToken
  nextOp(): OpToken
  peekAtom(): AtomToken,
  peekOp(): OpToken
  isAtEnd(): boolean
}

function mkLexer(source: string): Lexer {
  const tokens = source.split('').filter(c=>!/\s/.test(c))
    .map<Token>(c => /[a-zA-Z0-9]/.test(c) ? { type: 'ATOM', literal: c } : { type: 'OP', op: c})
  function assertTokenType(token: Token, type: Token['type']): any {
    if (token.type != type) {
      throw new Error(`Expect ${type}, got ${token.type}`)
    }
    return token
  }
  function next() {
    return tokens.shift() ?? { type: 'EOF' }
  }
  function peek() {
    return tokens[0] ?? { type: 'EOF' }
  }
  return {
    next,
    peek,
    nextAtom() {
      return assertTokenType(next(), 'ATOM')
    },
    nextOp() {
      return assertTokenType(next(), 'OP')
    },
    peekAtom() {
      return assertTokenType(peek(), 'ATOM')
    },
    peekOp() {
      return assertTokenType(peek(), 'OP')
    },
    isAtEnd() {
      return tokens.length == 0
    }
  }
}

type Expr = ({
  type: 'LITERAL', value: AtomToken
} | {
  type: 'BINARY', op: OpToken, left: Expr, right: Expr
}) & { toString(): string }

function mkBinary(op: OpToken, left: Expr, right: Expr): Expr {
  return {type: 'BINARY', op, left, right, toString() {
    return `(${left.toString()} ${op.op} ${right.toString()})`
  }}
}
function mkLiteral(value: AtomToken): Expr {
  return { type: 'LITERAL', value, toString() { return value.value } }
}

然后，实现上面的 algo 函数，这里为它取名叫 expr，这里同时定义了各运算符的优先级，获取优先级的函数同时要传入操作符的位置，因为同一个操作符在不同位置可以拥有不同优先级：

type OpDef = {token: OpToken, precedence: number, assoc: 'L' | 'R', position: 'postfix' | 'infix' | 'prefix'}
const ZERO_OP_DEF: OpDef = { precedence: 0, assoc: 'L', position: 'infix', token: { type: 'OP', op: 'ZERO' } }
function opDef(token: OpToken, position: OpDef['position']): OpDef {
  function mkOpDef(precedence: number, assoc: OpDef['assoc']): OpDef {
    return {token, precedence, assoc, position}
  }
  switch (position) {
    case 'infix':
      switch (token.op) {
        case 'ZERO': return ZERO_OP_DEF
        case '@': return mkOpDef(1, 'L')
        case '-': case '+': return mkOpDef(2, 'L')
        case '*': case '/': return mkOpDef(3, 'L')
        case '^': return mkOpDef(4, 'R')
      }
      break
  }
  throw new Error(`unknown ${position} operator: ${token.op}`)
}

function precedenceHigherThan(lexer: Lexer, lastOp: OpDef): boolean {
  if (lexer.isAtEnd()) {
    return false
  }
  const currentOp = opDef(lexer.peekOp(), 'infix')
  return currentOp.precedence > lastOp.precedence
}

function expr(lexer: Lexer, lastOpDef: OpDef = ZERO_OP_DEF): Expr {
  let x = mkLiteral(lexer.nextAtom())
  while (precedenceHigherThan(lexer, lastOpDef)) {
    const op = lexer.nextOp()
    const right = expr(lexer, opDef(op, 'infix'))
    x = mkBinary(op, x, right)
  }
  return x
}

const parseAndPrint = (str: string) => console.log(expr(mkLexer(str)).toString())

parseAndPrint("1") // 1
parseAndPrint("1 + 2") // (1 + 2)
parseAndPrint("1 + 2 * 3") // (1 + (2 * 3))
parseAndPrint("1 + 2 * 3 ^ 4") // (1 + (2 * (3 ^ 4)))
parseAndPrint("1 + 2 * 3 ^ 4 @ 5") // ((1 + (2 * (3 ^ 4))) @ 5)
parseAndPrint("1 + 2 @ 3") // ((1 + 2) @ 3)

结合性

优先级能处理了，那结合性呢？看看当前的实现的结合性是怎样的：

1 2	`parseAndPrint("1 + 2 + 3") // ((1 + 2) + 3) parseAndPrint("1 ^ 2 ^ 3") // ((1 ^ 2) ^ 3)`

看上去是左结合，将优先级检查中currentOp.precedence > op.precedence的>改为>=能得到右结合的结果，因此，只需要调整比较优先级的逻辑即可实现结合性：

function precedenceHigherThan(lexer: Lexer, lastOp: OpDef): boolean {
  if (lexer.isAtEnd()) {
    return false
  }
  const currentOp = opDef(lexer.peekOp(), 'infix')
  if (currentOp.precedence != lastOp.precedence) {
    return currentOp.precedence > lastOp.precedence
  }
  if (currentOp.assoc != lastOp.assoc) {
    throw new Error(`同一优先级两运算符 ${currentOp.token.op}, ${lastOp.token.op} 有不同结合性！`)
  }
  // 对于 1 + 2 + 3，+是左结合，认为右边（current）的+优先级小于左边（last）的+
  // 所以左结合要返回 false
  return currentOp.assoc === 'L' ? false : true
}

parseAndPrint("1 + 2 + 3") // ((1 + 2) + 3)
parseAndPrint("1 ^ 2 ^ 3") // (1 ^ (2 ^ 3))

前缀操作符

然后实现前缀和中缀操作符，关于这两种操作符的性质，参考一下 js 的相关文档，一般来说前缀和中缀的操作符的优先级都要比中缀的高。

如何理解前缀运算符？前缀运算符就像是一个没有左操作符的中缀操作符，比如-1 + 2，理解为X - 1 + 2，前缀运算符也有其优先级，它优先级比幂运算低，也就是说-2 ^ 3 = - (2 ^ 3)。要处理前缀运算符，需要修改第一次读取 x 时的逻辑——如果为 op，走前缀运算符逻辑，否则走原逻辑：

// 添加新 Expr Prefix……
function opDef(token: OpToken, position: OpDef['position']): OpDef {
  function mkOpDef(precedence: number, assoc: OpDef['assoc']): OpDef {
    return {token, precedence, assoc, position}
  }
  switch (position) {
    case 'prefix':
      switch (token.op) {
        case '-': case '+': return mkOpDef(4, 'R')
      }
      break;
    case 'infix':
      /* ... */
      break;
  }
  throw new Error(`unknown ${position} operator: ${token.op}`)
}

function expr(lexer: Lexer, lastOpDef: OpDef = ZERO_OP_DEF): Expr {
  let x = tokenMatch(lexer.next(), {
    ATOM(t) {
      // 原逻辑
      return mkLiteral(t)
    },
    OP(op) {
      const def = opDef(op, 'prefix')
      return mkPrefix(op, expr(lexer, def))
    }
  })
  while (precedenceHigherThan(lexer, lastOpDef)) {
    const op = lexer.nextOp()
    const right = expr(lexer, opDef(op, 'infix'))
    x = mkBinary(op, x, right)
  }
  return x
}

实践可以发现，前缀操作符的优先级只会改变它右边的表达式的解析顺序，它不关心当前的 lastOp。同时，前缀操作符的结合性是无关紧要的——无论是什么结合性，它本质上都得走右结合。

后缀操作符

后缀操作符和中缀操作符其实形式一致，它们均是先读了左操作数，再根据当前操作符决定进一步操作，如果是加减乘除等，就走相应中缀逻辑，如果是阶乘!，就走相应后缀的逻辑……为了实现方便，这里要求后缀操作符和中缀操作符不能重复（这也没啥问题，有哪个语言这个是重复的？）。规定阶乘的优先级要高于^。

因为在检测操作数后的操作符时，中缀和后缀操作符都可能会出现，所以 opDef 函数需要允许返回 null，在没找到相应操作符时不直接失败：

function opDef(token: OpToken, position: OpDef['position']): OpDef | null {
  function mkOpDef(precedence: number, assoc: OpDef['assoc']): OpDef {
    return {token, precedence, assoc, position}
  }
  switch (position) {
    case 'prefix':
      switch (token.op) {
        case '-': case '+': return mkOpDef(4, 'L')
      }
      break
    case 'infix':
      switch (token.op) {
        case 'ZERO': return ZERO_OP_DEF
        case '@': return mkOpDef(1, 'L')
        case '-': case '+': return mkOpDef(2, 'L')
        case '*': case '/': return mkOpDef(3, 'L')
        case '^': return mkOpDef(5, 'R')
      }
      break
    case 'postfix':
      switch (token.op) {
        case '!': return mkOpDef(7, 'R')
      }
  }
  return null
}

然后，修改检查优先级的函数，获取当前操作符时同时检查中缀和后缀；如果没有获取到当前操作符的定义，返回 false，这样设计在后面会看到好处。然后修改 expr 函数，根据操作符的性质把业务分发给相应的代码块：

function precedenceHigherThan(lexer: Lexer, lastOp: OpDef): boolean {
  if (lexer.isAtEnd()) {
    return false
  }
  const currentOp = opDef(lexer.peekOp(), 'infix') ?? opDef(lexer.peekOp(), 'postfix')
  if (currentOp == null) {
    return false
  }
  if (currentOp.precedence != lastOp.precedence) {
    return currentOp.precedence > lastOp.precedence
  }
  if (currentOp.assoc != lastOp.assoc) {
    throw new Error(`同一优先级两运算符 ${currentOp.token.op}, ${lastOp.token.op} 有不同结合性！`)
  }
  // 对于 1 + 2 + 3，+是左结合，认为右边（current）的+优先级小于左边（last）的+
  // 所以左结合要返回 false
  return currentOp.assoc === 'L' ? false : true
}

function expr(lexer: Lexer, lastOpDef: OpDef = ZERO_OP_DEF): Expr {
  let x = tokenMatch(lexer.next(), {
    ATOM(t) {
      return mkLiteral(t)  // 原逻辑
    }, 
    OP(op) {
      const def = opDef(op, 'prefix')
      if (!def) {
        throw new Error(`unknown prefix op: ${def}`)
      }
      return mkPrefix(op, expr(lexer, def))
    }
  })
  while (precedenceHigherThan(lexer, lastOpDef)) {
    const op = lexer.nextOp()
    const infixOpDef = opDef(op, 'infix')
    const postfixOpDef = opDef(op, 'postfix')
    // 如果是中缀
    if (infixOpDef) {
      const right = expr(lexer, infixOpDef)
      x = mkBinary(op, x, right)
    } else if (postfixOpDef) {
      x = mkPostfix(op, x)
    } else {
      // 这里不可能到达，precedenceHigherThan 为 true 要求操作符必须是合法的中缀或后缀操作符
      throw new Error('Impossible')
    }
  }
  return x
}

括号

然后是括号，没有括号怎么成？

如何处理括号呢？考虑表达式1 * (2 + 3) * 4能注意到，左括号(是出现在操作符之前，右括号)出现在操作符之后，所以处理左括号的逻辑理应放到前缀操作符，右括号的逻辑理应放到后缀操作符中……

先处理左括号，注意在处理括号中的表达式时，它是不关心括号之前的操作符的优先级的，因此 lastOp 重设为 0：

function expr(lexer: Lexer, lastOpDef: OpDef = ZERO_OP_DEF): Expr {
  let x = tokenMatch(lexer.next(), {
    ATOM(t) {
      return mkLiteral(t)  // 原逻辑
    }, 
    OP(op) {
      if (op.op === '(') {
        const inner = expr(lexer)
        lexer.nextOp(')')
        return inner
      }
      // 前缀操作符
    }
  })
  // ...
}

但其实只改这里就行了，不需要在后缀的部分显式处理)：while 在检查当前操作符的优先级时会遇到)，然后它发现没有)的中缀、后缀操作符的定义，因此马上停止解析，把当前的 x 返回出来，)就像一堵墙，把所有解析过程给它阻断，最后控制流又回到前缀中处理(的那部分代码去处理，消费掉这个)。

数组索引

数组索引形如1 + a[i] + 3，这里有让人将它分到中缀运算符的冲动，但其实它分到后缀更合适——i 的范围是明确界定的，不参与优先级的运算。

但要我觉得，其实放哪都一样，它和后缀的!，中缀的+-*/^并非一路货色，实际上每个中缀（出现在第一个操作数后的）操作符都有自己的处理逻辑，只不过某些运算符的逻辑正好一样罢了，后面实际上也是这样操作的。

需要定义后缀操作符[的优先级——这里究竟应当解释为(1 + a)[i] + 3还是1 + (a[i]) + 3呢？此外，处理[i]中的 i 和处理括号时的行为是相同的：

function opDef(token: OpToken, position: OpDef['position']): OpDef | null {
  // ...
  switch (position) {
    // ...
    case 'postfix':
      switch (token.op) {
        case '[':case '!': return mkOpDef(7, 'R') 
      }
  }
  return null
}

function expr(lexer: Lexer, lastOpDef: OpDef = ZERO_OP_DEF): Expr {
  // ...
  while (precedenceHigherThan(lexer, lastOpDef)) {
    // ...
    if (infixOpDef) {
      // ...
    } else if (postfixOpDef) {
      if (op.op === '[') {
        const i = expr(lexer)
        lexer.nextOp(']')
        x = mkBinary(op, x, i)
      } else {
        // 原逻辑
        x = mkPostfix(op, x)
      }
    } else {
      // 这里不可能到达，precedenceHigherThan 为 true 要求操作符必须是合法的中缀或后缀
      throw new Error('Impossible')
    }
  }
  return x
}

三目运算符

最后是三目，最终 boss。作为一个现代语言，要我说就不该支持三目，让三目滚蛋，换成 if 表达式。但这里还是实现一下。

如何理解三目呢？a ? b : c，一种最直接的方式是，将?:想象成一对括号，从而让 b 不再参与优先级的计算以简化问题。对于a ? b : c ? d : e，将它理解为a ?: c ?: e即可，记住三目是右结合的。并非所有语言的三目都是这样实现的，但同时并非所有语言的三目的行为都是一样的（恼，正经人谁用三目不加括号的？除了右结合，假设三目的其他特性都是作死）

if (infixOpDef) {
  if (op.op === '?') {
    const thenExpr = expr(lexer)
    lexer.nextOp(':')
    const elseExpr = expr(lexer, infixOpDef) // 把优先级得带上！ ? 和：中间的部分等于是加了括号，但：后面的部分优先级是起作用的
    x = mkTernary(op, x, thenExpr, elseExpr)
  } else {
    // 原逻辑
    const right = expr(lexer, infixOpDef)
    x = mkBinary(op, x, right)
  }
}

抽象各运算符的逻辑

在 pratt parsing 法中，一切操作符归根结底是前缀操作符和中缀操作符——如果操作符比第一个操作数先出现，则是前缀操作符，否则是中缀操作符（虽然它叫中缀，但只是说指示对应操作符的 token 出现在第一个操作数之后，无关其他操作数在什么位置，有多少个操作数）。另外，Atom 也认为是前缀操作符。

为此，可以把不同运算符的逻辑都抽象出来——加减乘除？自增自减，阶乘？乃至于括号，三目，数组运算符？甚至 Atom？都抽象出对应的逻辑（并让这些逻辑都可以回调 expr），这些逻辑块称为 Parselet，这些 Parselet 均返回Expr，前缀和中缀需要各自定义相应的 Parselet 类型，因为它们已知的信息不同——前缀只知道当前的 token，中缀知道已有的 x 和当前的 token。这些 Parselet 进行自己的逻辑时必然会回调 expr 函数。

假设我们已经把每个 parselet 都抽象出来了，但将它们硬编码到了 expr 函数中，形式可能会是这样的：

def expr(lexer, lastOp):
  xToken = lexer.next()
  x = xToken match {
    # 这里的 atom@Atom(_) 模仿的是 haskell 的相应语法，在模式匹配成功后再次把整个模式对应的值都赋给它
    atom@Atom(_) => atomPrefixParselet(lexer, atom) # 注意到 parselet 是不需要知晓当前的 lastOp 信息的
    op@Op('(')   => parenPrefixParselet(lexer, op)
    op@Op('+')   => plusPrefixParselet(lexer, op)
    op@Op('-')   => minusPrefixParselet(lexer, op)
    # ...
    _            => panic("unknown token: ...")
  }
  # 注意 precedenceHigherThan 仍旧需要知道各操作符的优先级，这点不能变
  while precedenceHigherThan(lexer, lastOp):
    op = lexer.next()
    # 注意这里的左结合行为
    x = op match {
      op@Op('?') => conditionalInfixParselet(lexer, x, op)
      op@Op('[') => arrayAccessInfixParselet(lexer, x, op)
      op@Op('+') => plusInfixParselet(lexer, x, op) 
      op@Op('!') => factorialInfixParselet(lexer, x, op) 
      # ...
      _          => panic('impossible') # 如果 token 没定义过，它根本不可能进到 while 里来
    }
  return x

如何避免硬编码相应 parselet 到 expr 函数中呢？能注意到这里实际上是根据 token 的 type 和 value 去决定分发到哪个 parselet 上，因此我们可以建立相应哈希表，根据 type 和 value 获取相应 parselet（工业上必定是类似的操作），但这 key 有两个实际上不太优雅，我们可以做两次分发，为每个 type 定义相应 parselet（这样甚至能把泛型给利用起来了），再让这些 parselet 根据 value 去分发到对应 parselet，缺点是代码比较复杂些。

这里走最省事的方式——每个 parselet 都直接定义相应谓词检查该 token 自己要不要，这是不合适的，应当在“编译期”就知晓当前的定义，因为需要检查当前的优先级和结合性规则是否合法。

最终形状可能会是这样：

def expr(lexer, lastOp):
  xToken = lexer.next()
  x: Expr = prefixParseletMap[xToken](lexer, xToken) # getPrefixParselet 可能失败
  while precedenceHigherThan(lexer, lastOp):
    op = lexer.next()
    x = infixParselet[op](lexer, x, op)
  return x

但注意 precedenceHigherThan 的实现，precedenceHigherThan 同样需要知道这里的 op（通过 peek）的优先级。因此，我们可以将优先级信息保存到 parselet 中，在 precedenceHigherThan 函数中同样去找到 parselet，再找到优先级信息。

但前缀操作符也有优先级信息——这决定前缀操作符后的 atom 是和它先结合还是和它的下一个操作符先结合，总之能得到下面的类型：

type PrefixParselet = {
  accept: (token: Token) => boolean
  precedence: number,
  // 这里 expr 调用 parselet 的时候把自己也给传进去，保证 parselet 在看不到 expr 函数的情况下也能直接调用 expr 函数
  parse: (lexer: Lexer, x: Token, exprFn: Parser['expr']) => Expr
}

type InfixParselet = {
  accept: (token: Token) => boolean
  precedence: number, assoc: 'L' | 'R',
  parse: (lexer: Lexer, x: Expr, op: Token, exprFn: Parser['expr']) => Expr
}

type Parser = {
  // 因为谓词直接定义在 parselet 上了…
  registerPrefixParselet: (parselet: PrefixParselet) => void,
  registerInfixParselet: (parselet: InfixParselet) => void,
  expr: (lexer: Lexer, lastOpPrecedence?: number) => Expr
}

注意 expr 不需要知晓上一个操作符的结合性——如果上一个操作符的优先级和当前操作符的优先级相同，则它们的结合性会是一致的，不然这语法规则就是有歧义的——同一个优先级下的操作符的结合性需要一致。

function newParser(): Parser {
  const prefixParselets: PrefixParselet[] = []
  const infixParselets: InfixParselet[] = []

  function getPrefixParselet(token: Token) {
    const res = prefixParselets.find(parselet => parselet.accept(token))
    if (!res) throw new Error(`No Prefix parselet defined for ${JSON.stringify(token)}`)
    return res
  }
  function getInfixParselet(token: Token) {
    const res = infixParselets.find(parselet => parselet.accept(token))
    return res ?? null
  }

  function precedenceHigherThan(lexer: Lexer, lastOpPrecedence: number): boolean {
    if (lexer.isAtEnd()) {
      return false
    }
    const currentParselet = getInfixParselet(lexer.peek())
    if (currentParselet == null) {
      return false
    }
    if (currentParselet.precedence != lastOpPrecedence) {
      return currentParselet.precedence > lastOpPrecedence
    }
    return currentParselet.assoc === 'L' ? false : true
  }

  function expr(lexer: Lexer, lastOp = 0): Expr {
    const xToken = lexer.next()
    let x = getPrefixParselet(xToken).parse(lexer, xToken, expr)
    while(precedenceHigherThan(lexer, lastOp)) {
      const op = lexer.next()
      x = getInfixParselet(op)!.parse(lexer, x, op, expr)
    }
    return x
  } 
  return {
    registerInfixParselet(parselet) { infixParselets.push(parselet) },
    registerPrefixParselet(parselet) { prefixParselets.push(parselet) },
    expr
  }
}

用例

接下来，用 parselet 把之前定义过的东西再定义一次，其中为“一般”的前缀、中缀、后缀操作符定义了相关函数以方便其的定义，但像原子，括号，三目，数组索引等语法仍需要手写相应 parselet。

注意 parselet 在被调用时，触发 parselet 的 token 已经被消费了，不需要在 parselet 中进行消费操作。

const parser = newParser()

// 原子
parser.registerPrefixParselet({
  precedence: -1, // 这个优先级不会被使用到
  accept: token => token.type == 'ATOM',
  parse(lexer, x, exprFn) {
    return mkLiteral(x as AtomToken)
  },
})

// 括号
parser.registerPrefixParselet({
  precedence: -1, // 同样的不会使用到
  accept: token => token.type == 'OP' && token.op === '(',
  parse(lexer, x, exprFn) {
    const res = exprFn(lexer)
    if (lexer.nextOp().op !== ')') throw new Error(`Expect ')'`)
    return res
  },
})

// 一般的前缀运算符对应的 praselet
function prefixOperators(precedence: number, ops: string): PrefixParselet {
  return {
    precedence,
    accept(token) {
      return token.type === 'OP' && ops.includes(token.op)
    },
    parse(lexer, x, exprFn) {
        const right = exprFn(lexer, this.precedence)
        return mkPrefix(x as OpToken, right)
    },
  }
}

// 一般的中缀运算符对应的 parselet
function infixOperators(precedence: number, assoc: 'L'| 'R', ops: string): InfixParselet {
  return { 
    assoc, precedence,
    accept(token) {
      return token.type === 'OP' && ops.includes(token.op)
    },
    parse(lexer, x, op, exprFn) {
      op = op as OpToken
      const right = exprFn(lexer, this.precedence)
      return mkBinary(op, x, right)
    },
  }
}

// 一般的后缀运算符对应的 parselet
function suffixOperators(precedence: number, ops: string): InfixParselet {
  return {
    precedence, assoc: 'R', // 后缀运算符的结合性是个有意思的问题…但一般来说，后缀运算符的优先级会高于中缀，因此结合性应当是不起作用的
    accept(token) {
      return token.type === 'OP' && ops.includes(token.op)
    },
    parse(lexer, x, op, exprFn) {
      return mkPostfix(op as OpToken, x)
    },
  }
}

parser.registerPrefixParselet(prefixOperators(3, '+-!'))
parser.registerInfixParselet(infixOperators(1, 'L', '+-'))
parser.registerInfixParselet(infixOperators(2, 'L', '*/%'))
parser.registerInfixParselet(infixOperators(4, 'R', '^'))
parser.registerInfixParselet(suffixOperators(5, '!'))

// 数组索引
parser.registerInfixParselet({
  precedence: 5, assoc: 'L', // 这个结合性同样是没意义的，因为数组索引属于后缀运算符
  accept(token) {
    return token.type === 'OP' && token.op === '['
  },
  parse(lexer, x, op, exprFn) {
    const index = exprFn(lexer)
    lexer.nextOp(']')
    return mkBinary({type: 'OP', op: '[]'}, x, index)
  },
})
// 三目
parser.registerInfixParselet({
  precedence: 0.5, assoc: 'R', // 三目的结合性有用
  accept(token) {
    return token.type === 'OP' && token.op === '?'
  },
  parse(lexer, x, op, exprFn) {
    const thenExpr = exprFn(lexer)
    lexer.nextOp(':')
    const elseExpr = exprFn(lexer, this.precedence)
    return mkTernary({type: 'OP', op: '?:'}, x, thenExpr, elseExpr)
  },
})

使用栈处理四则运算

在学习 pratt 解析后，我突然意识到其实使用栈来处理四则运算表达式的思想和 partt 是一致的——，如果遇到的上一个操作符的优先级大于等于当前的（左结合），则栈顶的操作数就是右操作数，去马上计算该操作符对应的表达式（马上得给它标红）。这样把整个表达式过一遍后，所有连续的非严格降序的操作符都已被计算，因此没有处理的操作符的优先级会是一个非严格升序的状态，再处理这些升序的操作符即可，巧的是操作符出栈的顺序正好就是计算的顺序。

比如，计算1 + 4 * 2 * 3 + 2，读到第二个*后马上计算4 * 2，然后读到第二个+后，马上计算 8 * 3，最后表达式会变成1 + 24 + 2，但此时就停止了——业务逻辑是在遇到操作符时执行的，所以最终还得把这个表达式再操作一遍，但操作这个是很方便的。

为什么需要维护两个栈？因为我们总是需要上一个操作符的优先级信息，所以操作数和操作符分开放。先不考虑括号的话，实现会是下面这样：

function stackTop<T>(stack: T[]): T {
  if (!stack || stack.length == 0) throw new Error('stack is empty')
  return stack[stack.length - 1]
}

function applyEvalOnce(numStack: number[], opStack: string[]): void {
  function applyOp(a: number, op: string, b: number): number {
    switch (op) {
      case '+': return a + b
      case '-': return a - b
      case '*': return a * b
      case '/': return a / b
      case 'ZERO': return b
    }
    throw new Error()
  }
  
  const b = numStack.pop()!
  const a = numStack.pop()!
  const op = opStack.pop()!
  numStack.push(applyOp(a, op, b)) 
}

function precedence(op: string): number {
  const map: Record<string,number> = {
    '+': 1, '-': 1, '*': 2, '/': 2, 'ZERO': 0
  }
  return map[op]
}

function evalExpr(expr: string): number {
  const lexer = mkLexer(expr)
  const numStack: number[] = [-9999]
  const opStack: string[] = ['ZERO']

  while (!lexer.isAtEnd()) {
    const token = lexer.next()
    if (token.type === 'ATOM') {
      numStack.push(+token.literal)
      continue
    }
    const op = (token as OpToken).op
    // 如果当前优先级小于等于上一个操作符的优先级，上一个操作符已经可以执行了
    if (precedence(op) <= precedence(stackTop(opStack))) {
      applyEvalOnce(numStack, opStack)
    }
    opStack.push(op) 
  }
  // 然后，栈中仍剩的操作符将是升序的
  while (opStack.length != 0) {
    applyEvalOnce(numStack, opStack)
  }
  return numStack[0]
}

注意这实现中为了处理方便，不用在检查上一个操作符的时候检查操作符栈非空，给它填充一个最低优先级的操作符，并让它的语义为返回右操作数。

然后是括号，括号很 trick，括号就像一堵高墙，阻止左括号前面的操作符进行计算，比如对1 * (2 + 3)，不能在遇到+的时候把(当作操作符去处理了（同时也不能遇到(先把*给处理了，因此左括号要走自己的逻辑），因此可以给左括号设置一个很低的优先级来避免它猴急。但此后仍然是照常计算，直到遇到右括号，此时在操作符栈中，左括号上面的操作符的优先级会是非严格升序的，因此在遇到左括号之前把它们全都给计算掉，然后扔掉栈顶的左括号即可，这样就计算出来了括号中的结果并填入操作符栈中。

function precedence(op: string): number {
  const map: Record<string,number> = {
    '+': 1, '-': 1, '*': 2, '/': 2, 'ZERO': 0, '|': -999
  }
  return map[op]
}

function evalExpr(expr: string): number {
  const lexer = mkLexer(expr)
  const numStack: number[] = [-9999]
  const opStack: string[] = ['ZERO']

  while (!lexer.isAtEnd()) {
    const token = lexer.next()
    if (token.type === 'ATOM') {
      numStack.push(+token.literal)
      continue
    }
    const op = (token as OpToken).op
    if (op === '(') {
      // 其实这时候 push 个啥都行，它只是个标识符，所以这里 push 一个'|'因为它更应景
      opStack.push('|') 
    } else if (op === ')') {
      while (stackTop(opStack) !== '|') {
        applyEvalOnce(numStack, opStack)
      }
      opStack.pop() // 丢掉 '|'
    } else {
      if (precedence(op) <= precedence(stackTop(opStack))) {
        applyEvalOnce(numStack, opStack)
      }
      opStack.push(op) 
    }
  }
  while (opStack.length != 0) {
    applyEvalOnce(numStack, opStack)
  }
  return numStack[0]
}

pratt 完整实现

type AtomToken = {type: 'ATOM', literal: string}
type OpToken = {type: 'OP', op: string}
type EofToken = { type: 'EOF' }
type Token = AtomToken | OpToken | EofToken

type Lexer = {
  next(): Token,
  peek(): Token,
  nextAtom(): AtomToken
  nextOp(value?: string): OpToken
  peekAtom(): AtomToken,
  peekOp(): OpToken
  isAtEnd(): boolean
}

function tokenMatch<T>(token: Token, fn: Partial<{ATOM: (t: AtomToken) => T, OP: (t: OpToken) => T, EOF: (t: EofToken) => T}>) {
  if (!fn[token.type]) {
    throw new Error(`pattern match failed, type: ${token.type}`)
  }
  return (fn[token.type] as any)(token)
}

function mkLexer(source: string): Lexer {
  const tokens = source.split('').filter(c=>!/\s/.test(c))
    .map<Token>(c => /[a-zA-Z0-9]/.test(c) ? { type: 'ATOM', literal: c } : { type: 'OP', op: c})
  function assertTokenType(token: Token, type: Token['type']): any {
    if (token.type != type) {
      throw new Error(`Expect ${type}, got ${token.type}`)
    }
    return token
  }
  function next() {
    return tokens.shift() ?? { type: 'EOF' }
  }
  function peek() {
    return tokens[0] ?? { type: 'EOF' }
  }
  return {
    next,
    peek,
    nextAtom() {
      return assertTokenType(next(), 'ATOM')
    },
    nextOp(value?: string) {
      const op = assertTokenType(next(), 'OP') as OpToken
      if (value && value != op.op) {
        throw new Error(`Expect ${value}, got ${op.op}`)
      }
      return op
    },
    peekAtom() {
      return assertTokenType(peek(), 'ATOM')
    },
    peekOp() {
      return assertTokenType(peek(), 'OP')
    },
    isAtEnd() {
      return tokens.length == 0
    }
  }
}

type Expr = ({
  type: 'LITERAL', value: AtomToken
} | {
  type: 'UNARY', op: OpToken, right: Expr
} | {
  type: 'BINARY', op: OpToken, left: Expr, right: Expr
} | {
  type: 'TERNARY', op: OpToken, left: Expr, middle: Expr, right: Expr
}) & { toString(): string }

function mkLiteral(value: AtomToken): Expr {
  return { type: 'LITERAL', value, toString() { return value.literal } }
}
function mkUnary(op: OpToken, right: Expr): Expr {
  return {type: 'UNARY', op, right, toString() { return `(${op.op} ${right})` } }
}
function mkBinary(op: OpToken, left: Expr, right: Expr): Expr {
  return {type: 'BINARY', op, left, right, toString() {
    return `(${op.op} ${left} ${right})`
  }}
}
function mkTernary(op: OpToken, left: Expr, middle: Expr, right: Expr): Expr {
  return {type: 'TERNARY', op, left, middle, right, toString() { return `(${op.op} ${left} ${middle} ${right})` } }
}

type PrefixParselet = {
  accept: (token: Token) => boolean
  precedence: number,
  // 这里 expr 调用 parselet 的时候把自己也给传进去，保证 parselet 在看不到 expr 函数的情况下也能直接调用 expr 函数
  parse: (lexer: Lexer, x: Token, exprFn: Parser['expr']) => Expr
}

type InfixParselet = {
  accept: (token: Token) => boolean
  precedence: number, assoc: 'L' | 'R',
  parse: (lexer: Lexer, x: Expr, op: Token, exprFn: Parser['expr']) => Expr
}

type Parser = {
  // 因为谓词直接定义在 parselet 上了…
  registerPrefixParselet: (parselet: PrefixParselet) => void,
  registerInfixParselet: (parselet: InfixParselet) => void,
  expr: (lexer: Lexer, lastOpPrecedence?: number) => Expr
}

function newParser(): Parser {
  const prefixParselets: PrefixParselet[] = []
  const infixParselets: InfixParselet[] = []

  function getPrefixParselet(token: Token) {
    const res = prefixParselets.find(parselet => parselet.accept(token))
    if (!res) throw new Error(`No Prefix parselet defined for ${JSON.stringify(token)}`)
    return res
  }
  function getInfixParselet(token: Token) {
    const res = infixParselets.find(parselet => parselet.accept(token))
    return res ?? null
  }

  function precedenceHigherThan(lexer: Lexer, lastOpPrecedence: number): boolean {
    if (lexer.isAtEnd()) {
      return false
    }
    const currentParselet = getInfixParselet(lexer.peek())
    if (currentParselet == null) {
      return false
    }
    if (currentParselet.precedence != lastOpPrecedence) {
      return currentParselet.precedence > lastOpPrecedence
    }
    return currentParselet.assoc === 'L' ? false : true
  }

  function expr(lexer: Lexer, lastOp = 0): Expr {
    const xToken = lexer.next()
    let x = getPrefixParselet(xToken).parse(lexer, xToken, expr)
    while(precedenceHigherThan(lexer, lastOp)) {
      const op = lexer.next()
      x = getInfixParselet(op)!.parse(lexer, x, op, expr)
    }
    return x
  } 
  return {
    registerInfixParselet(parselet) { infixParselets.push(parselet) },
    registerPrefixParselet(parselet) { prefixParselets.push(parselet) },
    expr
  }
}

const parser = newParser()

parser.registerPrefixParselet({
  precedence: -1, // 这个优先级不会被使用到
  accept: token => token.type == 'ATOM',
  parse(lexer, x, exprFn) {
    return mkLiteral(x as AtomToken)
  },
})
parser.registerPrefixParselet({
  precedence: -1, // 同样的不会使用到
  accept: token => token.type == 'OP' && token.op === '(',
  parse(lexer, x, exprFn) {
    const res = exprFn(lexer)
    if (lexer.nextOp().op !== ')') throw new Error(`Expect ')'`)
    return res
  },
})

// 一般的前缀运算符对应的 praselet
function prefixOperators(precedence: number, ops: string): PrefixParselet {
  return {
    precedence,
    accept(token) {
      return token.type === 'OP' && ops.includes(token.op)
    },
    parse(lexer, x, exprFn) {
        const right = exprFn(lexer, this.precedence)
        return mkUnary(x as OpToken, right)
    },
  }
}

// 一般的中缀运算符对应的 parselet
function infixOperators(precedence: number, assoc: 'L'| 'R', ops: string): InfixParselet {
  return { 
    assoc, precedence,
    accept(token) {
      return token.type === 'OP' && ops.includes(token.op)
    },
    parse(lexer, x, op, exprFn) {
      op = op as OpToken
      const right = exprFn(lexer, this.precedence)
      return mkBinary(op, x, right)
    },
  }
}

function suffixOperators(precedence: number, ops: string): InfixParselet {
  return {
    precedence, assoc: 'L', // 后缀运算符的结合性是个有意思的问题…但一般来说，后缀运算符的优先级会高于中缀，因此结合性应当是不起作用的
    accept(token) {
      return token.type === 'OP' && ops.includes(token.op)
    },
    parse(lexer, x, op, exprFn) {
      return mkUnary(op as OpToken, x)
    },
  }
}

parser.registerPrefixParselet(prefixOperators(3, '+-!'))
parser.registerInfixParselet(infixOperators(1, 'L', '+-'))
parser.registerInfixParselet(infixOperators(2, 'L', '*/%'))
parser.registerInfixParselet(infixOperators(4, 'R', '^'))
parser.registerInfixParselet(suffixOperators(5, '!'))

// 数组索引
parser.registerInfixParselet({
  precedence: 5, assoc: 'L', // 这个结合性同样是没意义的，因为数组索引属于后缀运算符
  accept(token) {
    return token.type === 'OP' && token.op === '['
  },
  parse(lexer, x, op, exprFn) {
    const index = exprFn(lexer)
    lexer.nextOp(']')
    return mkBinary({type: 'OP', op: '[]'}, x, index)
  },
})
// 三目
parser.registerInfixParselet({
  precedence: 0.5, assoc: 'R', // 三目的结合性有用
  accept(token) {
    return token.type === 'OP' && token.op === '?'
  },
  parse(lexer, x, op, exprFn) {
    const thenExpr = exprFn(lexer)
    lexer.nextOp(':')
    const elseExpr = exprFn(lexer, this.precedence)
    return mkTernary({type: 'OP', op: '?:'}, x, thenExpr, elseExpr)
  },
})

const parse = (str: string) => console.log(parser.expr(mkLexer(str)).toString())

parse('3 + a[i[2]![3] * 2 + 1]') // (+ 3 ([] a (+ (* ([] (! ([] i 2)) 3) 2) 1)))
parse('a ? b + 1 : c + d ? d : e + 2') // (?: a (+ b 1) (?: (+ c d) d (+ e 2)))

编译原理

本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 协议，转载请注明出处！

计算机系统要素学习笔记 Part1——从 NAND 到 CPU 上一篇

《Crafting Interpreters》学习笔记 2——状态，控制流，函数，语义分析下一篇

理解 Pratt parsing——自顶向下算符优先解析法

优先级