## Begin parser
from string import *
from yapps import SyntaxError, NoMoreTokens
from yapps import Scanner

class LispScanner(Scanner):
    def __init__(self, str):
        Scanner.__init__(self,[
            ('")"', ')'),
            ('"("', '('),
            ("'[ \\t\\n\\r]+'", '[ \011\012\015]+'),
            ('NUM', '[0-9]+'),
            ('ID', '[-+*/!@$%^&=.a-zA-Z0-9_]+'),
            ('STR', '"\\([^\\"]+\\|\\\\.\\)*"'),
            ], ["'[ \\t\\n\\r]+'"], str)

class Lisp:
    def __init__(self, scanner):
        self.scanner = scanner

    def token(self, _pos_, type):
        'Makes sure the next token matches one in type'
        return self.scanner.token(_pos_, [type])[3]

    def seq(self,_pos_=0):
        _start_,_,_token_,_text_ = self.scanner.token(_pos_,
            ['")"', 'ID', 'STR', 'NUM', '"("'])
        if _token_ == '")"':
            return ([]), _pos_
        else:
            expr,_pos_ = self.expr(_pos_)
            seq,_pos_ = self.seq(_pos_)
            return ([expr] + seq), _pos_

    def expr(self,_pos_=0):
        _start_,_,_token_,_text_ = self.scanner.token(_pos_,
            ['ID', 'STR', 'NUM', '"("'])
        if _token_ == 'ID':
            ID = _text_
            return (('id',ID)), 1+_pos_
        elif _token_ == 'STR':
            STR = _text_
            return (('str',eval(STR))), 1+_pos_
        elif _token_ == 'NUM':
            NUM = _text_
            return (('num',atoi(NUM))), 1+_pos_
        else:
            return self.list(_pos_)

    def list(self,_pos_=0):
        _start_,_,_token_,_text_ = self.scanner.token(_pos_,['"("'])
        seq,_pos_ = self.seq(1+_pos_)
        self.token(_pos_,'")"')
        return seq, 1+_pos_

def parse(rule, input):
    parser = Lisp(LispScanner(input))
    try: return getattr(parser, rule)()[0]
    except SyntaxError, s:
        try:
            from yapps import print_error
            print_error(input, s, parser.scanner)
        except ImportError:
            print 'Syntax Error',s.msg,'on line',1+count(input[:s.pos], '\n')
    except NoMoreTokens:
        print 'Ran out of input'