6

この構文に一致させようとしています：

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

私のscala packratパーサーコンビネーターは次のようになります:

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);
    }
}

しかし、これはうまくいきません。それは「貪欲に一致」し、私に教えてくれます：

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

または、|を aに変更すると|||、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)
...

エラーが発生する理由がわかりました。上記のような構文を解析するにはどうすればよいですか? それは私には難解ではないようです

編集: http://scala-programming-language.1934581.n4.nabble.com/Packrat-parser-guidance-td1956908.htmlで参照されている論文に基づいて、 私のプログラムが実際に新しい packrat パーサーを使用していないことがわかりました。

すなわち。に変更Parser[Any]して代わりにPackratParser[Any]使用するlazy valdef

上記を次のように書き直しました。

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);
    }
}
4

2 に答える 2

10

問題は (少なくとも部分的には) 実際に Packrat パーサーを使用していないことです。Scala のPackratParsersトレイトのドキュメントを参照してください。

PackratParsers の使用は、パーサーの使用と非常によく似ています。

  • パーサーを (直接またはサブクラスを介して) 拡張するクラス/特性は、PackratParsers に混在させることができます。例: オブジェクト MyGrammar は、PackratParsers で StandardTokenParsers を拡張します
  • 以前に正式なパラメーターなしで def として宣言された各文法生成は遅延 val になり、その型は Parser[Elem] から PackratParser[Elem] に変更されます。したがって、たとえば def production: Parser[Int] = {...} は lazy val production: PackratParser[Int] = {...} になります。
  • 重要: PackratParsers の使用は、全か無かの決定ではありません。それらは、単一の文法で通常のパーサーと自由に混合できます。

Scala 2.8 のパーサー コンビネーターについては、これを完全に修正するのに十分な知識はありませんが、次の変更により、セミコロンまで解析することができました。これは、あなたが達成したことよりも改善されています。

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))
}
于 2010-07-27T14:28:07.277 に答える
1

生産

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

再帰的に残されます。に展開します。

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

2行目で左再帰が発生します。これが、パーサーがスタックをオーバーフローさせる原因です。

左再帰生成を避けて文法を書き直す必要があります。

expr ::= ID {. [0-9]+}
于 2010-07-27T13:21:38.653 に答える