Il modo giusto per leggere dall'elenco dei token per implementare l'albero di analisi

Sto provando ad affrontare il While problema di lingua su HackerRank usando Scala. Mi è stato assegnato un set di regole grammaticali e devo implementare l'interprete vero e proprio sottostante.

Ho deciso di avvicinarmi a questo costruendo un lexer e un parser in due fasi separate. Il mio lexer funziona perfettamente: codifica correttamente i token e li racchiude in un List di Tokens dove Tokens è definito come segue:

case class Token(typeof: String, value: Any);

In questo momento, il mio problema è puramente concettuale: come dovrei scorrere l'elenco dei token per implementare un albero di analisi?

Nota che non ho ancora implementazioni per i nodi reali del mio albero di analisi, poiché voglio risolvere questo problema prima (anche se sono felice di sentire suggerimenti per lo stesso se è indispensabile per risolvere questo problema) .

Ecco cosa ho fatto finora:

• Ho dato un'occhiata a l'algoritmo dello shunting-yard , ma non lo sono certo come generalizzarlo per qualcosa al di là delle operazioni aritmetiche. Ho pensato di avere stack multipli progettati per diversi tipi di nodi, ma non sono convinto che sia il modo giusto per farlo - questo sarebbe facilmente impossibile da mantenere.

• Ho considerato un ingenuo attraversamento lineare in cui creo una lista vuota, inserisco i miei token dal mio elenco di token uno alla volta e analizzo ogni volta lo stack cercando di far corrispondere una regola di grammatica ad esso (se corrisponde, rimuovo i nodi dalla lista altrimenti lo lascio essere), ma sono riluttante a farlo perché sembra a) inefficiente e b) sconfigge il punto di una fase di lexing separata. Sto cercando qualcosa di più pulito.

Oltre a questo, sono bloccato. Sono nuovo nel gioco del parsing e vorrei capire qual è l'approccio giusto.

HackerRank supporta solo Scala 2.11, che ha rimosso ufficialmente la libreria parser-combinator dalla libreria standard, quindi non posso usarla. Sono felice di utilizzare qualsiasi funzione funzionale che Scala porti, ma non mi interessa fare affidamento su qualcosa che implementa solo linguaggi funzionali solo .

Per la cronaca, ecco il mio codice Lexer:

import scala.collection.mutable.HashMap

class Lexer {
    // defining keywords and tokens
    val parenthesis_mapping = HashMap("""(""" -> """)""","""{""" -> """}""");
    val keywords = List("if", "then", "else", "while", "do", "true", "false");
    val boolean_operators = List("and","or")
    val arithmetic_operators = List("""+""","""-""","""/""","""*""",""">""","""<""")
    val variables = """([a-z]+)""".r
    val numbers = """([0-9]*\.?[0-9]+)""".r

    // converts string token to corresponding Token type
    def convert(input : String): Token = {
        if (keywords.contains(input)) { return Token("KEYWORD",input) }
        else if (boolean_operators.contains(input)) { return Token("BOOLEAN",input) }
        else if (arithmetic_operators.contains(input)) { return Token("ARITHMETIC", input) }
        else if (parenthesis_mapping.keys.exists(_ == input)) { return Token("OPENING", input) }
        else if (parenthesis_mapping.values.exists(_ == input)) { return Token("CLOSING", input) }
        else { return input match {
            case variables(output) => Token("VARIABLE", output)
            case """:=""" => Token("ASSIGNMENT", null)
            case numbers(output) => Token("NUMBER", output.toInt)
            case """;""" => Token("BREAK", null)
            case _ => Token("NULL", input)
        } }
    }

   // splits input string and applies 'convert' to each token
   def lex(strings: String): List[Token] = {...} // only providing signature here
  }

ed ecco la grammatica che devo implementare

Below is the description of grammar that we will use:

• x, y ∈ Var (variables)

• n ∈ Num (numerals/integers)

• op_{a} ∈ Opa (arithmetic operators)
  ob_{a} ::= + | - | * | /

• op_{b} ∈ Opb (boolean operators)
  op_{b} ::= and | or

• op_{r} ∈ Opr (relational operators)
  op_{r} ::= > | <

• a ∈ AExp (arithmetic expressions)
  a ::= x | n | a1 opa a2 | ( a )

• b ∈ BExp (boolean expressions)
  b ::= true | false | b1 opb b2 | a1 opr a2 | ( b )

• S ∈ Stmt (statements)
  S ::= x := a | S1 ; S2 | if b then { S1 } else { S2 } | while b do { S }

Here all operators are left associative. Their precedence order is as follows.

1. Arithmetic Operators: (*, /) > (+, -) > (>, <)
2. Boolean Operators: and > or.

You can safely assume that all variables have integer type and are initialized properly. All variables name will consist of only lowercase letter ('a'-'z') and it's length will not exceed 10.

Note that ";" is more like of a sequencing operator. It is used to concatenate two statements. That's why there will be no ";" at the end of block of statements.

Un esempio della sintassi risultante:

fact := 1 ;
val := 10000 ;
cur := val ;
mod := 1000000007 ;

while ( cur > 1 )
  do
   {
      fact := fact * cur ;
      fact := fact - fact / mod * mod ;
      cur := cur - 1
   } ;

cur := 0