analyser des structures récursives en scala

Question

J'essaie de construire un analyseur dans scala qui peut analyser des chaînes simples ressemblant à du SQL. J'ai les bases qui fonctionnent et je peux analyser quelque chose comme:

select id from users where name = "peter" and age = 30 order by lastname

Mais maintenant, je me suis demandé comment analyser les classes imbriquées et imbriquées, c'est-à-dire.

select name from users where name = "peter" and (age = 29 or age = 30)

La production actuelle de mon 'combinePredicate' se présente comme suit:

def combinedPredicate = predicate ~ ("and"|"or") ~ predicate ^^ {
  case l ~ "and" ~ r => And(l,r)
  case l ~ "or" ~ r => Or(l,r)
}

J'ai essayé de référencer de manière récursive la production combinePredicate en elle-même, mais il en résulte un flux de pile.

btw, je suis juste en train d'expérimenter ici ... ne pas mettre en œuvre l'ensemble de la spécification ansi-99;)

Answer 1

Eh bien, la récursivité doit être délimitée d’une manière ou d’une autre. Dans ce cas, vous pouvez faire ceci:

def combinedPredicate = predicate ~ rep( ("and" | "or" ) ~ predicate )
def predicate = "(" ~ combinedPredicate ~ ")" | simplePredicate
def simplePredicate = ...

Donc, il n'y aura jamais de débordement de pile car, pour récidiver, il doit d'abord accepter un caractère. C'est la partie la plus importante. Si vous vous assurez toujours que la récursivité ne se produira pas sans d'abord accepter un personnage, vous ne rentrerez jamais dans une récursion infinie. À moins, bien sûr, d'une entrée infinie. : -)

Answer 2

Le débordement de pile que vous rencontrez est probablement le résultat d'un langage récursif de gauche:

def combinedPredicate = predicate ~ ...
def predicate = combinedPrediacate | ...

Les combinateurs d’analyseur de Scala 2.7 sont des analyseurs d’analyse de descente récursive. Les analyseurs récursifs de descente ont des problèmes avec ceux-ci car ils ne savent pas du tout quel est le symbole du terminal quand ils le rencontrent. D'autres types d'analyseurs tels que les combinateurs d'analyseurs de packrat de Scala 2.8 n'auront aucun problème à cela, bien que vous deviez définir la grammaire à l'aide de lazy val au lieu de méthodes, comme ceci:

lazy val combinedPredicate = predicate ~ ...
lazy val predicate = combinedPrediacate | ...

Vous pouvez également modifier la langue pour éviter la récursion gauche. D'après l'exemple que vous me donnez, le fait d'exiger des parenthèses dans cette langue pourrait résoudre le problème de manière efficace.

def combinedPredicate = predicate ~ ...
def predicate = "(" ~> combinedPrediacate <~ ")" | ...

Chaque niveau de récursion plus profond correspond à une autre parenthèse analysée. Vous savez que vous n’avez pas à récidiver plus profondément lorsque vous êtes à court de parenthèses.

Answer 3

Après avoir pris connaissance des solutions concernant la priorité des opérateurs, vous avez proposé:

  def clause:Parser[Clause] = (predicate|parens) * (
            "and" ^^^ { (a:Clause, b:Clause) => And(a,b) } |
            "or" ^^^ { (a:Clause, b:Clause) => Or(a,b) } )

  def parens:Parser[Clause] = "(" ~> clause  <~ ")"

Ce qui est probablement une autre façon d’écrire ce que @ Daniel a écrit;)