Phân tích ngôn ngữ dựa trên thụt đầu dòng bằng cách sử dụng bộ phối hợp phân tích cú pháp phân tách cú pháp

Question

Có cách nào thuận tiện để sử dụng bộ phối hợp phân tích cú pháp của Scala để phân tích ngôn ngữ có thụt lề không? (Ví dụ Python)

Answer 1

Giả sử chúng ta có một ngôn ngữ rất đơn giản, nơi đây là một chương trình hợp lệ

block 
    inside 
    the 
    block 

và chúng tôi muốn phân tích này thành một List[String] với mỗi dòng bên trong khối như một String.

Trước tiên, chúng tôi xác định phương thức lấy mức thụt lề tối thiểu và trả về trình phân tích cú pháp cho một dòng có mức thụt đầu dòng đó.

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

Sau đó, chúng tôi xác định một khối có mức thụt lề tối thiểu bằng cách lặp lại trình phân tích cú pháp dòng với dấu phân cách phù hợp giữa các dòng.

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

Bây giờ chúng ta có thể xác định một phân tích cú pháp cho ngôn ngữ nhỏ của chúng tôi như thế này:

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

đầu tiên Nó xác định mức thụt đầu dòng hiện tại và sau đó đi mà như tối thiểu để phân tích cú pháp dòng. Hãy thử nghiệm nó:

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

println(block(new CharSequenceReader(s))) 

Và chúng tôi nhận

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

Đối với tất cả những điều này để biên dịch, bạn cần phải nhập khẩu này

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

Và bạn cần phải đặt tất cả mọi thứ vào một đối tượng mà kéo dài RegexParsers giống như vậy

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

Answer 2

Từ những gì tôi biết, không, các bộ phối hợp phân tích cú pháp Scala không có hỗ trợ cho loại điều này ra khỏi hộp. Bạn chắc chắn có thể làm điều đó bằng cách phân tích không gian trắng theo một cách có ý nghĩa, nhưng bạn sẽ gặp phải một số vấn đề vì bạn cần một số dạng máy trạng thái để theo dõi ngăn xếp thụt đầu dòng.

Tôi khuyên bạn nên thực hiện bước tiền xử lý. Đây là một tiền xử lý ít mà thêm dấu để tách khối thụt vào:

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

Thực hiện văn bản này cho phép:

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

... kết quả sau

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

Và bạt bạn có thể sử dụng thư viện tổ hợp để thực hiện phân tích cú pháp theo cách đơn giản hơn.

Hy vọng điều này sẽ giúp