Parsen rekursive Strukturen in scala

Question

Ich versuche, einen Parser in scala contruct, die eine einfache SQL-ähnliche Strings analysieren kann. Ich habe die Grundlagen bekam arbeiten und kann so etwas wie analysieren:

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

Aber jetzt habe ich mich gefragt, wie verschachtelten und Klassen zu analysieren, d.

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

Die aktuelle Produktion von meiner 'combinedPredicate' sieht wie folgt aus:

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

Ich habe versucht Referenzierung rekursiv die combinedPredicate Produktion in sich, aber das führt zu einer Stackoverflow.

btw, ich experimentiere gerade hier ... nicht die gesamte ansi-99-Spezifikation implementiert;)

Answer 1

Nun, hat Rekursion irgendwie begrenzt werden. In diesem Fall könnten Sie dies tun:

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

So wird es nie Überlauf stapeln, weil zu recurse, muss es zuerst um ein Zeichen zu akzeptieren. Dies ist der wichtigste Teil - wenn Sie immer Rekursion gewährleisten wird nicht passieren, ohne vorher ein Zeichen zu akzeptieren, werden Sie nie in eine unendliche Rekursion erhalten. Es sei denn natürlich, Sie haben unendlich Eingang. : -)

Answer 2

Der Stack-Überlauf Sie erleben, ist wahrscheinlich das Ergebnis einer linksrekursive Sprache:

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

Der Parser Kombinatoren in Scala 2.7 sind Rekursiver Abstieg. Rekursiver Abstieg hat Probleme mit diesen, weil sie keine Ahnung hat, wie das Terminalsymbol ist, wenn sie zum ersten Mal begegnen. Andere Arten von Parsern wie Scala 2.8 der packrat Parser Kombinatoren werden kein Problem damit haben, wenn Sie die Grammatik lazy vals statt Methoden benötigen zu definieren, etwa so:

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

Alternativ können Sie die Sprache Refactoring linke Rekursion zu vermeiden. Aus dem Beispiel bist du mir zu geben, erfordern Klammern in dieser Sprache effektiv das Problem lösen könnte.

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

Nun hat jede tiefere Ebene der Rekursion entspricht andere Klammern analysiert. Sie wissen, Sie müssen nicht tiefer Rekursion, wenn Sie aus den Klammern ausgeführt werden.

Answer 3

Nach etwa Lösungen für Operator Vorrang zu lesen und kam mit dem folgenden:

  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  <~ ")"

Wich ist wahrscheinlich nur eine andere Art zu schreiben, was @ Daniel schrieb;)