|
996
|
1 class ParsingException(Exception):
|
|
|
2 pass
|
|
|
3
|
|
|
4 class Exp:
|
|
|
5 def show(self, indent_level):
|
|
|
6 return ' ' * indent_level + str(self.body)
|
|
|
7 def __str__(self):
|
|
|
8 # return self.show(0)
|
|
|
9 return str(self.body)
|
|
|
10
|
|
|
11 class StringExp(Exp):
|
|
|
12 def __init__(self, line):
|
|
|
13 self.line = line
|
|
|
14 def __str__(self):
|
|
|
15 return '"' + self.line + '"'
|
|
|
16
|
|
|
17 class SpecialExp(Exp):
|
|
|
18 def __init__(self, body):
|
|
|
19 self.body = body
|
|
|
20
|
|
|
21 class NameExp(Exp):
|
|
|
22 def __init__(self, body):
|
|
|
23 self.body = body
|
|
|
24
|
|
|
25 class ApplyExp(Exp):
|
|
|
26 def __init__(self, rator, rand):
|
|
|
27 self.rator = rator
|
|
|
28 self.rand = rand
|
|
|
29 def show(self, indent_level):
|
|
|
30 indent = ' ' * indent_level
|
|
|
31 strings = [indent + 'Apply:', self.rator.show(indent_level+1),
|
|
|
32 indent + 'To:', self.rand.show(indent_level+1)]
|
|
|
33 return '\n'.join(strings)
|
|
|
34 def __str__(self):
|
|
|
35 return str(self.rator) + ' ' + str(self.rand)
|
|
|
36
|
|
|
37
|
|
|
38 class LambdaExp(Exp):
|
|
|
39 def __init__(self, arg, body):
|
|
|
40 self.arg = arg
|
|
|
41 self.body = body
|
|
|
42 def show(self, indent_level):
|
|
|
43 indent = ' ' * indent_level
|
|
|
44 strings = [indent + 'Lambda ' + self.arg + ': ' , self.body.show(indent_level+1)]
|
|
|
45 return '\n'.join(strings)
|
|
|
46 def __str__(self):
|
|
|
47 # Perhaps we can combine this lambda with whatever is nested inside.
|
|
|
48 args = [self.arg]
|
|
|
49 curr = self
|
|
|
50 while isinstance(curr.body, LambdaExp):
|
|
|
51 curr = curr.body
|
|
|
52 args.append(curr.arg)
|
|
|
53 body_str = str(curr.body)
|
|
|
54 argstrings = ','.join(args)
|
|
|
55 if ' ' in body_str:
|
|
|
56 body_str = '('+body_str+')'
|
|
|
57 return '\\' + argstrings + '.' + body_str
|
|
|
58
|
|
|
59
|
|
|
60 def parse_exp(tokens, start_token, env, bound_vars):
|
|
|
61 def parse_one_exp(tokens, start_token, env, bound_vars):
|
|
|
62 """Parses a single expression NOT an application
|
|
|
63 of one expression to another, but possibly an
|
|
|
64 application inside (), starting from start_token. Returns a pair
|
|
|
65 (expression_object, last_token + 1)"""
|
|
|
66 index = start_token
|
|
|
67 current = tokens[index]
|
|
|
68 index += 1
|
|
|
69 if current[0] == '"':
|
|
|
70 # a string
|
|
|
71 exp = StringExp(current[1:-1])
|
|
|
72 elif current[0].isalpha():
|
|
|
73 # a name
|
|
|
74 if current in bound_vars:
|
|
|
75 exp = NameExp(current)
|
|
|
76 elif current in env:
|
|
|
77 exp = env[current]
|
|
|
78 else:
|
|
|
79 raise ParsingException("Unbound variable: " + current)
|
|
|
80 elif current[0] == '#':
|
|
|
81 exp = SpecialExp(current)
|
|
|
82 elif current == '(':
|
|
|
83 exp, index = parse_exp(tokens, index, env, bound_vars)
|
|
|
84 assert tokens[index] == ')'
|
|
|
85 index += 1
|
|
|
86 elif current == '\\':
|
|
|
87 # first read the names
|
|
|
88 names = []
|
|
|
89 while 1:
|
|
|
90 assert tokens[index].isalpha()
|
|
|
91 names.append(tokens[index])
|
|
|
92 index += 1
|
|
|
93 if tokens[index] == '.':
|
|
|
94 break
|
|
|
95 assert tokens[index] == ','
|
|
|
96 index += 1
|
|
|
97 # now index points at the last dot
|
|
|
98 index += 1
|
|
|
99 body, index = parse_one_exp(tokens, index, env, bound_vars + names)
|
|
|
100 # now create as many nested LambdaExps as we have names
|
|
|
101 while names:
|
|
|
102 body = LambdaExp(names[-1], body)
|
|
|
103 names = names[:-1]
|
|
|
104 exp = body
|
|
|
105 else:
|
|
|
106 raise ParsingException("Expression cannot start with " + current)
|
|
|
107 return exp, index
|
|
|
108
|
|
|
109 index = start_token
|
|
|
110 exps = []
|
|
|
111 while index < len(tokens) and tokens[index] != ')' and tokens[index] != ';':
|
|
|
112 exp, index = parse_one_exp(tokens, index, env, bound_vars)
|
|
|
113 exps.append(exp)
|
|
|
114 if exps == []:
|
|
|
115 raise ParsingException("Empty expression")
|
|
|
116 while len(exps) > 1:
|
|
|
117 app = ApplyExp(exps[0],exps[1])
|
|
|
118 exps = [app] + exps[2:]
|
|
|
119 return exps[0], index
|
|
|
120
|
|
|
121 def parse(tokens, env):
|
|
|
122 """Parses a list of tokens, and performs name substitution
|
|
|
123 from 'env' if any is necessary. Returns a pair (exp, env) with env a dict
|
|
|
124 containing any new definitions. Parsed expression will NOT
|
|
|
125 contain names of definitions."""
|
|
|
126 current = 0
|
|
|
127 env = env.copy()
|
|
|
128 while 1:
|
|
|
129 if len(tokens) - current < 2:
|
|
|
130 # Not enough room for a definition here
|
|
|
131 break
|
|
|
132 if tokens[current+1] == '=':
|
|
|
133 name = tokens[current]
|
|
|
134 exp, current = parse_exp(tokens, current+2, env, bound_vars=[])
|
|
|
135 env[name] = exp
|
|
|
136 assert tokens[current] == ';'
|
|
|
137 current += 1
|
|
|
138 else:
|
|
|
139 # not a definition. So we're done.
|
|
|
140 break
|
|
|
141 if current == len(tokens):
|
|
|
142 return None, env # useful in the REPL
|
|
|
143 exp, current = parse_exp(tokens, current, env, bound_vars=[] )
|
|
|
144 assert current == len(tokens)
|
|
|
145 return exp, env
|
