Рекурсивного спуск синтаксического анализа: высокая очередность унарные

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 потребляются)

Однако при попытке добавление меток д (префикс minusing, как -4, не инфиксная minusing как 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, но должно быть легко следовать.

Edit: Запуск примера на 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 для разбора сложной очередности/ассоциативности относительно легко.