Scala：サンプルパーサーを使用したパーサーコンビネーター

時々、自分の小さなプログラミング言語を考え出し、インタプリタを書きたいと思っています。 今回、私はscalaで書き始め、パーサーコンビネーターライブラリについて学び、驚いた。パーサーを簡単かつ簡単に書くことができることがわかった。 この記事を「フクロウの描き方」のチュートリアルにしないために、以下は"1 + 2 * sin(pi / 2)"



ような式の解析と計算の実装です。

式自体の解析と計算は、空でない行を44行だけ占有します。その数を減らすことを強く望んでいたわけではありませんが、本当にシンプルで簡潔に見えます。 githubのプロジェクト 。

比較のために：

• 長いjavaの例
• C＃の短いがあいまいな例
• パーボイルドを使用したjavaの例

したがって、結果が表示されるのを待つことができない場合：

 object FormulaParser extends RegexParsers with PackratParsers { def id: Parser[Id] = "[a-zA-Z][a-zA-Z0-9_]*".r ^^ Id def number: Parser[Number] = "-" ~> number ^^ (n => Number(-n.value)) | ("[0-9]+\\.[0-9]*".r | "[0-9]+".r) ^^ (s => Number(s.toDouble)) def funcCall: Parser[FuncCall] = id ~ ("(" ~> expression <~ ")") ^^ {case id ~ exp => FuncCall(id, exp)} def value: Parser[Expression] = number | funcCall | id | ("(" ~> expression <~ ")") lazy val term: PackratParser[Expression] = term ~ ("*" | "/") ~ value ^^ binOperation | value lazy val expression: PackratParser[Expression] = expression ~ ("+" | "-") ~ term ^^ binOperation | term ... }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次の行を見てください。

 def value: Parser[Expression] = number | funcCall | id | ("(" ~> expression <~ ")")
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

疑い深く文法の説明に似ていますが、開発環境がほとんどのエラーをすぐに検出して強調表示できる有効なコードです。

これは、次の理由で可能です。

1. Scalaでは、メソッドが"~", "~>", "<~", "|", "^^"
   
   
   
   などの素晴らしい名前を付けることができます。 p
   
   
   
   パーサーとq
   
   
   
   パーサーの組み合わせはp〜qとして記述され、それらの1つを選択する機能： p|q
   
   
   
   。 p.andThen(q)
   
   
   
   またはp.or(q)
   
   
   
   よりもはるかに読みp.or(q)
   
   
   
   
2. 暗黙のおかげで、文字列"abc"
   
   
   
   と正規表現"[0-9]+".r
   
   
   
   両方が必要に応じてパーサーに変換されます。
3. この言語には、エラーをすぐにキャッチできる強力な静的型システムがあります。

私はあなたに興味を持ったと思うので、すべてが整然とするでしょう。

目次：

1. Pegexパーサー
2. Packratパーサー
3. パーサーコード全体
4. 式評価
5. 結論

パーサーコンビネーター。

これらのクラスは標準言語ライブラリに含まれていましたが、別のライブラリに持ち出されました。 最後に、より詳細な情報を見つけることができるリンクを提供しました。

正規表現パーサー

