Scala. Парсер сложных выражений. OutOfMemoryError

Я хотел бы создать парсер для сложных выражений с порядком операций. У меня есть пример, но он работает очень медленно и выдает исключение OutOfMemoryError. Как я могу это улучшить?

def expr: Parser[Expression] = term5
def term5: Parser[Expression] =
    (term4 ~ "OR" ~ term4) ^^ { case lhs~o~rhs => BinaryOp("OR", lhs, rhs) } |
    term4
def term4: Parser[Expression] =
    (term3 ~ "AND" ~ term3) ^^ { case lhs~a~rhs => BinaryOp("AND", lhs, rhs) } |
    term3
def term3: Parser[Expression] =
    (term2 ~ "<>" ~ term2) ^^ { case lhs~ne~rhs => BinaryOp("NE", lhs, rhs) } |
    (term2 ~ "=" ~ term2) ^^ { case lhs~eq~rhs => BinaryOp("EQ", lhs, rhs) } |
    (term2 ~ "NE" ~ term2) ^^ { case lhs~ne~rhs => BinaryOp("NE", lhs, rhs) } |
    (term2 ~ "EQ" ~ term2) ^^ { case lhs~eq~rhs => BinaryOp("EQ", lhs, rhs) } |
    term2
def term2: Parser[Expression] =
    (term1 ~ "<" ~ term1) ^^ { case lhs~lt~rhs => BinaryOp("LT", lhs, rhs) } |
    (term1 ~ ">" ~ term1) ^^ { case lhs~gt~rhs => BinaryOp("GT", lhs, rhs) } |
    (term1 ~ "<=" ~ term1) ^^ { case lhs~le~rhs => BinaryOp("LE", lhs, rhs) } |
    (term1 ~ ">=" ~ term1) ^^ { case lhs~ge~rhs => BinaryOp("GE", lhs, rhs) } |
    (term1 ~ "LT" ~ term1) ^^ { case lhs~lt~rhs => BinaryOp("LT", lhs, rhs) } |
    (term1 ~ "GT" ~ term1) ^^ { case lhs~gt~rhs => BinaryOp("GT", lhs, rhs) } |
    (term1 ~ "LE" ~ term1) ^^ { case lhs~le~rhs => BinaryOp("LE", lhs, rhs) } |
    (term1 ~ "GE" ~ term1) ^^ { case lhs~ge~rhs => BinaryOp("GE", lhs, rhs) } |
    term1
def term1: Parser[Expression] =
    (term ~ "+" ~ term) ^^ { case lhs~plus~rhs => BinaryOp("+", lhs, rhs) } |
    (term ~ "-" ~ term) ^^ { case lhs~minus~rhs => BinaryOp("-", lhs, rhs) } |
    (term ~ ":" ~ term) ^^ { case lhs~concat~rhs => BinaryOp(":", lhs, rhs) } |
    term 
def term: Parser[Expression] =
    (factor ~ "*" ~ factor) ^^ { case lhs~times~rhs => BinaryOp("*", lhs, rhs) } |
    (factor ~ "/" ~ factor) ^^ { case lhs~div~rhs => BinaryOp("/", lhs, rhs) } |
    (factor ~ "MOD" ~ factor) ^^ { case lhs~div~rhs => BinaryOp("MOD", lhs, rhs) } |
    factor
def factor: Parser[Expression] =
    "(" ~> expr <~ ")" |
    ("+" | "-") ~ factor ^^ { case op~rhs => UnaryOp(op, rhs) } |
    function |
    numericLit ^^ { case x => Number(x/*.toFloat*/) } |
    stringLit ^^ { case s => Literal(s) } |
    ident ^^ { case id => Variable(id) }

scala parser-combinators

Andrei Sibircevs 19.12.2011 источник

comment

Какой тестовый пример? А какой парсер вы используете? - Daniel C. Sobral 19.12.2011

comment

