おもこん

おもこんは「思いつくままにコンピュターの話し」の省略形です

NIM(石取りゲーム)

NIMと英語ではいい、日本では「石取りゲーム」「三山崩し」と呼ばれるゲームがあります。 チップ(硬貨を模したプラなどの円盤)を3か所に置きます。チップの数は適当で良いです。 この3つの場所を「山」ということもあります。 2人でゲームをし、交代でチップを取ります。 このとき、いくつ取っても良いが、一つの場所(山)からしか取れません。 2つ以上の場所から取るのはルール違反です。 また、必ず石は取らなくてはならず、パスすることはできません。 こうして、最後にチップを取った者が勝者になります。

NIM

具体的な例を紹介しましょう。 最初の山が2-3-4だったとします。

A: 右の山から3つ取り、2-3-1にする

B: 左の山から1つ取り、1-3-1にする

A: 中央の山から3つ取り、1-0-1にする

B: 左の山から1つ取り、0-0-1にする

A: 右の山から1つ取り、0-0-0にする。

最後のチップをAが取ったので、Aの勝ちです。 勝敗が決まると、最後はかならず0-0-0の形になります。

勝ちパターン

しばらくやってみると、勝ちパターンがあることが分かります。 例えば、自分が石を取って、0-1-1の形で相手に手を回すと、相手はどちらかの山からひとつ石を取るしかなく、最後の石は自分が取ることができます。 このような勝ちパターンを「必勝形」と呼ぶことにします。 「必勝形」はその形をもって相手の手番にすることに注意してください。 逆に言えば、相手に必勝形を作られて、自分の手番になり、互いに最善手をくりかえせば、自分の負けになります。

必勝形には、他にも0-2-2や0-3-3のように、1か所がゼロで、他の2か所が同じ数のものがあります。 また、1-2-3も必勝形です。 少し考えてみれば、これらが必勝形であることがわかると思います。

必勝形の分析

必勝形を分析して、そのパターンの成り立ちが分かれば、NIMに勝てるようになります。 これは難しい問題ですが、すでにこのパターンの仕組みは知られています。 ポイントは数字を二進数で表すことです。 いくつかの必勝形を二進数で書いてみましょう。

必勝形 二進数
0-3-3 0-11-11
1-2-3 1-10-11
1-4-5 1-100-101
2-4-6 10-100-110

気づいたでしょうか。 ビットごとに見ると、1が偶数(0個の場合も偶数です)であることがわかります。 例えば、2-4-6のときは、10-100-110で、左端(4の位)が1が2個で偶数、中央(2の位)が1が2個で偶数、右端(1の位)が1が0個で偶数です。

コンピュータ言語では、ビットごとの排他的論理和(XOR)をとる演算が定義されていることが多いです。 Rubyの場合は、^がそれにあたります。 排他的論理和では、

0^0=0
1^0=1
0^1=1
1^1=0

となります。 上の例では1桁だけですが、2桁以上の数でもこの演算子でビットごとの排他的論理和を計算できます。 例えば、

3^5=011^101=110=6

となります。

必勝形では、それぞれの数の排他的論理和をとるとゼロになります。 例えば、1-2-3は必勝形ですが、

1^2^3(十進数表記)=1^10^11(二進数表記)
= 00(二進数表記、各ビットの1の数が偶数だから全部0になる)
= 0

排他的論理和がゼロの状態からチップを取ると、排他的論理和が0では無くなります。 そこから、うまくチップを取ると再び排他的論理和がゼロになります。 このことは、成り立つことが知られています。 証明はインターネットで探せばどこかにあるでしょう。

したがって、ひとたび必勝形を作り、相手に手番を渡したプレーヤーは、常に排他的論理和がゼロの状態をキープすることができます。 そして最終的に勝利を手に入れることができるのです。

コンピュータで必勝形を探す

コンピュータで必勝形を探すプログラムは簡単です。 要するに排他的論理和がゼロになるような取り方を計算するだけですから。 このプログラムをRubyで作ってみました。 起動時に引数で3つの山のチップの数を与えると、必勝形を作って表示します。 もしも、最初に与えたチップの数がすでに必勝形であれば、プレーヤーは勝つことができません。 その場合は、プログラムは"Lost"と表示します。

class Nim
    attr_reader(:a, :b, :c)
    # The arguments below must be non-negative.
    # If some of them are negative, they will be replaced by the absolutes of them.
    def initialize(a=0,b=0,c=0)
        @a = a>=0 ? a : -a
        @b = b>=0 ? b : -b
        @c = c>=0 ? c : -c
    end
    def try
        x = @a^@b^@c
        return false if x == 0
        if @a > @a^x
            @a = @a^x
        elsif @b > @b^x
            @b = @b^x
        elsif @c > @c^x
            @c = @c^x
        else
            return false
        end
        true
    end
    def to_s
        "#{@a}, #{@b}, #{@c}"
    end
end

def usage
    $stderr.print "Usage: ruby nim.rb a b c\n"
end

if ARGV.size != 3
    usage
    return
end

h = Nim.new(ARGV[0].to_i, ARGV[1].to_i, ARGV[2].to_i)
if h.try
    print h
else
    print "Lost"
end

これは単に必勝形を計算するだけで、対戦型ではありません。 対戦型にするには、ユーザとのインタラクティブな部分を処理するプログラムが必要になります。

RubyGemsに登録してあるマイGem紹介

