5th Floor, Inc.

記事一覧

オレオレ記法を作ろう！ 〜2.ミニミニ記法〜
(12/8/2017)

こんにちは！フィフス・フロア開発チームの notozeki です。

この記事は、「オレオレ記法を作ろう！」というシリーズの第2回目です。前回は、記法を作るのに便利な Racc というツールを紹介し、簡単に使い方を説明しました。

今回は、いよいよ実際に記法を解析するプログラムを作っていこうと思います。ただ、いきなり Markdown のような全部入りの記法を作るのは大変なので、機能を絞った「ミニミニ記法」とでも呼ぶようなものを作ろうと思います。

ところで、記法を解析するプログラムのことを、専門用語で「パーサ (parser)」といいます。parse という英語が「（文を）解析する」という意味を持ち、それをするプログラムなので -er をつけて parser です。今後はこの用語を使っていきます。今回は「ミニミニ言語パーサ」を作るわけですね。

前置きはこれくらいにして、早速開発していきましょう！今回の内容は、前回の記事に基いているので、未読の方はまずそちらをお読みくださいね。

前準備: 規則の組み合わせ

実際にパーサを作る前に、まずは前回のおさらいも兼ねながら、少し複雑な文法の書き方についておさえておきます。

前回の最後の時点で、文法の部分はこのようになっていました。

expr : INTEGER '+' INTEGER { puts val[0] + val[2] }
     | INTEGER '-' INTEGER { puts val[0] - val[2] }

この文法は、1 + 2 や 8 - 5 のような2つの数の足し算と引き算を扱えるようにしたものでしたね。覚えていますか？

長い式への対応

まず、このパーサを 1 + 2 + 3 のような、長い式に対応させてみましょう。文法を以下のように変更してください。

top : expr { puts val[0] }

expr : expr '+' primary { result = val[0] + val[2] }
     | expr '-' primary { result = val[0] - val[2] }
     | primary          { result = val[0] }

primary : INTEGER { result = val[0] }

今回の例がこれまでと大きく違う点は、「規則」が複数あるということです。これまでは expr という規則が1つだけありましたが、今回は top, expr, primary の3つに増えています。このように、規則はいくつでも書くことができます。

さらに、expr の右側を見ると、他の規則の名前（primary など）が書いてあることがわかります。このように、規則の中では、トークンだけでなく他の規則を使うことができるのです。

規則の説明

一つ一つの規則を見ていきましょう。まず一番わかりやすいのは以下の規則ですね（簡単のために「アクション」の部分は省略します）。

primary : INTEGER

これは、「primary とは、INTEGER という種類のトークン1つである」ということを表す規則です。これだけなら primary と書かずに直接 INTEGER と書いても良さそうですが、このあとの拡張のためにあえて規則を一つ増やしています。

expr : expr '+' primary
     | expr '-' primary
     | primary

つぎに expr です。少し長いですが、これは「expr とは、expr, '+', primary を順に並べたもの、もしくは expr, '-', primary を順に並べたもの、もしくは primary である」ということを表す規則です。

少し難しいので、具体例で考えてみます。1 + 2 + 3 のような式を考えてみましょう。これは、次のような流れで解釈されていきます。

  • 最初の 1 + 2 の部分が、expr だと解釈される
    • 1 は INTEGER → primary → expr
    • 2 は INTEGER → primary
    • expr '+' primary は expr
  • 次に、expr + 3 が expr と解釈される
    • 3 は INTEGER → primary
    • expr '+' primary は expr

したがって、1 + 2 + 3 のような長い式でも、expr だと解釈することができるようになります。

最後に、top を見てみましょう。これも簡単な規則です。

top : expr

「top とは、 expr である」という規則です。特に難しいことはありませんね。

ただし、この規則には重要な点があります。それは、「最終的にこの規則に当てはまれば、入力された文字列の文法は正しい」とみなされる規則であるという点です。逆に、この規則に当てはまらなければ、入力された文字列は文法に従っていないことになります。このような規則を「スタート規則」と呼びます。スタート規則は、デフォルトでは一番上に書いた規則が使われます。今回は top が（文字通り）一番上に書いてある規則なので、スタート規則になります。

