前のエントリー で簡易S式パーサを re.Scanner で作ったのですが、まぁ個人的にまとめておいたほうが後々使えるだろう、ということでライブラリにまとめました。ダンパもついているので、S式の読み込みの他、PythonオブジェクトをS式で出力することができます。

実装には引き続き re.Scanner を活用しています。おかげで短い行数でキレイにかけているのではないかと。

ダウンロード

simplesexp.py

ソースはこんな感じ(テストのぞく)。

import re, sys
from unicodedata import east_asian_width

try:
  from re import Scanner
except ImportError:
  from sre import Scanner

class ParseError(StandardError): pass

class Ident(unicode):
  def __repr__(self):
    return "Ident(%s)"%unicode.__repr__(self)

class Symbol(unicode):
  def __repr__(self):
    return "Symbol(%s)"%unicode.__repr__(self)

class Pair(list): 
  def __repr__(self):
    return "Pair(%s)"%list.__repr__(self)

class Token(object):
  def __init__(self, value, pos):
    self.value = value
    self.pos   = pos
  def __repr__(self):
    return repr(self.value)

class Binding(object):
  def __init__(self, dct):
    self.dct = dict(((k, k.__class__), v) for k,v in dct.iteritems())
  __contains__ = lambda self, key: (key, key.__class__) in self.dct
  __getitem__  = lambda self,key:  self.dct[(key, key.__class__)]

default_binding = {"#t":True, "true":True, "#f":False, "false":False, "nil":None, "dict":Ident(u'alist->hash-table')}

class Reader(object):
  PAREN = {"]":"[", ")":"("}
  def __init__(self, binding=None, symbol_marker="'", use_dict=True):
    self.binding = binding or default_binding
    self.symbol_marker = symbol_marker
    self.use_dict = use_dict

  def read(self, value):
    self.result = []
    self.paren_stack = []
    self.source = value
    self.pos = 0
    self.scanner = Scanner([
      (r"\s+", self("skip")),
      (r";[^\n]*\n", self("skip")),
      (r""""(((?<=\\)")|[^"])*((?<!\\)")""", self("str")),
      (r"(\(|\[)", self("open")),
      (r"(\)|\])", self("close")),
      (r"(([\d]+|(((\d+)?\.[\d]+)|([\d]+\.)))e[\+\-]?[\d]+)|(((\d+)?\.[\d]+)|([\d]+\.))", self("number")),
      (r"\-?((0x[\da-f]+)|(0[0-7]+)|([1-9][\d]*)|0)[l]?", self("number")),
      (r"""%s([^\(\[\)\]\s"]+)"""%self.symbol_marker, self("symbol")),
      (r"""([^\(\[\)\]\s"]+)""", self("ident")),
      (r"""".*""", self("unterm_str")),
      (r".*", self("unknown_token"))
    ], re.M|re.S|re.I)
    self.scanner.scan(self.source)
    if self.paren_stack:
      self.raise_error("missing closing parenthesis.")
    return self.parse(self.result)

  def append(self, v):
    self.last().append(Token(v, self.pos))

  def __call__(self, name):
    def _(scanner, s):
      self.pos += len(s)
      return getattr(self, name)(s)
    return _

  def unknown_token(self,s): self.raise_error("unknown token: %s"%s)
  def skip(self, _): pass
  def open(self, s):
      new_lst = []
      self.last().append(new_lst)
      self.paren_stack.append([s, new_lst])
  def close(self, s):
      if not self.paren_stack:
        self.raise_error("missing opening parenthesis.")
      if self.PAREN[s] != self.paren_stack.pop()[0]:
        self.raise_error("missing closing parenthesis.")
  def str(self, s): self.append(eval('u""'+s+'""'))
  def unterm_str(self, s): self.raise_error("unterminated string literal.")
  def number(self, s): self.append(eval(s))
  def symbol(self, s): self.append(Symbol(s[1:]))
  def ident(self, s): 
    if s in self.binding:
      self.append(self.binding[s])
    else:
      self.append(Ident(s))

  def last(self):
    if self.paren_stack:
      return self.paren_stack[-1][1]
    else:
      return self.result

  def parse(self, rs):
    def is_ident(value, expected):
      return getattr(value,"value", None) == Ident(expected)
    def is_pair(rs):
      return getattr(rs, "__len__", lambda :0)()==3 and is_ident(rs[1], u".")

    if isinstance(rs, list):
      if not len(rs):
        return []
      elif self.use_dict and is_ident(rs[0], u"alist->hash-table"):
        if len(rs) != 2:
          self.raise_error("alist->hash-table: expected 1 arguments, got %d."%(len(rs)-1), rs[0].pos)
        if not all(is_pair(a) for a in rs[1]):
          self.raise_error("alist->hash-table: aruguments must be alist", rs[0].pos)
        return dict((self.parse(i[0]), self.parse(i[2])) for i in rs[1])
      elif len(rs)!=3 and any(is_ident(t, u".") for t in rs):
        self.raise_error('illegal use of "."', rs[0].pos)
      elif is_pair(rs):
        parsed = self.parse(rs[2])
        if not isinstance(rs[2], list):
          return Pair([rs[0].value, parsed])
        if isinstance(parsed, Pair):
          return Pair([rs[0].value, parsed])
        elif isinstance(parsed, list):
          return [rs[0].value]+parsed
        else:
          return [rs[0].value, parsed]
      else:
        return map(self.parse, rs)
    else:
      return rs.value

  def raise_error(self, msg="parse error", pos=None, range=3):
    pos = pos or self.pos
    lines = self.source.split("\n")
    curline = self.source[:pos].count("\n")
    linepos = pos - len("\n".join(lines[:curline]))
    buf = ["\n"]
    for i in xrange(max(0, curline-range), curline+1):
      buf.append("% 5d: %s"%(i+1, lines[i]))
    width = 7 + sum(east_asian_width(c) == 'W' and 2 or 1 for c in unicode(lines[i]))
    buf.append("%s~"%(" "*width))
    buf.append("line %d, %d: %s"%(curline+1,linepos, msg))
    raise ParseError(("\n".join(buf)).encode(sys.stderr.encoding))

