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

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オブジェクトとして返る

で

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 Symbol(unicode):
  12.   def __repr__(self):
  13.     return "Symbol(%s)"%unicode.__repr__(self)
  14.  
  15. class TokenProcessor(object):
  16.   PAREN = {"]":"[", ")":"("}
  17.   def __init__(self, value):
  18.     self.result = []
  19.     self.append = self.result.append
  20.     self.string = value
  21.     self.paren_stack = []
  22.     self.pos = 0
  23.  
  24.   def __call__(self, name):
  25.     def _(*a):
  26.       self.before(*a)
  27.       return getattr(self, name)(*a)
  28.     return _
  29.  
  30.   def before(self, scanner, s):
  31.     self.pos += len(s)
  32.     self.skip(scanner, s)
  33.  
  34.   def error(self, scanner, s): self.raise_error("unknown token: %s"%s)
  35.  
  36.   def skip_whitespaces(self, scanner, s): self.append(",")
  37.  
  38.   def skip(self, scanner, s):
  39.     last = "".join(self.result[-2:])
  40.     if last in ["[,", ",,", ",]"]:
  41.       self.result[-2:] = sorted(last, key=ord)[1]
  42.  
  43.   def atom(self, scanner, s):
  44.     if s in ["(", "["]:
  45.       self.append("[")
  46.       self.paren_stack.append(s)
  47.     elif s in [")", "]"]:
  48.       if not self.paren_stack:
  49.         self.raise_error("missing opening parenthesis.")
  50.       if self.PAREN[s] != self.paren_stack.pop():
  51.         self.raise_error("missing closing parenthesis.")
  52.       self.append("]")
  53.     elif re.match(r"""^(".*)$""", s or ""):
  54.       self.append("u"+s)
  55.     elif re.match(r"""^((\-?\d[\de\.]+)|(\s*)|(.*"))$""", s or ""):
  56.       self.append(s)
  57.     else:
  58.       self.append("Symbol(u\"%s\")"%s)
  59.  
  60.   def raise_error(self, msg="parse error", range=3):
  61.     lines = self.string.split("\n")
  62.     curline = self.string[:self.pos].count("\n")
  63.     linepos = self.pos - len("\n".join(lines[:curline]))
  64.     buf = ["\n"]
  65.     for i in xrange(max(0, curline-range), curline+1):
  66.       buf.append("% 5d: %s"%(i+1, lines[i]))
  67.     width = 6 + sum(east_asian_width(c) == 'W' and 2 or 1 for c in lines[i])
  68.     buf.append("%s~"%(" "*width))
  69.     buf.append("line %d, %d: %s"%(curline+1,linepos, msg))
  70.     raise ParseError(("\n".join(buf)).encode(sys.stderr.encoding))
  71.  
  72. def read_sexp(sexp):
  73.   processor = TokenProcessor(sexp)
  74.   scanner = Scanner([
  75.     (r"\s+", processor("skip_whitespaces")),
  76.     (r";[^\n]*\n", processor("skip")),
  77.     (r""""(?:[^"])*"|(\]|\[|\)|\(|[^\(\)\s]+)""", processor("atom")),
  78.     (r".*", processor("error"))
  79.   ], re.M)
  80.   scanner.scan(processor.string)
  81.   if processor.paren_stack:
  82.     processor.raise_error("missing closing parenthesis.")
  83.   result = eval("".join(processor.result).lstrip(","))
  84.   return (isinstance(result, tuple) and (result[0],0) or (result,0))[0]
  85.  

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

python code
  1. print read_sexp(u"""("ほげほげ"
  2. ;comment
  3. ;comment
  4. (hogehoge 123) ;aaaaaaa
  5. "hoge\\"aaaa"
  6. ;comment
  7. ;comment
  8.  
  9. aaaa b)""")
  10.  

output:

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

エラーも一応。

