Scalaで言語処理

Table of Contents

1 概要

Scalaのparser combinatorの機能を学び,電卓を作成する.

1.1 注意

本Webページの作成には Emacs org-mode を用い, 数式等の表示は MathJax を用いています. IEでは正しく表示されないことがあるため, Firefox, Safari等のWebブラウザでJavaScriptを有効にしてお使いください. また org-info.js を利用しており, 「m」キーをタイプするとinfoモードでの表示になります. 利用できるショートカットは「?」で表示されます.

2 正規表現

Scalaプログラムでの 正規表現 (regular expressions)は,与えられた文字列が正規表現で指定した パターンにマッチするかどうかを調べるために用いられる. なお,正規表現は,形式言語理論の 正規言語 (regular languages), すなわち 有限オートマトン (finite automata)に対応している.

例えば,正規表現 w* は文字 w を0回以上繰り返したパターンを表しており, 空文字列および w, ww, www, wwww などにマッチする. Scalaでの実行例は以下のようになる.

scala> "www".matches("w*")
res: Boolean = true

scala> "vvv".matches("w*")
res: Boolean = false

この正規表現 w* に対応する 非決定性有限オートマトン (NFA)は,以下のように図示できる.

images/scala-parse-nfa1_bb1978a58cc0e9f32a4aa608874cf75d7e210b9e.png

同様に,正規表現 w+ は文字 w を1回以上繰り返したパターンを表す. すなわち w+ww* と同等になる.

scala> "www".matches("w+")
res: Boolean = true

scala> "".matches("w+")
res: Boolean = false

この正規表現 w+ に対応するNFAは,以下のように図示できる.

images/scala-parse-nfa2_4dee6572353668c60aea2c1b62496ba9e4c485cc.png

複数の文字列の可能性があるパターンは \((r_1|r_2|\cdots|r_n)\) のように表す. 例えば (A|T|G|C)+ は, A または T または G または C の文字を1回以上繰り返したパターンである.

scala> "ATTACCA".matches("(A|T|G|C)+")
res: Boolean = true

上の例は, [ATGC]+ と表すこともできる. \([c_1c_2\cdots c_n]\) は,いずれかの文字 \(c_i\) と一致するパターンを表す.

scala> "ATTACCA".matches("[ATGC]+")
res: Boolean = true

正規表現 \([c_1c_2\cdots c_n]\) で, [0123456789] のように選択肢の文字の文字コードが連続している場合には, [0-9] のように文字の範囲を用いて記述できる. 例えば [0-9] は10進表記の1桁とマッチし, [0-9a-fA-F] は16進表記の1桁とマッチする.

scala> "2018".matches("[0-9]+")
res: Boolean = true

scala> "7E2".matches("[0-9a-fA-F]+")
res: Boolean = true

さらに [0-9]\d と記述できる. ただし,バックスラッシュはScalaの文字列記法中でエスケープ文字にあたるため, Scalaプログラム中では "\\d" のように,バックスラッシュを2つ書く必要がある. あるいは,エスケープ文字を無効にした文字列表記を用いて """\d""" と記述する.

scala> "2018".matches("\\d+")
res: Boolean = true

scala> "2018".matches("""\d+""")
res: Boolean = true

scala> "7E2".matches("""[\da-fA-F]+""")
res: Boolean = true

パターン \(r?\) は \(r\) または空とマッチする記法である. すなわち \((|r)\) と同等になる. 例えば -? は,文字列 - または空文字列とマッチする. したがって,負の数を含む整数の10進表記とマッチする正規表現として -?\d+ が利用できる.

scala> "-2018".matches("""-?\d+""")
res: Boolean = true

この正規表現 -?\d+ に対応するNFAは,以下のように図示できる.

images/scala-parse-nfa3_928e4858b493ae9f81d14be57fc4c6b69e5b54d1.png

正規表現には,他にも様々な表現方法があるが,とりあえず以上で説明を終える. Scalaで利用できる正規表現の詳細は Java 8の正規表現 のページなどを参考にされたい.

2.1 練習問題

  1. 正規表現「 (A*|T*|G*|C*) 」は,どのような文字列にマッチするか.
    (解答例)

    空文字列, A, T, G, C, AA, TT, GG, CC, AAA, TTT, GGG, CCC など.

  2. 正規表現「 (A*|T*|G*|C*)+ 」は,どのような文字列にマッチするか.
    (解答例)

    正規表現「 (A|T|G|C)* 」と同じ文字列にマッチする.

  3. A, T, G, C の文字だけからなる空でない文字列で,長さが3の倍数のものとマッチする正規表現は何か.
    (解答例)

    例えば「 ([ATGC][ATGC][ATGC])+ 」である. 繰り返しを表す記法 \(\{m\}\) を用いれば,「 ([ATGC]{3})+ 」と書ける.

  4. 正規表現「 \d+ 」は 007 など,先頭に余分な 0 がある場合にもマッチしてしまう. これを避けるには,どのような正規表現を用いれば良いか.
    (解答例)

    [1-9]\d* 」で良さそうだが, 0 とマッチしない.

    scala> "0".matches("""[1-9]\d*""")
    res: Boolean = false
    

    したがって「 (0|[1-9]\d*) 」などとすれば良い.

    scala> "0".matches("""(0|[1-9]\d*)""")
    res: Boolean = true
    
  5. 正規表現「 -?\d+ 」は,先頭に余分な 0 がある場合にもマッチするだけでなく, -0 にもマッチしてしまう. これを避けるには,どのような正規表現を用いれば良いか.
    (解答例)

    (0|-?[1-9]\d*) 」などとすれば良い.

  6. 0と1の2種類の文字だけからなる文字列 (空文字列も含む)を二進列 (binary sequence)と呼ぶ. 二進列にマッチする正規表現は何か.
    (解答例)

    (0|1)* 」など.

  7. 1をちょうど1個含む二進列 (1, 01, 10, 001, 010, 100など)にマッチする正規表現は何か.
    (解答例)

    0*10* 」など.

  8. 1をちょうど2個含む二進列 (11, 011, 101, 110, 0011など)にマッチする正規表現は何か.
    (解答例)

    0*10*10* 」など.

  9. 10を含まない二進列 (空文字列および0, 1, 00, 01, 11, 000, 001, 011, 111など)にマッチする正規表現は何か. また,01を含まない二進列ならどうか.
    (解答例)

    10を含まない二進列は「 0*1* 」など,01を含まない二進列は「 1*0* 」など.

  10. 00を含まない二進列 (空文字列および0, 1, 01, 10, 11, 010, 011, 101, 110, 111など)にマッチする正規表現は何か. また,11を含まない二進列ならどうか.
    (解答例)

    00を含まない二進列は「 1*(01+)*0? 」など, 01を含まない二進列は「 0*(10+)*1? 」など.

  11. 1が偶数回現れている二進列 (空文字列および0, 00, 11, 000, 011, 101, 110, 0000, 0011, 0101, 0110など) にマッチする正規表現は何か.
    (解答例)

    (0*10*1)*0* 」など.

  12. 0と1のどちらも偶数回現れている二進列 (空文字列および00, 11, 0000, 0011, 0101, 0110, 1010, 1100, 1111など) にマッチする正規表現は何か.なお,対応するNFAは以下の通りである.
    images/scala-parse-nfa4_747c240bfc5db7cccb3c2434a02dfb221f99bf6d.png
    (解答例)

    NFAを正規表現に変換する方法を用いれば 「 (00|11|((01|10)(00|11)*(01|10)))* 」などが得られる.

  13. お絵かきロジック (別名はノノグラム,イラストロジック,ピクロスなど)と呼ばれる パズルを考えよう (Wikipedia: お絵かきロジック). 例えば,パズルの横幅が8マスで,1行目のヒントが「 2 3 」だとする. この時,1行目を塗りつぶす可能なパターンは 11011100, 11001110, 11000111, 01101110, 01100111, 00110111 の6通りがある (黒を塗ったマスを 1 で,白のままのマスを 0 で表している). 横幅が8マス以上の場合も含め,これらのパターンを表す正規表現は何か.
    (解答例)

    0*110+1110* 」など.

  14. 2017年7月5日のイギリスのBBCラジオで,正規表現を用いたパズルが出題された.

    このパズルを解いてみよう. 解答は BBC.scala のプログラムでチェックできる.

    (解答例)

    以下に解答が示されている.

    確かにすべての正規表現にマッチしている.

    scala> :load BBC.scala
    scala> check(Seq(
           " YOURBESTANDWI", 
           "SESTREFUGEFROM", 
           "ALLTROUBLESISI",
           "NYOURSCIENCE -",
           " ADA LOVELACE "))
    

    世界最初のプログラマといわれているAda Lovelace (Wikipedia: エイダ・ラブレス)による言葉

    Your best and wisest refuge from all troubles is in your science — Ada Lovelace

    を表している.

3 文脈自由文法とEBNF

電卓で用いる数式の 構文 (syntax)などは, 形式文法 (formal grammar)の一種である 文脈自由文法 (context free languages)を用いて定義することができる. 文脈自由文法による文法定義には, バッカス・ナウア記法 (Backus-Naur Form; BNF)を拡張した EBNF などが用いられることが多い. BNFやEBNFは 対象言語 (object language)の文法を定義する言語であるから, メタ言語 (metalanguage)と呼ばれることがある.

EBNFの具体的な書き方には,様々な流儀があるが,ここでは以下のように書くことにする.

  • 終端記号 (terminal symbols; 対象言語の文字列): "a" のようにダブル・クォーテーションでくくって表す.
  • 非終端記号 (nonterminal symbols; EBNFの記号): expression のようにイタリック文字で表記する.非終端記号は,構文カテゴリーを表す.
  • 構文規則 (syntax rules): 以下のような形式で表し,非終端記号で表される文字列集合を定義する. \begin{align*} \mbox{非終端記号} & ::= \mbox{定義} \end{align*}

