パーサコンビネータで構文解析をより身近なものにする

　こんにちは、広告システム開発部の菅原です。

　今回は構文解析のお話です。構文解析は、コンパイラ、自然言語処理（テキストマイニング）、AST（抽象構文木）、AltJS（Alternatives to Javascript） などのベースとなる重要な技術の一つです。本記事では、実例としてコンパイラを交えて説明しつつ、パーサコンビネータを使って簡単に構文解析を行えることを紹介していきます。

構文解析が使われている技術について

　文字列が関わる様々な技術の根底に、構文解析は関与しています。構文解析がどのように関わっているか、その実例としてコンパイラの仕組みを簡単に見ていきます。

　コンパイラ（Compiler）とは、人間が理解しやすい高級言語で記述されたプログラムを、ハードウェア寄りの低級言語（機械語もしくは中間言語）に変換するプログラム1です。

　一言で「変換」と表記しましたが、このプロセスは、大きく分けて次の四つの機構から成ります。

  1. 字句解析（Lexical Analysis）
    • ソースコードを読み込んで、トークン（字句）に分解する工程
  2. 構文解析（Syntactic Analysis）
    • 分解したトークン列をもとに構文木を構築する工程
  3. 最適化（Optimization）
    • 構築した構文木を効率の良いものに変換する工程
  4. コード生成（Code Generation）
    • 構文木からオブジェクトコードを生成する工程

構文解析と構文解析器

　コンパイラの場合は、二番目の機構に構文解析が含まれています。構文解析を行う機構のことを「構文解析器（Parser）」と呼びます。後述するパーサジェネレータ（パーサコンビネータ）のライブラリの最近の実装では、字句解析器2と構文解析器の機構も併せて持っていることが珍しくなく、トークン分割から構文木構築までカバーできるものがほとんどです。

パーサジェネレータ（パーサコンビネータ）

　構文解析器を生成するプログラムを「パーサジェネレータ（Parser Generator）」と言います。パーサジェネレータそのものは構文解析器ではありません。また、パーサジェネレータの中でも、演算子と関数を組み合わせて構文解析器を生成できるプログラムを「パーサコンビネータ（Parser Combinator）」と呼びます。

構文解析器の手続き

　構文解析器では、構文木に対する手続きによって、トップダウン構文解析とボトムアップ構文解析の二つに大分類されます。トップダウン構文解析は、最上位の根から最下位の葉へ向かって書き換えていく手続きであり、一方のボトムアップ構文解析では、最下位の葉から最上位の根に向かって書き換えていく手続きです。

トップダウン構文解析とボトムアップ構文解析

　トップダウン構文解析器とボトムアップ構文解析器には、主たる構文解析法が下表のように分類されます。

構文解析法分類される解析器
LL parser
Recursive descent parser
Packrat parser		トップダウン構文解析器
LR parser（SLR parser / LALR parser / GLR parser）
Earley parser
Cocke-Younger-Kasami parser		ボトムアップ構文解析器

パーサコンビネータを使うための準備

　構文解析の簡単な概要について把握できたところで、パーサコンビネータを使う準備を整えていきます。実行環境は、macOS Sierra 10.12.4 で、パッケージ管理システムは、Homebrew を使い、コーディングには Sublime Text 3 を使う前提です。使用する言語は、パーサコンビネータのライブラリがあれば、どの言語でも構わないのですが、文字列操作に優れた Haskell を選択します。

Haskell のインストール

　まず始めに、Homebrew で Haskell（Glasgow Haskell Compiler） をインストールします。

$ brew install ghc

Cabal-install のインストール

　続いて、Haskell のパッケージ管理システム cabal をインストールします（Homebrew でのパッケージ名は、cabal-install になります）。

$ brew install cabal-install

　インストールが完了したら、cabal のパッケージリストの更新を行います。

$ cabal update

　パッケージリストが最新化されたところで、新しいバージョンの cabal-install をインストールします。

$ cabal install --global cabal-install

hsdev のインストール

　cabal-install を更新した後、Sublime Text 3 上でコード補完等を行ってくれるパッケージ hsdev をインストールします。

$ cabal install hsdev

SublimeHaskell の導入

