class ParsingException(Exception):
    pass

class Exp:
    def show(self, indent_level):
        return ' ' * indent_level + str(self.body)
    def __str__(self):
        # return self.show(0)
        return str(self.body)

class StringExp(Exp):
    def __init__(self, line):
        self.line = line
    def __str__(self):
        return '"' + self.line + '"'

class SpecialExp(Exp):
    def __init__(self, body):
        self.body = body

class NameExp(Exp):
    def __init__(self, body):
        self.body = body

class ApplyExp(Exp):
    def __init__(self, rator, rand):
        self.rator = rator
        self.rand = rand
    def show(self, indent_level):
        indent = ' ' * indent_level
        strings = [indent + 'Apply:', self.rator.show(indent_level+1),
                   indent + 'To:', self.rand.show(indent_level+1)]
        return '\n'.join(strings)
    def __str__(self):
        return str(self.rator) + ' ' + str(self.rand)


class LambdaExp(Exp):
    def __init__(self, arg, body):
        self.arg = arg
        self.body = body
    def show(self, indent_level):
        indent = ' ' * indent_level
        strings = [indent + 'Lambda ' + self.arg + ': ' ,  self.body.show(indent_level+1)]
        return '\n'.join(strings)
    def __str__(self):
        # Perhaps we can combine this lambda with whatever is nested inside.
        args = [self.arg]
        curr = self
        while isinstance(curr.body, LambdaExp):
            curr = curr.body
            args.append(curr.arg)
        body_str = str(curr.body)
        argstrings = ','.join(args)
        if ' ' in body_str:
            body_str = '('+body_str+')'
        return '\\' + argstrings + '.' + body_str


def parse_exp(tokens, start_token, env, bound_vars):
    def parse_one_exp(tokens, start_token, env, bound_vars):
        """Parses a single expression NOT an application
        of one expression to another, but possibly an
        application inside (), starting from start_token. Returns a pair
        (expression_object, last_token + 1)"""
        index = start_token
        current = tokens[index]
        index += 1
        if current[0] == '"':
            # a string
            exp = StringExp(current[1:-1])
        elif current[0].isalpha():
            # a name
            if current in bound_vars:
                exp = NameExp(current)
            elif current in env:
                exp = env[current]
            else:
                raise ParsingException("Unbound variable: " + current)
        elif current[0] == '#':
            exp = SpecialExp(current)
        elif current == '(':
            exp, index = parse_exp(tokens, index, env, bound_vars)
            assert tokens[index] == ')'
            index += 1
        elif current == '\\':
            # first read the names
            names = []
            while 1:
                assert tokens[index].isalpha()
                names.append(tokens[index])
                index += 1
                if tokens[index] == '.':
                    break
                assert tokens[index] == ','
                index += 1
            # now index points at the last dot
            index += 1
            body, index = parse_one_exp(tokens, index, env, bound_vars + names)
            # now create as many nested LambdaExps as we have names
            while names:
                body = LambdaExp(names[-1], body)
                names = names[:-1]
            exp = body
        else:
            raise ParsingException("Expression cannot start with " + current)
        return exp, index

    index = start_token
    exps = []
    while index < len(tokens) and tokens[index] != ')' and tokens[index] != ';':
        exp, index = parse_one_exp(tokens, index, env, bound_vars)
        exps.append(exp)
    if exps == []:
        raise ParsingException("Empty expression")
    while len(exps) > 1:
        app = ApplyExp(exps[0],exps[1])
        exps = [app] + exps[2:]
    return exps[0], index

def parse(tokens, env):
    """Parses a list of tokens, and performs name substitution
    from 'env' if any is necessary. Returns a pair (exp, env) with env a dict
    containing any new definitions. Parsed expression will NOT
    contain names of definitions."""
    current = 0
    env = env.copy()
    while 1:
        if len(tokens) - current < 2:
            # Not enough room for a definition here
            break
        if tokens[current+1] == '=':
            name = tokens[current]
            exp, current = parse_exp(tokens, current+2, env, bound_vars=[])
            env[name] = exp
            assert tokens[current] == ';'
            current += 1
        else:
            # not a definition. So we're done.
            break
    if current == len(tokens):
        return None, env # useful in the REPL
    exp, current = parse_exp(tokens, current, env, bound_vars=[] )
    assert current == len(tokens)
    return exp, env