また,定義中に以下のような記法を使用する.

EBNFでの記法説明
\(\alpha_1\ \alpha_2\)\(\alpha_1\) と \(\alpha_2\) の連結
\(\alpha_1 \mid \alpha_2\)\(\alpha_1\) または \(\alpha_2\)
\(\{\ \alpha\ \}\)\(\alpha\) の0回以上の繰り返し
\([\ \,\alpha\ \,]\)\(\alpha\) または空
\((\ \alpha\ )\)\(\alpha\) のグループ化

例えば,以下は10進数字を表す構文カテゴリー digit と, 10進表記の整数を表す構文カテゴリー integer を定義している. \begin{align*} \textit{digit} & ::=\ \mbox{"0"}\ \mid\ \mbox{"1"}\ \mid\ \mbox{"2"}\ \mid\ \mbox{"3"}\ \mid\ \mbox{"4"}\ \mid\ \mbox{"5"}\ \mid\ \mbox{"6"}\ \mid\ \mbox{"7"}\ \mid\ \mbox{"8"}\ \mid\ \mbox{"9"} \\ \textit{integer} & ::=\ [\ \mbox{"-"}\ ]\ \textit{digit}\ \{\ \textit{digit}\ \} \end{align*}

3.1 練習問題

  1. Scalaを含めほとんどのプログラミング言語の構文 (syntax)はBNFやEBNFで定義されている. C, Java, Scalaの構文定義をWebで探せ.
    (解答例)

    Cの構文については以下などが見つかる.

    Java 8の構文は以下で定義されている.

    Scala version 2.12の構文は以下で定義されている.

  2. メールアドレスの構文や,WebのURL (URI)の構文はRFC (Request For Comments)と呼ばれる文書で定義されている. それらの構文をWebで探せ.
    (解答例)

    メールアドレスの構文は,例えばRFC 5322の「3.4.1 addr-spec仕様」で定義されている.

    URIの構文は,例えばRFC 3986の「Appendix A」で定義されている.

  3. 以下の構文定義について,どのような文字列が受理されるか. \begin{align*} \textit{s} & ::=\ \textit{integer}\ \mid\ \mbox{"("}\ \textit{s}\ \mbox{","}\ \textit{s}\ \mbox{")"} \end{align*}
    (解答例)

    "1", "(1,-2)", "((1,-2),(-3,4))", "(((1,-2),(-3,4)),-5)"など.

    形式言語の理論で学ぶように, このように左右のカッコが対応する文字列のパターンは正規文法では記述できず, 文脈自由文法を用いる必要がある.

  4. 以下の構文定義について,どのような文字列が受理されるか. \begin{align*} \textit{s} & ::=\ \textit{integer}\ \mid\ \mbox{"("}\ \textit{s}\ \{\ \mbox{","}\ \textit{s}\ \}\ \mbox{")"} \end{align*}
    (解答例)

    "1", "(1)", "(1,-2)", (1,-2,3), "((1,-2,3),(-4),5)"など.

  5. 1から99までの整数を漢数字で表した時の構文をEBNFで定義せよ. ただし,12などは通常は1に対応する「ー」を省略して「十二」と書くが, 「十二」と「一十二」のどちらで表しても良いものとする.
    (解答例)

    例えば以下のように定義できる. \begin{align*} \textit{jint1} & ::=\ \mbox{"一"}\ \mid\ \mbox{"二"}\ \mid\ \mbox{"三"}\ \mid\ \mbox{"四"}\ \mid\ \mbox{"五"}\ \mid\ \mbox{"六"}\ \mid\ \mbox{"七"}\ \mid\ \mbox{"八"}\ \mid\ \mbox{"九"} \\ \textit{jint2} & ::=\ [\ \textit{jint1}\ ]\ \mbox{"十"}\ [\ \textit{jint1}\ ]\ \mid\ \textit{jint1} \end{align*}

  6. 空でない二進列で回文 (palindrome)になっているもの (0, 1, 00, 11, 000, 010, 101, 111など)の構文をEBNFで定義せよ.
    (解答例)

    例えば以下のように定義できる (空文字列を許せば,より簡単になる). \begin{align*} \textit{p} & ::=\ \mbox{"0"}\ \mid\ \mbox{"1"}\ \mid\ \mbox{"00"}\ \mid\ \mbox{"11"}\ \mid\ \mbox{"0"}\ \textit{p}\ \mbox{"0"}\ \mid\ \mbox{"1"}\ \textit{p}\ \mbox{"1"} \end{align*}

  7. 180度回転させても同じになる数をストロボグラマティック数 (Wikipedia: ストロボグラマティック数)という. 0, 1, 8, 11, 69, 88, 96, 101, 111, 181, 609, 619, 689, 808などがそうである (0, 1, 6, 8, 9だけを用いる). ストロボグラマティック数を定義するEBNFを示せ.
    (解答例)

    例えば以下のように定義できる (空文字列を許せば,より簡単になる). \begin{align*} \textit{s} & ::=\ \mbox{"0"}\ \mid\ \mbox{"1"}\ \mid\ \mbox{"8"}\ \mid\ \mbox{"11"}\ \mid\ \mbox{"69"}\ \mid\ \mbox{"88"}\ \mid\ \mbox{"96"}\ \mid\ \\ & \qquad \mbox{"1"}\ \textit{s}\ \mbox{"1"}\ \mid\ \mbox{"6"}\ \textit{s}\ \mbox{"9"}\ \mid\ \mbox{"8"}\ \textit{s}\ \mbox{"8"}\ \mid\ \mbox{"9"}\ \textit{s}\ \mbox{"6"} \end{align*}

  8. 正規表現「w+とw+でw+」にマッチする文字列のうち, 「wwとwwwでwwwww」のように,1番目のwの個数 (この例の場合は2)と,2番目のwの個数 (この例では3)の和が, 3番目のwの個数 (この例では5)に一致している文字列を定義するEBNFを示せ.
    (解答例)

    例えば以下のように定義できる. \begin{align*} \textit{s} & ::=\ \mbox{"wと"}\ \textit{t}\ \mbox{"w"}\ \mid\ \mbox{"w"}\ \textit{s}\ \mbox{"w"} \\ \textit{t} & ::=\ \mbox{"wでw"}\ \mid\ \mbox{"w"}\ \textit{t}\ \mbox{"w"} \end{align*}

4 前置記法の電卓

4.1 構文定義

まず,文法が簡単な前置記法 (prefix notation)の電卓を考える. すなわち,加減乗除算を +(x,y), -(x,y), *(x,y), /(x,y) のように記述する記法である. この記法だと,例えば \(3+1-4*2\) は -(+(3,1),*(4,2)) と記述する.

この構文は,EBNFで以下のように定義できる.

\begin{align*} \textit{expr} & ::=\ \textit{integer}\ \mid\ \textit{func}\ \mbox{"("}\ \textit{expr}\ \mbox{","}\ \textit{expr}\ \mbox{")"} \\ \textit{func} & ::=\ \mbox{"+"}\ \mid\ \mbox{"-"}\ \mid\ \mbox{"*"}\ \mid\ \mbox{"/"} % \end{align*}

Scalaのparser combinatorを用いると,EBNFと同様の記法で構文を定義し, 与えられた文字列の構文解析を実現できる. ただ,すべての構文定義を実現できるわけではない. Scalaのparser combinatorは, トップダウン型の再帰下降構文解析 (recursive descent parsing)のため 左再帰 (left recursive)な構文規則は利用できない. しかし,それと同等の記述が可能であり,実用上は問題ない.

EBNFで,具体的に構文を定義しようとすると,空白の取り扱いが面倒になる. 数を表している文字列の途中に空白文字は許したくないが,コンマやカッコの前後には空白文字を許したい. これを,EBNFで正しく定義しようとすると,たとえば以下のようになり,無駄に複雑だ. \begin{align*} \textit{expr} & ::=\ \textit{spaces}\ (\ \textit{integer}\ \mid\ \textit{func}\ \mbox{"("}\ \textit{expr}\ \mbox{","}\ \textit{expr}\ \mbox{")"}\ )\ \textit{spaces} \\ \textit{func} & ::=\ \textit{spaces}\ (\ \mbox{"+"}\ \mid\ \mbox{"-"}\ \mid\ \mbox{"*"}\ \mid\ \mbox{"/"}\ )\ \textit{spaces} \\ \textit{spaces} & ::=\ \{\ \mbox{" "}\ \} \end{align*} そこで,数や変数名など途中に空白文字を許さない構文単位を トークン (token)と呼び, トークンとトークンの間には自動的に空白を許すことにすれば便利だ.

scala.util.parsing.combinator.JavaTokenParsers では, 以下の関数が事前に定義されており,トークンとして利用可能である. なお JavaTokenParsers は scala.util.parsing.combinator.RegexParsers のサブクラスになっており, 正規表現を用いて新たなトークンを定義することもできる.

関数名トークンの種類
ident変数名などの識別名x, x1, 名前 など
wholeNumber整数12, -34 など
decimalNumber符号なし小数12, 12.3, .14 など
floatingPointNumber浮動小数点数3.14, 6.02e23 など
stringLiteral文字列"abc", "\\d" など

そこで wholeNumber を利用すれば, 上で示した \(\textit{integer} ::=\ [\ \mbox{"-"}\ ]\ \textit{digit}\ \{\ \textit{digit}\ \}\) という構文定義は不要になり,前置記法の電卓の構文定義の全体は以下のようになる (もちろん,最後行を省いて wholeNumber だけを使用するのでも良い).