　Sublime Text 3 上で、Shift+Controll+P のショートカットキーを押してコマンドパレットを起動させます。この状態で「install」と入力すると、ドロップダウンの予測一覧が表示されますので、その中の「Package Control:Install Pacakge」の項目にフォーカスが当たった状態で「Enter」キーを押下します。すると、パッケージ検索パレットに切り替わるので、「SublimeHaskell」を検索してインストールします。

SublimeHaskell の設定

　メニューバーから、Preferences > Package Settings > SublimeHaskell の順にメニューを辿って行き、「Settings - User」の項目を押下します。下記のように、hsdev のパスを記述し、Haskell のコマンドオプションを警告の表示・非表示を自分の好みで設定します。コマンドオプションについては、こちらが参考になります。

{
    "enable_hdevtools": false,
    "auto_completion_popup": true,
    "add_to_PATH": [
        "~/.cabal/bin/hsdev"
    ],
    "ghc_opts":
    [
        "-fno-warn-type-defaults",
        "-fno-warn-missing-signatures",
        "-fno-warn-incomplete-patterns",
        "-fwarn-unused-binds"
    ]
}

パーサコンビネータを使ってみる

　Haskell には、Parsec という LL parse の非常に優れたパーサコンビネータライブラリがあります。このライブラリを使って四則演算ができる簡易計算機を作ってみようと思います。

インタラクティブモードでソースコードを実行する

　簡易計算機を作る前にインタラクティブモードでソースコードを読み込んで実行する手順を示します。 Haskell でプログラミング入門恒例の hello world を書いて hello.hs というファイル名で保存します。

main = do
    print "hello world"

　このソースコードを保存した場所に cd コマンドで移動した後、ghci コマンドでインタラクティブモードにしてから、「:load hello.hs」でソースコードを読み込み、main で実行します。

$ ghci
Prelude> :load helo.hs
*Main> main
"hello world"

数値を読み取れるようにする

　まずは、数値を読み取れるようにしてみます。1文字以上読み取りたいので many1 を、その上で数値を読み取るので digit の関数を組み合わせて使います。正規表現だと「[0-9]+」と同じようなイメージで考えてください。しかし、このままの構文解析器だと文字列出力になってしまうので、Int 型に変換します。

import Text.Parsec

-- bind での書き方
number = many1 digit >>= \x -> return (read x :: Int)
-- do で bind する書き方
number2 = do
    x <- many1 digit
    return (read x :: Int)

main = do
    parseTest number "123"  -- 123
    parseTest number2 "456" -- 456

足し算をできるようにする

　数値を読み取れるようになったので、今度は足し算をできるようにしてみましょう。足し算だけの計算式は、「a+b+…+z」の書式で表せることから、「数値」と「プラス記号と数値のセットの繰り返し」であることがわかるので、0回以上の繰り返しを表す many 関数と、数値を読み取るための自作関数 number を組み合わせます。そして、プラス記号が計算時には不要になるため、アプリカティブの「*>」（右辺のみ残す）を使用します。foldl 関数は、ここでは計算式の項を左から順に畳み込むために使用します。

import Text.Parsec
import Control.Applicative ((*>))

add = do
    a <- number
    b <- many $ (char '+' *> number >>= \y -> return (+ y))
    return $ foldl (\x f -> f x) a b

number = do
    x <- many1 digit
    return (read x :: Int)

main = do
    parseTest number "123" -- 123
    parseTest add "1+2"    -- 3
    parseTest add "1+2+4"  -- 7

引き算もできるようにする

　足し算だけでなく引き算もできるようにしてみます。引き算そのものをできるようにするのは特に難しくありませんので、足し算と同じような内容で構文解析器を組んで行きます。ただし、Haskell の仕様上、マイナス記号が単項演算子として扱われてしまうため、subtract 関数を使うことで引き算を実現します。なお、足し算と引き算の演算優先度は同じなので、足し算と引き算の両方を演算できるようにするためには、選択「<|>」を使います。

import Text.Parsec
import Control.Applicative ((*>))

expr = do
    a <- number
    b <- many $
            (char '+' *> number >>= \y -> return (+ y))
        <|> (char '-' *> number >>= \y -> return (subtract y))
    return $ foldl (\x f -> f x) a b