アクションの説明

では、一旦省略していたアクションを含めて、規則をもう一度見ていきましょう。文法全体を再掲します。

top : expr { puts val[0] }

expr : expr '+' primary { result = val[0] + val[2] }
     | expr '-' primary { result = val[0] - val[2] }
     | primary          { result = val[0] }

primary : INTEGER { result = val[0] }

前回までは、アクションでは単に puts するくらいしかしませんでした。しかし、今回は result という変数への代入がたくさんあります。

じつは、アクションは値を返すことできます。Ruby の関数やメソッドと同様です。1つだけちがうのは、return を使う代わりに result という変数に代入するということです。

そして、アクションの返り値は、その規則の「値」になります。前回学んだ「トークンの値」と同じです。つまり、別のアクションで val[0], val[1], ... 等で参照することができるのです。

たとえば、1 とだけ入力したことを考えてみましょう。これは、以下のように処理されていきます。

  • primary : INTEGER に当てはまる。このとき、result = val[0] であるので、INTEGER の値 1 が、primary の値になる。
  • expr : primary に当てはまる。このときも result = val[0] であるので、primary の値 1 が、expr の値になる。
  • top : expr に当てはまる。このとき、puts val[0] なので、expr の値 1 が puts により画面に表示される。

このように、規則から規則へと値を伝えていくことができます。これは記法パーサを作るときも使うことになるので、覚えておいてください。

実行

さて、ここまででプログラムの動きは一通りわかったはずなので、今度は実際に動かしてみましょう。念のため、プログラム全体を掲載しておきますが、文法の部分以外は前回と同じです。このファイルを parser.y という名前で保存してください。

class Parser
rule
  top : expr { puts val[0] }

  expr : expr '+' primary { result = val[0] + val[2] }
       | expr '-' primary { result = val[0] - val[2] }
       | primary          { result = val[0] }

  primary : INTEGER { result = val[0] }
end

---- inner

def parse(text)
  @chars = text.chars
  do_parse
end

def next_token
  c = @chars.shift
  if c =~ /[0-9]/
    buf = c
    while (c = @chars.shift) && c =~ /[0-9]/
      buf << c
    end
    @chars.unshift(c)
    [:INTEGER, buf.to_i]
  elsif c =~ /\s/
    next_token
  elsif c == nil
    [false, nil]
  else
    [c, nil]
  end
end

def on_error(*args)
  puts 'ng'
end

---- footer

if $0 == __FILE__
  $stdin.each_line do |line|
    Parser.new.parse(line)
  end
end

では、実行してみましょう。まず、この文法ファイルを Ruby のスクリプトに変換する必要がありました。racc コマンドを使います。

$ racc parser.y -o parser.rb

これで parser.rb というファイルができているはずです。これを ruby コマンドで実行してみましょう。

$ ruby ./parser.rb

実行すると、何も起きずにプログラムが止まったはずです。ここに式を入力すれば、結果が表示されます。

1 + 2 
3
1 + 2 + 3
6
1 + 2 - 3
0

3つ以上の数を含む長い式を入力しても動くはずです！　足し算と引き算が混ざっていてもちゃんと動作しますね。すばらしい。

この記事では式の解析についてはこれ以上踏み込みませんが、掛け算や割り算に対応したり、( ) で優先順位をつけられるようにしても面白いと思います。余裕があればチャレンジしてみましょう。

ミニミニ記法

少々前準備が長くなってしまいましたが、いよいよ記法パーサの開発に入ろうと思います。

ミニミニ記法の書き方

パーサを作る前に、まずどんな記法にするか考えなければいけません。どんな記法にしましょうね……よし、こんな感じにしてみましょう。

これは最初の段落です。**これは強調です。**

一行以上空けると別の段落になります。

まずはこんなところでしょう。上記のような記法で書いた文章を解析して、以下のような HTML に変換することにします。

<p>これは普通の段落です。<strong>これは強調です。</strong></p>
<p>一行以上空けると別の段落になります。</p>

