遞歸下降解析：高優先級一元運算符

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消耗）

然而，當我嘗試加入一種minus方法d（前綴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，但應該很容易跟隨。

編輯：於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相對容易解析複雜的優先級/關聯性。