number = do
    x <- many1 digit
    return (read x :: Int)

main = do
    parseTest number "123" -- 123
    parseTest expr "1+2"   -- 3
    parseTest expr "3-1"   -- 2
    parseTest expr "2+3-1" -- 4

さらに掛け算と割り算もできるようにする

　掛け算と割り算もできるようにしてみましょう。これらの計算は、足し算・引き算よりも演算の優先度が高いので、正しく計算するためには、同じ関数 expr の中で選択を使うことができません。そのため、掛け算と割り算用の関数 term を用意します。

import Text.Parsec
import Control.Applicative ((*>))

eval a b = foldl (\x f -> f x) <$> a <*> b

expr = eval term $ many $
            (char '+' *> term >>= \y -> return (+ y))
        <|> (char '-' *> term >>= \y -> return (subtract y))

term = eval number $ many $
            (char '*' *> number >>= \y -> return (* y))
        <|> (char '/' *> number >>= \y -> return (`div` y))

number = do
    x <- many1 digit
    return (read x :: Int)

main = do
    parseTest number "123"     -- 123
    parseTest expr "2+4/2-1*3" -- 1

四則演算ができる簡易計算機として完成させる

　四則演算ができるようになりましたが、これだけでは不完全です。計算式の空白があっても正しく計算できるように spaces 関数、アプリカティブを使いこなしてパーレン内の項を優先して計算できるようにした factor 関数を作ります。

import Text.Parsec
import Control.Applicative ((<$>), (<*>), (*>), (<*))

eval a b = foldl (\x f -> f x) <$> a <*> b

expr = eval term $ many $
            (char '+' *> term >>= \y -> return (+ y))
        <|> (char '-' *> term >>= \y -> return (subtract y))

term = eval factor $ many $
            (char '*' *> factor >>= \y -> return (* y))
        <|> (char '/' *> factor >>= \y -> return (`div` y))

factor = spaces *> (char '(' *> expr <* char ')' <|> number) <* spaces

number = do
    x <- many1 digit
    return (read x :: Int)

main = do
    parseTest number "123"
    parseTest expr   "123"
    parseTest expr   "1 + 20 + 300"      -- 321
    parseTest expr   "100 - 20 - 3"      -- 77
    parseTest expr   "3 * 60 + 4 / 2"    -- 182
    parseTest expr   "3 * 30 - 50 / 2"   -- 65
    parseTest expr   "3 * (60 + 4) / 2"  -- 96
    parseTest expr   "3 * (30 - 50) / 2" -- -30

Haskell 以外の言語のパーサコンビネータ

　Haskell 以外のプログラミング言語のパーサコンビネータライブラリの一例を紹介します。なお、ここに挙げた以外もパーサコンビネータの実装はありますので、下表のライブラリが特別良いというわけではありません。

言語名ライブラリ名とリンク
PHPloco
JavascriptEsprima
PythonParsec.py
Rubyrsec
Javajparsec
Gogoparsec
Scalascala.util.parsing.combinator.Parsers
ElixirCombine
C#Sprache
C++boost Spirit
Visual BasicVBParserCombinator

最後に

　たった数十行程度で四則演算が出来る計算機を作成できたことから、パーサコンビネータを使うと簡単に構文解析を行えることがわかるかと思います。本記事では紹介していませんが、この簡単さ具合で、テキストマイニングや抽象構文木などもより簡単にすることができます。

　なお、本記事で作成した簡易計算機を発展させていくと、最終的には、プログラムのコンパイラにも、AltJS のように入力したソースコードから Javascript を出力するコンパイラにもすることができます。俺様プログラミング言語を作る夢があるなら、実現も不可能ではありません。

  1. コンパイラはいくつかの種類があり、C 言語や C++ などの言語で、機械語へと直接一括コンパイルするコンパイラを「ネイティブコンパイラ」、C# や Java のなどの言語で、中間言語にコンパイルするコンパイラを「Ahead-Of-Time コンパイラ」と言います（中間言語から機械語にコンパイルするコンパイラは「Just-In-Time コンパイラ」と呼びます）。 ↩︎

  2. 字句解析を行う機構を「字句解析器（Lexical Analyzer）」と呼びます。 ↩︎