Разбор рекурсивного спуска: унарные операторы с высоким приоритетом

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. потребленный плюс
   3. умножать
      1. количество (5 израсходованных)
      2. времена потребляются
      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: вы можете захотеть взглянуть на парсеры предшествующего оператора для сравнительного анализа сложного приоритета / ассоциативности.