\begin{align*} \textit{expr} & ::=\ \textit{integer}\ \mid\ \textit{func}\ \mbox{"("}\ \textit{expr}\ \mbox{","}\ \textit{expr}\ \mbox{")"} \\ \textit{func} & ::=\ \mbox{"+"}\ \mid\ \mbox{"-"}\ \mid\ \mbox{"*"}\ \mid\ \mbox{"/"} \\ \textit{integer} & ::=\ \textit{wholeNumber} \end{align*}

これを,ほぼそのままの形で記述したScalaのプログラムを以下に示す(CalcP0.scala).

プログラムの3行目以降で CalcP0 という名前のオブジェクトを定義している. CalcP0JavaTokenParsers クラス (正確にはtrait)を継承したオブジェクトであり, scala.util.parsing.combinator.JavaTokenParsers および scala.util.parsing.combinator.RegexParsers で定義されているメソッドが利用できる.

import scala.util.parsing.combinator._

object CalcP0 extends JavaTokenParsers {
  def expr: Parser[Any] = integer | func ~ "(" ~ expr ~ "," ~ expr ~ ")"
  def func = "+" | "-" | "*" | "/"
  def integer = wholeNumber
}

CaclP0 オブジェクト内で定義されている 関数 expr が前置記法の式の パーサ (parser; 構文解析器)である. そして,関数 func が演算子の部分をパースするパーサ, 関数 integer が整数の部分をパースするパーサとなっている.

関数 expr の定義部分を見ればわかるように, 「または」はEBNFと同様に "|" を用いているが,「連結」には "~" を用いている. その他の記法は以下のように対応しており, Scalaのparser combinatorで,EBNFの記法をほぼ自然に記述できることがわかる.

Scalaでの記法EBNFでの記法説明
\(\alpha_1\) ~ \(\alpha_2\)\(\alpha_1\ \alpha_2\)\(\alpha_1\) と \(\alpha_2\) の連結
\(\alpha_1 \mid \alpha_2\)\(\alpha_1 \mid \alpha_2\)\(\alpha_1\) または \(\alpha_2\)
rep( \(\alpha\) )\(\{\ \alpha\ \}\)\(\alpha\) の0回以上の繰り返し
opt( \(\alpha\) )\([\ \,\alpha\ \,]\)\(\alpha\) または空
( \(\alpha\) )\((\ \alpha\ )\)\(\alpha\) のグループ化

このプログラムは以下のようにすればScala REPL内から実行できるようになる (Scalaを実行する同じフォルダ中にCalcP0.scalaを保存しておくこと).

$ scala
scala> :load CalcP0.scala

まず,CalcP0オブジェクト中で定義されている関数を直接実行できるようにimport命令を実行する.

scala> import CalcP0._

なお,import命令の実行は,プログラムをloadするたびに行う必要がある.

parseAll 関数を用いると,与えた文字列に対して 構文解析 (parsing)を実行することができる. 例えば,以下は +(12,34)expr として構文解析した結果である.

scala> parseAll(expr, "+(12,34)")
res: CalcP0.ParseResult[Any] = [1.9] parsed: (((((+~()~12)~,)~34)~))

出力中の [1.9] は,文字列 +(12,34) の1文字目から9文字目の前 (つまり最終文字)まで 構文解析できたことを表し, (((((+~()~12)~,)~34)~)) が構文解析の結果として得られた 構文木 (parse tree)を文字列表示したものである.

この表示は,非常にわかりにくい.実は,以下のような構造になっている (解読できるだろうか?).

((((("+" ~ "(") ~ "12") ~ ",") ~ "34") ~ ")")

これを構文木として図示すると以下のようになる(トークンは四角の箱で表している).

images/scala-parse-tree1_6bea852829d794f8d3438302153ed20ad025ae80.png

"+", "(", "12", ",", "34", ")" の各トークンに対し, 2項演算子 "~" で左結合的に対が作成されていることがわかる.

このように,得られた構文木中に意味的には不要なトークン("(", ",", ")")が 含まれており,複雑になっている.

Scalaのparser combinatorには,不要な構造を削除する演算が用意されている. 演算子 "~" の代わりに "~>" を用いると左側の構文解析結果が構文木から削除され, "<~" を用いると右側の構文解析結果が構文木から削除される.

以下のプログラム CalcP1.scala は, "<~" を用いて不要なトークンを結果の構文木から省いている.

import scala.util.parsing.combinator._

object CalcP1 extends JavaTokenParsers {
  def expr: Parser[Any] = integer | (func <~ "(") ~ (expr <~ ",") ~ (expr <~ ")")
  def func = "+" | "-" | "*" | "/"
  def integer = wholeNumber
}

実行するには,以下のように入力する.

scala> :load CalcP1.scala
scala> import CalcP1._
scala> parseAll(expr, "+(12,34)")
res: CalcP1.ParseResult[Any] = [1.9] parsed: ((+~12)~34)

表示された結果は,以下のような構文木を表している.

images/scala-parse-tree2_7df0b78282016f6f0f271239db7e4189211ad14d.png

4.2 練習問題

  1. 上記で定義した expr だけを受理する正規表現は書けるか.
    (解答例)

    書けない.入れ子になった左右のカッコが対応する条件を正規表現では記述できない. すなわち expr で定義される文字列全体は正規言語ではない.

  2. CalcP1.scala を修正して CalcP1float.scala を作成し,整数でなく浮動小数点数が利用できるようにせよ. すなわち,例えば以下の構文解析が成功するようにする.
    scala> parseAll(expr, "+(1.2, 3.4)")
    
    (解答例)

    例えば以下のようにする(CalcP1float.scala). オブジェクト名も CalcP1float と変更している.

    def expr: Parser[Any] = number | (func <~ "(") ~ (expr <~ ",") ~ (expr <~ ")")
    def func = "+" | "-" | "*" | "/"
    def number = floatingPointNumber
    

    以下のようにして実行する.

    scala> :load CalcP1float.scala
    scala> import CalcP1float._
    scala> parseAll(expr, "+(1.2, 3.4)")
    res: CalcP1float.ParseResult[Any] = [1.12] parsed: ((+~1.2)~3.4)
    
  3. CalcP1.scala を修正して CalcP1unary.scala を作成し, "-(12)""abs(-34)" などの1引数の演算や関数を記述できるようにせよ. すなわち,例えば以下の構文解析が成功するようにする.
    scala> parseAll(expr, "-(12)")
    scala> parseAll(expr, "abs(-34)")
    
    (解答例)

    例えば以下のようにする(CalcP1unary.scala). オブジェクト名も CalcP1unary と変更している.

    def expr: Parser[Any] =
      integer |
      (func1 <~ "(") ~ (expr <~ ")") |
      (func2 <~ "(") ~ (expr <~ ",") ~ (expr <~ ")")
    def func1 = "-" | ident
    def func2 = "+" | "-" | "*" | "/" | ident
    def integer = wholeNumber
    

    ここでは,1引数の関数名として ident を許しているから, abs だけでなく任意の識別名が利用可能となっている. また,2引数の関数名としても任意の識別名が利用できるようにしている.

  4. 以下の関数 hexnum を用いると #7E2 などの16進表記の整数をトークンとして利用できる.
    def hexnum = "#" ~> "[0-9a-fA-F]+".r
    

    CalcP1.scala を修正して CalcP1hex.scala を作成し,16進表記の整数を利用できるようにせよ.

    (解答例)

    例えば以下のようにする(CalcP1hex.scala).

    import scala.util.parsing.combinator._
     
    object CalcP1hex extends JavaTokenParsers {
      def expr: Parser[Any] =
        integer |
        hexnum |
        (func <~ "(") ~ (expr <~ ",") ~ (expr <~ ")")
      def func = "+" | "-" | "*" | "/"
      def integer = wholeNumber
      def hexnum = "#" ~> "[0-9a-fA-F]+".r
    }
    

4.3 構文解析結果の表現

Scalaのparser combinatorの結果である構文木は,どのように表現されているのだろうか.

まず,以下のようなcase class Xを定義してみる.

scala> case class X(_1: Any, _2: Any)

このクラス X は,第1引数 _1 と第2引数 _2 を要素とするオブジェクトを生成する (注意: new X(12,34) は単に X(12,34) と書くのでも良い).

scala> val x = new X(12, 34)
x: X = X(12,34)

scala> x._1
res: Any = 12

scala> x._2
res: Any = 34

引数のデータ型は Any で任意だから,以下のように入れ子にすることも可能だ.

scala> val y = new X(new X(12,34),56)
y: X = X(X(12,34),56)

この時 y は,以下のような木を表していると考えることができる.

images/scala-parse-tree3_49ce5a9a13c9723595633103bddc8d1c6c4744e0.png

しかし,この場合 y._1 は,可能だが y._1._1 は失敗する.

scala> y._1
res: Any = X(12,34)

scala> y._1._1
<console>:13: error: value _1 is not a member of Any
       y._1._1
            ^

この原因は y._1 のデータ型が Any と推論されており, Any に対しては値 _1 が定義されていないためだ.

これを避けるには,以下のように X の定義に型パラメータを指定すれば良い.

scala> case class X[A,B](_1: A, _2: B)

第1引数のデータ型を A, 第2引数のデータ型を B というパラメータで与える ことが可能になる. たとえば new X[Int,Int](12, 34) とすると,データ型 AB がともに Int としてオブジェクトが生成される.

実際には,Scala処理系が型推論によりデータ型を推論してくれるので, 型パラメータの部分は省略可能だ. 以下の例を見ると, 自動的にデータ型が正しく推論されていることがわかる (xy のデータ型が,それぞれ X[Int,Int]X[X[Int,Int],Int] と 推論されている).

scala> val x = new X(12, 34)
x: X[Int,Int] = X(12,34)

scala> val y = new X(new X(12,34),56)
y: X[X[Int,Int],Int] = X(X(12,34),56)

この木からデータを取り出すには y._1._1 などとしても良いが,match-case構文を用いるのが便利だ.

scala> x match { case X(a,b) => List(a, b) }
res: List[Int] = List(12, 34)

