Создание рекурсивной структуры данных с помощью комбинаторов парсеров в scala

Я новичок в Scala, работаю над S99, пытаясь изучить Scala. Одна из проблем связана с преобразованием строки в древовидную структуру данных. Я могу сделать это «вручную», я также хочу посмотреть, как это сделать, используя библиотеку комбинатора парсеров Scala.

Структура данных для дерева

sealed abstract class Tree[+T]
case class Node[+T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T] {
  override def toString = "T(" + value.toString + " " + left.toString + " " + right.toString + ")"
}
case object End extends Tree[Nothing] {
  override def toString = "."
}
object Node {
  def apply[T](value: T): Node[T] = Node(value, End, End)
}

И вход должен быть строкой, например: a(b(d,e),c(,f(g,)))

Я могу разобрать строку, используя что-то вроде

trait Tree extends JavaTokenParsers{
  def leaf: Parser[Any] = ident
  def child: Parser[Any] = node | leaf | ""
  def node: Parser[Any] = ident~"("~child~","~child~")" | leaf 
}

Но как я могу использовать библиотеку синтаксического анализа для построения дерева? Я знаю, что могу использовать ^^ для преобразования, например, некоторой строки в целое число. Меня смущает необходимость «знать» левое и правое поддеревья при создании экземпляра Node. Как я могу это сделать, или это признак того, что я хочу сделать что-то другое?

Не лучше ли мне взять то, что возвращает синтаксический анализатор ((((((a~()~(((((b~()~d)~,)~e)~)))~,)~(((((c~()~)~,)~(((((f~()~g)~,)~)~)))~)))~)) для приведенного выше примера ввода), и построить дерево на его основе, чем использовать операторы синтаксического анализатора, такие как ^^ или ^^^, для непосредственного построения дерева?


parsing scala tree parser-combinators
person anchorite    schedule 27.12.2012    source источник

Ответы (1)


arrow_upward
5
arrow_downward

Можно сделать это чисто с помощью ^^, и вы довольно близко:

object TreeParser extends JavaTokenParsers{
  def leaf: Parser[Node[String]] = ident ^^ (Node(_))
  def child: Parser[Tree[String]] = node | leaf | "" ^^ (_ => End)
  def node: Parser[Tree[String]] =
    ident ~ ("(" ~> child) ~ ("," ~> child <~ ")") ^^ {
      case v ~ l ~ r => Node(v, l, r)
    } | leaf
}

И сейчас:

scala> TreeParser.parseAll(TreeParser.node, "a(b(d,e),c(,f(g,)))").get
res0: Tree[String] = T(a T(b T(d . .) T(e . .)) T(c . T(f T(g . .) .)))

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

person Travis Brown    schedule 28.12.2012
comment
Ха, я думал, что JavaTokenParsers это какая-то библиотека Java. Вы снова придумали лучший ответ! - person drstevens; 28.12.2012
comment
Вы правы в том, что у вас никогда не было T(. .). Я оставил бит "" => (_ => End). Я удалил свой ответ для ясности. - person drstevens; 28.12.2012
comment
Спасибо как за ответ, так и за мета-ответ о том, как решить проблему такого типа. Теперь мне нужно перечитать главу о синтаксических анализаторах в книге «Программирование на Scala», чтобы увидеть, что еще я пропустил. - person anchorite; 28.12.2012