Scala Parserのアドホック演算子の優先順位を表す

Question

私は、scala RegexParsersを使って、私が使っているプログラミング言語の算術フラグメント専用のパーサーを作成しようとしています。 現状では、私のトップレベルの表現パーサーの形式は次のとおりです。

parser: Parser[Exp] = binAppExp | otherKindsOfParserLike | lval | int 

それは"a.b, a.b[c.d], a[b], {record=expression, like=this}"のようなものだけで罰金（lvalsを受け付け今、私は"1 + b/c = d"のような表現を可能にしたいのですが、潜在的に（ソースで。スラールではなく、言語ではない）コンパイル時のユーザー定義演算子

最初の考えは、操作を再帰的かつ数値的に優先順位でエンコードすると、より高い優先順位をアドホックに追加することができ、操作式の右辺の優先順位の低いサブクラスを消費するので、かなり一般的なオペラでそのアイデアのおもちゃを作ろうとしていますators。 だから、私はのようなものに構文解析することを"1 * 2+1"が期待しています。ここではcase class Call(functionName: String, args: Seq[Exp]) extends Expです。

代わりに、IntExp(1)として解析します。

これがうまくいかない理由はありますか（私は行方不明のまま再帰的に実行されますか？そうであれば、何か間違っていると思われます。それ以外の理由で間違っているのでしょうか？

def binAppExp: Parser[Exp] = { 
    //assume a registry of operations 
    val ops = Map(
     (7, Set("*", "/")), 
     (6, Set("-", "+")), 
     (4, Set("=", "!=", ">", "<", ">=", "<=")), 
     (3, Set("&")), 
     (2, Set("|")) 
    ) 

    //relevant ops for a level of precedence 
    def opsWithPrecedence(n: Int): Set[String] = ops.getOrElse(n, Set.empty) 

    //parse an op with some level of precedence 
    def opWithPrecedence(n: Int): Parser[String] = ".+".r ^? (
     { case s if opsWithPrecedence(n).contains(s) => s }, 
     { case s => s"SYMBOL NOT FOUND: $s" } 
    ) 

    //assuming the parse happens, encode it as an AST representation 
    def folder(h: Exp, t: LangParser.~[String, Exp]): CallExp = 
     CallExp(t._1, Seq(h, t._2)) 

    val maxPrecedence: Int = ops.maxBy(_._1)._1 

    def term: (Int => Parser[Exp]) = { 
     case 0 => lval | int | notApp | "(" ~> term(maxPrecedence) <~ ")" 
     case n => 
     val lowerTerm = term(n - 1) 
     lowerTerm ~ rep(opWithPrecedence(n) ~ lowerTerm) ^^ { 
      case h ~ ts => ts.foldLeft(h)(folder) 
     } 
    } 

    term(maxPrecedence) 
    } 

Answer 1

さて、私がしようとしていたものは本質的に不可能ではなかったので、細部には間違っていました。

コアの考え方は、優先順位のレベルから演算子/パーサーまでのマッピングを維持し、そのテーブルに基づいてパーズを再帰的に探します。括弧で囲まれた式を許可した場合、括弧内のパーサの呼び出し内で可能な最も先行するパーサへの呼び出しをネストするだけです。誰が今までこのような何かをしたいだけの場合には

は、ここに重く上記にそれを関連付けるためにコメント算術/論理演算子のセットのためのコードがあります：

def opExp: Parser[Exp] = { 
sealed trait Assoc 

val ops = Map(
    (1, Set("*", "/")), 
    (2, Set("-", "+")), 
    (3, Set("=", "!=", ">", "<", ">=", "<=")), 
    (4, Set("&")), 
    (5, Set("|")) 
) 

def opsWithPrecedence(n: Int): Set[String] = ops.getOrElse(n, Set.empty) 

/* before, this was trying to match the remainder of the expression, 
    so something like `3 - 2` would parse the Int(3), 
    and try to pass "- 2" as an operator to the op parser. 
    RegexParsers has an implicit def "literal : String => SubclassOfParser[String]", 
    that I'm using explicitly here. 
*/ 

def opWithPrecedence(n: Int): Parser[String] = { 
    val ops = opsWithPrecedence(n) 
    if (ops.size > 1) { 
    ops.map(literal).fold (literal(ops.head)) { 
     case (l1, l2) => l1 | l2 
    } 
    } else if (ops.size == 1) { 
    literal(ops.head) 
    } else { 
    failure(s"No Ops for Precedence $n") 
    } 
} 

def folder(h: Exp, t: TigerParser.~[String, Exp]): CallExp = CallExp(t._1, Seq(h, t._2)) 

val maxPrecedence: Int = ops.maxBy(_._1)._1 

def term: (Int => Parser[Exp]) = { 
    case 0 => lval | int | "(" ~> { term(maxPrecedence) } <~ ")" 
    case n if n > 0 => 
    val lowerTerm = term(n - 1) 
    lowerTerm ~ rep(opWithPrecedence(n) ~ lowerTerm) ^^ { 
     case h ~ ts if ts.nonEmpty => ts.foldLeft(h)(folder) 
     case h ~ _ => h 
    } 
} 

term(maxPrecedence) 

}