scala> y match { case X(a,b) => List(a, b) }
res: List[Any] = List(X(12,34), 56)

xy に代入されているデータが,パターン X(a,b) とマッチされ, 変数 ab に対応する部分が代入され,さらに List(a,b) が作成されてそれが値となっている.

さらに y に対して X(X(a,b),c) というパターンを用いることもできる (便利ですね!).

scala> y match { case X(X(a,b),c) => List(a, b, c) }
res: List[Int] = List(12, 34, 56)

Scalaのparser combinatorでは,上の X の代わりに "~" という名前のクラスが利用されている.

scala> :load CalcP0.scala
scala> import CalcP0._

scala> val z = new ~(new ~(12,34), 56)
z: Int ~ Int ~ Int = ((12~34)~56)

scala> z match { case ~(~(a,b),c) => List(a,b,c) }
res: List[Int] = List(12, 34, 56)

データ型の表記と,データの表示に中置記法が用いられているため, データ型 X[X[Int,Int],Int] に対応するものとして Int ~ Int ~ Int が表示され, データ X(X(12,34),56) に対応するものとして ((12~34)~56) が表示されているが, 同様であることがわかる.

なお,パターンの表記にも中置記法が利用可能なため,よりわかりやすく記述できる.

scala> z match { case a ~ b ~ c => List(a,b,c) }
res: List[Int] = List(12, 34, 56)

4.4 練習問題

  1. new X(12, "ab") のデータ型はどのようになると思うか.
    (解答例)

    実行してみると X[Int,String] だとわかる.

    scala> new X(12, "abc")
    res: X[Int,String] = X(12,abc)
    
  2. new X(new X(12,34), new X(56,78)) のデータ型はどのようになると思うか.
    (解答例)

    実行してみると X[X[Int,Int],X[Int,Int]] だとわかる.

    scala> new X(new X(12,34), new X(56,78))
    res: X[X[Int,Int],X[Int,Int]] = X(X(12,34),X(56,78))
    
  3. new X(new X(12,34), new X(56,78)) が変数 t に代入されているとして, 葉の値の合計を求めるにはどうすればよいか.
    (解答例)

    例えば以下のようにする.

    scala> val t = new X(new X(12,34), new X(56,78))
    scala> t match { case X(X(a,b),X(c,d)) => a + b + c + d }
    res: Int = 180
    

4.5 構文解析結果の利用

ここまでで,前置記法の式の構文解析が実現できた. Scalaのparser combinatorでは,構文解析結果に対する処理を記述することもできる. その機能を用いて,前置記法の電卓を実現しよう. なお,ここでは計算結果は整数 (BigInt)とし,浮動小数点の電卓の実現は練習問題とする.

CalcP1.scalaexpr の定義を見ると

def 関数名: Parser[Any] = 構文定義1 | 構文定義2 | ... | 構文定義n

のようになっている. これを,Scalaで任意精度の整数を表すデータ型BigIntを返すようにするには, 以下のように記述する(わかりやすく改行を追加している).

def 関数名: Parser[BigInt] =
  構文定義1 ^^ BigIntを返す関数1 |
  構文定義2 ^^ BigIntを返す関数2 |
  ...
  構文定義n ^^ BigIntを返す関数n

ここで「BigIntを返す関数i」は,「構文定義i」の構文解析結果を引数としてBigIntの結果を返す関数である.

expr の「構文定義1」は integer で,これは構文解析結果として文字列 (String)を返す. したがって「BigIntを返す関数1」としては,10進整数の文字列表記からその値を求める関数を 記述すれば良い(データ型は String => BigInt).

