電卓を作る、第 2 回

Scala のパーサー・コンビネーター

Ted Neward
配信 2008年 10月 21日

コンテンツシリーズ

このコンテンツは全#シリーズのパート#です：多忙な Java 開発者のための Scala ガイド

https://www.ibm.com/developerworks/jp/views/global/libraryview.jsp?series_title_by=多忙な+java+開発者のための+scala+ガイド

このシリーズの続きに乞うご期待。

このコンテンツはシリーズの一部分です：多忙な Java 開発者のための Scala ガイド

このシリーズの続きに乞うご期待。

前回の記事で行った大変な作業を思い出してください。DSL (ここでは、ばかばかしいほど単純な電卓用言語) を作成しようとして、この言語で利用可能な、次のようなオプションを含むツリー構造を作成しました。

バイナリーの加算/減算/乗算/除算のための演算子
単項否定演算子
数値

この背後にある実行エンジンは、これらの演算の実行方法を知っており、さらには結果を得る上で必要な計算量を減らすための明示的な最適化ステップまで備えています。

前回の記事を終えた時点でのコードは次のようなものでした。

リスト 1. 電卓用の DSL: AST とインタープリター

package com.tedneward.calcdsl
{
  private[calcdsl] abstract class Expr
  private[calcdsl]  case class Variable(name : String) extends Expr
  private[calcdsl]  case class Number(value : Double) extends Expr
  private[calcdsl]  case class UnaryOp(operator : String, arg : Expr) extends Expr
  private[calcdsl]  case class BinaryOp(operator : String, left : Expr, right : Expr) 
   extends Expr

  object Calc
  {
    /**
     * Function to simplify (a la mathematic terms) expressions
     */
    def simplify(e : Expr) : Expr =
    {
      e match {
        // Double negation returns the original value
        case UnaryOp("-", UnaryOp("-", x)) => simplify(x)
  
        // Positive returns the original value
        case UnaryOp("+", x) => simplify(x)
  
        // Multiplying x by 1 returns the original value
        case BinaryOp("*", x, Number(1)) => simplify(x)
  
        // Multiplying 1 by x returns the original value
        case BinaryOp("*", Number(1), x) => simplify(x)
  
        // Multiplying x by 0 returns zero
        case BinaryOp("*", x, Number(0)) => Number(0)
  
        // Multiplying 0 by x returns zero
        case BinaryOp("*", Number(0), x) => Number(0)
  
        // Dividing x by 1 returns the original value
        case BinaryOp("/", x, Number(1)) => simplify(x)
  
        // Dividing x by x returns 1
        case BinaryOp("/", x1, x2) if x1 == x2 => Number(1)
  
        // Adding x to 0 returns the original value
        case BinaryOp("+", x, Number(0)) => simplify(x)
  
        // Adding 0 to x returns the original value
        case BinaryOp("+", Number(0), x) => simplify(x)
  
        // Anything else cannot (yet) be simplified
        case _ => e
      }
    }
    
    def evaluate(e : Expr) : Double =
    {
      simplify(e) match {
        case Number(x) => x
        case UnaryOp("-", x) => -(evaluate(x))
        case BinaryOp("+", x1, x2) => (evaluate(x1) + evaluate(x2))
        case BinaryOp("-", x1, x2) => (evaluate(x1) - evaluate(x2))
        case BinaryOp("*", x1, x2) => (evaluate(x1) * evaluate(x2))
        case BinaryOp("/", x1, x2) => (evaluate(x1) / evaluate(x2))
      }
    }
  }
}

また前回の記事を読んだ方は、最適化ステップを改善するという演習課題を出しておいたことも覚えていると思います。つまりリスト 1 のコードで行っているように単に最上位レベルで単純化を行うのではなく、ツリーの中に深く入り込んで単純化プロセスを実行する方法についての演習課題です。私が見る限りこの最適化を行うための最も単純と思える方法を、Lex Spoon 氏が見つけてくれました。彼の方法では、まずツリーの「端」(各式の中にオペランドがある場合、そのオペランド) を単純化し、次にその単純化された結果を使って最上位レベルの式を単純化します (リスト 2)。

