Параметр общего типа для вложенных списков - PullRequest
Новая
       7

Параметр общего типа для вложенных списков

3 голосов
/ 31 августа 2011

Я пытаюсь написать синтаксический анализатор, который должен анализировать список Пролога (например, [1,2,3,4]) в соответствующий список Scala. Я запрограммировал парсер с помощью комбинаторов разбора Scalas.

Мой парсер до сих пор выглядит так: 

class PListParser extends JavaTokenParsers{
    def list:Parser[List[Any]] = "[" ~> listArgs <~ "]"
    def listArgs:Parser[List[Any]] = list | repsep(args, ",")
    def args:Parser[String] = "(.)*".r
}

Есть ли возможность превратить параметры типа первых двух парсеров во что-то более конкретное? Как и общий параметр для вложенных списков произвольной размерности, но с тем же типом подчеркивания.

Ответы [ 2 ]

5 голосов
/ 01 сентября 2011

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

sealed trait Tree[A]
case class Leaf[A](value: A) extends Tree[A] {
  override def toString: String = value.toString
}
case class Node[A](items: List[Tree[A]]) extends Tree[A] {
  override def toString: String = "Node(" + items.mkString(", ") + ")"
}

(Делайте toString как вам нравится, но я думаю, что заданный по умолчанию список слишком многословен)

Затем, с небольшими исправлениями в вашей грамматике (+ метод синтаксического анализа, просто для простого тестирования на REPL) 

object PrologListParser extends JavaTokenParsers{
    def list:Parser[Tree[String]] = "[" ~> listArgs <~ "]"
    def listArgs:Parser[Tree[String]] = repsep(list | args, ",") ^^ {Node(_)}
    def args:Parser[Tree[String]] = """([^,\[\]])*""".r ^^ {Leaf(_)}
    def parse(s: String): ParseResult[Tree[String]] = parse(list, s)
}


PrologListParser.parse("[a, b, [c, [d, e], f, [g], h], [i, j], k]")

res0: PrologList.ParseResult [Tree [String]] = [1.42] проанализировано: Узел (a, b, Узел (c, Узел (d, e), f, Узел (g), h), Узел (i, j), k)

1 голос
/ 01 сентября 2011

(не проверено) 

sealed trait PrologTerm

case class PInt(i: Integer) extends PrologTerm { 
  override def toString = i.toString 
}
case class PAtom(s: String) extends PrologTerm { 
  override def toString = s.toString 
}
case class PComplex(f: PAtom, args: List[PrologTerm]) extends PrologTerm {
  override def toString = f.toString+"("+args.mkString(", ")+")"
}
case class PList(items: List[PrologTerm]) extends PrologTerm {
  override def toString = "["+items.mkString(", ")+"]"
}

object PrologListParser extends JavaTokenParsers {
  def term : Parser[PrologTerm] = int | complex | atom | list
  def int : Parser[PInt] = wholeNumber ^^ {s => PInt(s.toInt)}
  def complex : Parser[PComplex] = 
    (atom ~ ("(" ~> repsep(term, ",") <~ ")")) ^^ {case f ~ args => PAtom(f, args)}
  def atom : Parser[PAtom] = "[a-z][a-zA-Z_]*".r ^^ {PAtom(_)}
  def list : Parser[PList] = ("[" ~> repsep(term, ",") <~ "]") ^^ {PList(_)}
}
...