Python: S式パーサライブラリを作りました

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

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

ダウンロード

simplesexp.py

ソースはこんな感じ（テストのぞく）。

python code
  1. import re, sys
  2. from unicodedata import east_asian_width
  3.  
  4. try:
  5.   from re import Scanner
  6. except ImportError:
  7.   from sre import Scanner
  8.  
  9. class ParseError(StandardError): pass
  10.  
  11. class Ident(unicode):
  12.   def __repr__(self):
  13.     return "Ident(%s)"%unicode.__repr__(self)
  14.  
  15. class Symbol(unicode):
  16.   def __repr__(self):
  17.     return "Symbol(%s)"%unicode.__repr__(self)
  18.  
  19. class Pair(list):
  20.   def __repr__(self):
  21.     return "Pair(%s)"%list.__repr__(self)
  22.  
  23. class Token(object):
  24.   def __init__(self, value, pos):
  25.     self.value = value
  26.     self.pos = pos
  27.   def __repr__(self):
  28.     return repr(self.value)
  29.  
  30. class Binding(object):
  31.   def __init__(self, dct):
  32.     self.dct = dict(((k, k.__class__), v) for k,v in dct.iteritems())
  33.   __contains__ = lambda self, key: (key, key.__class__) in self.dct
  34.   __getitem__ = lambda self,key: self.dct[(key, key.__class__)]
  35.  
  36. default_binding = {"#t":True, "true":True, "#f":False, "false":False, "nil":None, "dict":Ident(u'alist->hash-table')}
  37.  
  38. class Reader(object):
  39.   PAREN = {"]":"[", ")":"("}
  40.   def __init__(self, binding=None, symbol_marker="'", use_dict=True):
  41.     self.binding = binding or default_binding
  42.     self.symbol_marker = symbol_marker
  43.     self.use_dict = use_dict
  44.  
  45.   def read(self, value):
  46.     self.result = []
  47.     self.paren_stack = []
  48.     self.source = value
  49.     self.pos = 0
  50.     self.scanner = Scanner([
  51.       (r"\s+", self("skip")),
  52.       (r";[^\n]*\n", self("skip")),
  53.       (r""""(((?<=\\)")|[^"])*((?<!\\)")""", self("str")),
  54.       (r"(\(|\[)", self("open")),
  55.       (r"(\)|\])", self("close")),
  56.       (r"(([\d]+|(((\d+)?\.[\d]+)|([\d]+\.)))e[\+\-]?[\d]+)|(((\d+)?\.[\d]+)|([\d]+\.))", self("number")),
  57.       (r"\-?((0x[\da-f]+)|(0[0-7]+)|([1-9][\d]*)|0)[l]?", self("number")),
  58.       (r"""%s([^\(\[\)\]\s"]+)"""%self.symbol_marker, self("symbol")),
  59.       (r"""([^\(\[\)\]\s"]+)""", self("ident")),
  60.       (r"""".*""", self("unterm_str")),
  61.       (r".*", self("unknown_token"))
  62.     ], re.M|re.S|re.I)
  63.     self.scanner.scan(self.source)
  64.     if self.paren_stack:
  65.       self.raise_error("missing closing parenthesis.")
  66.     return self.parse(self.result)
  67.  
  68.   def append(self, v):
  69.     self.last().append(Token(v, self.pos))
  70.  
  71.   def __call__(self, name):
  72.     def _(scanner, s):
  73.       self.pos += len(s)
  74.       return getattr(self, name)(s)
  75.     return _
  76.  
  77.   def unknown_token(self,s): self.raise_error("unknown token: %s"%s)
  78.   def skip(self, _): pass
  79.   def open(self, s):
  80.       new_lst = []
  81.       self.last().append(new_lst)
  82.       self.paren_stack.append([s, new_lst])
  83.   def close(self, s):
  84.       if not self.paren_stack:
  85.         self.raise_error("missing opening parenthesis.")
  86.       if self.PAREN[s] != self.paren_stack.pop()[0]:
  87.         self.raise_error("missing closing parenthesis.")
  88.   def str(self, s): self.append(eval('u""'+s+'""'))
  89.   def unterm_str(self, s): self.raise_error("unterminated string literal.")
  90.   def number(self, s): self.append(eval(s))
  91.   def symbol(self, s): self.append(Symbol(s[1:]))
  92.   def ident(self, s):
  93.     if s in self.binding:
  94.       self.append(self.binding[s])
  95.     else:
  96.       self.append(Ident(s))
  97.  
  98.   def last(self):
  99.     if self.paren_stack:
  100.       return self.paren_stack[-1][1]
  101.     else:
  102.       return self.result
  103.  
  104.   def parse(self, rs):
  105.     def is_ident(value, expected):
  106.       return getattr(value,"value", None) == Ident(expected)
  107.     def is_pair(rs):
  108.       return getattr(rs, "__len__", lambda :0)()==3 and is_ident(rs[1], u".")
  109.  
  110.     if isinstance(rs, list):
  111.       if not len(rs):
  112.         return []
  113.       elif self.use_dict and is_ident(rs[0], u"alist->hash-table"):
  114.         if len(rs) != 2:
  115.           self.raise_error("alist->hash-table: expected 1 arguments, got %d."%(len(rs)-1), rs[0].pos)
  116.         if not all(is_pair(a) for a in rs[1]):
  117.           self.raise_error("alist->hash-table: aruguments must be alist", rs[0].pos)
  118.         return dict((self.parse(i[0]), self.parse(i[2])) for i in rs[1])
  119.       elif len(rs)!=3 and any(is_ident(t, u".") for t in rs):
  120.         self.raise_error('illegal use of "."', rs[0].pos)
  121.       elif is_pair(rs):
  122.         parsed = self.parse(rs[2])
  123.         if not isinstance(rs[2], list):
  124.           return Pair([rs[0].value, parsed])
  125.         if isinstance(parsed, Pair):
  126.           return Pair([rs[0].value, parsed])
  127.         elif isinstance(parsed, list):
  128.           return [rs[0].value]+parsed
  129.         else:
  130.           return [rs[0].value, parsed]
  131.       else:
  132.         return map(self.parse, rs)
  133.     else:
  134.       return rs.value
  135.  
  136.   def raise_error(self, msg="parse error", pos=None, range=3):
  137.     pos = pos or self.pos
  138.     lines = self.source.split("\n")
  139.     curline = self.source[:pos].count("\n")
  140.     linepos = pos - len("\n".join(lines[:curline]))
  141.     buf = ["\n"]
  142.     for i in xrange(max(0, curline-range), curline+1):
  143.       buf.append("% 5d: %s"%(i+1, lines[i]))
  144.     width = 7 + sum(east_asian_width(c) == 'W' and 2 or 1 for c in unicode(lines[i]))
  145.     buf.append("%s~"%(" "*width))
  146.     buf.append("line %d, %d: %s"%(curline+1,linepos, msg))
  147.     raise ParseError(("\n".join(buf)).encode(sys.stderr.encoding))
  148.  
  149. class Dumper(object):
  150.   def __init__(self, binding=None ,symbol_marker="'"):
  151.     binding = binding or default_binding
  152.     self.binding = Binding(dict(zip(binding.values(), binding)))
  153.     self.symbol_marker = symbol_marker
  154.  
  155.   def dump(self, obj):
  156.     result = self.to_sexp(obj, [])
  157.     if isinstance(result, list) and len(result) and result[0]=="(":
  158.       result = result[1:-1]
  159.     return u" ".join(result)
  160.  
  161.   def to_sexp(self, obj, result):
  162.     ap = result.append
  163.     tos = lambda v: self.to_sexp(v, result)
  164.     if isinstance(obj, Pair):
  165.       ap("(")
  166.       tos(obj[0])
  167.       ap(" . ")
  168.       tos(obj[1])
  169.       ap(")")
  170.     elif isinstance(obj, (tuple, list)):
  171.       ap("(")
  172.       map(tos, obj)
  173.       ap(")")
  174.     else:
  175.       if isinstance(obj, dict):
  176.         ap("( alist->hash-table ")
  177.         tos([(k, Ident(u"."), v) for k,v in obj.items()])
  178.         ap(" ) ")
  179.       elif obj in self.binding:
  180.         ap(unicode(Ident(self.binding[obj])))
  181.       elif isinstance(obj, Symbol):
  182.         ap(u"'%s"%unicode(obj))
  183.       elif isinstance(obj, (Ident,int, float, long)):
  184.         ap(unicode(obj))
  185.       else:
  186.         s = unicode(repr(obj)).decode("unicode_escape")
  187.         m = re.match(r"""^[u|r]?["|'](.*)["|']$""", s, re.M|re.S)
  188.         if m:
  189.           s = m.group(1)
  190.         ap("\"%s\""%s.replace('"','\\"').replace("\\'","'"))
  191.     return result
  192.  
  193. dumper = Dumper()
  194. read = Reader().read
  195. dump = dumper.dump
  196.  