RubyGemsRubyのライブラリで、誰でも登録し、ダウンロードすることができます。 私は2つのGemを登録してあるので、ここで紹介したいと思います。 興味を持った方はぜひダウンロードして使ってみてください。 前提として、Rubyがインストールされていなければなりません。 OSは問いません。WindowsでもLinuxでも動きます(Macは手元にないので試していませんが、動くと思います)。

電卓プログラム

まず、s_calcというGemです。 これは関数電卓(scientific calculator)です。 インストールはgemコマンドで行います。

$ gem install s_calc

これには、2つの使い方があり、ひとつはコマンドとして、もうひとつはRubyのライブラリとしてです。 まず、コマンドとしてはcalcという名前で使います。

$ calc
calc > 1+2*3
7
calc >q
$

こんな感じです。 三角関数や、指数対数も使えます。 また、前回計算結果をvという変数に入れています。

$ calc
calc > 1/2
0.5
calc > v+3
3.5
calc >q
$

変数も使えます。変数はアルファベットのみからなります。

$ calc
calc > abc=100
100
calc > abc*3
300
calc >q
$

Rubyのライブラリとして使うときは

  • require "calc"として取り込む
  • c = Calc.newなどとして、Calcクラスのインスタンスを生成する
  • c.run("1+2*3")のように、計算式を引数にしてrunメソッドをコールすると、答えが返される

なお、GitHubソースコードとドキュメントがあります。

LaTeXのソースファイル管理

LaTeXで文書(とくに大きな文書)を作るための環境を整えるプログラムです。 インストールは

$ gem install lbt

でできます。

主な使い方は

  • lbt new ディレクトリ名で作られるディレクトリ下にソースファイルを書く
  • ソースファイルはLaTeX形式でもMarkdown形式でも良い。Markdownは拡張子.mdとする。これはPandocでLaTeX形式に自動変換される
  • sec1.texあるいはsec1.mdなどのファイル名でソースファイルを作る
  • lbt buildコンパイルをすると、PDFファイルができあがる

詳しくはGItHubにあるドキュメントを見てください。 自分の実感としては、ドキュメント作成が手軽になったと思います。

Ubuntuの新バージョン23.10

Ubuntuの新しいバージョン23.10がリリースされ、約2週間経ちました。

Ubuntu23.10をインストール

リリース後すぐに23.04からのアップグレードができるかと思っていたら、どうもそうではなかったようです。 自分のUbuntuの設定では新リリースにアップグレードできる場合には通知が来るようになっていました。 しかし、今まで待っても来なかったので、新規にインストールすることにしました。 つまり、今までのUbuntu23.04のパーテションを初期化してそこにUbuntu23.10をインストールしました。

このような新規インストールはアップグレードよりも手間がかかります。

  • 必要なファイルをバックアップする。私の場合は、個人フォルダの中身を見て、必要なものをバックアップしました。
  • 新規インストールをする
  • 必要なソフトウェアを追加インストールする。私の場合は、TeXLive、Rbenv(Rubyを含む)をネットからインストールし、パッケージからはGit、Pkg-config、Mesonなどをインストールしました。

比較的スムーズに作業は進み、1日ですべて終わりました。

Gtk4のバージョンがアップ

Gtk4のバージョンは4.12.2にアップデートされていました。 以前のUbuntu23.04でのGtk4がが4.10.1だったので、だいぶ進んだ感があります。 Gtk4は4.10で大幅に変更されましたが、4.12でも少し変更があります。 「Gtk4チュートリアル」を見直して、必要な対応をしなければならないと思っています。 ですが、分量が多いので時間が必要でしょう。 来月から、個人的に忙しくなるし・・・・

Ubuntu23.10の変更点

これについては、参考になるサイトがあります。

見た目ですぐに分かるのは、デスクトップが新しくなったことです。 前のバージョンではGNOME44でしたが、今回はGNOME45になっています。 左上の「アプリケーション」の文字が無くなり、ワークスペースがそこに表示されるようになりました。 細かい変更は他にもたくさんあるのですが、上のサイトに詳しいので、そちらをご覧ください。

おまけ

今回のインストールで、RubyインストーラであるRbenvも進歩していることに気がつきました。 今まで面倒な手作業が多かったのが、インストール用のスクリプトができて、ほとんど一発でインストールできます。

ソフトウェアは日々進歩していますね。

ファイル名に使える文字

ファイル名に使える文字はOSによって違う

Linuxでファイルを作るときにはほとんどの文字がファイル名に使えます。 厳密にいえば、OSというよりもOSの採用しているファイルシステムに依存します。 UBUNTU 23.04ではファイルシステムext4です。 ext4ではスラッシュとヌル以外をファイル名に用いることができます(ウィキペディア参照)。

これに対して、WIndowsはファイル名に使える文字が少ないのです。 次の文字はファイル名に使えません。

  • /
  • \
  • :
  • *
  • "
  • ?
  • <
  • >
  • |
  • NULL

また、WIndowsではLinuxと違い、大文字小文字を区別しません。

(注)

私はほとんどWIndowsを使っていないので、詳しくはないのですが、WSL-2というLinuxファイルシステムWIndowsでマウントする仕組みがあるそうです。 それを使うと上記のような非互換を避けることができるようです。 ただし、このことはNTFSやFATでフォーマットされたHDDやUSBメモリが上記の禁止文字を許すという意味ではありません。

USBメモリのフォーマット

現在、市販のUSBメモリのフォーマットはFAT32が多いといわれています。 また、HDDの場合はFAT32またはNTFSが多いようです。 いずれにしても、これらの製品をそのままLinuxで使うときはファイル名などの注意が必要です。

最も良いのは、上記の禁止文字をファイル名に使わないことです。 そうすれば、無用のトラブルを避けることができます。

仮に禁止文字の入っているファイル名のファイルがLinuxファイルシステムにあったとしましょう。 例えばabc?.txtのように禁止文字?が入ったファイル名のファイルです。 これをFAT32USBメモリにコピーしようとすると、ファイル名が不適当だというエラーがでてコピーできません。 ファイル名を適切に変更してコピーすればコピーは可能です。

fchangeプログラム

以上の問題を解決するために、Linuxファイルシステム上のファイルに対して、(WIndowsの)禁止文字を含むファイル名を変更するプログラムを作ってみました。 fchangeという名前のRubyプログラムです。 先程の禁止文字(ヌルを除く)をすべてアンダースコア(_)に変更します。 例えば

abc?.txt => abc_.txt

プログラムはGitHubにアップロードしてあります。

用途が限られたプログラムですが、HDDにバックアップをとるときなどは便利だと思います。

HDDやUSBのファイルフォーマットを変更する。

HDDやUSBの使い始めのときに、ext4ファイルシステムにフォーマットしておくと上記のような苦労がありません。 その代わり、そのディスクをWIndowsでも使うとなると、単純にはext4を読むことができません。 Windowsで読み込むにはWSL-2を使えば良い(らしい)です。 上記のMicrosoftの「WSL-2でLinuxディスクのマウントを開始する」を参照してください。

もしも、あなたがWindowsを使わずLinuxオンリーならば、ext4でフォーマットするのがベストです。

結論

最も良いのは、HDDやUSBはWindowsのフォーマットで、Linuxシステム上のファイルでも禁止文字を使わないことです。 自分もそうしていたつもりだったのですが、バックアップをとる段階で禁止文字をファイルに使っていたことに気づきました。

もしも読者に同じことが起こったら、fchangeがひとつの解決法を提供します(ただし、問題が発生しても責任はとれないので自己責任でお願いします)。

単項マイナスと構文解析

追記 2023/10/16 Calcのことで訂正があります。

単項マイナスとは

単項マイナスとは、式のなかに使われるマイナスで、その数字の符号を変えるためのものです。 例えば「−2」は2の符号をマイナスに変更する演算です。 「ー」には「引き算」を表す場合もありますが、単項マイナスの演算はそれではありません。 例をあげてみましょう。

  • 「ー2」・・・単項マイナス
  • 「3−2」・・・引き算のマイナスで、単項マイナスではない

単項マイナスと引き算のマイナスは異なる演算子ですから、違う文字を割り当てれば混乱しないのですが、習慣上同じ文字を使うことになってしまいました。

単項マイナスと括弧

単項マイナスには括弧をつけるという数式記述上の習慣があります。

2+(-3)
2-(-3)
2*(-3)+6/(-3)

これは括弧なしで「2+−3」と書いたときに、それが「2+(−3)」とは分かりにくいという、人間の感覚上の問題があるからです。 実は、単項マイナスの優先順位を加減乗除よりも高くしておけば、曖昧にはなりません。

2+-3=2+(-3)=-1
2--3=2-(-3)=2+3=5
2*-3+6/-3=2*(-3)+6/(-3)=(-6)+(-2)=-8

人間と違って、コンピュータは見た目でなく、論理的に式を解析しますから、括弧なしでもきちんと式を解釈してくれます。 我々人間にとって、これは慣れの問題だと思うので、括弧なしの単項マイナスOKと決めてしまっても大丈夫なのではないでしょうか。

なお、数式の記述において単項マイナスの括弧を省略できるケースがあります。 それは数式の最初に単項マイナスがくる場合です。 例えば「−2*3+4」という式を考えてみましょう。 乗算と加算では乗算が優先するものとします。つまり、掛け算「*」は足し算「+」よりも前に計算します。 この式は2通りに解釈できますが、どちらも同じ結果になります。

-2*3+4 = (-2)*3+4 = -6+4 = -2
-2*3+4 = -(2*3)+4 = -6+4 = -2

このように解釈が分かれても結果が同じになるので、括弧を省略して良いわけです。 これは3項を足す場合に括弧がなくて良いのと同じ理由です。

1+2+3 = (1+2)+3 = 3+3 = 6
1+2+3 = 1+(2+3) = 1+5 = 6

このように加算は、左結合または右結合のいずれをとっても結果が同じになり、そのことから括弧を無しで書くことが許されます。

括弧なし単項マイナスを許容する場合のBNF

括弧なし単項マイナスを許容する式を構文解析するためのBNFを考えてみましょう。 なお、BNF構文解析については前回の記事を参照してください。

演算子の優先順位を定義しておけば、極めて単純なBNFになります。 以下のファイルをsample3.yとして保存します。

class Sample3
  token NUMBER
  prechigh
    nonassoc UMINUS
    left '*' '/'
    left '+' '-'
  preclow
  options no_result_var
rule
  expression  : expression '+' expression { val[0] + val[2] }
              | expression '-' expression { val[0] - val[2] }
              | expression '*' expression { val[0] * val[2] }
              | expression '/' expression { if val[2] != 0 then val[0] / val[2] else raise "Division by zero." end }
              | '-' expression =UMINUS { -val[1] }
              | '(' expression ')' { val[1] }
              | NUMBER
end

---- header

---- inner

def lex(s)
  @tokens = []
  until s.empty?
    case s[0]
    when /[+\-*\/()]/
      @tokens << [s[0], s[0]]
      s = s[1..-1] unless s.empty?
    when /[0-9]/
      m = /\A[0-9]+/.match(s)
      @tokens << [:NUMBER, m[0].to_f]
      s = m.post_match
    else
      raise "Unexpected character."
    end
  end
