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]