Разбор рекурсивного спуска: унарные операторы с высоким приоритетом
Я выяснил, как реализовать бинарные операторы с приоритетом, как это (псевдокод):
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
было бы:
- плюс
- умножать
- количество (4 потреблено)
- потребленный плюс
- умножать
- количество (5 израсходованных)
- времена потребляются
- количество (6 израсходовано)
- умножать
Тем не менее, когда я пытаюсь добавить minus
метод (префикс минус, как -4
не инфикс минус вроде 4 - 5
):
method minus
consume(minus_t)
plus()
end
Это занимает очень низкий приоритет, поэтому -4 + 5
становится -(4 + 5)
скорее, чем (-4) + 5
и это нежелательно.
Что я могу сделать, чтобы сделать унарный оператор с высоким приоритетом?
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: вы можете захотеть взглянуть на парсеры предшествующего оператора для сравнительного анализа сложного приоритета / ассоциативности.