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）

色々と追加/改良