Parsecライブラリでパーサをつくる

ちょっとパーサー・コンビネータについて調べる機会があって、その流れで有名なHaskellのライブラリParsecについての紹介テキスト “Parsing expressions and statements”（Haskell.org）を読んでみました。以下に訳出。ただしかなり適当。ところで「左右ファクタリング」（left/right factoring）って何ですか??

　　　　　＊　＊　＊

式と文をパースする

ここではParsecライブラリを使って、式と文を持つちょっとした構文をパースしてみましょう。主な目的はmakeTokenParserとbuildExpressionParserという2つの関数を紹介することですが、これらは一般的な用途の多くをカバーしたものになっています。

（ParsecライブラリはHaskellプラットフォームに同梱されているほか、Parsec単体でも利用が可能です。）

ここでは下記のモジュールを使用します：

import Control.Applicative((<*))
import Text.Parsec
import Text.Parsec.String
import Text.Parsec.Expr
import Text.Parsec.Token
import Text.Parsec.Language

1 サンプルとなる構文

以下が式〔expression〕の構文規則です：

expr  ::= var | const | ( expr ) | unop expr | expr duop expr
var   ::= letter { letter | digit }*
const ::= true | false
unop  ::= ~
duop  ::= & | =

演算子の優先順序は高い方から並べると次のようになります：~, &, =。二つの二項演算子はいずれも左結合です。

続いて以下が文〔statement〕の構文規則です：

stmt ::= nop | var := expr | if expr then stmt else stmt fi | while expr do stmt od
       | stmt { ; stmt }+

これらの規則に加えて、ブロックコメントも可能です。{- これはコメントです -}

これらの構文はパースされて内部表現（抽象構文木）に変換されます。（利用目的によっては、内部表現についてはスキップして一気に評価やコード生成といった事項に進むのですが……今回は内部表現についてしっかり見ていきましょう！）以下が内部表現です：

data Expr = Var String | Con Bool | Uno Unop Expr | Duo Duop Expr Expr
    deriving Show
data Unop = Not deriving Show
data Duop = And | Iff deriving Show
data Stmt = Nop | String := Expr | If Expr Stmt Stmt | While Expr Stmt
          | Seq [Stmt]
    deriving Show

2 サンプルのパーサー

段取りはこうです。まず、コメントや文字に関するルール（何を識別子とみなし、何を演算子とみなすか）、予約語、予約された演算子について仕様を決めるためレコード*1のフィールドに値を設定します。続いて、このレコードをmakeTokenParserに与えて、ユーティリティ・パーサーからなるレコードを得ます。このパーサーによって私たちは（文字レベルではなく）トークンのレベルで作業を行うことが可能になります。式パーサーはbuildExpressionParserの助けを借りて作成します。最後に、文パーサーを再帰下降パーサーとして記述します。

2.1 シンボルを定義する

LanguageDefがはじめに作成すべきレコード型の名前です。いくつものプリセットが提供されていて、それらの中から1つを選んでいくつかのフィールドだけカスタマイズして使用します。ミニマリストなプリセットはemptyDefです。これを下記のように変更します：

def = emptyDef{ commentStart = "{-"
              , commentEnd = "-}"
              , identStart = letter
              , identLetter = alphaNum
              , opStart = oneOf "~&=:"
              , opLetter = oneOf "~&=:"
              , reservedOpNames = ["~", "&", "=", ":="]
              , reservedNames = ["true", "false", "nop",
                                 "if", "then", "else", "fi",
                                 "while", "do", "od"]
              }

2.2 トークン・パーサーを作成する

上述のレコードをmakeTokenParser関数に渡すと、TokenParserという型のレコードが返されます。このレコードのフィールドたちは、いずれも小さなパーサーです。これらはさまざまなトークン（識別子、演算子、予約されたもの、いろいろな形のカッコ）を読み取って返すとともに、あらかじめ設定した定義に基づきコメントをスキップします。さらにパーサによってトークンのあとに続くホワイトスペースは無視されます。これらを使うことで、私たちはトークンレベルで、ホワイトスペースについて心配することなしに、式パーサーと文パーサーを組み立てることができます。ただし1つ注意：これらのパーサーはパース対象の先頭にあるホワイトスペースは無視してくれないので、私たち自身で始末してあげる必要があります。とはいえ、これはとても簡単なことですが。ちなみに私たちがここで使用するパーサーは提供されている多くのうちのほんのわずかです。先ほど定義したdefにmakeTokenParser関数を適用し、レコードのパターンマッチを使って必要なパーサだけつまみ出しましょう：