リスト 2. ひたすら単純化

    /*
     * Lex's version:
     */
    def simplify(e: Expr): Expr = {
      // first simplify the subexpressions
      val simpSubs = e match {
        // Ask each side to simplify
        case BinaryOp(op, left, right) => BinaryOp(op, simplify(left), simplify(right))
        // Ask the operand to simplify
        case UnaryOp(op, operand) => UnaryOp(op, simplify(operand))
        // Anything else doesn't have complexity (no operands to simplify)
        case _ => e
      }

      // now simplify at the top, assuming the components are already simplified
      def simplifyTop(x: Expr) = x match {
        // Double negation returns the original value
        case UnaryOp("-", UnaryOp("-", x)) => x
  
        // Positive returns the original value
        case UnaryOp("+", x) => x
  
        // Multiplying x by 1 returns the original value
        case BinaryOp("*", x, Number(1)) => x
  
        // Multiplying 1 by x returns the original value
        case BinaryOp("*", Number(1), x) => x
  
        // Multiplying x by 0 returns zero
        case BinaryOp("*", x, Number(0)) => Number(0)
  
        // Multiplying 0 by x returns zero
        case BinaryOp("*", Number(0), x) => Number(0)
  
        // Dividing x by 1 returns the original value
        case BinaryOp("/", x, Number(1)) => x
  
        // Dividing x by x returns 1
        case BinaryOp("/", x1, x2) if x1 == x2 => Number(1)
  
        // Adding x to 0 returns the original value
        case BinaryOp("+", x, Number(0)) => x
  
        // Adding 0 to x returns the original value
        case BinaryOp("+", Number(0), x) => x
  
        // Anything else cannot (yet) be simplified
        case e => e
      }
      simplifyTop(simpSubs)
    }

Lex に謝意を表します。

構文解析

では、DSL を作成する上での残り半分を考えましょう。何らかのテキスト入力を取得して AST に変換するコード・セグメントを作成する必要があります。このプロセスは、正式には構文解析として知られるものです (もっと正確に言えば、トークン化と字句解析、そして構文解析です)。

パーサーを作成するためのこれまでの方法には、次の 2 つがあります。

手動でパーサーを作成する
ツールにパーサーを作成させる

手動でパーサーを作成するためには、入力ストリームから手動で文字を抽出して検証し、そしてこの文字だけではなく、この文字の前にあった他の文字群にも (場合によってはこの文字の後に来る文字群にも) 基づいて、何らかのアクションを実行します。手動でパーサーを作成する方法は規模の小さな言語の場合には迅速で容易ですが、言語の規模が大きくなるにつれて困難になりがちです。

手動でパーサーを作成する方法に代わる方法として、ツールにパーサーを生成させる方法があります。今のところ、このためのツールは 2 つあり、それぞれのツールは親愛の情を込めて lex (「lexer」(字句解析器) を作成することから) と yacc (Yet Another Compiler Compiler) と呼ばれています。パーサーを作成することに関心を持つプログラマーは手動でパーサーを作成する代わりに別のソース・ファイルを作成し、このファイルを「lex」に入力すると、まさにパーサーのフロントエンドが出来上がります。この生成されたコードは、その言語の基本的な文法ルール (どのトークンにキーワードがあり、どこにコード・ブロックが現れるか、など) を定義する「文法」ファイルと組み合わされ、yacc へ入力されてパーサー・コードが生成されます。

これはコンピューター・サイエンスの教科書にも載っている基本事項なので、この記事では有限状態オートマトンについての詳細や、LALR パーサーあるいは LR パーサーの詳細には触れません。こうした細部を深く掘り下げたい方はそれらの話題に関する本や記事 (あるいはその両方) を見つけて読んでくれるものとして話を進めます。

それでは、Scala でパーサーを作成する際の 3 番目の選択肢であり、Scala の持つ関数型の側面を全面的に活用して作成された、パーサー・コンビネーターについて調べることにしましょう。パーサー・コンビネーターを利用すると、Scala 言語のさまざまな部分を「組み合わせ」、ソリューションを提供する部品を作成することができます。このソリューションはコード生成を必要とせず、また起動用の言語仕様のように見えます。

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

