top page > computer > haskell > web_lecture > for_programmer > nml.html
更新日:
文責: 重城良国

NML(Nano Markup Language): 構文解析

Nml0.hs

はじめに

XMLをシンプルにしたNMLというマークアップ言語についてデコーダ、エンコーダを書く。

仕様

NML(Nano Markup Language)を考える。NMLの開きタグは<hoge>で閉じタグは</hoge>だ。タグに囲まれた文字列は子要素を持たないタグとして扱う。

これらを同じものとして扱う。

字句解析

文字列をトークン列にする。

型Token

開きタグ、閉じタグ、文字列の3種類のトークンがある。

data Token = Open String | Close String | Text String deriving Show

関数token

関数tokenはトークンをひとつ切り出し残りの文字列とともに返す。空文字列やタグが適切に閉じていないときにはNothingを返す。

token :: String -> Maybe (Token, String)
token "" = Nothing
token ('<' : '/' : s) = tag Close s
token ('<' : s) = tag Open s
token s | all isSpace tx = token r
| otherwise = Just (Text tx, r)
where (tx, r) = span (/= '<') s

先頭が</ならば次に定義する関数tagで閉じタグを、<ならば開きタグをきりだす。それ以外では<までをテキストとしてとる。ただしテキストが空白文字だけから成るときには次のトークンをきりだす。

タグの切り出し

タグをきりだす関数には最初の</や<を落とした文字列がわたされる。タグは>で終わる。関数tagの第1引数にOpenをわたすかCloseをわたすかで開きタグと閉じタグのどちらかが結果となる。

tag :: (String -> Token) -> String -> Maybe (Token, String)
tag f s = case span (/= '>') s of
(tg, _ : r) -> Just (f tg, r)
_ -> Nothing

_ -> Nothingの行は対応する>のない<以降が無視されることを示す。

関数Data.Char.isSpaceを使うのでモジュールの先頭に

import Data.Char

を追加する。

試してみる

% ghci Nml.hs
*Main> token "<hello>world</hello>"
Just (Open "hello","world<hello>")

関数tokenはトークンをひとつきりだす。トークン列をとるにはData.Listモジュールのunfoldrを使う。

*Main> :m + Data.List
*Main Data.List> unfoldr token "<hello>world</hello>"
[Open "hello",Text "world",Close "hello"]

構文解析

トークン列を樹構造に解析する関数を作る。

型はData.Tree.Treeを使って

type Nml = Tree String

とする。モジュールの先頭に

import Data.Tree

をおく。

関数parse

相互に再帰する関数parseとparseLを定義する。

parse :: [Token] -> Maybe (Nml, [Token])
parse (Open tg : ts) = case parseL ts of
(ns, Close tg' : r) | tg == tg' -> Just (Node tg ns, r)
_ -> Nothing
parse (Text tx : ts) = Just (Node tx [], ts)
parse _ = Nothing

関数parseは樹をひとつ読みこむ。Openトークンに対しては続くトークン列から複数の樹を読みこむ。対応するCloseトークンがあれば読みこんだ複数の樹を子とする樹を作成する。Textトークンは子要素をもたない樹に解析される。

関数parseL

parseL :: [Token] -> ([Nml], [Token])
parseL ts = flip (maybe ([], ts)) (parse ts) $ \(n, r) ->
let (ns, r') = parseL r in (n : ns, r')

関数parseで樹を読みこめれば、続く複数の樹を読みこみ(parseL r)、それらをリストにまとめる(n : ns)。樹が読みこめなければ空リストと、残りとしてもともとのトークン列を返す([], ts)。

関数nml

字句解析器と構文解析器を関数nmlにまとめる。

nml :: String -> Maybe Nml
nml = maybe Nothing (Just . fst) . parse . unfoldr token

Data.List.unfoldrを使っているのでモジュールの先頭に

import Data.List

を追加する。

モジュールNml

外から使うのは型Nmlと関数nmlなので

module Nml (Nml, nml) where

をファイルの先頭に置く。

*Main> :reload
*Nml> :m Nml
Prelude Nml> nml "<hello>world</hello>"
Just (Node {rootLabel = "hello", subForest = [Node {rootLabel = "world", subForest = []}]})

まとめ

XMLライクな構造のデコーダを作成した。

「構文: 代数的データ型のエクスポート」へもどる 「NML(2): 他の型への変換」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics