parsing - 递归下降解析: high precedence unary operators

Question

我已经弄清楚如何实现具有优先级的二元运算符，如下所示(伪代码):

method plus
   times()

   while(consume(plus_t)) do
       times()
   end
end

method times
   number()

   while(consume(times_t))
       number()
   end
end

// plus() is the root operation

// omitted: number() consumes a number token

所以当我解析 4 + 5 * 6 时，它会:

1. 加上
   1. 乘法
      1. 数量(已消耗 4 个)
   2. 消耗了plus_t
   3. 乘法
      1. 数量(已消耗 5 个)
      2. 消耗times_t
      3. 数量(已消耗 6 个)

但是，当我尝试添加 minus 方法时(像 -4 这样的前缀减法，而不是像 4 - 5 这样的中缀减法):

method minus
    consume(minus_t)
    plus()
end

它的优先级非常低，因此 -4 + 5 变为 -(4 + 5) 而不是 (-4) + 5 > 这是不可取的。

如何才能创建高优先级一元运算符？

Answer 1

您没有说明要在层次结构中的哪个位置添加 minus方法，但看起来您将其添加到上面 plus并将其设为根。

如果你想要的话，你需要把它放在最后unary -具有比 + 更高的优先级和* .

在你的伪代码中，类似这样的东西应该可以工作:

method times
   minus()

   while(consume(times_t))
       minus()
   end
end

method minus
    if(consume(minus_t))
      // next number should have a unary minus attached
      number()
    else
      number()
    end
end

这些天我正在学习解析器，所以我根据你的伪代码编写了一个完整的解析器，它是在 LiveScript 中，但应该很容易理解。

编辑:在 jsfiddle.net 上运行示例 - http://jsfiddle.net/Dogbert/7Pmwc/

parse = (string) ->
  index = 0

  is-digit = (d) -> '0' <= d <= '9'

  plus = ->
    str = times()
    while consume "+"
      str = "(+ #{str} #{times()})"
    str

  times = ->
    str = unary-minus()
    while consume "*"
      str = "(* #{str} #{unary-minus()})"
    str

  unary-minus = ->
    if consume "-"
      "(- #{number()})"
    else
      number()

  number = ->
    if is-digit peek()
      ret = peek()
      advance()
      while is-digit peek()
        ret += peek()
        advance()
      ret
    else
      throw "expected number at index = #{index}, got #{peek()}"

  peek = ->
    string[index]

  advance = ->
    index++

  consume = (what) ->
    if peek() == what
      advance()
      true

  plus()


console.log parse "4+5*6"
console.log parse "-4+5"
console.log parse "-4*-5+-4"

输出:

(+ 4 (* 5 6))
(+ (- 4) 5)
(+ (* (- 4) (- 5)) (- 4))

PS:您可能想看看Operator-precedence Parsers用于相对轻松地解析复杂的优先级/关联性。