end

def next_token
  @tokens.shift
end

---- footer

sample = Sample3.new
print "Type q to quit.\n"
while true
  print '> '
  $stdout.flush
  str = $stdin.gets.strip
  break if /q/i =~ str
  begin
    sample.lex(str)
    print "#{sample.do_parse}\n"
  rescue => evar
    m = evar.message
    m = m[0] == "\n" ? m[1..-1] : m
    print "#{m}\n"
  end
end

Raccを使ってコンパイルします。

$ racc sample3.y

すると、sample3.tab.rbというRubyのソースファイルができます。 これは、BNFに沿って計算するRubyプログラムです。 実行してみましょう。

$ ruby sample3.tab.rb
Type q to quit.
> 1+-2
-1.0
> 1--2
3.0
> 2*-3
-6.0
> -2*-3
6.0
> q
$

単項マイナスは高優先順位の演算子なので、乗除の計算に先立って計算しています。 括弧のない「1−−2」のような式は、違和感がありますが、文法的には曖昧さなしに定義できているわけです。

calcの場合

追記 2023/10/16

GitHubのCalcにバグがあり、修正しました。 それに伴い以前ここに書いた記事にもあやまりがありましたので、訂正して下記のように直しました。

GitHubに登録してあるCalcの場合も単項マイナスが他の演算子に優先するようになっています。

このBNFの中から、四則と単項マイナスの部分だけを取り出して、若干の手直しを加えると次のようになります。

  expression  : expression '+' expression { val[0] + val[2] }
              | expression '-' expression { val[0] - val[2] }
              | expression '*' expression { val[0] * val[2] }
              | expression '/' expression { if (val[2] != 0.0) then val[0] / val[2] else raise("Division by zero.") end }
              | '-' primary  =UMINUS { -(val[1]) }
              | primary
primary     : '(' expression ')' { val[1] }
              | NUM

BNFの完全な形については上記のリンクをたどり、racc/calc.yを参照してください。

徒然Ruby(44)Raccパーサ・ジェネレータ

パーサ・ジェネレータとは

パーサを日本語で「構文解析器」といいます。 「器」とといっても、「うつわ」ではなく「器械」、より適切にはアプリケーションまたはプログラムのことです。 つまり、構文解析をするプログラムです。

構文解析」とは、「プログラム言語などの構文」を「解析」することです。 簡単な例として、足し算を考えてみましょう。

1+2
11+34
123+456

3つの足し算の例があります。 出てくる数字は違うものですが、どれも「数字+数字」というパターンは変わりません。 3番めの文字列は7つの文字からなっています。

1, 2, 3, +, 4, 5, 6

この7文字はバラバラではなく、最初の3つがひとまとまりで、「123」という数字を表しており、その後「+」という演算記号、「456」という数字が続きます。 そこで、この7文字をタイプと値のセットで、それぞれ次のようにまとめましょう。

数字, 123
+, 何でも良い
数字, 456

数字には値が必要ですが、演算記号には値がありませんから、2番めの「値」のところは何でも良いのです。 ここでは、同じ演算記号の文字列"+"にしておきましょう。 また、「数字」というタイプは、Numberの最初の3文字をとって、シンボル:NUMで表すことにします。 すると、「123+456」という7文字の文字列は

[[:NUM, 123], ["+", "+"], [:NUM, 456]]

という配列にすることができます。 これを字句解析といいます。 配列の要素の[:NUM,123]を字句またはトークンといいます。 トークンのタイプを表す:NUMなどをタイプとかトークン・カインドといいます。 配列の2番めの要素「123」は値とか、意味上の値(semantic value)などといいます。 字句解析は、構文解析には含まれないというのが一般的な考え方です。

それでは、この構文はどういうものでしょうか。 さきほど述べたように、どの式も「数字+数字」の形です。 そこで、この式(expression)は

expression : NUM '+' NUM

と表すことができます。 式(expression)とは数字(NUM)の次にプラス('+')がきて、その次にまた数字(NUM)がくるというトークンの列のことである、ということです。 この記法をBNFバッカス・ナウア・フォーム)といいます。

この構文はRaccが理解できる形にしています。

  • NUMにはコロンをつけない(:NUMとはしない)
  • +はシングルクォートで囲む。

足し算のトークン・カインドを新たに決めることもできますが(例えばPLUSとして、字句解析では[:PLUS, "+"]とする)、演算子はそれ自体をトークン・カインドにすることが多いです。 そのことによって、トークン・カインドの種類が多くなるのを防ぎ、プログラマーの負担を軽くする狙いがあります。 演算子をそのままトークン・カインドにするときは、

  • BNFの中ではシングルクォートで囲む
  • 字句解析のトークン・カインドはシンボルではなく文字列を使う(:+ではなく'+'にする)

とします。シンボルでないことには注意してください。

このように式(expression)を定義すると、最初の3つの足し算はすべてこのBNFに沿っていることがわかります。 このBNFで表されたものを、文法(grammar)といいます。

Rubyなどのプログラム言語はもっと複雑な文法を持っていますが、その文法に入力(ソースファイル)があっているかどうかは確認ができます。 あっていなければ「Syntax Error」(文法上のエラー)となります。

例えば次のような式はさきほどの足し算の文法からはSyntax Errorになります。

1+2+3
10-6
-20

この3つはエラーが発見される時点が違います。 最初から順に見ていって、エラーになるところを●で表すと