概要

特徴は

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

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

 code
  1. (あああ hoge->fuga123 (1 . (2 . 3)) "hoge\\"hoge" ;comment2
  2. foo "aaa" #t <= 'foo
  3. "hogehoge
  4. foo
  5. " (5 . (6 .()))
  6. )
  7. (dict (
  8.   ("いいい" .
  9.     (alist->hash-table (
  10.       ("a-1" . "vvv")
  11.       ("a-2" . (
  12.         hoge foo bar
  13.       ))
  14.     )))
  15. ))
  16. (10 1L -45 010 0x10 -10 -0x10 3.14 10. .001 1e100 3.14e-10 0e0)
  17. ; comment3 ()(
  18.  
  19. """)
  20.  

という感じのS式が

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

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

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

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

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

09.19.08/09pm
Posted at:
09.19.08/05pm
Tags:
Comments:
0
Permalink

About

Author:yuin(http://inforno.net/)

文学部文化学科卒という生粋の文系趣味プログラマ。

主にRuby、Javascript、PHP、JAVA,Python,C,Scala,Schemeなどを使っています。今はPythonな感じかもしれない。今後作曲活動なども復活するかもしれない。

Links

Pages

Recently

Tags

SF1 activesupport1 api3 binary3 blog1 book1 cltc1 compiler1 craftlaunch2 cui1 development9 drecom1 electronics1 emulator6 erlang1 essay9 fckeditor1 feed1 gae3 gui2 javascript14 job4 language1 library10 life4 lingr1 linux1 nes5 network1 nicovideo1 nlp1 ocaml1 parser6 programing2 prototype_js7 python33 python30001 ruby5 rubyonrails2 scala6 scheme1 scrap1 scriptaculous1 sexp1 tasktools1 template2 text2 tk1 typo2 vim2 webpy2 windows3 wordpress2 xrea1 yahoo3

Monthly Archives