S式パーサ
import re def arrange(s): s = re.sub("[ \n\t]+", " ", " " + s + " ")[1:-1] if s[0] == "(": if s[1] == " ": s = s[0] + s[2:] if s[-2] == " ": s = s[:-2] + s[-1] return s def read(s): def s2list(s): def extract(s): s_f = 0 b_f = 0 for i in range(len(s)): if s[i] == " " and s_f == 0 and b_f == 0: return i elif s[i] == '"': if s_f == 0: s_f = 1 else: s_f = 0 elif s[i] == "(": b_f += 1 elif s[i] == ")": b_f -= 1 return -1 if s == "": return ["nil"] n = extract(s) if n == -1: return ["pair", read(s), ["nil"]] elif s[0] == ".": return read(s[2:]) return ["pair", read(s[0:n]), s2list(s[n + 1:])] if s[0] == '"': return ["str", s[1:-1]] elif s.isdigit(): return ["int", int(s)] elif s[0] == "(": return s2list(arrange(s)[1:-1]) elif s[0] == "'": return ["pair", ["blt", "quote"], ["pair", read(s[1:]), ["nil"]]] else: return ["atom", s] def parse(s): return read(arrange(s)) def list(pair): if pair == ["nil"]: return [] return [pair[1]] + list(pair[2]) def pair(lis, type="pair"): if lis == []: return ["nil"] return [type, lis[0], pair(lis[1:], type)] def last(pair_list): if pair_list[2] == ["nil"]: return pair_list[1] return last(pair_list[2]) def car(pair): return pair[1] def cdr(pair): return pair[2] if __name__ == "__main__": print read(arrange("( a b c ( d e) ( f) . g)"))
実行してみる↓
>>> read(arrange("( a b c ( d e) ( f) . g)") ['pair', ['atom', 'a'], ['pair', ['atom', 'b'], ['pair', ['atom', 'c'], ['pair', ['pair', ['atom', 'd'], ['pair', 'e', ['nil']]], ['pair', ['pair', 'f', ['nil']], ['atom', 'g']]]]]]
追記(2009/4/3)
色々と追加/改良