Scala, Parser Combinator для древовидных данных - PullRequest
Новая
       8

Scala, Parser Combinator для древовидных данных

6 голосов
/ 31 мая 2011

Как можно использовать парсеры для разбора записей, занимающих несколько строк? Мне нужно проанализировать данные дерева (и в конечном итоге преобразовать их в структуру данных дерева). Я получаю трудную для отслеживания ошибку синтаксического анализа в приведенном ниже коде, но не ясно, является ли это даже лучшим подходом к анализаторам Scala. Вопрос действительно больше в подходе к решению проблем, чем в отладке существующего кода.

Грамматик EBNF: 

SP          = " "
CRLF        = "\r\n"
level       = "0" | "1" | "2" | "3"
varName     = {alphanum}
varValue    = {alphnum}
recordBegin = "0", varName
recordItem  = level, varName, [varValue]
record      = recordBegin, {recordItem}
file        = {record}

Попытка реализовать и проверить грамматику: 

import util.parsing.combinator._
val input = """0 fruit
1 id 2
1 name apple
2 type red
3 size large
3 origin Texas, US
2 date 2 aug 2011
0 fruit
1 id 3
1 name apple
2 type green
3 size small
3 origin Florida, US
2 date 3 Aug 2011"""

object TreeParser extends JavaTokenParsers {
  override val skipWhitespace = false
  def CRLF = "\r\n" | "\n"
  def BOF = "\\A".r
  def EOF = "\\Z".r
  def TXT = "[^\r\n]*".r
  def TXTNOSP = "[^ \r\n]*".r
  def SP = "\\s".r
  def level: Parser[Int] = "[0-3]{1}".r ^^ {v => v.toInt}
  def varName: Parser[String] = SP ~> TXTNOSP
  def varValue: Parser[String] = SP ~> TXT
  def recordBegin: Parser[Any] =  "0" ~ SP ~ varName ~ CRLF
  def recordItem: Parser[(Int,String,String)] = level ~ varValue ~ opt(varValue) <~ CRLF ^^
    {case l ~ f ~ v => (l,f,v.map(_+"").getOrElse(""))}
  def record: Parser[List[(Int,String,String)]] = recordBegin ~> rep(recordItem)
  def file: Parser[List[List[(Int,String,String)]]] = rep(record) <~ EOF
  def parse(input: String) = parseAll(file, input)
}

val result = TreeParser.parse(input).get
result.foreach(println)

Ответы [ 2 ]

3 голосов
/ 31 мая 2011

Как сказал Дэниел, вам лучше позволить парсеру пропускать пропуски, чтобы минимизировать ваш код.Однако вам может потребоваться настроить значение whitespace, чтобы вы могли явно сопоставить конец строки .Я сделал это ниже, чтобы парсер не перемещался на следующую строку, если значение для записи не определено.

Насколько это возможно, попробуйте использовать парсеры, определенные в JavaTokenParsers, например, ident, если выхотите сопоставить буквенные слова.

Чтобы упростить отслеживание ошибок, выполните NoSuccess сопоставление для parseAll, чтобы вы могли увидеть, в какой момент произошел сбой синтаксического анализатора. 

import util.parsing.combinator._

val input = """0 fruit
1 id 2
1 name apple
2 type red
3 size large
3 origin Texas, US
2 var_without_value
2 date 2 aug 2011
0 fruit
1 id 3
1 name apple
2 type green
3 size small
3 origin Florida, US
2 date 3 Aug 2011"""

object TreeParser extends JavaTokenParsers {
  override val whiteSpace = """[ \t]+""".r

  val level = """[1-3]{1}""".r

  val value = """[a-zA-Z0-9_, ]*""".r
  val eol = """[\r?\n]+""".r

  def recordBegin = "0" ~ ident <~ eol

  def recordItem = level ~ ident ~ opt(value) <~ opt(eol) ^^ {
    case l ~ n ~ v => (l.toInt, n, v.getOrElse(""))
  }

  def record = recordBegin ~> rep1(recordItem)

  def file = rep1(record)

  def parse(input: String) = parseAll(file, input) match {
    case Success(result, _) => result
    case NoSuccess(msg, _) => throw new RuntimeException("Parsing Failed:" + msg)
  }
}

val result = TreeParser.parse(input)
result.foreach(println)
3 голосов
/ 31 мая 2011

Обработка пробелов явно не очень хорошая идея.И, конечно же, использование get означает, что вы потеряете сообщение об ошибке.В этом конкретном примере: 

[1.3] failure: string matching regex `\s' expected but `f' found

0 fruit

  ^

Что на самом деле довольно ясно, хотя вопрос в том, почему ожидал пробел.Теперь это, очевидно, обрабатывало правило recordBegin, которое определено следующим образом: 

"0" ~ SP ~ varName ~ CRLF

Таким образом, оно анализирует ноль, затем пробел, а затем fruit должен быть проанализирован против varName.Теперь varName определяется так: 

SP ~> TXTNOSP

Еще один пробел!Итак, fruit должен был начаться с пробела.

...