したがって、最も単純なのはRegexParsersです。 文字列および正規表現からパーサーへの暗黙的な変換を追加します。

 object SimpleExample extends RegexParsers { def boolTrue: Parser[Boolean] = "true" ^^ (_ => true) //    "true",   ,       boolean def bool: Parser[Boolean] = ("true" | "false") ^^ (_ == "true") //         def alternativeBool: Parser[Boolean] = "true" ^^ (_ => true) | "false" ^^ (_ => false) //       def int: Parser[Int] = "[0-9]+".r ^^ (_.toInt) //       . //  .r      def id: Parser[Id] = "[a-zA-Z][a-zA-Z0-9_]*".r ^^ Id // Id - ,       Id }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ところで、 ~



アイコンは、パーサーメソッドだけでなく、値のペアを格納するケースクラスの名前も示します。 Parsers.scala



のコードのParsers.scala



：

 case class ~[+a, +b](_1: a, _2: b) { override def toString = "("+ _1 +"~"+ _2 +")" }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

複数のパーサーから1つを収集するとします。

 def intInBrackets: Parser[Int] = "(" ~ int ~ ")" ^^ (p => p._1._2)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

どうなるの？

1. "("
   
   
   
   暗黙的に文字列から文字列を返すパーサーに変わります
2. パーサーのint
   
   
   
   はint
   
   
   
   返します
3. "(" ~ int
   
   
   
   〜intは~[String, Int]
   
   
   
   パーサーを作成します
4. "(" ~ int ~ ")"
   
   
   
   は、 ~[~[String, Int], String]
   
   
   
   を返すパーサーを作成します
5. パーサーは^^
   
   
   
   を呼び出します
6. 関数はp
   
   
   
   タイプ~[~[String, Int], String]
   
   
   
   引数p
   
   
   
   を取り~[~[String, Int], String]
   
   
   
   を返すメソッドに渡されます

この場合、ブラケットには有用な情報は含まれていません。 これを行うことができます：

 def intInBrackets: Parser[Int] = "(" ~> int <~ ")"
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

今回は、括弧は破棄されます。

• "(" ~> int
  
  
  
  は、括弧を解析してからInt
  
  
  
  を解析するパーサーを作成しますが、 Int
  
  
  
  のみを返します
• int <~ ")"
  
  
  
  は同じように機能しますが、左引数に対して

演算子<~



を使用した式は、優先度があまり高くないため、括弧で囲むことをお勧めします。

def

 def funcCall: Parser[FuncCall] = id ~ ("(" ~> expression <~ ")") ^^ (pair => FuncCall(pair._1, pair._2))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これで、次のコードの機能が明確になります。

 def number: Parser[Number] = "-" ~> number ^^ (n => Number(-n.value)) | ("[0-9]+\\.[0-9]*".r | "[0-9]+".r) ^^ (s => Number(s.toDouble)) // s.toDouble    . def value: Parser[Expression] = number | funcCall | id | ("(" ~> expression <~ ")") private def binOperation(p: Expression ~ String ~ Expression) = p match { case e1 ~ op ~ e2 => BinOperation(e1, BinOperator(op), e2) }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

私は少し面倒で、標準的な方法を使用して文字列を数値に変換しました。 時間を節約する必要があります）

パーサーの説明はコードであるため、あいまいな文法は引き続き機能します。 解析number | funcCall | id



の例ではnumber | funcCall | id



number | funcCall | id



失敗した場合にnumber



を解析しようとしているid-関数呼び出しなど たとえば、 (id | funcCall)



"sin（x）"を解析してId("sin")



を解析しようとする場合、順序が重要になる場合があり、 funcCall



パーサーfuncCall



呼び出されません。 正常に動作させるには、 (funcCall | id)



と記述する方が適切です。

Packratパーサー

1のシーケンスを解析したいとしましょう：

 object Ones extends RegexParsers { def ones: Parser[Any] = ones ~ "1" | "1" }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

解析のones



は、解析のones



を呼び出すという事実から始まります。

それらを解析しようとすると、スタックがオーバーフローします。

この場合、何かが「吸収」されるたびに説明を変更できます。 例：

 def ones: Parser[Any] = "1" ~ ones | "1"
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

しかし、文法はいつでも簡単に書き換えられるとは限りません。 タイプ3-2-1



式は(3-2)-1



として正確に認識される必要があり、オプション3-(2-1)



は機能しません。 分割では、同様の問題が発生します。 文法を複雑にすることなくこれを行う方法は？

Packrat-パーサーは私たちを救います。 彼らの考えは、パーサーが自分自身の呼び出しに関する情報を保存できるということです。 たとえば、作業の結果を保存し、同じことを2回解析しないようにしたり、再帰がある場合に正しく動作したりします。

 object Ones extends RegexParsers with PackratParsers{ lazy val ones: PackratParser[Any] = ones ~ "1" | "1" }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

PackratParsersトレイには、行やその他のものを「必要な」タイプのパーサーに暗黙的に変換します。

PackratParserは、一度だけ作成し、変数に保存するのが最適です。 さらに、パーサーp



がq



を使用し、 q



がp



を使用する場合、遅延初期化を使用する必要があります。

  lazy val term: PackratParser[Expression] = term ~ ("*" | "/") ~ value ^^ binOperation | value lazy val expression: PackratParser[Expression] = expression ~ ("+" | "-") ~ term ^^ binOperation | term
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

3-2-1を（3-2）-1として解析するのがどれほど簡単で簡単かは今では明らかだと思います。

おそらく質問があります：パーサーは情報をどこに保存しますか？ PackratParser内に直接保存されている場合、別の入力に対してパーサーを呼び出すと、誤った結果が生じる可能性があります。 したがって、必要な情報は、パーサーの「入力」データとともに保存されます。 ライブラリコードを調べて、これを確認できます。

 class PackratReader[+T](underlying: Reader[T]) extends Reader[T] { outer => private[PackratParsers] val cache = mutable.HashMap.empty[(Parser[_], Position), MemoEntry[_]] ... }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

したがって、パーサーは文字列を入力として受け入れませんが、 new PackratReader(new CharSequenceReader(string))



受け入れます

 def apply(code: String): Either[LexerError, Expression] = parse(expression, new PackratReader(new CharSequenceReader(code))) match { case Success(result, next) => Right(result) case NoSuccess(msg, next) => Left(LexerError(msg)) }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

最もクールなのは、packratパーサーを使用しても何も義務付けられないことです。通常のパーサーと組み合わせたり、その逆も可能です。

パーサーの準備ができました

全体としてのコード：

 object FormulaParser extends RegexParsers with PackratParsers { def id: Parser[Id] = "[a-zA-Z][a-zA-Z0-9_]*".r ^^ Id def number: Parser[Number] = "-" ~> number ^^ (n => Number(-n.value)) | ("[0-9]+\\.[0-9]*".r | "[0-9]+".r) ^^ (s => Number(s.toDouble)) def funcCall: Parser[FuncCall] = id ~ ("(" ~> expression <~ ")") ^^ {case id ~ exp => FuncCall(id, exp)} def value: Parser[Expression] = number | funcCall | id | ("(" ~> expression <~ ")") lazy val term: PackratParser[Expression] = term ~ ("*" | "/") ~ value ^^ binOperation | value lazy val expression: PackratParser[Expression] = expression ~ ("+" | "-") ~ term ^^ binOperation | term private def binOperation(p: Expression ~ String ~ Expression) = p match { case e1 ~ op ~ e2 => BinOperation(e1, BinOperator(op), e2) } def apply(code: String): Either[ParserError, Expression] = parse(expression, new PackratReader(new CharSequenceReader(code))) match { case Success(result, next) => Right(result) case NoSuccess(msg, next) => Left(ParserError(msg)) } case class ParserError(msg: String) } sealed trait Expression case class BinOperator(operator: String) case class Number(value: Double) extends Expression case class Id(name: String) extends Expression case class BinOperation(left: Expression, op: BinOperator, right: Expression) extends Expression case class FuncCall(funcName: Id, argument: Expression) extends Expression
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

解析の結果は、ツリーまたはエラーメッセージのいずれかです。

case



クラスは値の単なるラッパークラスであり、すべてExpressionインターフェイスを実装します。 sealed



という言葉は、このインターフェースを実装するクラスを同じファイルに含める必要があることを意味します。 これにより、 Expression



は4つのタイプのいずれかであると自信を持って言えます。

式の評価

式を評価するコードも簡単です。 正しい表現が入力されていると思います。

 object Evaluator { def apply(expression: Expression, variables: (String) => Double = Map.empty, functions: (String) => (Double) => Double = Map.empty): Double = { def eval(exp: Expression) = this (exp, variables, functions) expression match { case Number(value) => value case Id(name) => variables(name) case BinOperation(left, op, right) => operator2func(op)(eval(left), eval(right)) case FuncCall(funcId, expr) => functions(funcId.name)(eval(expr)) } } def operator2func(binOperator: BinOperator): (Double, Double) => Double = binOperator.operator match { case "+" => (a, b) => a + b case "-" => (a, b) => a - b case "*" => (a, b) => a * b case "/" => (a, b) => a / b } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Rock Chips- apply



関数内でeval



関数を宣言して、コードを読みやすくすることができapply



。 2番目のトリック-引数として、デフォルトでMap.empty



をMap.empty



します。 それは空であるため、任意の型であり、不変であり、したがって空のままであり、実際には同じオブジェクト-シングルトンへの参照を取得します。 Map.empty



にはapply(a: In):Out



メソッドがあります-これは関数と考えることができます。

ほとんどすべて

式の解析と評価の準備ができました。 結果のコード行を計算してみましょう（空ではない）：

1. パーサー：18行
2. ASTを記述するためのケースクラス：6
3. 式の評価：20行。

それだけです。コードは読みやすく、変更も簡単です。また、実際には余分なものは含まれていません。 美人！

動作しますか？

パーサーを記述する段階でもこれについて考える必要がありますが、チェックコードは何にも影響を与えないため、ここでのみ説明します。 （もちろん、テストを書くこともできます...しかし、この記事はテストではなくパーサーを書くことについてですので、できるだけ簡単にしました）

 object Main extends App { def eval(code: String, variables: (String) => Double = Map.empty, functions: (String) => (Double) => Double = Map.empty) = { val parsed = FormulaParser(code) parsed.left.foreach(error => println(s"\'$code\' parsing error: $error")) parsed.right.map(expr => Evaluator(expr, variables, functions)).foreach(d => println(s"\'$code\' = $d")) } eval("1") eval("0.1") eval("1.") eval(" 1 ") eval("-0.1") eval("1+2") eval("2-1") eval("2*3") eval("4/2") val vars = Map( "pi" -> math.Pi, "e" -> math.E) val funcs: (String) => (Double) => Double = Map( "sin" -> math.sin, "cos" -> math.cos, "inc" -> { d: Double => d + 1 } ) eval("pi", vars) eval("inc(e)", vars, funcs) eval("2+2*2") eval("1+2*(3+4*5)") eval("8/2/2") eval("8-1-2") eval("1. + 2.0 * sin(pi / 2)", vars, funcs) }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

おわりに

深刻な目的のために、パーサージェネレーターなどがあります。

ただし、比較的単純なものを解析したい場合は、試してすぐにフィードバックを取得します。上記のアプローチを使用できます。 ロシア語や英語でもほとんど情報がありません。 この記事が誰かの役に立つことを願っています。

便利なリンク：

1. githubライブラリ
2. DSL解析の例
3. 「scalaでのプログラミング」、 「パーサコンビネータ」の章

上記のコードをgithubに投稿しました

PS私はまだ、チェスと詩人でルアのような言語の私自身の通訳を追加する目標を持っています。 私は言語の構文を考え出したようで、パーサーを書く過程で矛盾に遭遇しました-私はいくつかの詩人を捨て、チェスをチェッカーに置き換えなければなりませんでしたが、結果はまだ非常に興味深いものです。