Markdown のまんまじゃないか！と言われそうですね…　おっしゃるとおりです。でもまずは簡単なところからということで、既存の記法を真似してみようと思います。

例文の中に使い方が書いてあるので説明をするまでもないかもしれませんが、一応説明しておきましょう。基本は行が段落になります。行が連続している場合はそれがすべて同じ段落になり、空行が入ると段落が変わります。

例:

これと
これは同じ段落

ここは違う段落

変換結果:

<p>
  これと
  これは同じ段落
</p>
<p>
  ここは違う段落
</p>

また、** で囲むと、囲まれた文字列を強調することができます。

例:

ここは強調ではありません。**ここは強調です。**

変換結果:

<p>ここは強調ではありません。<strong>ここは強調です。</strong></p>

文法

まずは文法作っていきましょう。いきなりですが完成形をお見せします。

top : blocks

blocks : block
       | blocks block

block : paragraph
      | BR

paragraph : lines BR

lines : line
      | lines line
line  : inlines BR

inlines : inline
        | inlines inline
inline  : chars
        | strong
chars   : CHAR
        | chars CHAR
strong  : DOUBLE_STAR chars DOUBLE_STAR

…ふう！これまでに比べるとだいぶ複雑になっていますね。少しずつ見ていきましょう。

単なる文字の列と強調

まずはこの2つの規則を見ていきましょう。

chars   : CHAR
        | chars CHAR
strong  : DOUBLE_STAR chars DOUBLE_STAR

一つ目は chars という規則で、これは単なる文字の列を表しています。「単なる文字」とは、記法の中で特別な意味を持つ文字「以外」を指します。今回の記法では、特別な意味を持つのは ** と改行（空行も記法として意味を持つため）です。それ以外の文字は、すべて「単なる文字」として扱われます。

chars の規則の中を見てみましょう。1つ目の規則はシンプルに CHAR のみです。CHAR は「単なる文字」1文字を表すトークンです（あとで next_token で実装します）。つまり、「単なる文字」1文字は、chars であると解釈されます。

もう1つの規則は、chars CHAR です。これは再帰的（chars の定義で chars を使う）な規則の一例です。少しややこしいですが、chars のあとに CHAR が続けば、それも chars であるということです。具体例を見てみましょう。例えば、abc という3文字（3つの CHAR）は、以下のように解釈されていきます。

CHAR CHAR CHAR
↓ (CHAR → chars)
chars CHAR CHAR
↓ (chars CHAR → chars)
chars CHAR
↓ (chars CHAR → chars)
chars

これは、いくら CHAR が続いても、同じような流れで最終的に chars として解釈されます。つまり、この chars の規則は、「CHAR が（1つ以上）連続して並んでいるもの」という規則を表しているのです。同じものが連続して並んでいるという規則は、文法を書く上で頻出のパターンですので、覚えておきましょう（このあともたくさん出てきます）。

strong のほうも見てみましょう。こちらはシンプルに 「DOUBLE_STAR chars DOUBLE_STAR が並んだもの」という規則になっています。chars は先程見たように「単なる文字」の並びです。DOUBLE_STAR は、double star、つまり星2つという意味で、** を表すトークンです（あとで next_token で実装します）。

インライン

次に、inlines と inline を見ていきましょう。

inlines : inline
        | inlines inline
inline  : chars
        | strong

inline から先に説明します。inline は、「一行」を構成するものを表す規則です。今回の記法では、一行を構成するものは「単なる文字の列」と「強調」の2つになります。

inlines は、inline が1つ以上並んだものを表す規則です。先程 chars で見たパターンですね。

行

次に lines と line です。

lines : line
      | lines line
line  : inlines BR

line は、一行を表す規則です。一行は、inlines、つまり一行を構成するものの列が続いたあとに、BR が続くという規則になっています。BR は、改行1つを表すトークンです（あとで next_token で実装します）。「一行」の定義なので、直感的ですね。1つ注意すべき点は、inlines は必ず何かしらの文字が含まれるので、この規則は「空行（改行しか無い行）」には当てはまらないということです。

lines は、ご多分に漏れず line が1つ以上続いたものを表します。

パラグラフ