1+2+●3
10-●6
-●20

黒丸の左側の要素を見た時シンタックスエラーが確定します。

少し複雑な文法

それでは、我々が普段使う足し算、引き算の計算をBNFにしてみましょう。

この計算では、数字、+、ー、(、)の5つのトークンが必要です。 具体例を見てみましょう。

1-2+3
(1-2)+3
1-(2+3)

最初の例は後回しにして、2番めを見てみます。 これは、はじめに1と2の2つの数字を引き算し、その結果と3を加える、というもので、木構造(ツリー)で表現すると

(1-2)+3

となります。 3番めは同様に、

1-(2+3)

です。

1行目の「1-2+3」には括弧がないので、上の図のどちらのツリーになるか、曖昧さが残ります。 通常は頭から計算するので、1-2を先に計算するのですが、構文解析上はそれを明示する必要があります。 その方法については後ほど述べることにします。

この例では1回の計算の結果が次の式の中で使われています。 つまり、「数字+数字」ではなく「式+式」のような場合があるということです。 そこで、BNFを少し変えてみます。

expression : expression '+' expression | expression '-' expression

縦棒(|)は「または」という意味で、その左側のパターンでも右側のパターンでも良いということです。 このBNFでは、expressionをexpressionで定義しているので、これだけでは構文を表したことになりません。 前は式を「数字+数字」としていました。 少なくとも数字が式の定義に出てこなければいけないでしょう。 そこで、次のように変えてみます。

expression : expression '+' expression
           | expression '-' expression
           | NUM

このように、定義は2行以上に渡っても良いことにします。 式は「式+式」または「式ー式」または「数字」のいずれかに一致すれば良い、ということです。 これならば、「1-2+3」は式であることがわかります。

  • 1」は「数字」したがって「式」でもある
  • 1-2」は「式ー数字」だが、数字は式でもあるので、「式ー式」になる。これはBNFの2行目のパターンなので式とみなせる。
  • 1-2+3」は「1-2」が式なので、「式+3」すなわち「式+数字」だが、数字は式だから「式+式」となり、BNFの1行目のパターンに一致するから式である。

しかし、実は違う方法で式であることも説明できます。

  • 1-2+3」は「2+3」が「数字+数字」、すなわち「式+式」だから、式となる
  • 1-2+3」は「2+3」が式なので、「数字ー式」となり、数字は式だから「式ー式」となり、BNFの2行目のパターンに一致するから式である。

1−2+3が式であることはBNFで確認できるが、その方法は少なくとも2通りあるということです。 しかも、その計算結果は異なり、それぞれ2と−4になります。 ですから、BNFの解釈が2通りというのはとてもまずいことなのです。 また、この2通りは、さきほど木構造で表した2通りと同じことだとわかります。 ですから、解釈が1通りになるには括弧を加える、というのはひとつの方法です。

expression : expression '+' expression
           | expression '-' expression
           | '(' expression ')'
           | NUM

これだと、「(1−2)+3」や「1−(2+3)」が文法的に合うようになります。 解釈が2通り出てしまう「1−2+3」は防げませんが、そういうものは

  • シンタックス・エラーだということにする
  • 解釈が2通りでたら「左側の演算から優先的に行う」という条件をつけて1通りに強制する

のどちらかを採用すればよいのです。

また、次のようにBNFを変更すると、常に計算は左から行われるようになります。

expression : expression '+' primary
           | expression '-' primary
           | primary
primary    : '(' expression ')'
           | NUM

「1−2+3」がこれでどのように解釈されるか考えてみましょう。 なお、primaryは日本語で一次因子とかプライマリーと呼ばれます。

  • 「1−2」は「数字ー数字」で、数字=>プライマリー=>式だから、「式ープライマリー」なので式になる
  • 「1−2+3」は「式+3」すなわち「式+数字」になり、それは「式+プライマリー」だから「式」になる

2+3を先に計算する方は上記のBNFには合いません。

  • 「2+3」は「数字+数字」=>「式+プライマリー」になるので「式」になる
  • 「1−2+3」は「数字ー式」=>「式ー式」になるが、「式ープライマリー」ではない。したがって、式にはならない

このBNFは計算の第二項が「式」ではなく「プライマリー」であるとして、プライマリーが「括弧で囲まれた式」か「数字」のみということで、括弧なしで右から計算することを取り除いています。

以上をまとめると、計算の順序の曖昧さを防ぐ方法は2つあり、

  • BNFで示す
  • 演算子+とーが2つあった場合、左から計算すると定義しておく

ということになります。

四則(加減乗除)計算のBNF

今回の最後に四則計算の文法定義のBNFを作ってみましょう。 足し算引き算のところで、演算子が2つあったとき、左から計算するか、右から計算するかの2通りの解釈が生まれる場合がありました。 似たものに、乗除と加減の優先順位の問題があります。

1+2*3

ここでは、Rubyと同じように掛け算はアスタリスク*)で表します。 この計算では、「2かける3」を先にやることになっています。 ですから、

1+2*3 = 1+6 = 7

となります。 これは小学校で習いますね。 ところが、コンピュータはそういうことを習っていませんから、BNFなどで、演算の優先順位を定義しなければなりません。 ところで、「1+6」の1や6を「項(term)」と呼びます。 また、「2*3」の2や3を「因子(factor)」といいます。 BNFだけで演算の優先順位を表現するには式、項、因子を分けて定義します。

expression  : expression '+' term
            | expression '-' term
            | term
term        : term '*' factor
            | term '/' factor
            | factor