Тестовый пример: println (TestParser.parse (\ nA = \ MY TEST STRING \ + \ nB = A: (1 + 2) + \ nC = 3 + \ nD = -4 + \ nE = 3 + 1 / (5 - 4) + \ nF = -5 + 1 + \ nG = -3 + 1 / (-5 - -3) + \ nH = 4,99 + \ nI = -4,99)) - Andrei Sibircevs 19.12.2011

comment

Он работает нормально, когда я использую: def expr: Parser [Expression] = term1. С def expr: Parser [Expression] = term2 работает медленно. С def expr: Parser [Expression] = term3 имеет исключение OutOfMemoryError. - Andrei Sibircevs 19.12.2011

comment

Пожалуйста, отредактируйте вопрос, указав эту информацию. - Daniel C. Sobral 19.12.2011

comment

Кроме того, дополните класс тем, что можно скомпилировать и протестировать. - Daniel C. Sobral 19.12.2011

Ответы (2)

arrow_upward
4
arrow_downward

По сути, он медленный и потребляет слишком много памяти, потому что ваша грамматика невероятно неэффективна.

Рассмотрим вторую строку: B = A:(1+2). Он попытается проанализировать эту строку следующим образом:

term4 OR term4, а затем term4.
term3 AND term3, а затем term3.
term2 <> term2, затем =, затем NE, затем EQ, а затем term2.
term1 8 разных операторов term1, затем term1.
термин + термин, термин - термин, термин : термин, а затем термин.
коэффициент * коэффициент, коэффициент /, коэффициент MOD, а затем коэффициент.
выражение в скобках, унарный множитель, функция, числовой литерал, строковый литерал, идент.

Первая попытка такая:

ident * factor + term < term1 <> term2 AND term3 OR term4

Я пропускаю скобки, унарные, функциональные, числовые и строковые литералы, потому что они не соответствуют A - хотя function, вероятно, соответствует, но его определение недоступно. Теперь, поскольку : не совпадает с *, он попробует следующую:

ident / factor + term < term1 <> term2 AND term3 OR term4
ident MOD factor + term < term1 <> term2 AND term3 OR term4
ident + term < term1 <> term2 AND term3 OR term4

Теперь перейдем к следующему term1:

ident * factor - term < term1 <> term2 AND term3 OR term4
ident / factor - term < term1 <> term2 AND term3 OR term4
ident MOD factor - term < term1 <> term2 AND term3 OR term4
ident - term < term1 <> term2 AND term3 OR term4

А дальше:

ident * factor : term < term1 <> term2 AND term3 OR term4
ident / factor : term < term1 <> term2 AND term3 OR term4
ident MOD factor : term < term1 <> term2 AND term3 OR term4
ident : term < term1 <> term2 AND term3 OR term4

