EBNF в Scala парсер комбинатор - PullRequest
Новая
       15

EBNF в Scala парсер комбинатор

11 голосов
/ 08 февраля 2009

У меня есть следующий EBNF, который я хочу проанализировать: 

PostfixExp      -> PrimaryExp ( "[" Exp "]" 
                                | . id "(" ExpList ")" 
                                | . length )*

И вот что я получил: 

def postfixExp: Parser[Expression] = (
    primaryExp ~ rep(
        "[" ~ expression ~ "]"
        | "." ~ ident ~"(" ~ repsep(expression, "," ) ~ ")" 
        | "." ~ "length") ^^ {
        case primary ~ list =>  list.foldLeft(primary)((prim,post) =>
                post match {
                    case "[" ~ length ~ "]" => ElementExpression(prim, length.asInstanceOf[Expression])
                    case "." ~ function ~"(" ~ arguments ~ ")" =>  CallMethodExpression(prim, function.asInstanceOf[String], arguments.asInstanceOf[List[Expression]])
                    case _ => LengthExpression(prim)
                }
            )
    })

Но я хотел бы знать, есть ли лучший способ, желательно без необходимости использовать кастинг (asInstanceOf).

1 Ответ

12 голосов
/ 09 февраля 2009

Я бы сделал это так: 

type E = Expression

def postfixExp = primaryExp ~ rep(
    "[" ~> expr <~ "]" ^^ { e => ElementExpression(_:E, e) }
  | "." ~ "length" ^^^ LengthExpression
  | "." ~> ident ~ ("(" ~> repsep(expr, ",") <~ ")") ^^ flatten2 { (f, args) =>
      CallMethodExpression(_:E, f, args)
    }
) ^^ flatten2 { (e, ls) => collapse(ls)(e) }

def expr: Parser[E] = ...

def collapse(ls: List[E=>E])(e: E) = {
  ls.foldLeft(e) { (e, f) => f(e) }
}

Сокращено expressions до expr для краткости, а также добавлен псевдоним типа E по той же причине.

Уловка, которую я здесь использую, чтобы избежать уродливого анализа случая, состоит в возвращении значения функции изнутри внутреннего производства. Эта функция принимает Expression (который будет primary) и затем возвращает новый Expression на основе первого. Это объединяет два случая выражения точка-диспетчеризация и выражения в скобках. Наконец, метод collapse используется для объединения линейных List значений функции в правильный AST, начиная с указанного основного выражения.

Обратите внимание, что LengthExpression просто возвращается как значение (используя ^^^) из соответствующего производства. Это работает, потому что сопутствующие объекты для case-классов (при условии, что LengthExpression действительно является case-классом) расширяют соответствующее значение функции, делегируя их конструктору. Таким образом, функция, представленная LengthExpression, принимает один Expression и возвращает новый экземпляр LengthExpression, точно удовлетворяя наши потребности в построении дерева более высокого порядка.

...