factor      : '(' expression ')'
            | NUMBER

このBNFは「2+3+4」のような括弧のない式は左から順に計算するようになっており、曖昧さが発生しません。 このBNFでは、単項マイナス、すなわち因子の符号を変えるマイナス(例えば「−2」のようなマイナス)はサポートしていません。

Racc で実装

このBNFをRaccのソースファイルに取り入れて、コンパイルしてみましょう。 Raccのソースファイルは拡張子.yにするのが習慣です。 大きく4つのパートに分かれます。

  • クラスの定義、BNFの記述部分。この部分はRaccによってRubyプログラムにコンバートされる
  • (header)クラス定義の前にコピーされるRubyプログラム
  • (inner)クラスの中のコンバートされる部分の前に挿入されるRubyプログラム
  • (footer)クラス定義のあとにコピーされるRubyプログラム。メインプログラムを書く場合はここに書く

クラス定義、BNFの記述部分

ここがRaccのソースプログラムのメインです。 スーパークラスは書かないようにします(class A < BのBの部分は書かない)。

  • token の後にトークンを宣言しておく。これは無くても良いが、トークンの綴間違いなどをチェックできる。例えばtoken NUMのようにする
  • optionsの後にオプションを指定できる。options no_result_varが良く用いられる。その意味はドキュメントを参照
  • rule以降(classのendまで)にBNFを記述する

具体例を次に示します。

class Sample1
  token NUMBER
  options no_result_var
rule
  expression  : expression '+' term { val[0] + val[2] }
              | expression '-' term { val[0] - val[2] }
              | term
  term        : term '*' factor { val[0] * val[2] }
              | term '/' factor { if val[2] != 0 then val[0] / val[2] else raise "Division by zero." end }
              | factor
  factor      : '(' expression ')' { val[1] }
              | NUMBER
end

BNF加減乗除をサポートする以前示したものと同じですが、その後ろに波括弧で囲まれた部分があります。 これはアクションと呼ばれるものです。 アクションの左側のBNFに一致したときに、そのアクションが実行されます。 配列valは左のBNFの要素に対応するアクションが実行されたときの結果です。 例えば

  factor      : '(' expression ')' { val[1] }
              | NUMBER

この2行目にはアクションがありませんが、その場合のアクションは{ val[0] }、すなわち最初のBNFの要素のアクションの結果を返す、ということになっています。 NUMBERは字句解析で返された数字に一致しますので、その値が返されます。 1行目は括弧で囲まれた式です。このBNFには、左括弧、式、右括弧の3つの要素があります。val[1]は2番めの要素である式のアクションの結果です。 したがって、この括弧で囲まれたfactorの値は、括弧で囲まれた式の値になります。

このようにして、それぞれの式に一致したときに、その計算がアクションとして行われます。

なお、定義するクラスをモジュールの中に入れたいときは

class MName::Sample1

のようにします。MNameはクラスを入れるモジュールの名前です。 Raccでコンパイルすると

module MName
  class Sample1
... ... ...
  end
end

このようになります。

ヘッダー、インナー、フッター

ヘッダーに良く書かれるのはrequire文です。 このサンプルプログラムでは特に記述するものはありません。

インナーには字句解析関係のプログラムを書きます。 また、Raccで生成したパーサが字句を一つずつ読み込むためのメソッドはnext_tokenというメソッド名に決まっています。 それを実装します。具体例を示します。

def lex(s)
  @tokens = []
  until s.empty?
    case s[0]
    when /[+\-*\/()]/
      @tokens << [s[0], s[0]]
      s = s[1..-1] unless s.empty?
    when /[0-9]/
      m = /\A[0-9]+/.match(s)
      @tokens << [:NUMBER, m[0].to_f]
      s = m.post_match
    else
      raise "Unexpected character."
    end
  end
end

def next_token
  @tokens.shift
end

メソッドlexが引数の文字列を字句解析するプログラムです。 ここでは、StrScanライブラリを使っていませんが、大きなプログラムでは高速な字句解析のためにStrScanを用いるほうが良いです。 その場合は、headerのところにstrscanライブラリをrequireしてください。 演算子は、その文字列をタイプと値にして@tokensにプッシュします。 数字(0以上の整数)はタイプを:NUMにしてその数字(Floatオブジェクトに直したもの)をプッシュします。 IntegerでなくFloatにしたのは、割り算で小数点以下まで出したかったからです。 Integerオブジェクトにしても良いのですが、その場合は割り算で小数点以下は切り捨てられます。 それ以外の文字は例外を発生させます。

メソッドnext_tokenは字句解析の配列からひとつづつ取り出して返します。

フッターの部分にはメインプログラムを書きます。 メインプログラムから、構文解析をするにはdo_parseメソッドをコールします。 そのコールの前にはlexメソッドによる字句解析は終了していなければなりません。 以下の例では一行入力しては、その計算をして表示します。

sample = Sample1.new
print "Type q to quit.\n"
while true
  print '> '
  $stdout.flush
  str = $stdin.gets.strip
  break if /q/i =~ str
  begin
    sample.lex(str)
    print "#{sample.do_parse}\n"
  rescue => evar
    m = evar.message
    m = m[0] == "\n" ? m[1..-1] : m
    print "#{m}\n"
  end
end

特に難しいことないと思います。 ソースプログラム(sampe1.y)の全体も以下に示しておきます。

class Sample1
  token NUMBER
  options no_result_var