パーサー・コンビネーターの背後にある要点を理解するためには、ある言語がどのようなものかを指定する方法である BNF (Becker-Naur Form: バッカス・ナウア記法) について簡単に知っていると役立ちます。例えば、ここでの電卓用言語を BNF の文法を使って記述するとリスト 3 のようになります。

リスト 3. 言語を記述する

input	::= ws expr ws eoi;

expr	::= ws powterm [{ws '^' ws powterm}];
powterm	::= ws factor [{ws ('*'|'/') ws factor}];
factor	::= ws term [{ws ('+'|'-') ws term}];
term	::= '(' ws expr ws ')' | '-' ws expr | number;

number	::= {dgt} ['.' {dgt}] [('e'|'E') ['-'] {dgt}];
dgt	::= '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9';
ws	::= [{' '|'\t'|'\n'|'\r'}];

ここで、式の左側にある各要素は考えられる入力の集合の名前であり、右側にある要素 (term: 項と言われます) は、オプションの組み合わせとしての、または必須の組み合わせとしての一連の式またはリテラル文字を表します。(BNF 文法の完全な詳細についても、「参考文献」に挙げた Aho/Lam/Sethi/Ullman などの本に適切に説明されています。)

なぜ BNF 形式で言語を表現することが強力かと言えば、わずかなステップを踏むことで BNF 形式から Scala のパーサー・コンビネーターに変換することができるからです。リスト 3 を BNF による単純な形式にすると、リスト 4 のようになります。

リスト 4. (再び) ひたすら単純化

expr   ::= term {'+' term | '-' term}
term   ::= factor {'*' factor | '/' factor}
factor ::= floatingPointNumber | '(' expr ')'

ここで、中括弧 ({}) はその内容を (ゼロ回以上) 繰り返す可能性があることを表し、縦の棒 (またはパイプ「|」) は「・・・または・・・」の関係を表します。従ってリスト 4 を読み取ると、factor は floatingPointNumber (ここでは、ある理由から定義がありませんが) であるか、左括弧プラス expr プラス右括弧のいずれかになります。

この状態から Scala パーサーに変換する方法は、非常に単純です (リスト 5)。

リスト 5. BNF から parsec へ

package com.tedneward.calcdsl
{
  object Calc
  {
    // ...
  
    import scala.util.parsing.combinator._
  
    object ArithParser extends JavaTokenParsers
    {
      def expr: Parser[Any] = term ~ rep("+"~term | "-"~term)
      def term : Parser[Any] = factor ~ rep("*"~factor | "/"~factor)
      def factor : Parser[Any] = floatingPointNumber | "("~expr~")" 
      
      def parse(text : String) =
      {
        parseAll(expr, text)
      }
    }

    def parse(text : String) =
    {
      val results = ArithParser.parse(text)
      System.out.println("parsed " + text + " as " + results + " which is a type "
       + results.getClass())
    }
	
	// ...
  }
}

BNF は基本的に、パーサー・コンビネーターのいくつかの構文要素によって置き換えられます。つまり空白は (シーケンスを示す) ~ メソッドに置き換えられ、繰り返しは rep メソッドに置き換えられ、そして選択項目は相変わらず | メソッドによって表現されます。リテラル・ストリングは標準的なリテラル・ストリングです。

この手法の強力さは 2 つの部分に見られます。第 1 に、Scala が提供する JavaTokenParsers 基底クラスをパーサーが継承している点です (そしてまた Java 言語での構文的な概念とあまり整合性のない言語が必要な場合には、この基底クラス自体が他の基底クラスから継承します)。そして第 2 に、floatingPointNumber という事前に考えられたコンビネーターを使うことによって浮動小数点数の解析の詳細を処理している点です。

この特定の文法（中置記法による電卓）は決して扱うのが難しいわけではなく (だからこそ多くのデモや記事で取り上げられています)、このためのパーサーを手動で作成することも難しくはないでしょう。これは BNF 文法とパーサー作成用のコードとが非常に似通っているため、とても簡単に短時間でパーサーを作成できるからです。

パーサー・コンビネーターの概念への入門