Scalaの匿名関数 (anonymous function)の機能を用いれば, 10進整数の文字列表記からその値を求める関数は (s => BigInt(s){ s => BigInt(s) } と記述できる. あるいは,さらに引数を省略して (BigInt(_)){ BigInt(_) } と記述しても良い. すなわち,以下のような記述となる.

def expr: Parser[BigInt] =
  integer ^^ { BigInt(_) } |
  (func <~ "(") ~ (expr <~ ",") ~ (expr <~ ")") ^^ { t => ... }

expr の「構文定義2」は (func <~ "(") ~ (expr <~ ",") ~ (expr <~ ")") で, (("+" ~ 12) ~ 34) などの構造が返ってきて, そのデータ型は ~[~[String,BigInt],BigInt] である. このように複雑な構造から必要なデータを取り出す場合,Scalaのmatch構文を用いることができる.

t match {
  case パターン1 => 処理1
  case パターン2 => 処理2
  ...
  case パターンn => 処理n
}

この時,「パターン1」から順に t の構造とパターンマッチ (pattern matching)が行われ, 最初にマッチした「パターンi」に対して「処理i」が実行される.

expr の「構文定義2」は (func <~ "(") ~ (expr <~ ",") ~ (expr <~ ")") に対するパターンは, f ~ x ~ y のように書けるから,以下のような記述となる (この場合,パターンは1つだけである).

def expr: Parser[BigInt] =
  integer ^^ { BigInt(_) } |
  (func <~ "(") ~ (expr <~ ",") ~ (expr <~ ")") ^^ { t => t match {
    case f ~ x ~ y => ...
  }}

構文定義中の func の部分が変数 f に, 最初の expr の部分が変数 x に, 次の expr の部分が変数 y に代入される. なお, f のデータ型は Stringxy のデータ型は BigInt である.

f に代入される値は "+", "-", "*", "/" のいずれかだ. したがって,パターンを以下のように4通り記述すれば,よりわかりやすくなる.

def expr: Parser[BigInt] =
  integer ^^ { BigInt(_) } |
  (func <~ "(") ~ (expr <~ ",") ~ (expr <~ ")") ^^ { t => t match {
    case "+" ~ x ~ y => ...
    case "-" ~ x ~ y => ...
    case "*" ~ x ~ y => ...
    case "/" ~ x ~ y => ...
  }}

また { t => t match { ... } } は,単に { ... } と省略して書くことができる.

def expr: Parser[BigInt] =
  integer ^^ { BigInt(_) } |
  (func <~ "(") ~ (expr <~ ",") ~ (expr <~ ")") ^^ {
    case "+" ~ x ~ y => ...
    case "-" ~ x ~ y => ...
    case "*" ~ x ~ y => ...
    case "/" ~ x ~ y => ...
  }

加減乗除の各演算に対し値を計算する処理を付け加えると,最終的なプログラムは以下のようになる (CalcP2.scala).

import scala.util.parsing.combinator._

object CalcP2 extends JavaTokenParsers {
  def expr: Parser[BigInt] =
    integer ^^ { BigInt(_) } |
    (func <~ "(") ~ (expr <~ ",") ~ (expr <~ ")") ^^ {
      case "+" ~ x ~ y => x + y
      case "-" ~ x ~ y => x - y
      case "*" ~ x ~ y => x * y
      case "/" ~ x ~ y => x / y
    }
  def func = "+" | "-" | "*" | "/"
  def integer = wholeNumber
}

以下は,実行例である.

scala> :load CalcP2.scala
scala> import CalcP2._
scala> parseAll(expr, "+(*(1,2), *(3,4))")
res: CalcP2.ParseResult[BigInt] = [1.18] parsed: 14

なお BigInt 上の演算としては,以下のものなどが利用できる.

- xマイナスx
x + yxとyの和
x - yxとyの差
x * yxとyの積
x / yx割るyの商
x % yx割るyの余り
x.absxの絶対値
x.min(y)xとyの最小値
x.max(y)xとyの最大値
x.gcd(y)xとyの最大公約数
x.pow(y)xのy乗 (yはInt)

またBigIntのリストxsに対して,以下が利用できる.

xs.sumxsの要素の和
xs.productxsの要素の積
xs.minxsの要素の最小値
xs.maxxsの要素の最大値

4.6 練習問題

  1. CalcP2.scala を修正して CalcP2float.scala を作成し,整数でなく浮動小数点数が利用できるようにせよ. 結果が Double となることに注意すること.
    (解答例)

    例えば CalcP2float.scala のように修正する.

  2. さらに修正し "-(0.1)", "abs(-2.3)", "max(4, 5)" などの演算および関数が利用できるようにせよ. なお,これらの関数は math.abs(-2.3), math.max((4, 5) などとすれば計算できる. 使用できる関数については scala.math パッケージを参照のこと.
    (解答例)

    例えば CalcP2float2.scala のように修正する. このプログラムでは func の定義に ident を追加することで,任意の識別名を利用できるようにしている. そのため,case文の場合分けを網羅的にするために以下の行を追加している.

    case _ => ???
    

    この行は,それより前のどのパターンにも一致しない場合に実行され, ??? という命令により scala.NotImplementedError: an implementation is missing というエラーが表示される.

    scala> parseAll(expr, "a(1)")
    scala.NotImplementedError: an implementation is missing
    .....
    

4.7 複数引数への拡張

さらに, +(x1, x2, …, xn) のように,複数の引数を許すようにしよう (n ≥ 1). この構文は,EBNFで以下のように定義できる. \begin{align*} \textit{expr} & ::=\ \textit{integer}\ \mid\ \textit{func}\ \mbox{"("}\ \textit{expr}\ \{\ \mbox{","}\ \textit{expr}\ \}\ \mbox{")"} \end{align*} ここで \(\{\ \alpha\ \}\) は \(\alpha\) の0回以上の繰り返しを表している.

これは,Scalaのparser combinatorを用いれば以下のように記述できる (CalcP3.scala).

import scala.util.parsing.combinator._

object CalcP3 extends JavaTokenParsers {
  def expr: Parser[Any] =
    integer |
    (func <~ "(") ~ expr ~ (rep("," ~> expr) <~ ")")
  def func = "+" | "-" | "*" | "/" | ident
  def integer = wholeNumber
}

rep("," ~> expr) が \(\{\ \mbox{","}\ \textit{expr}\ \}\) に対応している. また,任意の識別子を関数名として利用できるよう, func の定義に ident を追加している.

このプログラムを +(1,2,3,4) に対して実行すると以下の結果になる.

scala> :load CalcP3.scala
scala> import CalcP3._
scala> parseAll(expr, "+(1,2,3,4)")
res: CalcP3.ParseResult[Any] = [1.11] parsed: ((+~1)~List(2, 3, 4))

rep("," ~> expr) の部分に対応する結果がリスト List(2,3,4) となっていることがわかる. したがって,整数 (BigInt)の結果を計算するプログラムは以下のようになるだろう. ただし case _ => ??? の行は,上の練習問題の解答例で説明したように, どのパターンにもマッチしない場合に scala.NotImplementedError を表示するためのものである.

def expr: Parser[BigInt] =
  integer ^^ { BigInt(_) } |
  (func <~ "(") ~ expr ~ (rep("," ~> expr) <~ ")") ^^ {
    case "+" ~ x ~ ys => ...
    case "-" ~ x ~ ys => ...
    case "*" ~ x ~ ys => ...
    case "/" ~ x ~ ys => ...
    case _ => ???
  }

+(1,2,3,4) の場合,変数 x に整数 1 が代入され, 変数 ys に整数のリスト List(2,3,4) が代入される. したがって,結果は x + ys.sum とすれば良い (あるいは (x +: ys).sum でも良い).

-(1,2,3,4) の場合は \(1-2-3-4\) を表すと考えれば, 同様に結果は x - ys.sum で良い. また *(1,2,3,4) の場合は \(1\times 2\times 3\times 4\) を表すと考えられるから, 結果は x * ys.product となり, /(1,2,3,4) の場合も同様に x / ys.product で良いだろう.

しかし,引数の個数が1つの場合に問題が生じる. +(1), -(1), *(1), /(1) のいずれの場合も結果が 1 となる. +, *, / についてはこの結果でも良いが, -(1) の場合には -1 を結果とすべきだろう.

これは,以下のようにプログラムすれば解決できる (CalcP4.scala).

import scala.util.parsing.combinator._

object CalcP4 extends JavaTokenParsers {
  def expr: Parser[BigInt] =
    integer ^^ { BigInt(_) } |
    (func <~ "(") ~ expr ~ (rep("," ~> expr) <~ ")") ^^ {
      case "+" ~ x ~ ys => x + ys.sum
      case "-" ~ x ~ Nil => - x
      case "-" ~ x ~ ys => x - ys.sum
      case "*" ~ x ~ ys => x * ys.product
      case "/" ~ x ~ ys => x / ys.product
      case _ => ???
    }
  def func = "+" | "-" | "*" | "/" | ident
  def integer = wholeNumber
}

ys の箇所が空リスト Nil になる場合のcaseパターンを追加している. なお NilList() と書いても良い.

加減乗除以外のパターンはどのように書けば良いだろうか. 関数名を f として,f(x), f(x,y), f(x,y,z), f(x1,x2,…,xn) にマッチする パターンの書き方をまとめると以下のようになる.

  • case "f" ~ x ~ Nil 」のパターンは f(12) などのように1引数の場合にマッチし, x には 12 が代入される.
  • case "f" ~ x ~ List(y) 」のパターンは f(12,34) などのように2引数の場合にマッチし, x には 12y には 34 が代入される.
  • case "f" ~ x ~ List(y,z) 」のパターンは f(12,34,56) などのように3引数の場合にマッチし, x には 12y には 34, z には 56 が代入される.
  • case "f" ~ x ~ ys 」のパターンは f(x1,x2,…,xn) で n が1以上の場合にマッチし, x には x1 の値, ys には x2, …, xn の値のリストが代入される. 例えば, f(12,34,56,78) なら x12ysList(34,56,78) である.

関数fの計算を実装したプログラムの一部は以下のように書ける.

case "f" ~ x ~ Nil => ???        // f(x)を計算する場合
case "f" ~ x ~ List(y) => ???    // f(x,y)を計算する場合
case "f" ~ x ~ List(y,z) => ???  // f(x,y,z)を計算する場合
case "f" ~ x ~ ys => ???         // ysがList(x2,...xn)として f(x,x2,...,xn)を計算する場合

すなわち1行目の ??? の部分には f(x) の値を計算するプログラムを記述し, 2行目の ??? の部分には f(x,y) の値を計算するプログラムを記述し, 3行目の ??? の部分には f(x,y,z) の値を計算するプログラムを記述する. なお,このように複数のパターンがある場合, 最初にマッチするcase文が実行されるので,4行目はfの引数が4個以上の場合だけに実行される.

4.8 練習問題

  1. CalcP4.scala で parseAll(expr, "-(1,2,3,4)") を実行してみよ.
    (解答例)

    以下が実行例である.

    scala> :load CalcP4.scala
    scala> import CalcP4._
    scala> parseAll(expr, "-(1,2,3,4)")
    res: CalcP4.ParseResult[BigInt] = [1.11] parsed: -8
    
  2. CalcP4.scala で parseAll(expr, "abs(-1)") を実行するとどうなるか.
    (解答例)

    構文解析は成功しているが,その後の値の計算で, ??? が実行され scala.NotImplementedError が表示される.

  3. CalcP4.scala を修正し abs(x)x の絶対値を計算するように拡張せよ.
    (解答例)

    以下の行を追加すれば良い.

    case "abs" ~ x ~ Nil => x.abs
    
  4. CalcP4.scala を修正し min(x,y)xy の最小値を計算するように拡張せよ.
    (解答例)

    以下の行を追加すれば良い.

    case "min" ~ x ~ List(y) => x.min(y)
    

5 課題1

5.1 内容

以下からいくつかを選択し, Work1.scala に対して拡張を行うこと.

  1. xiすべての最大値を求める関数 max(x1, x2, ..., xn) を追加せよ.
    (ヒント)

    以下のようなcaseパターンを追加する (??? の部分は自分で考える).

    case "max" ~ x ~ ys => ???
    

    BigInt のリスト ys の最大値は ys.max で求めることができる. BigIntmax メソッドを使用すれば xy の最大値は x.max(y) で求めることができる. あるいは,まず (x +: ys) として xi すべてのリストを作成するのでも良い.

  2. 正の整数xとyの最大公約数を求める関数 gcd(x, y) を追加せよ.
    (ヒント)

    以下のようなcaseパターンを追加する (??? の部分は自分で考える).

    case "gcd" ~ x ~ List(y) => ???
    

    BigIntgcd メソッドを使用し x.gcd(y) とすれば x と y の最大公約数が求まる.

  3. 正の整数xiすべての最大公約数を求める関数 gcd(x1, x2, ... xn) を追加せよ.
    (ヒント)

    以下のようなcaseパターンを追加する (??? の部分は自分で考える).

    case "gcd" ~ x ~ ys => ???
    

    BigInt のリストに対し,すべての最大公約数を求めるには reduce を用いれば良い (Scalaでリスト処理 を参照).

  4. 正の整数xiすべての最小公倍数を求める関数 lcm(x1, x2, ... xn) を追加せよ.
    (ヒント)

    まず,xとyの最小公倍数を求める関数 lcm(x, y) を Work1 オブジェクト中に 以下のように定義する (??? の部分は自分で考える).

    object Work1 extends JavaTokenParsers {
      def lcm(x: BigInt, y: BigInt) = ???
      def expr: .....
      .....
    }
    

    以下のようにして事前にテストしておく.

    scala> :load Work1.scala
    scala> import Work1._
    scala> lcm(123456789, 987654321)
    res: BigInt = 13548070123626141
    

    また,以下のようなcaseパターンを追加する (??? の部分は自分で考える).

    case "lcm" ~ x ~ ys => ???
    

    ??? の中では, BigInt のリスト x +: ys に対して reduce を用いてすべての最小公倍数を求めれば良い.

  5. n番目のフィボナッチ数を求める関数 fib(n) を追加せよ.
    (ヒント)

    以下のようなcaseパターンを追加し,さらに Work1 オブジェクト内に関数 fib(n: Int): BigInt を定義する.

    case "fib" ~ n ~ Nil => fib(n.toInt)
    

    fib の定義については Scalaで再帰プログラミング を参照する. なお,末尾再帰にしないと fib(100) は計算できないので注意.

    以下のようにして事前にテストしておくと良い.

    scala> :load Work1.scala
    scala> import Work1._
    scala> fib(100)
    res: BigInt = 354224848179261915075
    
  6. 西暦y年 (y ≥ 1900) m月d日の正午のユリウス日 (JDN)を求める関数 julius(y, m, d) を追加せよ. 今日のユリウス日から自分の誕生日のユリウス日を引けば,何日生きてきたかがわかる.
    (ヒント)

    以下のようなcaseパターンを追加し,Work1 オブジェクト内に関数 julius(y: Int, m: Int, d: Int) を定義する.

    case "julius" ~ y ~ List(m,d) => BigInt(julius(y.toInt, m.toInt, d.toInt))
    

    ユリウス日 (JDN)の計算方法については Wikipedia: ユリウス通日 中の「グレゴリオ暦からの換算式」中の JDNへの換算式を参照する. ただし,以下の点に注意すること. 床関数 \(\lfloor x\rfloor\) は \(x\) 以下の最大の整数を表すから, \(x < 0\) の場合に,整数への切り捨てを意味する整数除算とは少し異なる. 例えば \(\lfloor -1/2 \rfloor\) は -1 で 0 ではない. 同様に \(x \bmod y\) と x % y の結果も, \(x\) が負の場合に異なるから注意する. \(-1 \bmod 12\) は 11 だが -1 % 12 は -1 になる. 関数 julius の定義は,以下のようになる.

    def julius(y: Int, m: Int, d: Int) = {
      .....
      val jdn = ......
      jdn  // jdnの値を返す
    }
    

    以下のようにして事前にテストしておくと良い.

    scala> :load Work1.scala
    scala> import Work1._
    scala> julius(1858, 11, 17)
    res: Int = 2400001
    scala> julius(2000, 1, 1)
    res: Int = 2451545
    scala> julius(2018, 1, 1)
    res: Int = 2458120
    
  7. n番目の素数を求める関数 prime(n) を追加せよ. ただしnおよび素数の値は Int の範囲内として良い.なお,1番目の素数は2である.
    (ヒント)

    以下のようなcaseパターンを追加し,Work1 オブジェクト内に関数 prime(n: Int) を定義する.

    case "prime" ~ n ~ Nil => BigInt(prime(n.toInt))
    

    n番目の素数を求める関数については Scalaで素数ものさしを探す を参照. 以下のようにして事前にテストしておくと良い.

    scala> :load Work1.scala
    scala> import Work1._
    scala> prime(306)
    res: Int = 2017
    scala> prime(2018)
    res: Int = 17551
    

5.2 テスト方法

テスト用のデータ test1.txt を同じフォルダにダウンロードし, 以下のように実行するとテストを実施できる.

scala> :load Work1.scala
scala> Work1.test
  • OK と表示された場合,構文解析に成功し,計算した結果が正しい.
  • NG と表示された場合,構文解析に成功したが,計算結果が正しくない.
  • ERR と表示された場合,構文解析でエラーが生じている.
  • XXX と表示された場合は,プログラムの誤りである.

あるいは,コマンドラインから以下のように入力する.

$ scala Work1.scala <test1.txt >out1.txt 2>&1
$ cat out1.txt

出力は out1.txt ファイルに保存され, cat コマンドで表示している.

scalacでコンパイルしてから実行するのでも良い.

$ scalac Work1.scala
$ scala Work1 <test1.txt >out1.txt 2>&1
$ cat out1.txt

5.3 提出方法

  • 提出期限: 2018-05-16 Wed 00:00 JST (講義の前日の真夜中まで)
    • その1週間後まで提出可能だが減点する.
  • 提出方法: BEEFから提出する.
    • 提出期限内ならば何度でも提出できる
  • 提出内容: 以下のファイルを提出すること.
    • Work1.scala (ファイル中に以下を記入すること)
      • 「学籍番号」,「氏名」
      • 「対応した拡張の番号」
      • 「対応した拡張の説明,工夫した点,苦労した点など」
      • 「感想」 (採点には無関係です)
    • out1.txt (上のテスト方法で実行した結果)
  • 注意
    • 必ず提出後のファイルをダウンロードして内容を確認すること.
    • 最大点を25点として採点する.
    • test1.txt の内容は変更しないこと.
    • Work1.scalaの「Do not modify the following lines」以下の行は変更しないこと.
    • 文字コードは必ずUTF-8にすること.以下のコマンドで文字コードをUTF-8にできる.
      $ mv Work1.scala Work1old.scala
      $ nkf -w <Work1old.scala >Work1.scala
      
    • case _ => ??? の行は削除せず,case文の最後に書いておくこと.

5.4 解説

  1. xiすべての最大値を求める関数 max(x1, x2, ..., xn) を追加せよ.
    (解答例)

    以下のようなcaseパターンを追加すれば良い.

    case "max" ~ x ~ ys => x.max(ys.max)
    

    以下でも良い.

    case "max" ~ x ~ ys => (x +: ys).max
    
  2. 正の整数xとyの最大公約数を求める関数 gcd(x, y) を追加せよ.
    (解答例)

    以下のようなcaseパターンを追加すれば良い.

    case "gcd" ~ x ~ List(y) => x.gcd(y)
    
  3. 正の整数xiすべての最大公約数を求める関数 gcd(x1, x2, ... xn) を追加せよ.
    (解答例)

    以下のようなcaseパターンを追加すれば良い.

    case "gcd" ~ x ~ ys => (x +: ys).reduce(_.gcd(_))
    

    この場合,2のcaseパターンは不要である.

  4. 正の整数xiすべての最小公倍数を求める関数 lcm(x1, x2, ... xn) を追加せよ.
    (解答例)

    関数 lcm(x, y) を Work1 オブジェクト中に 以下のように定義する.

    object Work1 extends JavaTokenParsers {
      def lcm(x: BigInt, y: BigInt) = (x * y) / x.gcd(y)
      def expr: .....
      .....
    }
    

    また,以下のようなcaseパターンを追加する.

    case "lcm" ~ x ~ ys => (x +: ys).reduce(lcm)
    
  5. n番目のフィボナッチ数を求める関数 fib(n) を追加せよ.
    (解答例)

    Work1 オブジェクト内に関数 fib(n: Int): BigInt を定義する (Scalaで再帰プログラミング の4.2 練習問題を参照).

     def fib(n: Int): BigInt = {
       def fib(n: Int, f0: BigInt, f1: BigInt): BigInt =
         n match {
           case 0 => f0
           case _ => fib(n - 1, f1, f0 + f1)
         }
       fib(n, 0, 1)
     }
    

    また,以下のようなcaseパターンを追加する.

    case "fib" ~ n ~ Nil => fib(n.toInt)
    
  6. 西暦y年 (y ≥ 1900) m月d日の正午のユリウス日 (JDN)を求める関数 julius(y, m, d) を追加せよ. 今日のユリウス日から自分の誕生日のユリウス日を引けば,何日生きてきたかがわかる.
    (解答例)

    Work1 オブジェクト内に関数 julius(y: Int, m: Int, d: Int) を定義する.

     def julius(year: Int, month: Int, day: Int) = {
       val y = if (month < 3) year - 1 else year
       val m = (month - 3 + 12) % 12
       val d = day - 1
       val n = d + ((153*m + 2) / 5) + 365*y + (y / 4) - (y / 100) + (y / 400)
       val mjd = n - 678881
       val jdn = mjd + 2400001
       jdn
     }
    

    また,以下のようなcaseパターンを追加する.

    case "julius" ~ y ~ List(m,d) => BigInt(julius(y.toInt, m.toInt, d.toInt))
    
  7. n番目の素数を求める関数 prime(n) を追加せよ. ただしnおよび素数の値は Int の範囲内として良い.なお,1番目の素数は2である.
    (解答例)

    Work1 オブジェクト内に関数 prime(n: Int) を定義する.

    def isPrime(p: Int) = (2 to math.sqrt(p).toInt).forall(p % _ != 0)
    def nextPrime(p: Int): Int = if (isPrime(p+1)) p+1 else nextPrime(p+1)
    def prime(n: Int): Int = if (n <= 1) 2 else nextPrime(prime(n - 1))
    

    また,以下のようなcaseパターンを追加する.

    case "prime" ~ n ~ Nil => BigInt(prime(n.toInt))
    

6 文法の拡張

"二千十八" など,日本語での数表記が可能な電卓へ拡張してみよう.

CalcP4.scalaexpr の定義を変更し, 日本語表記の文字列に対し整数を返す関数 jint を追加する.

def expr: Parser[BigInt] =
  integer ^^ { BigInt(_) } |
  jint |
  (func <~ "(") ~ expr ~ (rep("," ~> expr) <~ ")") ^^ {
    case "+" ~ x ~ ys => x + ys.sum
    case "-" ~ x ~ Nil => - x
    case "-" ~ x ~ ys => x - ys.sum
    case "*" ~ x ~ ys => x * ys.product
    case "/" ~ x ~ ys => x / ys.product
    case _ => ???
  }

では "一" から "九" の一桁の表記を可能なプログラムを作成してみよう (CalcPJ1.scala). プログラム中で jint1 は一桁の数を構文解析し BigInt の値を返す関数である.

import scala.util.parsing.combinator._

object CalcPJ1 extends JavaTokenParsers {
  def expr: Parser[BigInt] =
    integer ^^ { BigInt(_) } |
    jint |
    (func <~ "(") ~ expr ~ (rep("," ~> expr) <~ ")") ^^ {
      case "+" ~ x ~ ys => x + ys.sum
      case "-" ~ x ~ Nil => - x
      case "-" ~ x ~ ys => x - ys.sum
      case "*" ~ x ~ ys => x * ys.product
      case "/" ~ x ~ ys => x / ys.product
      case _ => ???
    }
  def func = "+" | "-" | "*" | "/" | ident
  def integer = wholeNumber
  def jint = jint1
  def jint1 =
    "一" ^^ { _ => BigInt(1) } |
    "二" ^^ { _ => BigInt(2) } |
    "三" ^^ { _ => BigInt(3) } |
    "四" ^^ { _ => BigInt(4) } |
    "五" ^^ { _ => BigInt(5) } |
    "六" ^^ { _ => BigInt(6) } |
    "七" ^^ { _ => BigInt(7) } |
    "八" ^^ { _ => BigInt(8) } |
    "九" ^^ { _ => BigInt(9) }
}

以下のように実行できる.

scala> :load CalcPJ1.scala
scala> import CalcPJ1._
scala> parseAll(expr, "+(一,二,三)")
res: CalcPJ1.ParseResult[BigInt] = [1.9] parsed: 6

次に,これを "二十三" などの二桁の表記が可能なように拡張しよう. 二桁の数は "二十" や "十三" なども可能である. つまり "二十三" での "二" や "三" の部分 (あるいは両方)が省略できる. したがって,二桁以下の数を表す jint2 の構文は以下のように定義できる.

def jint2 = opt(jint1) ~ "十" ~ opt(jint1) | jint1

opt(jint1) は,空または jint1 を表している. opt(jint1) に対する構文解析結果のデータ型は Option[BigInt] となり, 空の場合は None という値を持ち, 空でない場合は Some(x) という値を持つ (xjint1 の結果で BigInt).

ただし, jint2 の構文を以下のように定義すると "二十" の構文解析でエラーになってしまう.

def jint2 = jint1 | opt(jint1) ~ "十" ~ opt(jint1)

これは "二十" の構文解析で, jint1 の規則の適用が "二" の部分に対して先に成功してしまい, opt(jint1) ~ "十" ~ opt(jint1) の規則へ進まないためである. したがって,文法定義の際には,このような点に注意しなければならない.

結局,二桁以下の表記が利用できるプログラム CalcPJ2.scala は以下のようになる. def jint = jint2 としている点に注意する.

import scala.util.parsing.combinator._

object CalcPJ2 extends JavaTokenParsers {
  def expr: Parser[BigInt] =
    integer ^^ { BigInt(_) } |
    jint |
    (func <~ "(") ~ expr ~ (rep("," ~> expr) <~ ")") ^^ {
      case "+" ~ x ~ ys => x + ys.sum
      case "-" ~ x ~ Nil => - x
      case "-" ~ x ~ ys => x - ys.sum
      case "*" ~ x ~ ys => x * ys.product
      case "/" ~ x ~ ys => x / ys.product
      case _ => ???
    }
  def func = "+" | "-" | "*" | "/" | ident
  def integer = wholeNumber
  def jint = jint2
  def jint1 =
    "一" ^^ { _ => BigInt(1) } |
    "二" ^^ { _ => BigInt(2) } |
    "三" ^^ { _ => BigInt(3) } |
    "四" ^^ { _ => BigInt(4) } |
    "五" ^^ { _ => BigInt(5) } |
    "六" ^^ { _ => BigInt(6) } |
    "七" ^^ { _ => BigInt(7) } |
    "八" ^^ { _ => BigInt(8) } |
    "九" ^^ { _ => BigInt(9) }
  def jint2 =
    (opt(jint1) <~ "十") ~ opt(jint1) ^^ {
      case None ~ None => BigInt(10)
      case Some(x1) ~ None => 10 * x1
      case None ~ Some(x2) => 10 + x2
      case Some(x1) ~ Some(x2) => 10 * x1 + x2
    } |
    jint1
}

以下は,実行例である.

scala> :load CalcPJ2.scala
scala> import CalcPJ2._
scala> parseAll(expr, "+(十二,三十四,五十六)")
res: CalcPJ2.ParseResult[BigInt] = [1.14] parsed: 102

さらに,三桁の "九百九十九" 以下の値まで利用できる プログラム CalcPJ3.scala は以下のようになる. def jint = jint3 としている点に注意する.

import scala.util.parsing.combinator._

object CalcPJ3 extends JavaTokenParsers {
  def expr: Parser[BigInt] =
    integer ^^ { BigInt(_) } |
    jint |
    (func <~ "(") ~ expr ~ (rep("," ~> expr) <~ ")") ^^ {
      case "+" ~ x ~ ys => x + ys.sum
      case "-" ~ x ~ Nil => - x
      case "-" ~ x ~ ys => x - ys.sum
      case "*" ~ x ~ ys => x * ys.product
      case "/" ~ x ~ ys => x / ys.product
      case _ => ???
    }
  def func = "+" | "-" | "*" | "/" | ident
  def integer = wholeNumber
  def jint = jint3
  def jint1 =
    "一" ^^ { _ => BigInt(1) } |
    "二" ^^ { _ => BigInt(2) } |
    "三" ^^ { _ => BigInt(3) } |
    "四" ^^ { _ => BigInt(4) } |
    "五" ^^ { _ => BigInt(5) } |
    "六" ^^ { _ => BigInt(6) } |
    "七" ^^ { _ => BigInt(7) } |
    "八" ^^ { _ => BigInt(8) } |
    "九" ^^ { _ => BigInt(9) }
  def jint2 =
    (opt(jint1) <~ "十") ~ opt(jint1) ^^ {
      case None ~ None => BigInt(10)
      case Some(x1) ~ None => 10 * x1
      case None ~ Some(x2) => 10 + x2
      case Some(x1) ~ Some(x2) => 10 * x1 + x2
    } |
    jint1
  def jint3 =
    (opt(jint1) <~ "百") ~ opt(jint2) ^^ {
      case None ~ None => BigInt(100)
      case Some(x1) ~ None => 100 * x1
      case None ~ Some(x2) => 100 + x2
      case Some(x1) ~ Some(x2) => 100 * x1 + x2
    } |
    jint2
}

7 課題2

7.1 内容

以下からいくつかを選択し, Work2.scala に対して拡張を行うこと.

  1. "九千九百九十九" 以下の値を利用できるようにせよ.
    (ヒント)

    以下の構文定義を利用し, jint3 と同様に修正する.

    def jint4 = (opt(jint1) <~ "千") ~ opt(jint3) | jint3
    

    また def jint = jint4 と変更する.

  2. "九千九百九十九万九千九百九十九" 以下の値を利用できるようにせよ.
    (ヒント)

    以下の構文定義を利用し, jint3 と同様に修正する.

    def jintMan = (jint4 <~ "万") ~ opt(jint4) | jint4
    

    ただし,構文解析結果のパターンは case x1 ~ None の場合と case x1 ~ Some(x2) の2通りだけである.

  3. "九千九百九十九億九千九百九十九万九千九百九十九" 以下の値を利用できるようにせよ.
    (ヒント)

    以下の構文定義を利用する.

    def jintOku = (jint4 <~ "億") ~ opt(jintMan) | jintMan
    
  4. さらに "兆", "京", "垓" などを利用できるようにせよ (Wikipedia: 命数法).
    (ヒント)

    "兆" については以下の構文定義を利用する.

    def jintCho = (jint4 <~ "兆") ~ opt(jintOku) | jintOku
    

    1兆の値は BigInt("1000000000000") あるいは BigInt(10).pow(12) とすれば求まる.

  5. "きゅうひゃくきゅうじゅうきゅう" など,ひらがなの表記を利用できるようにせよ.
    (ヒント)

    jint1, jint2, jint3 などに規則を追加すれば良い. 例えば,六は "ろく" でも "ろっ" でも良いから,以下のようにする.

    ("六" | "ろく" | "ろっ") ^^ { _ => BigInt(6) } |
    

    ただし, "し" と "しち" の両方がある場合,"しち" のパターンを先に書く必要がある.

    同様に,百は以下のように変更すれば良い.ただし ??? の部分は自分で考える.

    (opt(jint1) <~ ("百" | "ひゃく" | "びゃく" | "ぴゃく")) ~ opt(jint2) ^^ {
      ???
    } |
    
  6. "和(1,2,3,4) など,日本語で加減乗除を記述できるようにせよ. 関数名は "和", "差", "積", "商" とすること.
    (ヒント)

    expr に規則を追加すれば良い. ident は "和" などの日本語文字列にもマッチするから, func の定義は変更しなくても良い.

  7. #7E2 などの16進表記が可能になるようにせよ.
    (ヒント)

    16進表記を許す構文規則については,以前の練習問題を参照. また BigInt("7E2", 16) とすれば,16進表記の文字列を BigInt に変換できる. expr について,以下の構文定義に変更する.ただし ??? の部分は自分で考える.

    def expr: Parser[BigInt] =
      integer ^^ { BigInt(_) } |
      hexnum ^^ { ??? } |
      jint |
      (func <~ "(") ~ expr ~ (rep("," ~> expr) <~ ")") ^^ {
        ???
      }
    
  8. "12k で 12000, "12M" で 12000000 などを表せるようにせよ (Wikipedia: SI接頭辞).
    (ヒント)

    expr について,以下の構文定義に変更する.ただし ??? の部分は自分で考える. また,最後の行に case _ => ??? を必ず追加すること.

    def expr: Parser[BigInt] =
      integer ~ ("k" | "M" | "G" | "T" | "P") ^^ {
        case x ~ "k" => ???  // x は10進表記の文字列
        ???
        case _ => ???  // この行はこのまま
      } |
      integer ^^ { BigInt(_) } |
      hexnum ^^ { ??? } |
      jint |
      (func <~ "(") ~ expr ~ (rep("," ~> expr) <~ ")") ^^ {
        ???
      }
    
  9. 36#z など,2進から36進までの任意の基数表記が可能になるようにせよ. 36#z の場合,36進表記であり z は35を表す. また 16#7E2 の場合,16進表記であり 7E2 は2018を表す. なお a から z の小文字と A から Z の大文字は,どちらでも同じ数字を表す. k進表記の文字列sをBigIntに変換するには BigInt(s, k) とする. 例えば BigInt("z", 36) の値は35, BigInt("7E2", 16) の値は2018である. なお,指定した基数が大きすぎる場合や,文字列中に基数の範囲外の数字が現れた場合, BigInt(s, k) で変換エラーが生じる可能性があるが,これは無視してプログラムを作成して良い.
    (ヒント)

    以下の構文定義を利用する.ただし ??? の部分は自分で考える.

    def expr: Parser[BigInt] =
      "\\d+".r ~ ("#" ~> "[0-9a-zA-Z]+".r) ^^ {
        case radix ~ num => ???
      } |
      integer ~ ("k" | "M" | "G" | "T" | "P") ^^ {
        case x ~ "k" => ???
        case x ~ "M" => ???
        ???
      } |
      integer ^^ { BigInt(_) } |
      hexnum ^^ { ??? } |
      jint |
      (func <~ "(") ~ expr ~ (rep("," ~> expr) <~ ")") ^^ {
        .....
      }
    

7.2 テスト方法

テスト用のデータ test2.txt を同じフォルダにダウンロードし, 以下のように実行するとテストを実施できる.

scala> :load Work2.scala
scala> Work2.test
  • OK と表示された場合,構文解析に成功し,計算した結果が正しい.
  • NG と表示された場合,構文解析に成功したが,計算結果が正しくない.
  • ERR と表示された場合,構文解析でエラーが生じている.
  • XXX と表示された場合は,プログラムの誤りである.

あるいは,コマンドラインから以下のように入力する.

$ scala Work2.scala <test2.txt >out2.txt 2>&1
$ cat out2.txt

出力は out2.txt ファイルに保存され, cat コマンドで表示している.

scalacでコンパイルしてから実行するのでも良い.

$ scalac Work2.scala
$ scala Work2 <test2.txt >out2.txt 2>&1
$ cat out2.txt

7.2.1 IntelliJでの実行方法

IntelliJ では,標準でparser combinatorはライブラリに含まれていない. 以下のようにすれば良い.

  • sbtプロジェクトとして作成する.
  • build.sbt に以下の行を追加する.
    libraryDependencies ++= Seq(
      "org.scala-lang.modules" %% "scala-parser-combinators" % "1.1.0"
    )
    
  • Work2.scalasrc/main/scala/ 中に作成する.
  • test2.txt は プロジェクト直下のディレクトリに置く.

実行方法は以下の通り.

  1. IntelliJウィンドウの下部のsbt shellを立ち上げ,以下のようにして プログラムをコンパイルする.
    > compile
    
  2. IntelliJウィンドウの下部のTerminalを立ち上げ,以下のように実行する.
    $ scala -cp target/scala-2.12/classes Work2 <test2.txt >out2.txt 2>&1
    

なお main を以下のように書き換えても良い (この変更をした Work2.scala を提出しても良い).

def main(args: Array[String]) {
  if (args.size == 0) {
    test(Source.stdin)
  } else if (args.size == 1) {
    test(Source.fromFile(args(0)))
  } else {
    val out = new java.io.PrintStream(args(1))
    Console.withOut(out) {
      Console.withErr(out) {
        test(Source.fromFile(args(0)))
      }
    }
    out.close
  }
}

この場合sbt shellで以下のように実行できる.

> run test2.txt
> run test2.txt out2.txt

1行目の場合,結果はウィンドウ内に表示される. 2行目の場合,結果は out2.txt ファイルに書き込まれる.

7.3 提出方法

  • 提出期限: 2018-05-31 Thu 00:00 JST
    • その1週間後まで提出可能だが減点する.
  • 提出方法: BEEFから提出する.
    • 提出期限内ならば何度でも提出できる
  • 提出内容: 以下のファイルを提出すること.
    • Work2.scala (ファイル中に以下を記入すること)
      • 「学籍番号」,「氏名」
      • 「対応した拡張の番号」
      • 「対応した拡張の説明,工夫した点,苦労した点など」
      • 「感想」 (採点には無関係です)
    • out2.txt (上のテスト方法で実行した結果)
  • 注意
    • 必ず提出後のファイルをダウンロードして内容を確認すること.
    • 最大点を25点として採点する.
    • test2.txt の内容は変更しないこと
    • Work2.scalaの「Do not modify the following lines」以下の行は変更しないこと.
    • 文字コードは必ずUTF-8にすること.以下のコマンドで文字コードをUTF-8にできる.
      $ mv Work2.scala Work2old.scala
      $ nkf -w <Work2old.scala >Work2.scala
      
    • case _ => ??? の行は削除せず,case文の最後に書いておくこと.
    • :load Work2.scala で多数のエラーが表示された場合, いったんscalaを抜けて scalac Work2.scala でコンパイルすると, 適切なエラーメッセージが得られる.

8 TODO 発展

以下 作成中

以下は,やや進んだ内容である. 興味があればプログラムを解読してみて欲しい.

8.1 Parser combinatorの仕組み

Parser combinatorの仕組みを調べるため,まず CalcP0.scala をロードして見よう.

scala> :load CalcP0.scala
scala> import CalcP0._

以下のようにすると wholeNumberintegerCalcP0.Parser クラスのインスタンスであり,結果が String であることが分かる.

scala> wholeNumber
res: CalcP0.Parser[String] = Parser ()

scala> integer
res: CalcP0.Parser[String] = Parser ()

Calc0.Parser の親クラスは scala.util.parsing.combinator.Parsers.Parser である.

scala.util.parsing.combinator.JavaTokenParsers のメソッド parse を利用すれば, これらの Parser で定義された構文規則にしたがって構文解析を行い, その結果 (CalcP0.ParseResult のインスタンス)を得ることができる.

scala> parse(integer, "123")
res: CalcP0.ParseResult[String] = [1.4] parsed: 123

なお CalcP0.ParseResult の親クラスは scala.util.parsing.combinator.Parsers.ParseResult となる.

上の例では,文字列の1文字目から4文字目の前までに対して構文解析が成功しており ([1.4] の表示), その結果が 123 という String であることがわかる. 結果の String だけを取り出すには get メソッドを用いる.

scala> parse(integer, "123").get
res: String = 123

"123 456" という文字列に対して同様に実行すると以下の結果になる.

scala> parse(integer, "123 456")
res: CalcP0.ParseResult[String] = [1.4] parsed: 123

この場合も4文字目の前までに対して構文解析が成功しており,5文字目以降の " 456" の部分は構文解析されていない. これは, "123 456" 全体は integer の構文規則に合致しないから,当然の結果である.

以下のように integer ~ integer (整数の後ろにもうひとつ整数がある)という構文規則を利用すれば, 全体に対して構文解析が成功する.

scala> parse(integer ~ integer, "123 456")
res: CalcP0.ParseResult[String ~ String] = [1.8] parsed: (123~456)

この場合の構文解析結果は String ~ String というデータ型となっている. これは ~ というクラスを用いてふたつの構文解析結果をまとめたものである.

メソッド _1 を用いれば最初の整数文字列,メソッド _2 を用いれば二番目の整数文字列を取り出せる.

scala> parse(integer ~ integer, "123 456").get._1
res: String = 123

scala> parse(integer ~ integer, "123 456").get._2
res: String = 456

integerParser オブジェクトだったが, integer ~ integerParser オブジェクトである.

scala> integer ~ integer
res: CalcP0.Parser[String ~ String] = Parser (~)

こちらの ~Parser クラスのメソッド (演算子)であり,これら二つの Parser オブジェクト (すなわち二つの integer)から,新しい Parser オブジェクトを生成する (美しいアイデアですね!).

このように,既存の Parser から新しい Parser を演算子 (コンビネータ)を用いて生成していることから, このような演算子は parser combinator と呼ばれている.

Scala で利用できる主な parser combinator を以下に示す. ただし parser1 で受理できる文字列を s1parser2 で受理できる文字列を s2 とする.

Combinator説明
parser1 ~ parser2s1s2 を連結した文字列を受理する Parser を作る
parser1 \(\mid\) parser2s1 または s2 の文字列を受理する Parser を作る
rep(parser1)s1 を0回以上繰り返した文字列を受理する Parser を作る
opt(parser1)s1 または空の文字列を受理する Parser を作る

さらに,上では以下の combinator を利用した.

Combinator説明
parser1 <~ parser2s1s2 を連結した文字列を受理するが
s1 を結果とする Parser を作る
parser1 ~> parser2s1s2 を連結した文字列を受理するが
s2 を結果とする Parser を作る
parser1 ^^ funcs1 を受理するが, s1func
変換したものを結果とする Parser を作る

8.2 複数の種類のデータ型を返す

プログラム CalcD1.scalaDouble および Double のリストをデータとし, その間の加減算を計算できる.

scalac でコンパイルしてから使用する.

$ scalac CalcD1.scala
$ scala
scala> import CalcD1._

scala> parseAll(expr, "[1, 2, 3]")
res: CalcD1.ParseResult[Value] = [1.10] parsed: [1.0,2.0,3.0]

scala> parseAll(expr, "+([1, 2, 3], [4, 5, 6])")
res: CalcD1.ParseResult[Value] = [1.24] parsed: [5.0,7.0,9.0]

scala> parseAll(expr, "-([1, 2, 3], 4)")
res: CalcD1.ParseResult[Value] = [1.16] parsed: [-3.0,-2.0,-1.0]

8.3 中置記法への対応

def expr: Parser[Any] = opt("-") ~ term ~ rep("+" ~ term | "-" ~ term)
def term: Parser[Any] = factor ~ rep("*" ~ factor | "/" ~ factor)
def factor: Parser[Any] = floatingPointNumber | "(" ~> expr <~ ")" | func
def func: Parser[Any] = (ident <~ "(") ~ expr ~ (rep("," ~> expr) <~ ")")

CalcI1.scala

CalcI2.scala

8.4 抽象構文木の利用

9 発展課題

Work1.scala, Work2.scala と同様に Work3.scala を作成し,自由に拡張を行え. ただし,テスト用のデータ test3.txt を作成し Work3.test でテストを実行できるようにせよ.

以下は,拡張の例である.

  1. "MMXVIII" など,ローマ数字の表記を可能にする (Wikipedia: ローマ数字).
  2. "nine hundreds and ninety nine" など,英語での表記を可能にする.
  3. 複素数の計算を行う電卓を作成する.
  4. 有理数 (分数)の計算を行う電卓を作成する.
  5. ベクトルや行列の計算を行う電卓を作成する.

9.1 提出方法

  • 提出期限: 2018-05-31 Thu 00:00 JST
    • その1週間後まで提出可能だが減点する.
  • 提出方法: BEEFから提出する.
    • 提出期限内ならば何度でも提出できる
  • 提出内容: 以下のファイルを提出すること.
    • Work3.scala (ファイル中に以下を記入すること)
      • 「学籍番号」,「氏名」
      • 「対応した拡張の説明,工夫した点,苦労した点など」
      • 「感想」 (採点には無関係です)
    • test3.txt (入力ファイル)
    • out3.txt (上のテスト方法で実行した結果)
  • 注意
    • 最大20点のボーナス点を与える.

Date: 2018-05-30 15:45:46 JST

Author: 田村直之

Validate XHTML 1.0