rule
  expression  : expression '+' term { val[0] + val[2] }
              | expression '-' term { val[0] - val[2] }
              | term
  term        : term '*' factor { val[0] * val[2] }
              | term '/' factor { if val[2] != 0 then val[0] / val[2] else raise "Division by zero." end }
              | factor
  factor      : '(' expression ')' { val[1] }
              | NUMBER
end

---- header

---- inner

def lex(s)
  @tokens = []
  until s.empty?
    case s[0]
    when /[+\-*\/()]/
      @tokens << [s[0], s[0]]
      s = s[1..-1] unless s.empty?
    when /[0-9]/
      m = /\A[0-9]+/.match(s)
      @tokens << [:NUMBER, m[0].to_f]
      s = m.post_match
    else
      raise "Unexpected character."
    end
  end
end

def next_token
  @tokens.shift
end

---- footer

sample = Sample1.new
print "Type q to quit.\n"
while true
  print '> '
  $stdout.flush
  str = $stdin.gets.strip
  break if /q/i =~ str
  begin
    sample.lex(str)
    print "#{sample.do_parse}\n"
  rescue => evar
    m = evar.message
    m = m[0] == "\n" ? m[1..-1] : m
    print "#{m}\n"
  end
end

コンパイルと実行

コンパイルは「racc ソースファイル名」で行います。

$ racc sample1.y
$ ls
sample1.y sample1.tab.rb

sample1.tab.rbがRaccで生成されたRubyプログラムです。 このファイルをエディタで見ると、BNFが様々な配列とメソッドに変換されているのがわかります。 実行してみましょう。

$ ruby sample1.tab.rb
Type q to quit.
> 1-2-5
-6.0
> 2*3+4*5
26.0
> (10+25)/(3+4)
5.0
> q

計算は正しく行われていますね。

演算子の優先順位と結合における左右の優先順位

BNFにあいまいさがあるときに、その解決方法として

  • BNFをあいまいさの残らない形に変更する
  • 演算の優先順位を指定する

の2つが考えられます。 後者には2つあり、例えば

  • 乗除は加減より優先的に計算する。例えば「1+2*3」では「1+2」よりも「2*3」を先に計算する。 このように演算子の間に優先順位をつけることにより、曖昧さを解決できることがあります。 四則では、
    • 乗除の優先順位は同じ。つまり「1*2/3」は「1*2」と「2/3」のどちらを先にするかの取り決めはない。この順については別に定めが必要
    • 加減の優先順位は同じ。
    • 乗除は加減に対して優先順位が高い
  • 同レベルの演算があったときに、左から先に計算する(左結合)または右からさきに計算する(右結合)を定める。 通常は加減乗除とも同レベルの演算は左から先に計算する。 右結合は少ないが、無いわけではない。たとえば累乗は右結合である。累乗を「^」で表すと「2^3^4」は「2^81」のことになる。

Raccでは、これらの優先順位を指定することができます。 優先順位をprecedenceといい、Raccはこの最初の4文字を用いて

  • prechigh: 優先順位が高い
  • preclow: 優先順位が低い

この2つ間に演算子を書き、同じ行には同じ優先順位、上の方が優先順位が高い、とします。

また、左結合はleft、右結合はrightで指定します。 以上のルールを用いると、BNFが単純でもパーサを生成することができます。

Raccのソースファイルの最初の部分を書き換えてみましょう。 なお、footerのインスタンス生成時のクラス名はSample1からSample2に変更が必要です。

class Sample2
  token NUMBER
  prechigh
    left '*' '/'
    left '+' '-'
  preclow
  options no_result_var
rule
  expression  : expression '+' expression { val[0] + val[2] }
              | expression '-' expression { val[0] - val[2] }
              | expression '*' expression { val[0] * val[2] }
              | expression '/' expression { if val[2] != 0 then val[0] / val[2] else raise "Division by zero." end }
              | '(' expression ')' { val[1] }
              | NUMBER
end

3行目から6行目が計算順を示す部分です。 このおかげで、BNFは短く、すっきりしたものになりました。

まとめ

この電卓プログラムのソースコードはわずか57行です。 これをRubyで書いたら、そんな短いコードではすみません。

Raccは構文解析が必要なプログラム、例えばインタープリタコンパイラ、電卓などを書くときの大きな手助けになります。 言語はCで書かれることが多いですが、Cの場合はパーサ・ジェネレータのBisonを使うことが多いです。 BisonもRaccのようなプログラムです。

Raccを使った電卓プログラムをGitHubにあげてありますので、参考に見てください。

また、Raccのドキュメントはこちらをご覧ください。

徒然Ruby(43)StrScanライブラリで字句解析

電卓プログラムの記事で予告したStrScanライブラリの話です。

StrScanライブラリのドキュメント

Rubyのドキュメントに説明があります。 簡単な説明ですが、それで使い方はわかると思います。

字句解析とは

字句解析は、主にプログラミング言語で使われます。 例えば次のようなRubyプログラムを考えてみましょう。

def hello
  print "Hello world\n"
end

このプログラムを分解すると、次の表のようになります。

文字列 タイプ
def 予約語def
空白 空白
hello 識別子 hello
改行 改行
空白 空白
空白 空白
print 識別子 print
空白 空白
"Hello world\n" 文字列 Hello world\n
改行 改行
end 予約語end
改行 改行

この中の空白は、区切りという意味しかなく、それがなくてもRubyインタープリタはプログラムを解釈できます。 ですので、これらは捨てられてしまいます。 なお、改行は言語によって空白と同じように捨てられることもあります。 Rubyは改行によって、文や式の区切りを表すことがあるので、残しておきます。 空白以外の要素はインタープリタに送られます。 それらの要素は字句またはトークン(token)と呼ばれます。