python code
  1. print read_sexp(u"""(
  2. aaaa
  3. bbbb (ccc ddd) )
  4. (eee
  5. ああああああ""")
  6.  

output:

 code
  1. __main__.ParseError:
  2.  
  3.     2: aaaa
  4.     3: bbbb (ccc ddd) )
  5.     4: (eee
  6.     5: ああああああ
  7.                   ~
  8. line 5, 7: missing closing parenthesis.
  9.  

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

というわけで

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

08.22.08/07pm
Posted at:
08.08.08/08pm
Tags:
Comments:
0
Permalink

Scalaでスタック指向言語をサクッと実装する

Scalaにはご存知のとおりscala.util.parsing.combinatorというパーサコンビネータライブラリがある。さらにはscala.util.parsing.astというのもあるわけだけど、これは激しく開発中な感じ。Scalaはバージョンがあがるとこういう開発中ライブラリはごそっと変わったりするので今はおいておく。ちなみに、2.7.1では前のパーサコンビネータはscala.util.parsing.combinatoroldといういかにも使いたくない名前にされてしまった。

パーサコンビネータといえば言語処理系だ（そうか？）。というわけでscala.util.parsing.astは置いておいて、とりあえずASTについてほとんど考える必要がない、簡単なスタック指向言語を実装してみることにする。実行はScala 2.7.1.finalで。

スタック指向言語とは

こんなブログを見ている人は、だいたいスタック指向言語を知っているだろうから俺みたいな素人が書いてもなんだけど、一応。 スタック指向言語にはForthやPostScriptやFactorがある。素晴らしく簡単にいうと、「とりあえずスタックがあればなんとかなるよね」という言語だ。

んでスタック使うなら逆ポーランドで書いてあったら、処理も楽だしいいんじゃね、読みにくい？Lispだって慣れてる人は無問題なんだし、慣れの問題じゃね、という感じである。

関数（スタック指向言語ではwordという）もスタックに値をつんで実行すればいい。wordから値を返すときも返したい分だけスタックにつめばいい。というわけで、非常に単純なのである。

今回はFactorライクなスタック指向言語処理系（インタプリタ）「SimpleFactor」を作ってみることに。文法とかはだいたいFactorと一緒なのでさきにFactorの文法を学んでおくと分かりやすい。

まずはレクサ

まずはレクサを作る。サポートするリテラルは文字列、整数値、真偽値で以下のような感じ。

  • 文字列："hoge"
  • 整数値：10, -10
  • 真偽値：t,f

あと、コメントは!から行末までとする。ソースはこんな感じで、ScalaのDSL構築能力を生かしてかなり定義どおりに書ける。

scala code
  1. import scala.util.parsing.combinator._
  2. import scala.util.parsing.combinator.syntactical._
  3. import scala.util.parsing.combinator.lexical._
  4. import scala.util.parsing.input.CharArrayReader.EofCh
  5. class Lexer extends StdLexical with ImplicitConversions {
  6.   override def token: Parser[Token] =
  7.     ( string ^^ StringLit
  8.     | '-' ~> number ^^ { case num => NumericLit("-" + num) }
  9.     | number ^^ NumericLit
  10.     | EofCh ^^^ EOF
  11.     | delim
  12.     | '\"' ~> failure("Unterminated string")
  13.     | rep(chrAny) ^^ checkKeyword
  14.     | failure("Illegal character")
  15.     )
  16.  
  17.  
  18.   def number = zero | (nonzero ~ rep(digit) ^^ {case x ~ y => mkS(x::y)})
  19.   def string = '\"' ~> rep(charSeq | chrExcept('\"', '\n', EofCh)) <~ '\"' ^^ {case x => mkS(x)}
  20.   def checkKeyword(xs : List[Any]) = {
  21.     val strRep = mkS(xs)
  22.     if (reserved contains strRep){ Keyword(strRep) }
  23.     else if(identiferRe.findFirstIn(strRep) != None ) { Identifier(strRep) }
  24.     else {ErrorToken("Not a Identifier: " + strRep)}
  25.   }
  26.  
  27.   override def whitespace: Parser[Any] =
  28.     rep( whitespaceChar | '!' ~ rep( chrExcept(EofCh, '\n') ))
  29.   def nonzero = elem("nonzero digit", d => d.isDigit && d != '0')
  30.   def zero: Parser[String] = '0' ^^^ "0"
  31.   def charSeq: Parser[String] =
  32.     ('\\' ~ '\"' ^^^ "\"" |'\\' ~ '\\' ^^^ "\\" |'\\' ~ '/' ^^^ "/" |'\\' ~ 'b' ^^^ "\b" | '\\' ~ '0' ^^^ ""
  33.     |'\\' ~ 'f' ^^^ "\f" |'\\' ~ 'n' ^^^ "\n" |'\\' ~ 'r' ^^^ "\r" |'\\' ~ 't' ^^^ "\t")
  34.   def identiferRe = """^(\w|[^"])+$""".r
  35.   def chrAny = chrExcept(EofCh, ' ', '\n', '\t', '\r', '\"', '!')
  36.  
  37.   def mkS[A](seq: Seq[A]) = seq mkString ""
  38. }
  39.  

Scalaで処理系を作る場合はとりあえずStdLexicalを継承して拡張すれば、だいたいOK。ここではTokenを返すパーサを定義する。KeywordやStringLitといったTokenを継承したケースクラスはscala.util.parsing.sytax.StdTokensで定義されていて、StdLexicalはStdTokensをMix-inしている。

抽象構文木をつくる

次に、このトークンの並びから文法を定義して、それに従って抽象構文木を作るわけだけど、スタック指向言語の場合、ここで難しいことはあまりない。

とりあえず、処理(といっても4種類、しかもうち2種類は意味なし）と、抽象構文木をあらわすケースクラスを作る。インタプリタなのでオペコードとかする意味はないけど、こうしとくとVMにしようと思ったとき楽なのでそうした。というよりエミュとかを作ることが好きなので、こういう数値を見ると安心するのである。

scala code
  1. import scala.util.logging.ConsoleLogger
  2. import scala.collection.mutable.{Stack, ArrayBuffer, HashMap}
  3. trait Opecode {
  4.   final val OP_NOP : byte = 0x00
  5.   final val OP_PUSH : byte = 0x01
  6.   final val OP_CALL : byte = 0x50
  7.   final val OP_RTN : byte = 0x51
  8. }
  9.  
  10. abstract class Node {
  11.   type Value
  12.   val v:Value
  13.   def value = v
  14. }
  15. abstract class NodeValue extends Node
  16. case class NodeStr(v:String) extends NodeValue { type Value = String }
  17. case class NodeInt(v:int) extends NodeValue { type Value = int }
  18. case class NodeBool(v:boolean) extends NodeValue { type Value = boolean }
  19. case class NodeSymbol(override val v:String) extends NodeStr(v)
  20. case class NodeQuotation(val v:List[Node]) extends Node{ type Value = List[Node] }
  21. case class NodeOpe(v:byte, operand:List[Node]) extends Node { type Value = byte }
  22. case class NodeNamed(v:Named) extends NodeValue with Opecode{ type Value = Named }
  23. case class NodeProgram(v:List[Node]) extends Node with Opecode{
  24.   type Value = List[Node]
  25.   var quotIndex = 0
  26.   def nextQuotSym = { quotIndex += 1; "quot"+quotIndex }
  27.  
  28.   def toplevel = {
  29.     val nullsf = List[NodeSymbol]()
  30.     val words = new ArrayBuffer[Node]
  31.     def visitNode(n:Node):List[Node] = n match {
  32.       case NodeNamed(NamedWord(name, sin, sout, body)) =>
  33.          words += NodeNamed(NamedWord(name, sin, sout, body.flatMap(visitNode)))
  34.          List[Node]()
  35.       case NodeQuotation(nodes) =>
  36.         val name = nextQuotSym
  37.         words += NodeNamed(NamedWord(name, nullsf, nullsf, nodes.flatMap(visitNode)))
  38.         List(NodeOpe(OP_PUSH, List(NodeSymbol(name))))
  39.       case x => List(x)
  40.     }
  41.     value.flatMap(visitNode)
  42.     words.toList
  43.   }
  44. }
  45.  
  46. abstract class Named(name:String)
  47. case class NamedWord(name:String, stackin:List[NodeSymbol], stackout:List[NodeSymbol], body:List[Node]) extends Named(name)
  48. case class NamedNativeWord[T](name:String, stackin:List[NodeSymbol],
  49.   stackout:List[NodeSymbol], body:()=>T) extends Named(name)
  50. class NamedTable extends HashMap[String, Named] {
  51. }
  52.  

Nodeという抽象クラスを継承して、いろんなノードを定義する。だいたい名前をみてのとおりだけど、わかりにくいところだとこんな感じ。

  • NodeNamed：名前付けされた値への参照
  • NodeSymbol：word名
  • NodeQuotation：無名関数(quotationという)
  • NodeProgram：プログラム全体

Namedは名前付けされた値なわけだけど、今回変数にあたるものはないので、wordのみがコレにあたる。NamedWordがSimpleFactorで書かれたふつーのword、NamedNativeWordはいわゆる組み込みwordでScalaで書いたものをあらわす。NamedTableはその対応を保存する単なるハッシュマップ。

さて、ではこいつらを使って構文木を作って実行する。

scala code
  1. class SimpleFactorInterp extends StdTokenParsers with ImplicitConversions with Opecode{
  2.   type Tokens = Lexer
  3.   val lexical = new Tokens
  4.   lexical.reserved ++= List("t", "f", "(", ")", "[", "]", ":", ";", "--")
  5.   lexical.delimiters ++= List("\n", " ", "\t")
  6.   import lexical.{NumericLit, StringLit, Keyword, Identifier}
  7.  
  8.   def program = rep(lWord) ^^ { case nodes => NodeProgram(nodes) }
  9.   def lWord = ":" ~ lSymbol ~ "(" ~ rep(lSymbol) ~ "--" ~ rep(lSymbol) ~ ")" ~ rep(lExpr) ~ ";" ^^
  10.                         { case ":" ~ name ~ "(" ~ sin ~ "--" ~ sout ~ ")" ~ body ~ ";" =>
  11.                             NodeNamed(NamedWord(name.value, sin, sout, body+NodeOpe(OP_RTN, List[Node]()))) }
  12.   def lExpr:Parser[Node] = (lString | lNumber | lBool | lInvokeWord | lQuotation)
  13.   def lString = accept("string", { case StringLit(n) => NodeOpe(OP_PUSH, List(NodeStr(n))) })
  14.   def lNumber = accept("number", { case NumericLit(n) => NodeOpe(OP_PUSH, List(NodeInt(n.toInt))) })
  15.   def lBool = accept("boolean",{ case Keyword("t") => NodeOpe(OP_PUSH, List(NodeBool(true)))
  16.                                        case Keyword("f") => NodeOpe(OP_PUSH, List(NodeBool(false))) })
  17.   def lInvokeWord = accept("symbol", { case Identifier(n) => NodeOpe(OP_CALL, List(NodeSymbol(n))) })
  18.   def lQuotation = "[" ~> rep(lExpr) <~ "]" ^^ { case expr => NodeQuotation(expr+NodeOpe(OP_RTN, List[Node]())) }
  19.  
  20.   def lSymbol = accept("symbol", { case Identifier(n) => NodeSymbol(n) })
  21.  
  22.   protected val stack = new Stack[Node]
  23.   protected var namedTable = new NamedTable
  24.  
  25.   def parse(input: String) =
  26.     phrase(program)(new lexical.Scanner(input)) match {
  27.       case Success(programNode, _) => initTopLevel(programNode.toplevel)
  28.       case x => error(x.toString)
  29.     }
  30.  
  31.   def initTopLevel(toplevelNodes:List[Node]) = {
  32.     def sl(v:String) = v.split(" ").map(NodeSymbol).toList
  33.     def nword[T](n:String, sin:String, sout:String, m:()=>T) =
  34.       (n, NamedNativeWord(n, sl(sin), sl(sout), m))
  35.     namedTable ++= List(
  36.       nword("drop", "x", "", ()=>{ pop }),
  37.       nword("dup", "x", "x x", ()=>{ val v = pop; npush(v,v) }),
  38.       nword("rotate", "x y z", "y z x", ()=> npop(3) match {
  39.         case List(x, y, z) => npush(y, z, x)
  40.       }),
  41.       nword("swap", "x y", "y x", ()=> npop(2) match {
  42.         case List(x, y) => npush(y, x)
  43.       }),
  44.  
  45.       nword("+", "x y", "z", ()=>{ iArI2(_+_) }),
  46.       nword("-", "x y", "z", ()=>{ iArI2(_-_) }),
  47.       nword("*", "x y", "z", ()=>{ iArI2(_*_) }),
  48.       nword("/", "x y", "z", ()=>{ iArI2(_/_) }),
  49.  
  50.       nword(">", "x y", "?", ()=>{ ilB2(_>_) }),
  51.       nword("<", "x y", "?", ()=>{ ilB2(_<_) }),
  52.       nword("==", "x y", "?", ()=>{ ilB2(_==_) }),
  53.       nword(">=", "x y", "?", ()=>{ ilB2(_>=_) }),
  54.       nword("<=", "x y", "?", ()=>{ ilB2(_<=_) }),
  55.  
  56.       nword("not", "?", "?", ()=> pop match {
  57.         case NodeBool(v) => push(NodeBool(!v))
  58.       }),
  59.       nword("and", "? ?", "?", ()=> (pop, pop) match {
  60.         case (NodeBool(true), NodeBool(true)) => push(NodeBool(true))
  61.         case (NodeBool(_), NodeBool(_)) => push(NodeBool(false))
  62.       }),
  63.       nword("or", "? ?", "?", ()=> (pop, pop) match {
  64.         case (NodeBool(false), NodeBool(false)) => push(NodeBool(false))
  65.         case (NodeBool(_), NodeBool(_)) => push(NodeBool(true))
  66.       }),
  67.  
  68.       nword(".", "obj", "", ()=>{ println(pop.value) }),
  69.       nword("call", "quot", "", ()=> pop match {
  70.         case NodeSymbol(qname) => callWord(qname)
  71.       }),
  72.  
  73.       nword("if", "? quot quot", "", ()=> (pop, pop, pop) match {
  74.         case (_, NodeSymbol(qname), NodeBool(true)) => callWord(qname)
  75.         case (NodeSymbol(qname), _, NodeBool(false)) => callWord(qname)
  76.       }),
  77.  
  78.       nword("string>number", "str", "x", ()=> pop match {
  79.         case NodeStr(str) => push(NodeInt(str.toInt))
  80.       }),
  81.       nword(">string", "obj", "str", ()=> { push(NodeStr(pop.value.toString)) })
  82.  
  83.     )
  84.     toplevelNodes.foreach {
  85.       case NodeNamed(n@NamedWord(name, _, _, _)) => namedTable(name) = n
  86.       case _ => ()
  87.     }
  88.   }
  89.  
  90.   def evaluate(input:String, args:Array[String]) = {
  91.     parse(input)
  92.     args.map(NodeStr).foreach(push _)
  93.     callWord("main")
  94.   }
  95.  
  96.   def callWord(wordName:String):unit =
  97.     namedTable(wordName.ensuring(namedTable.contains _, "word '"+wordName+"' is not defined.")) match {
  98.       case NamedNativeWord(_, sin, sout, body) => try {
  99.           body()
  100.         } catch {
  101.           case e => wordError(wordName, sin, sout)
  102.                     throw e
  103.         }
  104.       case NamedWord(_, sin, sout, body) =>
  105.         body foreach {
  106.           case NodeOpe(OP_PUSH, List(v, _*)) => push(v)
  107.           case NodeOpe(OP_CALL, List(NodeSymbol(name), _*)) =>
  108.             try {
  109.               callWord(name)
  110.             }catch {
  111.               case e => wordError(wordName, sin, sout)
  112.                         throw e
  113.             }
  114.           case NodeOpe(OP_RTN, _) => ()
  115.         }
  116.     }
  117.  
  118.   def npop(n:int):List[Node] = (1 to n).map(x=>pop).reverse.toList
  119.   def npush(ns:Node*) = ns.reverse.foreach(push(_))
  120.  
  121.   def iArI2(f:(int,int)=>int) = (pop, pop) match {
  122.     case (NodeInt(v1), NodeInt(v2)) => push(NodeInt(f(v2,v1)))
  123.   }
  124.   def ilB2(f:(int,int)=>boolean) = (pop, pop) match {
  125.     case (NodeInt(v1), NodeInt(v2)) => push(NodeBool(f(v2,v1)))
  126.   }
  127.   def wordError(name:String, sin:List[NodeSymbol], sout:List[NodeSymbol]) = {
  128.     printf("word '%s' ( %s -- %s ).\n", name, sin.map(_.value).mkString(" "),
  129.                                               sout.map(_.value).mkString(" "))
  130.   }
  131.   def push(a:Node) = stack.push(a)
  132.   def pop = stack.pop
  133.  
  134. }
  135.  

はじめの方でプログラムの文法を定義し、TokenからNodeのリストへ変換し、NodeProgramにする。処理の簡単さのため、プログラムはwordから構成されていて、プログラム開始時にはmain wordから実行が開始されるとするので

scala code
  1. def program = rep(lWord) ^^ { case nodes => NodeProgram(nodes) }
  2.  

wordは

 code
  1. : add ( x y -- z )
  2.  +
  3. ;
  4.  

という感じに定義するのでlWordの定義になっている。ほとんどそのまま書いた感じだ。( x y -- z )の部分はスタックエフェクトといって、このwordがスタックにどのような影響を与えるのかを記述している。あくまで説明であって本質的な意味はない。( x y -- z )ならスタックから2個取り出されて、結果が1個詰まれるのだな、ということがわかる。

あとは自明なので省略。

実行

そんなこんなでソースコードからNodeProgramが作れるようになった。次にNodeProgramからTOPレベル環境を作る。

ここでは、NodeProgramに含まれるquotationを(実行する際の）簡単さのためNamedWordに変換し、変換後のNamedWordの呼び出しに変換する。組み込みwordもここで定義している。これはこの部分で定義すると、クロージャになるため定義が簡単だから(popやpushといったSimpleFactorInterpのメソッドがそのまま書ける)である。また、パターンマッチを活用することで非常に直感的に書けていることが見て取れるかと。やっぱりパターンマッチ最高だわぁ･･･。そして出揃ったTOPレベルのwordをNamedTableにマッピングし、TOPレベル環境の作成が完了する。

あとはmain wordを呼び出すだけ。

サンプルコード

こんな感じ。サンプルでは10の階乗を計算している。

scala code
  1. object SimpleFactor extends ConsoleLogger{
  2.   def main(args: Array[String]) = {
  3.     log("Starting SimpleFactor.")
  4.     log("-"*40)
  5.     val ip = new SimpleFactorInterp
  6.     ip.evaluate("""
  7. ! Performs a factorial calculation.
  8. : main ( str -- )
  9. string>number fact .
  10. ;
  11.  
  12. : fact ( x -- y ) dup factit ;
  13.  
  14. : factit ( x y -- z )
  15. dup 1 <=
  16. [ drop ]
  17. [ 1 - dup rotate * swap factit ] if
  18. ;
  19.  
  20. """, args)
  21.   }
  22. }
  23.  
  24. SimpleFactor.main(Array("10"))
  25.  

ここで使っているwordを簡単に説明すると

  • string>number:スタックからpopし、文字列を数値に変換してpushする
  • *: スタックから2個popし、掛けたものをpushする
  • -: スタックから2個popし、引き算したものをpushする
  • <=:スタックから2個popし、<=な比較をして真偽値をpushする
  • .: スタックからpopし、文字列表現を表示する
  • dup:スタックからpopし、それを2回pushする
  • drop:スタックからpopする
  • rotate:「x y z」というスタックのトップ部分を、「y z x」にローテーションする
  • swap:「x y」というスタックのトップ部分を「y x」に入れ替える
  • if:「真偽値 真のとき実行するquotation 偽のとき実行するquotation」というスタックのトップ部分から条件を判定しquotationを実行する

てな感じ。これだけの命令でもちゃんとプログラムが書けて、条件分岐、ループが実現できるのはスタック指向言語を知らない人から見ると面白い部分かも。3 factなら

  • [ 3 3 ] : fact内dup
  • [ 3 3 3 ] : factit内dup
  • [ 3 3 3 1 ] : 1
  • [ 3 3 f ] : <=
  • [ 3 3 f quot ] : [ drop ]
  • [ 3 3 f quot quot ] : [1 - ... ]
  • [ 3 3 ] : if
  • [ 3 3 1 ] : 1
  • [ 3 2 ] :
    -
  • [ 3 2 2 ] : dup
  • [ 2 2 3 ] : rotate
  • [ 2 6 ] : *
  • [ 6 2 ] : swap
  • factitに戻る

こんな感じで計算される。

またLispのS式とマクロによる拡張性は名高いと思うが、スタック指向言語も単純に空白で区切られたwordが並んでいる、という点で非常に自己拡張性が高い。こういう変態的(?)な部分も魅力の一つ。

ForthはSUNのOpen Firmware、Firefox4で採用が予定されているJavascriptの処理系Tamarinの中など、今でもあまり表には見えてこない部分で使用されているので、これを機会にスタック指向言語を嗜んでみては。Forthは基本だけど、今なら注目され始めている(？)Factorかなあ。

簡単に作れます

というわけでScalaで簡単なスタック指向言語処理系を作ってみたわけだけど、非常に簡単。さくっと作れる。scala.util.parsing.astができたら、またなんか処理系を試し書きしてみようかな。

  • 20080519:ryugateさんの指摘を受けてソースコードのコピペミスを修正、また少し説明を足しました。
07.27.08/12am
Posted at:
05.17.08/10pm
Tags:
Comments:
(3)
Permalink

About

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

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

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

Links

Pages

Recently

Tags

DHT1 SF1 activesupport1 api4 binary3 blog1 book1 cltc1 compiler1 craftlaunch2 cui1 development9 drecom1 electronics1 emulator6 erlang1 essay10 fckeditor1 feed1 framework1 gae3 go1 gui2 javascript14 job4 kademlia1 language2 library14 life5 lingr1 linux1 nes5 network1 nicovideo1 nlp1 ocaml1 p2p1 parser6 programing2 prototype_js7 python39 python30001 rayphe1 ruby5 rubyonrails2 scala6 scheme1 scrap1 scriptaculous1 sexp1 tasktools1 template3 text3 tk1 typo2 vim2 webpy2 windows4 wordpress2 xrea2 yahoo4

Monthly Archives