Ага! Наконец-то мы нашли совпадение на term1! Но ( не соответствует <, поэтому ему нужно попробовать следующий термин2:

ident * factor + term > term1 <> term2 AND term3 OR term4

и т.д...

Все потому, что первый термин в каждой строке для каждого термина всегда будет совпадать! Чтобы сопоставить простое число, он должен проанализировать factor 2 * 2 * 5 * 9 * 4 * 4 = 2880 раз!

Но это еще не половина дела! Видите ли, поскольку termX повторяется дважды, он будет повторять все это с обеих сторон. Например, первое совпадение для A:(1+2) следующее:

ident : term < term1 <> term2 AND term3 OR term4
where ident = A
and   term  = (1+2)

Это неверно, поэтому он попробует > вместо <, а затем <= и т. Д. И т. Д.

Ниже я помещаю логирующую версию этого парсера. Попробуйте запустить его и увидеть все, что он пытается разобрать.

Между тем, есть хорошие примеры того, как писать эти парсеры. Используя sbaz, попробуйте:

sbaz install scala-devel-docs

Затем загляните в каталог doc/scala-devel-docs/examples/parsing дистрибутива Scala, и вы найдете несколько примеров.

Вот версия вашего парсера (без function), которая записывает все, что пытается:

sealed trait Expression
case class Variable(id: String) extends Expression
case class Literal(s: String) extends Expression
case class Number(x: String) extends Expression
case class UnaryOp(op: String, rhs: Expression) extends Expression
case class BinaryOp(op: String, lhs: Expression, rhs: Expression) extends Expression

object TestParser extends scala.util.parsing.combinator.syntactical.StdTokenParsers {
    import scala.util.parsing.combinator.lexical.StdLexical
    type Tokens = StdLexical
    val lexical = new StdLexical
    lexical.delimiters ++= List("(", ")", "+", "-", "*", "/", "=", "OR", "AND", "NE", "EQ", "LT", "GT", "LE", "GE", ":", "MOD")
    def stmts: Parser[Any] = log(expr.*)("stmts")
    def stmt: Parser[Expression] = log(expr <~ "\n")("stmt")
    def expr: Parser[Expression] = log(term5)("expr")
    def term5: Parser[Expression] = (
        log((term4 ~ "OR" ~ term4) ^^ { case lhs~o~rhs => BinaryOp("OR", lhs, rhs) })("term5 OR")
      | log(term4)("term5 term4")
    )
    def term4: Parser[Expression] = (
        log((term3 ~ "AND" ~ term3) ^^ { case lhs~a~rhs => BinaryOp("AND", lhs, rhs) })("term4 AND")
      | log(term3)("term4 term3")
    )
    def term3: Parser[Expression] = (
        log((term2 ~ "<>" ~ term2) ^^ { case lhs~ne~rhs => BinaryOp("NE", lhs, rhs) })("term3 <>")
      | log((term2 ~ "=" ~ term2) ^^ { case lhs~eq~rhs => BinaryOp("EQ", lhs, rhs) })("term3 =")
      | log((term2 ~ "NE" ~ term2) ^^ { case lhs~ne~rhs => BinaryOp("NE", lhs, rhs) })("term3 NE")
      | log((term2 ~ "EQ" ~ term2) ^^ { case lhs~eq~rhs => BinaryOp("EQ", lhs, rhs) })("term3 EQ")
      | log(term2)("term3 term2")
    )
    def term2: Parser[Expression] = (
        log((term1 ~ "<" ~ term1) ^^ { case lhs~lt~rhs => BinaryOp("LT", lhs, rhs) })("term2 <")
      | log((term1 ~ ">" ~ term1) ^^ { case lhs~gt~rhs => BinaryOp("GT", lhs, rhs) })("term2 >")
      | log((term1 ~ "<=" ~ term1) ^^ { case lhs~le~rhs => BinaryOp("LE", lhs, rhs) })("term2 <=")
      | log((term1 ~ ">=" ~ term1) ^^ { case lhs~ge~rhs => BinaryOp("GE", lhs, rhs) })("term2 >=")
      | log((term1 ~ "LT" ~ term1) ^^ { case lhs~lt~rhs => BinaryOp("LT", lhs, rhs) })("term2 LT")
      | log((term1 ~ "GT" ~ term1) ^^ { case lhs~gt~rhs => BinaryOp("GT", lhs, rhs) })("term2 GT")
      | log((term1 ~ "LE" ~ term1) ^^ { case lhs~le~rhs => BinaryOp("LE", lhs, rhs) })("term2 LE")
      | log((term1 ~ "GE" ~ term1) ^^ { case lhs~ge~rhs => BinaryOp("GE", lhs, rhs) })("term2 GE")
      | log(term1)("term2 term1")
    )
    def term1: Parser[Expression] = (
        log((term ~ "+" ~ term) ^^ { case lhs~plus~rhs => BinaryOp("+", lhs, rhs) })("term1 +")
      | log((term ~ "-" ~ term) ^^ { case lhs~minus~rhs => BinaryOp("-", lhs, rhs) })("term1 -")
      | log((term ~ ":" ~ term) ^^ { case lhs~concat~rhs => BinaryOp(":", lhs, rhs) })("term1 :")
      | log(term)("term1 term")
    )
    def term: Parser[Expression] = (
        log((factor ~ "*" ~ factor) ^^ { case lhs~times~rhs => BinaryOp("*", lhs, rhs) })("term *")
      | log((factor ~ "/" ~ factor) ^^ { case lhs~div~rhs => BinaryOp("/", lhs, rhs) })("term /")
      | log((factor ~ "MOD" ~ factor) ^^ { case lhs~div~rhs => BinaryOp("MOD", lhs, rhs) })("term MOD")
      | log(factor)("term factor")
    )
    def factor: Parser[Expression] = (
        log("(" ~> expr <~ ")")("factor (expr)")
      | log(("+" | "-") ~ factor ^^ { case op~rhs => UnaryOp(op, rhs) })("factor +-")
      //| function |
      | log(numericLit ^^ { case x => Number(x/*.toFloat*/) })("factor numericLit")
      | log(stringLit ^^ { case s => Literal(s) })("factor stringLit")
      | log(ident ^^ { case id => Variable(id) })("factor ident")
    )
    def parse(s: String) = stmts(new lexical.Scanner(s))
}

Daniel C. Sobral 19.12.2011

arrow_upward
0
arrow_downward

Мое первое улучшение было таким:

def term3: Parser[Expression] =
log((term2 ~ ("<>" | "=" | "NE" | "EQ") ~ term2) ^^ { case lhs~op~rhs => BinaryOp(op, lhs, rhs) })("term3 <>,=,NE,EQ") |
log(term2)("term3 term2")

Работает без OutOfMemoryError, но работает медленно. После просмотра doc / scala-devel-docs / examples / parsing / lambda / TestParser.scala я получил этот источник:

def expr: Parser[Expression] = term5
def term5: Parser[Expression] =
    log(chainl1(term4, term5, "OR" ^^ {o => (a: Expression, b: Expression) => BinaryOp(o, a, b)}))("term5 OR")
def term4: Parser[Expression] =
    log(chainl1(term3, term4, "AND" ^^ {o => (a: Expression, b: Expression) => BinaryOp(o, a, b)}))("term4 AND")
def term3: Parser[Expression] =
    log(chainl1(term2, term3, ("<>" | "=" | "NE" | "EQ") ^^ {o => (a: Expression, b: Expression) => BinaryOp(o, a, b)}))("term3 <>,=,NE,EQ")
def term2: Parser[Expression] =
    log(chainl1(term1, term2, ("<" | ">" | "<=" | ">=" | "LT" | "GT" | "LE" | "GE") ^^ {o => (a: Expression, b: Expression) => BinaryOp(o, a, b)}))("term2 <,>,...")
def term1: Parser[Expression] =
    log(chainl1(term, term1, ("+" | "-" | ":") ^^ {o => (a: Expression, b: Expression) => BinaryOp(o, a, b)}))("term1 +,-,:")
def term: Parser[Expression] =
    log(chainl1(factor, term, ("*" | "/" | "MOD") ^^ {o => (a: Expression, b: Expression) => BinaryOp(o, a, b)}))("term *,/,MOD")
def factor: Parser[Expression] =
    log("(" ~> expr <~ ")")("factor ()") |
    log(("+" | "-") ~ factor ^^ { case op~rhs => UnaryOp(op, rhs) })("factor unary") |
    log(function)("factor function") |
    log(numericLit ^^ { case x => Number(x/*.toFloat*/) })("factor numLit") |
    log(stringLit ^^ { case s => Literal(s) })("factor strLit") |
    log(ident ^^ { case id => Variable(id) })("factor ident")

Работает быстро. Извините, но я не могу понять, как функция chainl1 улучшает мой исходный код. Я не понимаю, как это работает.

Andrei Sibircevs 21.12.2011

Scala. Парсер сложных выражений. OutOfMemoryError

Ответы (2)

Похожие вопросы