1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
|
# -*- coding: utf-8 -*-
from ast import *
from token import Tag
from scope import Scope
class ParseError(Exception):
pass
class Parser:
def __init__(self, lexer):
self.lexer = lexer
self.scope = Scope()
self.move()
def parse(self):
return self.program()
def move(self):
self.token = self.lexer.scan()
#print "move(): %s" % self.token
def error(self, msg):
raise ParseError(msg)
def _match(self, tag):
if self.token == None:
self.error("Unexpected end of file.")
if self.token.tag != tag:
self.error("match: expected %s got %s\n" %(tag, self.token.tag))
val = self.token.value
self.move()
return val
def match(self, tag, *tags):
for t in (tag,) + tags:
res = self._match(t)
return res
# boolean = join { "||" join }.
def boolean(self):
res = self.join()
while self.token.tag == Tag.OPERATOR and self.token.value == "||":
res = BinaryExpression(res, self.match(Tag.OPERATOR), self.join(), self.lexer.line)
return res
# join = relation { "&&" relation }.
def join(self):
res = self.relation()
while self.token.tag == Tag.OPERATOR and self.token.value == "&&":
res = BinaryExpression(res, self.match(Tag.OPERATOR), self.relation(), self.lexer.line)
return res
# relation = expression { ( "==" | "!=" | "<" | "<=" | ">=" | ">" ) expression }.
def relation(self):
res = self.expression()
while self.token.tag == Tag.OPERATOR and self.token.value in ["==", "!=", "<", "<=", ">=", ">"]:
res = BinaryExpression(res, self.match(Tag.OPERATOR), self.expression(), self.lexer.line)
return res
# expression = term { ( "+" | "-" ) term }.
def expression(self):
res = self.term()
while self.token.tag == Tag.OPERATOR and self.token.value in ["+", "-"]:
res = BinaryExpression(res, self.match(Tag.OPERATOR), self.term(), self.lexer.line)
return res
# term = unary { ( "*" | "/" | "%" ) unary }.
def term(self):
res = self.unary()
while self.token.tag == Tag.OPERATOR and self.token.value in ["*", "/", "%"]:
res = BinaryExpression(res, self.match(Tag.OPERATOR), self.unary(), self.lexer.line)
return res
# unary = "!" unary | "-" unary | factor.
def unary(self):
if self.token.tag == Tag.OPERATOR and self.token.value in ["!", "-"]:
return UnaryExpression(self.match(Tag.OPERATOR), self.unary(), self.lexer.line)
return self.factor()
# factor = "(" boolean ")" | integer | "true" | "false" | ident | function_call.
def factor(self):
if self.token.tag == Tag.LPAREN:
self.move()
res = self.boolean()
self.match(Tag.RPAREN)
return res
if self.token.tag == Tag.NUMBER:
return Constant(self.match(Tag.NUMBER), self.lexer.line)
if self.token.tag == Tag.TRUE:
self.move()
return Constant(1, self.lexer.line)
if self.token.tag == Tag.FALSE:
self.move()
return Constant(0, self.lexer.line)
if self.token.tag == Tag.IDENT:
line = self.lexer.line
name = self.match(Tag.IDENT)
if not self.scope.contains(name):
raise SyntaxError("%s is not declared in line %d" % (name, line))
return Variable(name, line)
return self.function_call()
# function_call = "call" ident "[" [ expression_list ] "]".
def function_call(self):
name = self.match(Tag.CALL, Tag.IDENT)
self.match(Tag.LBRAK)
args = [] if self.token.tag == Tag.RBRAK else self.expression_list()
self.match(Tag.RBRAK)
return FunctionCall(name, args, self.lexer.line)
# ident_list = ident { "," ident }.
def ident_list(self):
ident = [self.match(Tag.IDENT)]
while self.token.tag == Tag.COMMA:
self.move()
ident.append(self.match(Tag.IDENT))
return ident
# expression_list = boolean { "," boolean }.
def expression_list(self):
exp = [self.boolean()]
while self.token.tag == Tag.COMMA:
self.move()
exp.append(self.boolean())
return exp
# function_list = function { function }.
def function_list(self):
funcs = [self.function()]
while self.token:
funcs.append(self.function())
return funcs
# statement_list = statement { statement }.
def statement_list(self):
if self.token.tag in [Tag.END, Tag.ELSE]:
return None
return Sequence(self.statement(), self.statement_list(), self.lexer.line)
# function = "fun" ident "[" [ ident_list ] "]" nl statement_list "end" nl.
def function(self):
line = self.lexer.line
name = self.match(Tag.FUN, Tag.IDENT)
self.match(Tag.LBRAK)
args = [] if self.token.tag == Tag.RBRAK else self.ident_list()
self.match(Tag.RBRAK, Tag.NEWLINE)
self.scope.new(name, args)
block = self.statement_list()
self.match(Tag.END, Tag.NEWLINE)
return Function(name, args, block, line)
# statement = [ if_statement | while_statement | assign_statement | return_statement | function_call ].
def statement(self):
return {Tag.IF: self.if_statement,
Tag.WHILE: self.while_statement,
Tag.IDENT: self.assignment,
Tag.RETURN: self.return_statement,
Tag.CALL: self.function_call,
}[self.token.tag]()
# if_statement = "if" boolean nl statement_list [ "else" nl statement_list ] "end" nl.
def if_statement(self):
line = self.lexer.line
self.match(Tag.IF)
condition = self.boolean()
self.match(Tag.NEWLINE)
true_case = self.statement_list()
else_case = None
if self.token.tag == Tag.ELSE:
self.move()
self.match(Tag.NEWLINE)
else_case = self.statement_list()
self.match(Tag.END, Tag.NEWLINE)
return IfStatement(condition, true_case, else_case, line)
# while_statement = "while" boolean nl statement_list "end" nl.
def while_statement(self):
line = self.lexer.line
self.match(Tag.WHILE)
condition = self.boolean()
self.match(Tag.NEWLINE)
body = self.statement_list()
self.match(Tag.END, Tag.NEWLINE)
return WhileStatement(condition, body, line)
# return_statement = "@" boolean nl.
def return_statement(self):
line = self.lexer.line
self.match(Tag.RETURN)
exp = self.boolean()
self.match(Tag.NEWLINE)
return ReturnStatement(exp, line)
# assignment = ident "=" boolean nl.
def assignment(self):
line = self.lexer.line
name = self.match(Tag.IDENT)
self.match(Tag.ASSIGNMENT)
exp = self.boolean()
self.match(Tag.NEWLINE)
self.scope.add(name)
return AssignStatement(name, exp, line)
# program = function_list.
def program(self):
return Program(self.function_list())
|