お次は paragraph です。

paragraph : lines BR

paragraph は、段落を表す規則です。今回の記法では、段落は、連続した行の並びで表現するのでした。したがって、lines に当てはまれば paragraph という規則にしています。ただし、最後に BR が来る点に注意が必要です。lines は必ず BR で終わる（上記の規則をもう一度確認してみてください）ため、ここにある BR は、「空行」を表すことになります。以下のようなイメージです（↓ が改行を表します）。

あいうえお↓
かきくけこ↓
↓←ココ
さしすせそ↓
...

←ココ と書いてあるところが、この規則の BR に当たる改行です。つまり、空行が空いていたら、そこまでを段落として扱うということです。これは「空行が入ると段落が変わる」という記法の決まりを表しています。

ブロック

終わりに近づいてきました。次は blocks と block です。

blocks : block
       | blocks block

block : paragraph
      | BR

block は、段落、もしくは改行（空行）のことです。これが1つ以上並んだものが blocks になります。なぜ段落だけでなく空行も block になるのかというと、以下のようなケースがあるためです（↓ が改行を表します）。

最初の段落。↓
↓←①
↓←②
次の段落。↑ここに2つ以上空行がある。↓

最初の空行（①）は paragraph の規則の方に当てはまりますが、次の空行（②）はいわば「宙ぶらりん」な状態の空行になってしまいます。このような空行を扱うために、block の規則に空行を入れているのです。

スタート規則

最後はスタート規則です。

top : blocks

シンプルですね！blocks 規則に当てはまれば、その文字列は文法に従っているということになります。

next_token

さて、文法の説明はこれくらいにして、次は next_token の実装を見ていきましょう。おさらいしておくと、next_token は文字列を「トークン」といわれる記号に置き換える役割を持ったメソッドでしたね。今回の文法には、CHAR、DOUBLE_STAR、BR という3種類のトークンが登場するため、それらを返すように実装します。

def next_token
  c = @chars.shift
  if c == '*'
    n = @chars.shift
    if n == '*'
      [:DOUBLE_STAR, nil]
    else
      @chars.unshift(n)
      [:CHAR, c]
    end
  elsif c =~ /\n/
    [:BR, nil]
  elsif c == nil
    [false, nil]
  else
    [:CHAR, c]
  end
end

式のパーサで書いたものと構造はほとんど変わりません。まず @chars（入力された文字列が1文字ずつ入っている配列；コンストラクタで定義します）から文字を1つ取り出します。

取り出した文字が * だと、** である可能性があるので、次の文字も取り出してみて調べます。次の文字も * であれば、めでたく ** を見つけたことになるので、DOUBLE_STAR というトークンを返します。もし次の文字が * でなければ、これは文中にたまたま現れた * であると考えられるので、（取り出してしまった1文字を戻した上で）「単なる文字」のトークン CHAR を返します。また、トークンの値はその文字自体にしておきます。

取り出した文字が改行であった場合は、改行を表す BR のトークンを返します。

取り出した文字が nil であった場合、配列がもう空であることがわかるため、次のトークンが無いことを示す false という種類のトークンを返します。

それ以外であれば、取り出した文字は「単なる文字」であると考えられるため、トークン CHAR を返します。ここでも、トークンの値は取り出した文字自体にします。

next_token についてはこれだけです。簡単ですね。

動作確認

さて、ここまでで一応動くプログラムはできたので、試しに一度パーサを実行してみましょう。ここまで解説したコードを含む以下の内容を、minimini.y というファイル名で保存してください。

class MiniMini
rule
  top : blocks { puts 'ok' }

  blocks : block
         | blocks block

  block : paragraph
        | BR

  paragraph : lines BR

  lines : line
        | lines line
  line  : inlines BR

  inlines : inline
          | inlines inline
  inline  : chars
          | strong
  chars   : CHAR
          | chars CHAR
  strong  : DOUBLE_STAR chars DOUBLE_STAR
end

---- inner

def parse(text)
  @chars = normalize(text).chars
  do_parse
end