これらのすべてがどのように動作するのかを理解するためには、パーサー・コンビネーターの実装について少し理解する必要があります。各「パーサー」は要するに、何らかの入力を取り入れて「パーサー」を生成する関数または case クラスです。例えば最も下位のレベルでは、パーサー・コンビネーターは単純なパーサーの上にあり、この単純なパーサーが何らかの入力読み取り要素 (Reader) を入力として取り、より上位レベルのセマンティクスを提供するもの (Parser) を生成します。

リスト 6. 基本的なパーサー

type Elem

type Input = Reader[Elem]

type Parser[T] = Input => ParseResult[T]

sealed abstract class ParseResult[+T]
case class Success[T](result: T, in: Input) extends ParseResult[T]
case class Failure(msg: String, in: Input) extends ParseResult[Nothing]

言い換えれば Elem は、構文解析の対象となりうる任意のものを表す抽象型であり、最も一般的なものはテキスト・ストリングまたはテキスト・ストリームです。そして Input は、その種類の型をラップする scala.util.parsing.input.Reader です (大括弧は Reader がジェネリック型であることを示しています。Java や C++ スタイルの構文を好む方は大括弧を不等号括弧とみなしてください)。次に T 型の Parser は Input を入力として取って ParseResult を生成する型であり、ParseResult の型は (基本的に) Success または Failure という 2 つの型のいずれかです。

もちろんパーサー・コンビネーター・ライブラリーには、ここに示したもの以外にもずっと多くの内容があります。数ステップで ~ 関数や rep 関数まで到達できるわけではありませんが、ここでの説明からパーサー・コンビネーターの動作に関する基本的な考え方を理解できるはずです。パーサーを「組み合わせる」ことによって、構文解析という概念の上に、より一層上位レベルの抽象化を実現するのです (これが「パーサー・コンビネーター」という名前の由縁です。つまり、さまざまな要素同士を組み合わせることによって構文解析動作を実現するのです)。

準備は完了したのでしょうか

まだ完全に終わってはいません。このパーサーを呼び出す簡単なテストを行ってみると、パーサーから返されるものが電卓システムの残り部分に必要なものにはなっていないことがわかります。

リスト 7. 何と、最初のテストは失敗します

package com.tedneward.calcdsl.test
{
  class CalcTest
  {
    import org.junit._, Assert._
	
	// ...
    
    @Test def parseNumber =
    {
      assertEquals(Number(5), Calc.parse("5"))
      assertEquals(Number(5), Calc.parse("5.0"))
    }
  }
}

このテストを実行すると失敗する理由は、パーサーの parseAll メソッドが、case クラス化した Number を返さず (これはパーサーの生成ルールに対して case クラスがどういう関係にあるのかパーサーのどこにも定義されていないことを考えると、ある程度理解することができます)、またテキスト・トークンや int から成るコレクションも返さないためであることがわかります。

パーサーはその代わり、Parsers.ParseResult を返します。ここで思い出して欲しいのですが、Parsers.ParseResult は Parsers.Success インスタンス (この内部には私達が求めている結果があります) であるか、そうでなければ Parsers.NoSuccess または Parsers.Failure、Parsers.Error のいずれかです (これらはどれも同じ内容を異なる形で表現しており、何らかの理由で構文解析ができなかったことを意味しています)。

構文解析が成功したとして、実際の結果を得るためには ParseResult の get メソッドを使ってその結果を抽出する必要があります。これはつまり、このテストをパスするように Calc.parse メソッドをほんの少し調整する必要があるということです (リスト 8)。

リスト 8. BNF から parsec へ

package com.tedneward.calcdsl
{
  object Calc
  {
    // ...
  
    import scala.util.parsing.combinator._
  
    object ArithParser extends JavaTokenParsers
    {
      def expr: Parser[Any] = term ~ rep("+"~term | "-"~term)
      def term : Parser[Any] = factor ~ rep("*"~factor | "/"~factor)
      def factor : Parser[Any] = floatingPointNumber | "("~expr~")" 
      
      def parse(text : String) =
      {
        parseAll(expr, text)
      }
    }

    def parse(text : String) =
    {
      val results = ArithParser.parse(text)
      System.out.println("parsed " + text + " as " + results + " which is a type "
         + results.getClass())
	  results.get
    }
	
	// ...
  }
}

これでテストが成功するはずです。

