Schéma d'analyse syntaxique utilisant des combinateurs d'analyseurs Scala

Question

J'écris un petit interpréteur de schéma dans Scala et je suis confronté à des problèmes d'analyse de listes dans Scheme. Mon code analyse les listes qui contiennent plusieurs nombres, identificateurs et booléens, mais il s'étouffe si j'essaie d'analyser une liste contenant plusieurs chaînes ou listes. Qu'est-ce que je rate?

Voici mon analyseur:

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

Comme il a été correctement signalé par @Gabe, vous a laissé quelques-espaces blancs non gérée:

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

Le seul problème avec le code est votre utilisation de caractères au lieu de chaînes. Ci-dessous, j'ai supprimé le redondant ^^ { case s => s } et remplacé tous les caractères par des chaînes. Je vais discuter plus en détail de ce problème ci-dessous.

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 
} 

Tous Parsers ont un accept implicite pour leurs types Elem. Donc, si l'élément de base est un Char, comme dans RegexParsers, alors il y a une action d'acceptation implicite pour eux, ce qui se passe ici pour les symboles (, ) et ", qui sont des caractères dans votre code.

Qu'est-ce RegexParsers faire est automatiquement sauter des espaces blancs (définis comme protected val whiteSpace = """\s+""".r, vous pouvez donc passer outre cela) automatiquement au début de toute String ou Regex. Il prend également soin de déplacer le curseur de positionnement au-delà de l'espace blanc en cas de message d'erreur. Une conséquence de ceci que vous semblez ne pas avoir réalisé est que " a string beginning with a space" aura son espace de préfixe enlevé de la sortie analysée, qui est très peu probable que ce soit quelque chose que vous voulez. :-)

En outre, puisque \s inclut de nouvelles lignes, une nouvelle ligne sera acceptable avant tout identificateur, ce qui peut être ou ne pas être ce que vous voulez.

Vous pouvez désactiver l'omission d'espace dans votre expression régulière en remplaçant skipWhiteSpace. D'autre part, la valeur par défaut skipWhiteSpace teste la longueur de whiteSpace, vous pouvez donc l'activer ou la désactiver en manipulant simplement la valeur de whiteSpace tout au long du processus d'analyse.