トークンはタイプと値のセットにします。 タイプは「トークン・カインド(token kind)」とも呼ばれます。 タイプの部分には文字列またはシンボルを使うことが多いです。 例えば「予約語のdef」はシンボル:DEFなどです。 ここで大文字を使ったのは、トークン・カインドに大文字を使う習慣があるからです。 ここでは、シンボルでトークン・カインドを表すことにしましょう。

タイプ トークン・カインド
予約語def :DEF
改行 :NL
識別子 :ID
文字列 :STR
予約語end :END

トークンを配列の形でまとめると、

[ [:DEF, "def"],
  [:ID, "hello"],
  [:NL, "NewLine"],
  [:ID, "print"],
  [:STR, "Hello world\n"],
  [:NL, "NewLine"],
  [:END, "end"],
  [:NL, "NewLine"]
]

となります。 配列の要素はすべて「タイプ」「値」という形になります。 予約語の場合はタイプだけで用が足りるので、値は何でも構いません。 [:DEF,"def"][:DEF,nil]としても、構文解析上は問題ありません。

このように、プログラムの文字列を、その言語の要素に分解することを「字句解析」といいます。 字句解析は、文字列のパターンを見つけることですから、正規表現のあるRubyでは簡単にできます。 しかし、短い時間でパターンを発見するにはStrScanライブラリを使うのが良いそうです。

StrScanライブラリ

StrScanライブラリの使い方をまとめると、次のとおりです。

  1. strscanライブラリをrequireする
  2. StringScannerインスタンスを生成する。そのとき、引数に対象となる文字列を与える
  3. scanメソッドでパターンを比較する

具体例を示しましょう。

require 'strscan'

s = StringScanner.new("def hello\n  print \"Hello world.\n\"\nend\n")

p s.scan(/def/) #=> "def"
p s.scan(/hello/) #=> nil
p s.scan(/[[:blank:]]/) #=> " "
p s.scan(/hello/) #=> "hello"
p s[0] #=> "hello"
p s.eos? #=> false
  • 1行目:strscanライブラリを取り込む
  • 3行目:StringScannerインスタンスを生成。引数が対象文字列。
  • 5行目:scanメソッドは、文字列の先頭が正規表現/def/に一致すれば、その文字列"def"を返す。文字列検索のポインタはdefの次の文字に移動
  • 6行目:scanメソッドは、ポインタ位置の文字列が正規表現/hello/に一致しないので、nilを返す
  • 7行目:scanメソッドは、ポインタ位置の文字列が正規表現/[[:blank:]]/(空白またはタブ)に一致するので、その文字列" "を返す。文字列検索のポインタは空白の次の文字に移動
  • 8行目:scanメソッドは、ポインタ位置の文字列が正規表現/hello/に一致するので、その文字列"hello"を返す。文字列検索のポインタはhelloの次の文字に移動
  • 9行目:[0]メソッドは、前回のマッチ文字列を返す。マッチが失敗していればnilを返す。また、正規表現でカッコを使うとマッチの一部をs[1]、s[2]、・・・で取り出せる
  • 10行目:ポインタが文字列の最後まで進んでないので、falseを返す。

StrScanライブラリを使った字句解析

では、そきほどのRubyコードの字句解析プログラムを作ってみましょう。

require 'strscan'

s = StringScanner.new("def hello\n  print \"Hello world.\n\"\nend\n")

token = []
until s.eos?
  if s.scan(/[[:blank:]]+/)
    ; # throw away space/tab characters
  elsif s.scan(/\n/)
    token << [:NL, "NewLine"]
  elsif s.scan(/def/)
    token << [:DEF, "def"]
  elsif s.scan(/end/)
    token << [:END, "end"]
  elsif s.scan(/"([^"]*)"/)
    token << [:STR, s[1]]
  elsif s.scan(/[[:alpha:]][[:alnum:]]*/)
    token << [:ID, s[0]]
  else
    raise "Unexpected character."
  end
end
p token

until文で、ポインタが文字列の終端になるまで繰り返します。 if-elsif文で順に空白、改行、予約語def、予約語end、文字列、識別子、その他に一致するかを見て、それぞれに対応するアクションを行います。 空白は無視され、「その他」には「Unexpected character.」の例外を発生させます。 これを実行すると次のような結果を得ることができます。

[[:DEF, "def"], [:ID, "hello"], [:NL, "NewLine"], [:ID, "print"], [:STR, "Hello world.\n"], [:NL, "NewLine"], [:END, "end"], [:NL, "NewLine"]]

なお

  • このプログラムでは文字列内のバックスラッシュ記法や式展開はサポートされず、ごく単純化した形になっています
  • Rubyの字句解析が目的であれば、Ripperライブラリがまさにそのためのライブラリです

実例

StrScanライブラリを用いた実例として、GitHubにCalcレポジトリがあります。

ファイルracc/calc.yの57行から77行のlexメソッドが電卓プログラムの字句解析部分になります。 Calcがどのような機能を持っているかはREADME.mdファイルを参照してください。

この字句解析は、Racc(パーサ・ジェネレータ)で使うことを前提にしています。 Raccの場合、トークン・カインドは次のような形になります。

  • 識別子をIDで表すことにすると、トークン・カインドはシンボル:IDにする
  • 演算子、例えば和の記号+などは、その文字列自身をトークン・カインドにする。注意すべきは、それは文字列"+"であって、シンボル:+ではない

次回はパーサ・ジェネレータのRaccについて投稿予定です。