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:

1. 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?

Answer 1

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.