递归下降解析：高优先级一元运算符

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相对容易解析复杂的优先级/关联性。