Блог

Давайте построим дерево синтаксического анализа для простых выражений, таких как 3 - 4 * 5 , используя scala.util.parsing.combinator._ :

 def expr: Parser[Any] = term ~ opt((" "|"-") ~ expr)
def term: Parser[Any] = factor ~ opt(("*"|"/") ~ factor)
def factor: Parser[Any] = wholeNumber | "(" ~> expr <~ ")"
  

С 3 - 4 * 5 результирующее дерево имеет вид:

        expr
      / |  
  term  -   expr
   |       / |  
 factor term * term  
   |      |      |
 number factor factor
   |      |      |
   3    number number
          |      |
          4      5
  

что правильно. Но с 3 - 4 5 моим деревом, похоже, не исправляется:

        expr
      / |  
  term  -   expr
   |       / |  
 factor term   term  
   |      |      |
 number factor factor
   |      |      |
   3    number number
          |      |
          4      5
  

Как я могу это исправить? Я думал, что это решение:

def expr: Parser[Any] = expr ~ opt((" "|"-") ~ term)

но это слишком неправильно…

Мой полный код:

 import scala.util.parsing.combinator._


class Expr

case class Number(value: Int) extends Expr {
    override def toString = s"$value"
}

case class Operator(left: Expr, right: Expr, f: (Int, Int) => Int) extends Expr {
    override def toString = s"($f, $left, $right)"
}

class SimpleLanguageParser extends JavaTokenParsers {

    def expr: Parser[Expr] = (term ~ opt((" " | "-") ~ expr)) ^^ {
        case a ~ None => a
        case a ~ Some(" " ~ b) => Operator(a, b, _   _)
        case a ~ Some("-" ~ b) => Operator(a, b, _ - _)
    }

    def term: Parser[Expr] = (factor ~ opt(("*" | "/" ) ~ term)) ^^ {
        case a ~ None => a
        case a ~ Some("*" ~ b) => Operator(a, b, _ * _)
        case a ~ Some("/" ~ b) => Operator(a, b, _ / _)
    }

    def factor: Parser[Expr] = wholeNumber ^^ (n => Number(Integer.parseInt(n))) | "(" ~> expr <~ ")"

}

object Main {
    def main(args: Array[String]) = {
        val parser = new SimpleLanguageParser
        val result = parser.parse(parser.expr, "3 - 4   5")
        println(result)
    }
}
  

Я думаю, term ~ opt((" "|"-") ~ expr) не удалось сохранить порядок операций / -.

 def largerExpr: Parser[Any] = expr ~ opt((" "|"-") ~ expr)
def expr: Parser[Any] = term ~ opt((" "|"-") ~ term)
  

EIDT

 def expr1: Parser[Expr] = (expr ~ opt((" " | "-") ~ expr)) ^^ {
    case a ~ None => a
    case a ~ Some(" " ~ b) => Operator(a, b, _   _)
    case a ~ Some("-" ~ b) => Operator(a, b, _ - _)
}

def expr: Parser[Expr] = (term ~ opt((" " | "-") ~ term)) ^^ {
    case a ~ None => a
    case a ~ Some(" " ~ b) => Operator(a, b, _   _)
    case a ~ Some("-" ~ b) => Operator(a, b, _ - _)
}
  

Ваш результат был бы (<function2>, 3, (<function2>, 4, 5)) , результатом использования expr1 является (<function2>, (<function2>, 3, 4), 5)