Scala Parser Combinators thủ thuật cho đệ quy bnf?

Question

Im cố gắng để phù hợp với cú pháp sau:

pgm ::= exprs 
exprs ::= expr [; exprs] 
expr ::= ID | expr . [0-9]+ 

My scala sưu tập điện phân tích cú pháp combinator trông như thế này:

import scala.util.parsing.combinator.PackratParsers 
import scala.util.parsing.combinator.syntactical._ 

object Dotter extends StandardTokenParsers with PackratParsers { 
    lexical.delimiters ++= List(".",";") 
    def pgm = repsep(expr,";") 
    def expr :Parser[Any]= ident | expr~"."~num 
    def num = numericLit 

     def parse(input: String) = 
    phrase(pgm)(new PackratReader(new lexical.Scanner(input))) match { 
     case Success(result, _) => println("Success!"); Some(result) 
     case n @ _ => println(n);println("bla"); None 
    } 

    def main(args: Array[String]) { 
     val prg = "x.1.2.3;" + 
      "y.4.1.1;" + 
      "z;" + 
      "n.1.10.30" 


      parse(prg); 
    } 
} 

Nhưng công việc doesnt này. Hoặc là nó "phù hợp với tham lam" và nói với tôi:

[1.2] failure: end of input expected 
x.1.2.3;y.4.1.1;z;n.1.10.30 

hoặc nếu tôi thay đổi | đến một ||| tôi nhận được một stackoverflow:

Exception in thread "main" java.lang.StackOverflowError 
at java.lang.Character.isLetter(Unknown Source) 
at java.lang.Character.isLetter(Unknown Source) 
at scala.util.parsing.combinator.lexical.Lexical$$anonfun$letter$1.apply(Lexical.scala:32) 
at scala.util.parsing.combinator.lexical.Lexical$$anonfun$letter$1.apply(Lexical.scala:32) 
... 

tôi kindoff hiểu tại sao tôi nhận được lỗi; Tôi có thể làm gì để phân tích một cú pháp như trên? Nó không có vẻ rằng bí truyền với tôi

EDIT: Dựa trên giấy được tham chiếu trong http://scala-programming-language.1934581.n4.nabble.com/Packrat-parser-guidance-td1956908.html tôi phát hiện ra rằng chương trình didnt tôi thực sự sử dụng phân tích cú pháp sưu tập điện mới.

Tức là. thay đổi Parser[Any]-PackratParser[Any] và sử dụng lazy val thay vì def

Tôi viết lại trên thế này:

import scala.util.parsing.combinator.PackratParsers 
import scala.util.parsing.combinator.syntactical._ 

object Dotter extends StandardTokenParsers with PackratParsers { 
    lexical.delimiters ++= List(".",";") 
    lazy val pgm : PackratParser[Any] = repsep(expr,";") 
    lazy val expr :PackratParser[Any]= expr~"."~num | ident 
    lazy val num = numericLit 

    def parse(input: String) = 
    phrase(pgm)(new PackratReader(new lexical.Scanner(input))) match { 
     case Success(result, _) => println("Success!"); Some(result) 
     case n @ _ => println(n);println("bla"); None 
    } 

    def main(args: Array[String]) { 
     val prg = "x.1.2.3 ;" + 
      "y.4.1.1;" + 
      "z;" + 
      "n.1.10.30" 


      parse(prg); 
    } 
} 

Answer 1

Vấn đề là (ít nhất một phần) bạn không thực sự sử dụng trình phân tích cú pháp Packrat. Xem tài liệu cho PackratParsers đặc điểm Scala, mà nói

Sử dụng PackratParsers rất giống việc sử dụng phân tích cú pháp:

• bất kỳ lớp/đặc điểm mở rộng phân tích cú pháp (trực tiếp hoặc thông qua một lớp con ) có thể kết hợp trong PackratParsers. Ví dụ: đối tượng MyGrammar kéo dài StandardTokenParsers với PackratParsers
• từng sản xuất trước đây ngữ pháp khai báo là một nét mà không thông số chính thức trở thành một val lười biếng, và kiểu của nó được thay đổi từ Parser [Elem] để PackratParser [Elem]. Vì vậy, ví dụ, sản xuất def: Parser [Int] = {...} trở nên lười biếng val sản xuất: PackratParser [Int] = {...}
• Chú ý: sử dụng PackratParsers không phải là một quyết định tất cả hoặc không có gì . Chúng có thể được trộn lẫn miễn phí với các trình phân tích cú pháp thường lệ trong một ngữ pháp duy nhất.

Tôi không biết đủ về Scala 2.8 của combinators phân tích cú pháp để sửa lỗi này hoàn toàn, nhưng với sự sửa đổi sau đây, tôi đã có thể có được nó để phân tích như xa như các dấu chấm phẩy, mà là một sự cải tiến qua những gì bạn đã hoàn thành.

object Dotter extends StandardTokenParsers with PackratParsers { 
    lexical.delimiters ++= List(".",";") 
    lazy val pgm:PackratParser[Any] = repsep(expr,";") 
    lazy val expr:PackratParser[Any]= ident ||| (expr~"."~numericLit) 

    def parse(input: String) = phrase(expr)(lex(input)) match { 
     case Success(result, _) => println("Success!"); Some(result) 
     case n @ _ => println(n);println("bla"); None 
    } 

    def lex(input:String) = new PackratReader(new lexical.Scanner(input)) 
} 

Answer 2

Việc sản xuất

expr ::= ID | expr . [0-9]+ 

còn lại đệ quy. Nó mở rộng thành

expr ::= ID 
expr ::= expr . [0-9]+ 

nơi đệ quy trái xảy ra trên dòng thứ hai. Đây là nguyên nhân khiến trình phân tích cú pháp tràn ngăn xếp.

Bạn nên viết lại ngữ pháp của mình để tránh các sản phẩm đệ quy trái.

expr ::= ID {. [0-9]+}