def next_token
  c = @chars.shift
  if c == '*'
    n = @chars.shift
    if n == '*'
      [:DOUBLE_STAR, nil]
    else
      @chars.unshift(n)
      [:CHAR, c]
    end
  elsif c =~ /\n/
    [:BR, nil]
  elsif c == nil
    [false, nil]
  else
    [:CHAR, c]
  end
end

def on_error(*args)
  puts 'ng'
end

def normalize(text)
  text.sub(/\n+\z/, '') + "\n\n"
end

---- footer

if $0 == __FILE__
  MiniMini.new.parse($stdin.read)
end

少しだけ、トリックを使っているところがあるので解説します。normalize というメソッドがありますが、これは入力された文字列を解析しやすいように加工するメソッドです。今回は、文字列の末尾は必ず「改行2つ」で終わるように加工しています。こうすることで、paragraph の規則が簡単になるというメリットがあります。

さて、ファイルを保存したら、以下のコマンドを実行して、文法ファイルから Ruby のスクリプトを生成します。

$ racc minimini.y -o minimini.rb
1 shift/reduce conflicts

おや？いままで見たことのないメッセージが出てきましたね。これは、簡単に言えば、適用できる規則が複数見つかった場合に出るメッセージです。ただし、shift/reduce conflicts の場合は、放っておいても問題がないケースも多々あります。今回は問題がないケースなので、これ以上は踏み込まずにそっと無視することにします[1]。

これで minimini.rb というファイルができているはずです。実行してみましょう。

$ ruby ./minimini.rb

ここでプログラムが止まると思うので、ここに解析したい文字列を入力してみてください。試しに、記法の例で出てきた以下の文章を入力してみます。入力が終わったら、最後に ctrl を押しながら D のキーを押してください。

これは最初の段落です。**これは強調です。**

一行以上空けると別の段落になります。(ここでctrl + Dを押す)
ok

ok と出ましたね！これは入力された文字列が文法に従っていることを示しています。色々と入力して遊んでみましょう。

HTMLへの変換

ここまで来たら、あとは HTML へ変換する機能をつければ記法パーサは完成です。「HTML へ変換」と言うと難しそうですが、やることは単純な文字列の加工だけです。それでは実際にやってみましょう。

変換は、各規則のアクションで行います。文法に以下のようにアクションを書き加えてみてください。

class MiniMini
options
  no_result_var
rule
  top : blocks                            { puts val[0] }

  blocks : block
         | blocks block                   { val[0] + val[1] }

  block : paragraph
        | BR                              { '' }

  paragraph : lines BR                    { "<p>#{val[0]}</p>" }

  lines : line
        | lines line                      { val[0] + val[1] }
  line  : inlines BR                      { val[0] }

  inlines : inline
          | inlines inline                { val[0] + val[1] }
  inline  : chars
          | strong
  chars   : CHAR
          | chars CHAR                    { val[0] + val[1] }
  strong  : DOUBLE_STAR chars DOUBLE_STAR { "<strong>#{val[1]}</strong>" }
end

先に、新出の options について説明します（class のすぐ下にあります）。これは、文法の書き方に関するオプションを指定できるものです。options の下、rule より前のところに、適用したいオプションを書きます。

今回は no_result_var というオプションを書いています。このオプションを使うと、各アクションの返り値を result に代入する必要がなくなり、アクションの最後の実行結果がそのままアクションの返り値として扱われるようになります。

つまり、これまで以下のように書いていたのを、

a : b c { result = val[0] + val[1] }

以下のように書くだけで良いということです。

a : b c { val[0] + val[1] }

アクションの中身がシンプルになるので、便利なオプションです。

さて、アクションの解説に戻ります。簡単なところで strong を見てみましょう。

strong : DOUBLE_STAR chars DOUBLE_STAR { "<strong>#{val[1]}</strong>" }

このアクションでは、chars の値（val[1]）を、HTML の<strong> タグで囲んだ文字列を返しています。この規則に当てはまるということは **あいう** のような文字列が現れたということなので、あいう の部分を取り出して <strong>あいう</strong> のような形に変換しているということです。

今度は chars を見てみましょう。

chars   : CHAR
        | chars CHAR                    { val[0] + val[1] }