いや失礼、まだ成功しません。このテストを実行してみると、パーサーから出力される結果は先ほど作成した AST 型 (expr とその類) にはまだなっておらず、List や String などで構成されるフォームにすぎません。もちろん、これらの結果を構文解析して expr インスタンスにし、それらを解釈することはできると思いますが、別の方法が必ずあるはずです。

実際、そうした方法があり、その方法の動作を理解するためにはパーサー・コンビネーターがどのようにして非「標準的な」要素 (つまり String や List でないもの) を生成するのかを少しばかり理解する必要があります。あるいは適切な用語を使って言うなら、パーサーはどのようにしてカスタム要素 (この場合は AST オブジェクト) を生成するのかを理解する必要があります。そしてそれが次回の話題です。

次回の記事では、パーサー・コンビネーターの実装の基礎を詳しく調べ、テキストの一部を構文解析して AST を作成し、評価する (そしてその後コンパイルする) ための方法を説明します。

このシリーズについて

このシリーズでは、Ted Neward が皆さんと共に Scala プログラミング言語を深く掘り下げます。このとても楽しみな developerWorks のシリーズでは、Scala が最近もてはやされている理由を調べ、Scala の言語機能の実際の動作を調べます。Scala のコードと Java のコードの比較が重要な場合には両者のコードを並べて示しますが、(これから学ぶように) Scala の機能のうちの多くは、Java には直接対応するものがありません。そして Scala の魅力の多くがあるのはそこなのです。結局のところ、Java で可能ならば、手間をかけて Scala を学ぶ必要はないのです。

まとめ

明らかにまだ作業は終わってはいません (まだ構文解析作業が残っています) が、パーサーの基本的な動作部分は用意できており、あとはパーサーの生成要素を拡張して AST 要素を生成すればよいだけです。

少し先回りをしたい読者は、ScalaDocs に説明されている ^^ メソッドを調べるか、あるいは『Programming in Scala』のパーサー・コンビネーターに関する章を見てみてください。ただし警告しておきますが、これらのリソースに記載されている例は簡単そうに見えるかもしれませんが、この言語はそうした例よりも少しばかり面倒であることを理解しておく必要があります。

もちろん、String や List などをそのまま扱い、AST の部分を無視することもできます。そして返される String や List をばらして再度解析し、AST 要素にすることもできます。しかし、そうしたことをはるかに上回ることがパーサー・コンビネーター・ライブラリーによって可能なことを考えれば、あえてそうする理由はないはずです。

ダウンロード可能なリソース

このコンテンツのPDF

目次

電卓を作る、第 2 回

コンテンツシリーズ

このコンテンツは全#シリーズのパート#です：多忙な Java 開発者のための Scala ガイド

このコンテンツはシリーズの一部分です：多忙な Java 開発者のための Scala ガイド

リスト 1. 電卓用の DSL: AST とインタープリター

リスト 2. ひたすら単純化

構文解析

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

リスト 3. 言語を記述する

リスト 4. (再び) ひたすら単純化

リスト 5. BNF から parsec へ

パーサー・コンビネーターの概念への入門

リスト 6. 基本的なパーサー

準備は完了したのでしょうか

リスト 7. 何と、最初のテストは失敗します

リスト 8. BNF から parsec へ

このシリーズについて

まとめ

ダウンロード可能なリソース

関連トピック

コメント

目次

電卓を作る、第 2 回

コンテンツシリーズ

このコンテンツは全#シリーズのパート#です： 多忙な Java 開発者のための Scala ガイド

このコンテンツはシリーズの一部分です：多忙な Java 開発者のための Scala ガイド

リスト 1. 電卓用の DSL: AST とインタープリター

リスト 2. ひたすら単純化

構文解析

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

リスト 3. 言語を記述する

リスト 4. (再び) ひたすら単純化

リスト 5. BNF から parsec へ

パーサー・コンビネーターの概念への入門

リスト 6. 基本的なパーサー

準備は完了したのでしょうか

リスト 7. 何と、最初のテストは失敗します

リスト 8. BNF から parsec へ

このシリーズについて

まとめ

ダウンロード可能なリソース

関連トピック

コメント

このコンテンツは全#シリーズのパート#です：多忙な Java 開発者のための Scala ガイド