Recursive descent parsing: high precedence unary operators

Question

I've figured out how to implement binary operators with precedence, like this (pseudocode):

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

So when I parse 4 + 5 * 6 it would:

plus
1. multiply
  1. number (4 consumed)
2. plus_t consumed
3. multiply
  1. number (5 consumed)
  2. times_t consumed
  3. number (6 consumed)

However, when I try adding a minus method (prefix minusing like -4, not infix minusing like 4 - 5):

method minus
    consume(minus_t)
    plus()
end

It takes a very low precedence, so -4 + 5 becomes -(4 + 5) rather than (-4) + 5 and this is undesirable.

What can I do to make a high precedence unary operator?

Dogbert Dogbert · Accepted Answer · 2013-11-10T12:39:33

You've not said where in the hierarchy you're adding the minus method, but it looks like you're adding it above plus and making it the root.

You need to put it at last if you want unary - to have a higher precedence than + and *.

In your pseudocode, something like this should work:

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

I'm learning about parsers these days, so I wrote a complete parser based on your pseudocode, it's in LiveScript, but should be easy to follow.

Edit: Running example on 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"

Output:

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

PS: you may want to look at Operator-precedence Parsers for parsing complex precedence/associativity relatively easily.

Recursive descent parsing: high precedence unary operators

1 Answers