class Dumper(object):
  def __init__(self, binding=None ,symbol_marker="'"):
    binding = binding or default_binding
    self.binding = Binding(dict(zip(binding.values(), binding)))
    self.symbol_marker = symbol_marker

  def dump(self, obj):
    result = self.to_sexp(obj, [])
    if isinstance(result, list) and len(result) and result[0]=="(":
      result = result[1:-1]
    return u" ".join(result)

  def to_sexp(self, obj, result):
    ap = result.append
    tos = lambda v: self.to_sexp(v, result)
    if isinstance(obj, Pair):
      ap("(")
      tos(obj[0])
      ap(" . ")
      tos(obj[1])
      ap(")")
    elif isinstance(obj, (tuple, list)):
      ap("(")
      map(tos, obj)
      ap(")")
    else:
      if isinstance(obj, dict):
        ap("( alist->hash-table ")
        tos([(k, Ident(u"."), v) for k,v in obj.items()])
        ap(" ) ")
      elif obj in self.binding:
        ap(unicode(Ident(self.binding[obj])))
      elif isinstance(obj, Symbol):
        ap(u"'%s"%unicode(obj))
      elif isinstance(obj, (Ident,int, float, long)):
        ap(unicode(obj))
      else:
        s = unicode(repr(obj)).decode("unicode_escape")
        m = re.match(r"""^[u|r]?["|'](.*)["|']$""", s, re.M|re.S)
        if m:
          s = m.group(1)
        ap("\"%s\""%s.replace('"','\\"').replace("\\'","'"))
    return result

dumper = Dumper()
read = Reader().read
dump = dumper.dump

概要

特徴は

  • 辞書を定義できる
  • ドット対に対応
  • 識別子に対して、任意のバインディングを指定できる
  • わりとちゃんとエラー表示される
  • シンボル表記、数値表記(python表記)に対応

といった当たりでしょうか。具体的にはテストコードを見てもらうと分かるかと。

