使用Scala解析器組合器解析基於縮進的語言

Question

是否有一種方便的方式使用Scala的解析器組合器來解析縮進顯着的語言？ （例如Python）的

Answer 1

假設我們有一個非常簡單的語言，其中這是一個有效的程序

block 
    inside 
    the 
    block 

，我們希望與塊內每行一個String解析成List[String]這一點。

我們首先定義一個方法，該方法採用最小縮進級別並返回具有該縮進級別的行的解析器。

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

然後，我們通過在行之間用合適的分隔符重複行解析器來定義具有最小縮進級別的塊。

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

現在，我們可以定義一個解析器爲我們這樣的小語：

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

它首先確定當前縮進級別，然後傳遞，作爲最小的線解析器。讓我們測試一下：

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

println(block(new CharSequenceReader(s))) 

而我們得到

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

對於這一切來編譯，你需要這些進口

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

而且你需要把一切都變成一個擴展的對象RegexParsers像這樣

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

Answer 2

從我所知，不，Scala解析器組合器不支持這種開箱即用的東西。您當然可以通過以有意義的方式解析空白區域來做到這一點，但由於您需要某種形式的狀態機來跟蹤縮進堆棧，因此您會遇到一些問題。

我會推薦做一個預處理步驟。這裏是一個小預處理這增加標記來分隔縮進塊：

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' 
} 

執行此文給：

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

...以下結果

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

而且後記你可以使用combinator庫以更簡單的方式進行解析。

希望這會有幫助