Parsing einer indentation-basierten Sprache mit Hilfe von Scala-Parser-Kombinatoren

Question

Gibt es eine bequeme Möglichkeit, die Parser-Kombinatoren von Scala zu verwenden, um Sprachen zu analysieren, bei denen der Einzug wichtig ist? (Zum Beispiel Python)

Answer 1

Nehmen wir an, wir haben eine sehr einfache Sprache, wo diese ein gültiges Programm ist

block 
    inside 
    the 
    block 

und wir wollen, dass diese mit jeder Zeile in eine List[String] analysieren innerhalb des Blocks als ein String.

Zuerst definieren wir eine Methode, die eine minimale Einrückungsebene annimmt und einen Parser für eine Zeile mit dieser Einrückungsebene zurückgibt.

def line(minIndent:Int):Parser[String] = 
    repN(minIndent + 1,"\\s".r) ~ ".*".r ^^ {case s ~ r => s.mkString + r} 

Dann definieren wir einen Block mit einem minimalen Einrückungslevel, indem wir den Linienparser mit einem geeigneten Trennzeichen zwischen den Zeilen wiederholen.

def lines(minIndent:Int):Parser[List[String]] = 
    rep1sep(line(minIndent), "[\n\r]|(\n\r)".r) 

Jetzt können wir einen Parser für unsere kleine Sprache wie folgt definieren:

val block:Parser[List[String]] = 
    (("\\s*".r <~ "block\\n".r) ^^ { _.size }) >> lines 

Es bestimmt zunächst die aktuelle Ebene Vertiefung und gelangt dann, dass als Minimum auf den Linien-Parser. Lassen Sie uns testen:

val s = 
"""block 
    inside 
    the 
    block 
outside 
the 
block""" 

println(block(new CharSequenceReader(s))) 

Und wir bekommen

[4.10] parsed: List( inside,  the,  block) 

Für all dies zu kompilieren, müssen Sie diese Einfuhren

import scala.util.parsing.combinator.RegexParsers 
import scala.util.parsing.input.CharSequenceReader 

Und Sie brauchen, um alles in ein Objekt zu setzen, die sich RegexParsers so

object MyParsers extends RegexParsers { 
    override def skipWhitespace = false 
    .... 

Answer 2

Von dem, was ich weiß, nein, die Scala-Parser-Kombinierer haben keine Unterstützung für diese Art von Ding aus der Box. Sie können dies sicherlich tun, indem Sie Leerraum auf eine sinnvolle Weise analysieren, aber Sie werden einige Probleme haben, da Sie eine Form von Zustandsmaschine benötigen, um den Eindrucksstapel zu verfolgen.

Ich würde einen Vorverarbeitungsschritt empfehlen. Hier ist ein kleiner Präprozessor des Marker fügt gegliederte Blöcke zu trennen:

object Preprocessor { 

    val BlockStartToken = "{" 
    val BlockEndToken = "}" 

    val TabSize = 4 //how many spaces does a tab take 

    def preProcess(text: String): String = { 
     val lines = text.split('\n').toList.filterNot(_.forall(isWhiteChar)) 
     val processedLines = BlockStartToken :: insertTokens(lines, List(0)) 
     processedLines.mkString("\n") 
    } 

    def insertTokens(lines: List[String], stack: List[Int]): List[String] = lines match { 
     case List() => List.fill(stack.length) { BlockEndToken } //closing all opened blocks 
     case line :: rest => { 
      (computeIndentation(line), stack) match { 
       case (indentation, top :: stackRest) if indentation > top => { 
        BlockStartToken :: line :: insertTokens(rest, indentation :: stack) 
       } 
       case (indentation, top :: stackRest) if indentation == top => 
        line :: insertTokens(rest, stack) 
       case (indentation, top :: stackRest) if indentation < top => { 
        BlockEndToken :: insertTokens(lines, stackRest) 
       } 
       case _ => throw new IllegalStateException("Invalid algorithm") 
      } 
     } 
    } 


    private def computeIndentation(line: String): Int = { 
     val whiteSpace = line takeWhile isWhiteChar 
     (whiteSpace map { 
      case ' ' => 1 
      case '\t' => TabSize 
     }).sum 
    } 

    private def isWhiteChar(ch: Char) = ch == ' ' || ch == '\t' 
} 

Ausführung für diesen Text gibt:

val text = 
    """ 
     |line1 
     |line2 
     | line3 
     | line4 
     | line5 
     |  line6 
     |  line7 
     | line8 
     | line9 
     |line10 
     | line11 
     | line12 
     | line13 
    """.stripMargin 
println(Preprocessor.preProcess(text)) 

... folgendes Ergebnis

{ 
line1 
line2 
{ 
    line3 
    line4 
    line5 
{ 
     line6 
     line7 
} 
} 
{ 
    line8 
    line9 
} 
line10 
{ 
    line11 
    line12 
    line13 
} 
} 

Und anschliessend können Sie Verwenden Sie die Kombinator-Bibliothek, um das Parsen einfacher durchzuführen.

Hoffe, dies hilft