разбор скалы с вложенными скобами

Question

Попытка разобрать вложенные выражения, такие как GroupParser.parse ("{{a} {{c} {d}}}") После многих часов у меня теперь есть следующий фрагмент кода, который хорошо разбирает {a}, но завершается неудачно с

[1.5] failure: ``}'' expected but `{' found  
{{a}{{b}{c}}}
    ^

sealed abstract class Expr

case class ValueNode(value:String) extends Expr

object GroupParser extends StandardTokenParsers {
    lexical.delimiters ++= List("{","}")

    def vstring = ident ^^ { case s => ValueNode(s) }   
    def expr = ( vstring | parens ) 
    def parens:Parser[Expr] = "{" ~> expr  <~ "}"

    def parse(s:String) = {
        val tokens = new lexical.Scanner(s)
        phrase(expr)(tokens)
    }

}

есть намеки?

Answer 1

Проблема не в вложении, а в последовательности. Ваша грамматика допускает произвольное вложение выражений внутри фигурных скобок, но не говорит о том, что выражение может быть упорядочено, поэтому синтаксический анализатор не может обработать {a}, за которым сразу следует {{b} {c}}. Вы можете кодировать последовательность, используя явную рекурсию в вашей грамматике или используя один из вариантов повторения в http://www.scala -lang.org / api / current / scala / util / parsing / combinator / Parsers.html

Answer 2

Можно ли повторять выражения несколько раз?Если это так, это сработает:

def expr = ( vstring | parens )+

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

Answer 3

Это анализирует два приведенных вами примера:

import scala.util.parsing.combinator.syntactical._

sealed abstract class Expr

case class ValueNode(value:String) extends Expr

case class ValueListNode(value:List[Expr]) extends Expr

object GroupParser extends StandardTokenParsers {
  lexical.delimiters ++= List("{","}")

  def vstring = ident ^^ { case s => ValueNode(s) }   
  def parens:Parser[Expr] = "{" ~> ( expr )  <~ "}"
  def expr = vstring | parens

  def exprList:Parser[Expr] = "{" ~> rep1( expr | exprList ) <~ "}" ^^ {
    case l => {
      ValueListNode(l)
    }
  }

  def anyExpr = expr | exprList

  def parse(s:String) = {
    val tokens = new lexical.Scanner(s)
    phrase(anyExpr)(tokens)
  }

  def test(s: String) = {
    parse(s) match {
      case Success(tree, _) =>
        println("Tree: " + tree)
      case e: NoSuccess => Console.err.println(e)
    }
  }

  def main(args: Array[String]) = {
    test("{a}")
    test("{{a}}")
    test("{{a}{{b}{c}}}")
  }
}

И успешно с выводом:

Tree: ValueNode(a)
Tree: ValueNode(a)
Tree: ValueListNode(List(ValueNode(a), ValueListNode(List(ValueNode(b), ValueNode(c)))))