Python:re.Scannerで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でトークナイズするときにはかなり便利なんじゃないかと思いました。

comments powered by Disqus