TokenParser{ parens = m_parens
           , identifier = m_identifier
           , reservedOp = m_reservedOp
           , reserved = m_reserved
           , semiSep1 = m_semiSep1
           , whiteSpace = m_whiteSpace } = makeTokenParser def

これらのパーサーの概要は以下のとおり：

m_parens: m_parens p
開きカッコをパースし、続いてpを実行します。そして閉じカッコをパースしたあと、pが返したものを返します。
m_identifier: 識別子を読み取って返します。識別子が予約語と衝突しないかどうかチェックします。
m_reservedOp: 例えば以下のようにすると：
m_reservedOp ":="
次のトークンが:=という予約された演算子であるかどうかチェックします。
m_reserved: 例えば以下のようにすると：
m_reserved "od"
次のトークンがodという予約語であるかどうかをチェックします。
m_semiSep1: m_semiSep1 p
セミコロンで分割された1つもしくはそれ以上のpの連続を読み取って返します。
m_whiteSpace: ホワイトスペースを無視して先に進みます。

レコードのフィールドとして提供される上述のパーサーやそれ以外のパーサーについても調べてみてください。どれもみんな便利にできています。

2.3 式パーサー

式パーサーはbuildExpressionParser関数から得られます。自分たちで再帰下降パーサーをつくり込んだり、左右ファクタリング〔left/right-factoring〕*2を実行したりする必要はありません。

exprparser :: Parser Expr
exprparser = buildExpressionParser table term <?> "expression"
table = [ [Prefix (m_reservedOp "~" >> return (Uno Not))]
        , [Infix (m_reservedOp "&" >> return (Duo And)) AssocLeft]
        , [Infix (m_reservedOp "=" >> return (Duo Iff)) AssocLeft]
        ]
term = m_parens exprparser
       <|> fmap Var m_identifier
       <|> (m_reserved "true" >> return (Con True))
       <|> (m_reserved "false" >> return (Con False))

ここでは演算子の優先順序（tableリストにおける並び順に基づく）、結合規則、それらの演算子が意味するアクションと、カッコで囲まれた式も含む不可分の項をパースする方法（ここでのみ再帰的下降が登場しますが、まあ些末なものです）を定義しています。いくつかの演算子を同じ優先順序に置くこともできますが、ここでは取り上げません。tableを定義するための一般的なフォーマットについては説明は難しいですが、こうして例示したりコピーして使用するのは容易です。

2.4 文パーサー

文パーサーはセミコロンで区切られたリストに注意しつつ（m_semiSep1を使えば簡単です）、便利なトークン・パーサーと式パーサーを使って、再帰的下降で組み立てていきます。先頭のホワイトスペースをスキップしなくてはならない点を忘れてはなりません。

mainparser :: Parser Stmt
mainparser = m_whiteSpace >> stmtparser <* eof
    where
      stmtparser :: Parser Stmt
      stmtparser = fmap Seq (m_semiSep1 stmt1)
      stmt1 = (m_reserved "nop" >> return Nop)
              <|> do { v <- m_identifier
                     ; m_reservedOp ":="
                     ; e <- exprparser
                     ; return (v := e)
                     }
              <|> do { m_reserved "if"
                     ; b <- exprparser
                     ; m_reserved "then"
                     ; p <- stmtparser
                     ; m_reserved "else"
                     ; q <- stmtparser
                     ; m_reserved "fi"
                     ; return (If b p q)
                     }
              <|> do { m_reserved "while"
                     ; b <- exprparser
                     ; m_reserved "do"
                     ; p <- stmtparser
                     ; m_reserved "od"
                     ; return (While b p)
                     }

3 試しに使ってみる

最後に、ちょっとしたテストのためのコードを書いてみましょう。この関数は文字列のパラメータをパースして、パース・エラーかさもなくばパースしたコードの実行結果を返します。

play :: String -> IO ()
play inp = case parse mainparser "" inp of
             { Left err -> print err
             ; Right ans -> print ans
             }

　　　　　＊　＊　＊

以上は、Haskell.orgで公開されている記事“Parsing expressions and statements”の訳出。

*1:Haskellの概念。JavaやC#で言えば所定のフィールドを持つクラスのインスタンス、JavaScriptでは所定のプロパティを持つオブジェクトに該当しますが、Haskellにおける他の概念同様イミュータブル──つまり不変です。

*2:これって一体？

M12i.

学術書・マンガ・アニメ・映画の消費活動とプログラミングについて