analisi delle strutture ricorsive in scala

Question

Sto cercando di creare un parser in scala in grado di analizzare semplici stringhe simili a SQL. Ho le basi funzionanti e posso analizzare qualcosa del tipo:

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

Ma ora mi chiedevo come analizzare nidificati e classi, ad esempio

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

L'attuale produzione del mio "combinatoPredicato" è simile al seguente:

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

Ho provato a fare riferimento in modo ricorsivo alla produzione combinata di Critical all'interno di se stessa, ma questo si traduce in uno stackoverflow

a proposito, sto solo sperimentando qui ... non implementando l'intera specifica ansi-99;)

Answer 1

Beh, la ricorsione deve essere delimitata in qualche modo. In questo caso, potresti farlo:

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

Quindi non impilerà mai l'overflow perché, per ricorrere, deve prima accettare un personaggio. Questa è la parte importante: se assicuri sempre che la ricorsione non accada senza prima accettare un personaggio, non entrerai mai in una ricorsione infinita. A meno che, ovviamente, tu abbia un input infinito. : -)

Answer 2

L'overflow dello stack che stai riscontrando è probabilmente il risultato di un linguaggio ricorsivo a sinistra:

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

I combinatori di parser in Scala 2.7 sono parser di discesa ricorsivi. I parser di discesa ricorsivi hanno problemi con questi perché non hanno idea di come sia il simbolo terminale quando lo incontrano per la prima volta. Altri tipi di parser come i combinatori di parser packrat di Scala 2.8 non avranno problemi con questo, anche se dovrai definire la grammatica usando lazy val invece dei metodi, in questo modo:

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

In alternativa, puoi riformattare la lingua per evitare la ricorsione a sinistra. Dall'esempio che mi stai dando, richiedere parentesi in questa lingua potrebbe risolvere efficacemente il problema.

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

Ora ogni livello più profondo di ricorsione corrisponde a un'altra parentesi analizzata. Sai che non devi ricorrere più in profondità quando finisci le parentesi.

Answer 3

Dopo aver letto le soluzioni per la precedenza degli operatori e ho trovato quanto segue:

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

Probabilmente è solo un altro modo di scrivere ciò che ha scritto @Daniel;)