1つ目の規則にはアクションがありませんね。じつは、アクションを書かないと、デフォルトで { val[0] } と書いたのと同じ扱いになります。したがって、この場合だと CHAR トークンの値が、そのままこの規則の値になります。このようなケースでは記述を減らせて便利です。

2つ目の規則では、chars の値と CHAR の値を + で連結しています。chars の値も CHARの値も文字列のはずなので、+ で連結できます。したがって、最終的には chars の値は、「単なる文字」が続いた文字列になります。

他もアクションもほぼ同様ですので、詳しくは解説しません。paragraph では中身を <p> タグで囲むようにしています。最後に、top で変換結果を表示しています。

これでミニミニ記法パーサは完成です！実際に動作させてみましょう。

実行

いよいよ、完成したパーサを実行してみます。先程の文法の内容を minimini.y に上書きして、いつも通り文法ファイルを変換をします。

$ racc minimini.y -o minimini.rb 
1 shift/reduce conflicts

成功したら、minimini.rb を実行します。今回も記法の例文を入力してみましょう（入力が終わったら ctrl + D を押すのを忘れずに）。

$ ruby ./minimini.rb 
これは最初の段落です。**これは強調です。**

一行以上空けると別の段落になります。
<p>これは最初の段落です。<strong>これは強調です。</strong></p><p>一行以上空けると別の段落になります。</p>

HTML が出力されました！！成功です！ぱちぱちぱち。

せっかくなので、出力結果をブラウザで表示させてみましょう。以下のようにコマンドを実行すると、結果が画面ではなく index.html というファイルに出力されます。

$ ruby ./minimini.rb > index.html
これは最初の段落です。**これは強調です。**

一行以上空けると別の段落になります。
$ # 画面には出力されずに終了する

そうしたら、Webサーバを立ち上げてこの index.html をブラウザで見れるようにします。Webサーバについて知らなくても大丈夫です。以下のコマンドを実行するだけです。

$ ruby -run -e httpd .
[2017-12-05 19:59:01] INFO  WEBrick 1.3.1
[2017-12-05 19:59:01] INFO  ruby 2.4.1 (2017-03-22) [x86_64-darwin17]
[2017-12-05 19:59:01] INFO  WEBrick::HTTPServer#start: pid=54448 port=8080

Ruby のバージョンによって少し表示は違うかもしれませんが、上記のような表示になっていれば成功です。

では、ブラウザを立ち上げて、http://localhost:8080/ というページを開いてみてください。

あああっっっ！！！！文字化け！！うわ〜〜〜〜〜っ！！！

あんまりちゃんとした HTML を書き出していないので当然といえば当然ですね……　文字コードの設定ができるブラウザなら、UTF-8 を選んでみてください（Safari なら「表示」＞「テキストエンコーディング」＞「Unicode (UTF-8)」でできます）。

すごい！これで自分で勝手に作った記法がブラウザで表示できちゃいました。感動です。

まとめ

今回は、非常にコンパクトな記法を持つ「ミニミニ記法」のパーサを作ってみました。実際に HTML を書き出して、（文字化けしながらも）ブラウザで表示することまでできました。ミニミニ記法はシンプルですが、基本はおさえてありますので、余力のある方はここからさらに独自の記法を追加してみてください。inline の規則を追加するところから始めるのがおすすめです。あとは、文字化けしないようにちゃんとした HTML[2] を書き出すようにするのも良いですね。

さて、今回で基本的な記法パーサは完成しました。次回は、もう少し発展的な記法と、記法パーサを開発する上でのより実践的なテクニックについてご紹介したいと思います。お楽しみに！

  1. この記事では、わかりやすさを優先するために、この話の前提となる「シフト」や「還元」の話はあまり詳しく解説してきませんでした。そのあたりの概念も含めて詳しく知りたい方は、速習yaccなどをご参考にしてください。 ↩︎

  2. 文字化けするのは、HTML 中に文字コードの指定が無いためです。HTML5でマークアップしてみよう－HTML5リファレンスなどを参考に、書き出す HTML を改良してみましょう。 ↩︎