(あああ hoge->fuga123 (1 . (2 . 3)) "hoge\\"hoge" ;comment2 
foo "aaa" #t <= 'foo 
"hogehoge
foo
" (5 . (6 .()))
)
(dict (
  ("いいい" .
    (alist->hash-table (
      ("a-1" . "vvv")
      ("a-2" . (
        hoge foo bar 
      ))
    )))
))
(10 1L -45 010 0x10 -10 -0x10 3.14 10. .001 1e100 3.14e-10 0e0)
; comment3 ()(

""")

という感じのS式が

[
  [Ident(u'あああ'), Ident(u'hoge->fuga123'), Pair([1, Pair([2, 3])]), u'hoge"hoge',
  Ident(u'foo'), u'aaa', True, Ident(u'<='), Symbol(u'foo'),
  u'hogehoge\nfoo\n', [5,6]],
  {u'いいい': 
    {u'a-1': u'vvv', 
    u'a-2': [Ident(u'hoge'), Ident(u'foo'), Ident(u'bar')]}},
  [10, 1L, -45, 010, 0x10, -10, -0x10, 3.14, 10., .001, 1e100, 3.14e-10, 0e0]
]

となります。 IdentSymbol はunicodeのサブクラス、 Pair はリストのサブクラスになっているので、違和感なく使えると思います。

また、 alist->hash-table で辞書が作れます。デフォルトで dictalist->hash-table をバインドしてますので、 dict でも辞書が作れます。この機能はオンオフ切り替えも可能です。

その他、 #tTrue などSchemeっぽくデフォルトバインディングが用意してあります。もちろん、バインディングは変更可能ですのでCLっぽくもできます。


と、こんな感じです。一番便利なのはやっぱり辞書ですかねえ。なので、YAML,JSONで書いてる設定ファイルをS式で置き換え・・・なんてことができるかもしれません。


Rubyの StringScanner は個人的にかなり好きなモジュールで、Rubyでちょっとしたパーサなどを書くときに重宝しています。

一方、Pythonにはexperimentalながら re.Scanner というクラスがあります( >= 2.4 )。experimentalなのでマニュアルにはのっていませんが。この re.Scanner はかなりシンプルなんですが典型的な StringScanner の使い方の範疇では、こちらのほうがキレイに書けるような気がします。

re.Scanner の使い方

使い方は非常に簡単で

  • (regex, action) のリストを渡してScannerオブジェクトを作成

    • action は(scanner, string_matched) => stringな関数、Noneを返せば結果は無視される。
  • scanメソッドでスキャン。結果が配列で返ってくる

といった感じ。関数を渡すので、 StringScanner のようなwhileループを作る必要がなく、キレイにまとまります。

例:S式パーサ

re.Scanner は簡単、ということでS式パーサでも。トークナイズ+αな処理をするので、 action をインスタンスメソッドにして状態を保存することにします。

目標は

  • 数値(っぽいもの)、文字列、シンボルが使える
  • シンボルのみ、新たにクラスを定義して(unicodeのサブクラス)それにマップ。それ以外は組み込み型に。
  • パースエラーも分かりやすく
  • 結果はPythonのリストorオブジェクトとして返る

import re, sys
from unicodedata import east_asian_width

try:
  from re import Scanner
except ImportError:
  from sre import Scanner

class ParseError(StandardError): pass

class Symbol(unicode):
  def __repr__(self):
    return "Symbol(%s)"%unicode.__repr__(self)

class TokenProcessor(object):
  PAREN = {"]":"[", ")":"("}
  def __init__(self, value):
    self.result = []
    self.append = self.result.append
    self.string = value
    self.paren_stack = []
    self.pos = 0

  def __call__(self, name):
    def _(*a):
      self.before(*a)
      return getattr(self, name)(*a)
    return _

  def before(self, scanner, s):
    self.pos += len(s)
    self.skip(scanner, s)

  def error(self, scanner, s): self.raise_error("unknown token: %s"%s)

  def skip_whitespaces(self, scanner, s): self.append(",")

  def skip(self, scanner, s):
    last = "".join(self.result[-2:])
    if last in ["[,", ",,", ",]"]: 
      self.result[-2:] = sorted(last, key=ord)[1]

  def atom(self, scanner, s):
    if s in ["(", "["]:
      self.append("[")
      self.paren_stack.append(s)
    elif s in [")", "]"]:
      if not self.paren_stack:
        self.raise_error("missing opening parenthesis.")
      if self.PAREN[s] != self.paren_stack.pop():
        self.raise_error("missing closing parenthesis.")
      self.append("]")
    elif re.match(r"""^(".*)$""", s or ""):
      self.append("u"+s)
    elif re.match(r"""^((\-?\d[\de\.]+)|(\s*)|(.*"))$""", s or ""):
      self.append(s)
    else:
      self.append("Symbol(u\"%s\")"%s)

  def raise_error(self, msg="parse error", range=3):
    lines = self.string.split("\n")
    curline = self.string[:self.pos].count("\n")
    linepos = self.pos - len("\n".join(lines[:curline]))
    buf = ["\n"] 
    for i in xrange(max(0, curline-range), curline+1):
      buf.append("% 5d: %s"%(i+1, lines[i]))
    width = 6 + sum(east_asian_width(c) == 'W' and 2 or 1 for c in lines[i])
    buf.append("%s~"%(" "*width))
    buf.append("line %d, %d: %s"%(curline+1,linepos, msg))
    raise ParseError(("\n".join(buf)).encode(sys.stderr.encoding))

def read_sexp(sexp):
  processor = TokenProcessor(sexp)
  scanner = Scanner([
    (r"\s+", processor("skip_whitespaces")),
    (r";[^\n]*\n", processor("skip")),
    (r""""(?:[^"])*"|(\]|\[|\)|\(|[^\(\)\s]+)""", processor("atom")),
    (r".*", processor("error"))
  ], re.M)
  scanner.scan(processor.string)
  if processor.paren_stack:
    processor.raise_error("missing closing parenthesis.")
  result = eval("".join(processor.result).lstrip(","))
  return (isinstance(result, tuple) and (result[0],0) or (result,0))[0]

こんな感じ。非常にシンプルな気がします。

print read_sexp(u"""("ほげほげ"
;comment
  ;comment
  (hogehoge 123) ;aaaaaaa
  "hoge\\"aaaa"
;comment
;comment

aaaa          b)""")

output:

[u'\u307b\u3052\u307b\u3052', [Symbol(u'hogehoge'), 123], u'hoge"aaaa', Symbol(u'aaaa'), Symbol(u'b')]

エラーも一応。

print read_sexp(u"""(
aaaa
bbbb (ccc ddd) )
(eee 
ああああああ""")

output:

__main__.ParseError:

    2: aaaa
    3: bbbb (ccc ddd) )
    4: (eee
    5: ああああああ
                  ~
line 5, 7: missing closing parenthesis.

エラー表示もいい感じ。フォントにもよりますが(等幅なら大丈夫)、一応文字幅を考慮して ~ をエラー箇所に出すようにしています。HTML上だと日本語はずれちゃうかもだけど。

というわけで

Pythonでトークナイズするときにはかなり便利なんじゃないかと思いました。


前のエントリー でGAEにおけるトランザクションの問題は一応解決をみた。

その後、GAEで開発を続けた結果、やはりGAEにブログを移行するのは断念した。理由としては

  • os.listdir などで不審な挙動が見られた
  • スキーマを変更したときが非常に面倒
  • インポート、エクスポートの難しさ

が主なところ。

os.listdir については、web.pyでテンプレートを検索するときに os.listdir を使っているのだけど、どうも動きが怪しい。正しくファイルリストが帰ってきたり帰ってこなかったりするのだ。何回も本番にアップして試したところ、 os.listdir("hoge");os.listdir("hoge") というように同じ内容で2回連続で呼び出すとなぜか確実にファイルリストが帰ってくる、という・・・これはちょっと・・・

スキーマの変更に関しては、まんま。変更したとき、それを本番に反映させるのがめんどくさい。

インポートエクスポートも負荷を考えるとしんどい。現在もWEBはレンタルサーバで運用しているのでわざわざGAEにもっていく旨みもない。

ということでせっかくブログをつくったのに移行をやめたのである。


しかし、せっかく作ったのにもったいない。ということで今度はGAE用につくったブログを普通にMySQLを使うようにポーティングした。今回はそれに試験的に移行してみたのだ。

なぜWordpressからわざわざ独自ブログソフトウェアに移行したのか。理由は前のエントリーにも書いたとおりだけど

  • Wordpressのコードが気に食わない(OSSとしてバランスをとっている、というのはあるんですが)
  • 使用しているテンプレートや、プラグインも含めると出力されるHTMLが汚い。
  • ついている機能の半分以上は使っていない。ブログライトユーザの俺には機能が多すぎる。

    • 自分の使う機能が固まった。それさえあれば俺には十分とわかり始めた。
  • セキュリティ的にもWordpressはターゲットになっていて微妙。

以上のようなところをふまえ

  • 明快なコード。
  • キレイなXHTML。
  • 自分が使う機能だけ実装。
  • 堅牢なコード。

ということを心がけた。またレンタルサーバで動かすということで

  • なるべく静的HTMLとしてキャッシュしてmod_rewriteで飛ばす
  • 見た目や外部連携に関する動的な部分はなるべくクライアントサイドで

ということにも気を配った。

このブログは3年目に入るのだけど、やはりWEBの世界というのは流れが速いもので大分変化があった。その中で、外部連携はほぼJSONPで行えるようになったのでサーバサイドでやらなくても良くなった。今回実装したブログでは各SBMのブクマ数を表示しているけど、これも全てJSONPでクライアントサイドで実現している。それに対し、旧ブログ(Wordpress)ではサーバサイドで定期的に取得していた。

という感じで出来上がったのがこのブログだ。もうひとつ、実はこのブログ、XREAでしかもPython2.5で動かしている。あれ、XREAでPython2.5使えたっけ、というあなた。実は簡単に使えちゃうワザがあるんですよ。それについては、また。


あまりテストもせず試験的に移行してみたのでおかしい部分もあるかと思いますが、そこはおいおい。パーマリンクはそのままになっていると思います。基本的にURLは変更していません。また、CGIで動かしていますので、負荷が高ければ前のに戻す予定です。