Parsing-Schema mit Scala Parser Kombinator

Question

Ich schreibe einen kleinen Schema-Interpreter in Scala und ich habe Probleme beim Parsen von Listen in Scheme. Mein Code analysiert Listen, die mehrere Zahlen, Bezeichner und boolesche Werte enthalten, aber er erstickt, wenn ich versuche, eine Liste mit mehreren Zeichenfolgen oder Listen zu analysieren. Was vermisse ich?

Hier ist mein Parser:

class SchemeParsers extends RegexParsers { 

// Scheme boolean #t and #f translate to Scala's true and false 
def bool : Parser[Boolean] = 
    ("#t" | "#f") ^^ {case "#t" => true; case "#f" => false} 

// A Scheme identifier allows alphanumeric chars, some symbols, and 
// can't start with a digit 
def id : Parser[String] = 
    """[a-zA-Z=*+/<>!\?][a-zA-Z0-9=*+/<>!\?]*""".r ^^ {case s => s} 

// This interpreter only accepts numbers as integers 
def num : Parser[Int] = """-?\d+""".r ^^ {case s => s toInt} 

// A string can have any character except ", and is wrapped in " 
def str : Parser[String] = '"' ~> """[^""]*""".r <~ '"' ^^ {case s => s} 

// A Scheme list is a series of expressions wrapped in() 
def list : Parser[List[Any]] = 
    '(' ~> rep(expr) <~ ')' ^^ {s: List[Any] => s} 

// A Scheme expression contains any of the other constructions 
def expr : Parser[Any] = id | str | num | bool | list ^^ {case s => s} 
} 

Answer 1

Wie es von @Gabe Recht darauf hingewiesen wurde, linken Seite erkennt man weiß Räume nicht behandelte:

scala> object SchemeParsers extends RegexParsers { 
    | 
    | private def space = regex("[ \\n]*".r) 
    | 
    | // Scheme boolean #t and #f translate to Scala's true and false 
    | private def bool : Parser[Boolean] = 
    |  ("#t" | "#f") ^^ {case "#t" => true; case "#f" => false} 
    | 
    | // A Scheme identifier allows alphanumeric chars, some symbols, and 
    | // can't start with a digit 
    | private def id : Parser[String] = 
    |  """[a-zA-Z=*+/<>!\?][a-zA-Z0-9=*+/<>!\?]*""".r 
    | 
    | // This interpreter only accepts numbers as integers 
    | private def num : Parser[Int] = """-?\d+""".r ^^ {case s => s toInt} 
    | 
    | // A string can have any character except ", and is wrapped in " 
    | private def str : Parser[String] = '"' ~> """[^""]*""".r <~ '"' <~ space ^^ {case s => s} 
    | 
    | // A Scheme list is a series of expressions wrapped in() 
    | private def list : Parser[List[Any]] = 
    |  '(' ~> space ~> rep(expr) <~ ')' <~ space ^^ {s: List[Any] => s} 
    | 
    | // A Scheme expression contains any of the other constructions 
    | private def expr : Parser[Any] = id | str | num | bool | list ^^ {case s => s} 
    | 
    | def parseExpr(str: String) = parse(expr, str) 
    | } 
defined module SchemeParsers 

scala> SchemeParsers.parseExpr("""(("a" "b") ("a" "b"))""") 
res12: SchemeParsers.ParseResult[Any] = [1.22] parsed: List(List(a, b), List(a, b)) 

scala> SchemeParsers.parseExpr("""("a" "b" "c")""") 
res13: SchemeParsers.ParseResult[Any] = [1.14] parsed: List(a, b, c) 

scala> SchemeParsers.parseExpr("""((1) (1 2) (1 2 3))""") 
res14: SchemeParsers.ParseResult[Any] = [1.20] parsed: List(List(1), List(1, 2), List(1, 2, 3)) 

Answer 2

Das einzige Problem mit dem Code ist Ihre Benutzung Zeichen statt Strings. Im Folgenden habe ich die redundante ^^ { case s => s } entfernt und alle Zeichen durch Zeichenfolgen ersetzt. Ich werde dieses Problem weiter unten diskutieren.

class SchemeParsers extends RegexParsers { 

// Scheme boolean #t and #f translate to Scala's true and false 
def bool : Parser[Boolean] = 
    ("#t" | "#f") ^^ {case "#t" => true; case "#f" => false} 

// A Scheme identifier allows alphanumeric chars, some symbols, and 
// can't start with a digit 
def id : Parser[String] = 
    """[a-zA-Z=*+/<>!\?][a-zA-Z0-9=*+/<>!\?]*""".r ^^ {case s => s} 

// This interpreter only accepts numbers as integers 
def num : Parser[Int] = """-?\d+""".r ^^ {case s => s toInt} 

// A string can have any character except ", and is wrapped in " 
def str : Parser[String] = "\"" ~> """[^""]*""".r <~ "\"" 

// A Scheme list is a series of expressions wrapped in() 
def list : Parser[List[Any]] = 
    "(" ~> rep(expr) <~ ")" ^^ {s: List[Any] => s} 

// A Scheme expression contains any of the other constructions 
def expr : Parser[Any] = id | str | num | bool | list 
} 

Alle Parsers haben eine implizite accept für ihre Elem Typen. Also, wenn das Basiselement ein Char ist, wie in RegexParsers, dann gibt es eine implizite Annahme Aktion für sie, was passiert hier für die Symbole (, ) und ", die Zeichen in Ihrem Code sind.

Was RegexParsers automatisch zu tun ist, weiß Räume (definiert als protected val whiteSpace = """\s+""".r, so dass Sie, dass außer Kraft setzen könnten) überspringen automatisch am Anfang jeder String oder Regex. Es sorgt auch dafür, dass der Positionierungscursor bei Fehlermeldungen über den Leerraum hinaus bewegt wird.

Eine Konsequenz davon, dass Sie nicht erkannt haben, ist, dass " a string beginning with a space" seinen Präfixraum aus der geparsten Ausgabe entfernt haben wird, was sehr unwahrscheinlich ist, etwas zu sein, was Sie wollen. :-)

Auch, da \s neue Zeilen enthält, wird eine neue Zeile vor jedem Bezeichner akzeptiert, der sein kann oder nicht, was Sie wollen.

Sie können das Überspringen von Leerzeichen in Ihrer Regex als Ganzes deaktivieren, indem Sie skipWhiteSpace außer Kraft setzen. Auf der anderen Seite testet der Standard skipWhiteSpace auf die Länge whiteSpace, so dass Sie ihn möglicherweise ein- und ausschalten können, indem Sie den Wert whiteSpace während des gesamten Parsing-Prozesses manipulieren.