-
Notifications
You must be signed in to change notification settings - Fork 1
/
semanticAnalyser.coffee
389 lines (298 loc) · 13.6 KB
/
semanticAnalyser.coffee
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
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
[RBTree, RBTNode] = require './rbtree.coffee'
Types = require './constants.coffee'
class Semantics
constructor: ->
@Dictionary = []
@ASTParser = new AST
@globalScopeName = 'top'
@Dictionary[@globalScopeName] = [null, new RBTree]
@initialise()
# builds label tree and performs semantic checking
analyse: (parseTree) ->
@findDeclarations parseTree, @globalScopeName
@check parseTree, @globalScopeName
# Actually performs semantic checking of the program
# for IO calls the values given need just to be defined
# for became both sides of the operation have to be of same type
# for ate and drank checks whether argument is a number
# for any other function call definition types and run time types need to be the same
# for loops and ifs checks whether condition evaluates to boolean type
# for return statements if there is enclosing function it tries to match function return type and type of return statement
check: (node, scope) ->
if node?
switch node.type
when Types.NODE_IO
[varType, position] = @ASTParser.ioCall node
if varType is Types.NODE_VAR
@isDefined node.children[0], scope
else if varType is Types.NODE_FUN_CALL
@check node.children[0], scope
@isDefined node.children[0], @globalScopeName
else if varType is Types.NODE_OP
@isOfType node.children[0], scope, Types.TYPE_NUMBER
when Types.NODE_FUN_CALL
functionName = node.value
functionNode = @isDefined node, @globalScopeName
if functionName is 'had' or functionName is 'was a' then return
if functionName is 'became'
[lhs, rhs, position] = @ASTParser.functionCallBecame node
varType = (@isDefined lhs, scope).returnType
if rhs.type is Types.NODE_OP
@isOfType rhs, scope, Types.TYPE_NUMBER
varReturnType = Types.TYPE_NUMBER
else if rhs.type is Types.NODE_FUN_CALL
@check rhs, scope
varReturnType = (@isDefined rhs, @globalScopeName).returnType
else if rhs.type is Types.NODE_VAR
varReturnType = (@isDefined rhs, scope).returnType
else if rhs.type is Types.NODE_VAR_ARRAY_ELEM
varReturnType = (@isDefined rhs, scope).returnType
else
varReturnType = rhs.children[0].value
if varType isnt varReturnType
throw new SemanticError "Both sides of assignment have to be of same type\n" + "lhs is of type '" + varType + "'\n rhs is of type '" + varReturnType + "'", position
else if functionName is 'ate' or functionName is 'drank'
varReturnType = (@isDefined node.children[0], scope).returnType
if varReturnType isnt Types.TYPE_NUMBER
throw new SemanticError "Trying to pass variable of type '" + varReturnType + "'.\n" + "Ate and drank operators are defined only for numbers", position
else
typeCheck = functionNode.typeCheck
callingTypes = node.children.map (node, index) => @computeExpressionType node, scope
sameTypes = typeCheck callingTypes
if not sameTypes
throw new SemanticError "Could not find matching function for call '" + functionName + "'' with types '" + callingTypes.join "', '" + "'", node.position
when Types.NODE_LOOP
[whileCondition, whileBody, position] = @ASTParser.whileBlock node
# loops can have their own scope so we need to check variable existence in new scope
whileScope = Types.NODE_LOOP + "@" + position.line
@isOfType whileCondition, scope, null
@check child, whileScope for child in whileBody
when Types.NODE_IF, Types.NODE_ELSE_IF
[ifCondition, ifBody, position] = @ASTParser.ifBlock node
@isOfType ifCondition, scope, null
@check child, scope for child in ifBody
when Types.NODE_ELSE
@check child, scope for child in node.children
when Types.NODE_RETURN
[returnNode, position] = @ASTParser.returnCall node
if node.children[1]?
throw new SemanticError "Functions can only return one value", position
returnType = @computeExpressionType returnNode, scope
enclosingFunction = @lookup @globalScopeName, scope
# return statement doesn't have to have enclosing function
if enclosingFunction? and returnType isnt enclosingFunction.returnType
throw new SemanticError "Return type: '" + returnType + "' doesn't agree with function '" + enclosingFunction.key + "' return type '" + enclosingFunction.returnType + "'", position
@check returnNode, scope
when Types.NODE_FUN_DEF
[functionName, functionHeader, returnType, position] = @ASTParser.functionDefinition node
[retType, header, functionBody...] = node.children
@check child, functionName for child in functionBody
when Types.NODE_LOOK
functionNode = @isDefined node, @globalScopeName
varReturnType = (@isDefined node.children[0], scope).returnType
functionNode.typeCheck varReturnType
when Types.NODE_LOOK_DEF
[glassName, returnType, position] = @ASTParser.lookingGlassDefinition node
[retType, lookBody...] = node.children
@check child, glassName for child in lookBody
else
@check child, scope for child in node.children
# checks whether node in the current scope is of given type
isOfType: (node, scope, type) ->
expectedType = type
condTypes = (exp) =>
switch exp.type
when Types.NODE_OP
condTypes subExp for subExp in exp.children
if exp.value in Types.boolOperators
foundType = expectedType
else
foundType = Types.TYPE_NUMBER
when Types.NODE_CONST
foundType = exp.children[0].value
when Types.NODE_VAR
foundType = (@isDefined exp, scope).returnType
when Types.NODE_VAR_ARRAY_ELEM
foundType = (@isDefined exp, scope).returnType
when Types.NODE_FUN_CALL
@check child, scope for child in exp.children
foundType = (@isDefined exp, @globalScopeName).returnType
if expectedType?
if foundType isnt expectedType
throw new SemanticError "Wrong type in expression.\n" + "Expected: " + expectedType + "\n Found: " + foundType, exp.position
else
expectedType = foundType
condTypes node
# function that defines how to perform type checking on user defined functions
functionTypeCheck: (types) ->
(runTimeArgs) =>
unifiedTypes = types.map (typeVar, index) -> typeVar is runTimeArgs[index]
unifiedTypes.reduce ((previous, current) -> previous and current), yes
# returns type of give node in its scope
computeExpressionType: (node, scope) ->
switch node.type
when Types.NODE_VAR_ARRAY_ELEM
(@isDefined node, scope).returnType
when Types.NODE_VAR
(@isDefined node, scope).returnType
when Types.NODE_CONST
node.children[0].value
when Types.NODE_OP
@isOfType node, scope, Types.TYPE_NUMBERO
Types.TYPE_NUMBER
when Types.NODE_FUN_CALL
@check child, scope for child in node.children
(@isDefined node, @globalScopeName).returnType
# walks parse tree and populates label tree with definitions of functions and variables from parse tree
findDeclarations: (node, scope) ->
if node?
switch node.type
when Types.NODE_LOOK_DEF
[glassName, returnType, position] = @ASTParser.lookingGlassDefinition node
functionNode = @lookup @globalScopeName, glassName
if functionNode?
throw new SemanticError "Function '" + glassName + "' has already been declared.\n Trying to redeclare", position
(@getScope @globalScopeName).rbInsert new RBTNode glassName, position, returnType, @functionTypeCheck [returnType]
newScope = new RBTree
newScope.rbInsert new RBTNode 'it', position, returnType, @functionTypeCheck [returnType]
@Dictionary[glassName] = [null, newScope]
[retType, lookBody...] = node.children
@findDeclarations child, glassName for child in lookBody
when Types.NODE_FUN_DEF
[functionName, functionHeader, returnType, position] = @ASTParser.functionDefinition node
functionNode = @lookup @globalScopeName, functionName
if functionNode?
throw new SemanticError "Function '" + functionName + "' has already been declared.\n Trying to redeclare", position
(@getScope @globalScopeName).rbInsert new RBTNode functionName, position, returnType, @functionTypeCheck functionHeader
[retType, header, functionBody...] = node.children
newScope = new RBTree
header.children.forEach (argument, index, funcNode) =>
[varName, varType, position] = @ASTParser.variableDeclaration argument
newScope.rbInsert new RBTNode varName, position, varType, @functionTypeCheck [varType]
@Dictionary[functionName] = [null, newScope]
@findDeclarations child, functionName for child in functionBody
when Types.NODE_LOOP
[whileCondition, whileBody, position] = @ASTParser.whileBlock node
whileScope = Types.NODE_LOOP + "@" + position.line
@Dictionary[whileScope] = [scope, new RBTree]
@findDeclarations child, whileScope for child in whileBody
when Types.NODE_FUN_CALL
if node.value is 'was a'
[varName, varType, position] = @ASTParser.variableDeclaration node
varNode = @lookup scope, varName
if varNode?
throw new SemanticError "Variable '" + varName + "' has already been declared as '" + varNode.returnType + "'.\n Trying to redeclare as '" + varType + "'", position
(@getScope scope).rbInsert new RBTNode varName, position, varType, @functionTypeCheck [varType]
if node.value is 'had'
[arrName, arrType, position] = @ASTParser.arrayDeclaration node
arrNode = @lookup scope, arrName
if arrNode?
throw new SemanticError "Array '" + arrName + "' has already been declared as '" + arrNode.returnType + "'.\n Trying to redeclare as '" + arrType + "'", position
(@getScope scope).rbInsert new RBTNode arrName, position, arrType, @functionTypeCheck [arrType]
else
@findDeclarations node, scope for node in node.children
# perform lookup of name within scope
lookup: (scope, name) ->
@getScope(scope).rbFind name
# performs lookup of name but bubbles up until no enclosing scope exists
totalLookup: (scope, name) ->
if scope?
lookupResult = @lookup scope, name
if not lookupResult?
return @totalLookup (@getOuterScope scope), name
else
return lookupResult
else
return null
getScope: (scope) ->
@Dictionary[scope][1]
getOuterScope: (scope) ->
@Dictionary[scope][0]
# Populates label tree with language defined functions to prevent overwriting
initialise: () ->
globalScope = @getScope(@globalScopeName)
globalScope.rbInsert (new RBTNode 'was a', null, null)
globalScope.rbInsert (new RBTNode 'became', null, null)
globalScope.rbInsert (new RBTNode 'what was', null, null)
globalScope.rbInsert (new RBTNode 'spoke', null, null)
globalScope.rbInsert (new RBTNode 'said Alice', null, null)
globalScope.rbInsert (new RBTNode 'ate', Types.TYPE_NUMBER, null)
globalScope.rbInsert (new RBTNode 'drank', Types.TYPE_NUMBER, null)
globalScope.rbInsert (new RBTNode 'had', null, null)
globalScope.rbInsert (new RBTNode Types.NODE_OP, Types.TYPE_NUMBER, null)
# Checks whether node is defiend with the scope.
# If yes returns the label tree node associated with this parse tree node.
isDefined: (node, scope) ->
switch node.type
when Types.NODE_FUN_CALL
functionNode = @lookup scope, node.value
if not functionNode?
throw new SemanticError "Call to undefined function: " + node.value, node.position
functionNode
when Types.NODE_VAR
varNode = @totalLookup scope, node.value
if not varNode?
throw new SemanticError "Variable '" + node.value + "' hasn't been declared", node.position
varNode
when Types.NODE_VAR_ARRAY_ELEM
varArr = @totalLookup scope, node.children[0].value
if not varArr?
throw new SemanticError "Array '" + node.children[0].value + "' hasn't been declared", node.position
varArr
when Types.NODE_LOOK
glassNode = @lookup @globalScopeName, node.value
if not glassNode?
throw new SemanticError "Call to undefined function: " + node.value, node.position
glassNode
# Class representing error of semantic analyser
SemanticError: class SemanticError extends Error
constructor: (@message, position) ->
@line = position.line
@column = position.column
@name = 'SemanticError'
class AST
constructor: ->
variableDeclaration: (node) ->
varName = node.children[0].value
varType = node.children[1].value
position = node.position
[varName, varType, position]
arrayDeclaration: (node) ->
arrName = node.children[0].value
arrType = node.children[2].value
position = node.position
[arrName, arrType, position]
functionDefinition: (node) ->
returnType = node.children[0].value
functionName = node.children[1].value
functionHeader = node.children[1].children.map (argument, index) ->
argument.children[1].value
position = node.position
[functionName, functionHeader, returnType, position]
lookingGlassDefinition: (node) ->
returnType = node.children[0].value
glassName = node.value
position = node.position
[glassName, returnType, position]
functionCallBecame: (node) ->
lhs = node.children[0]
rhs = node.children[1]
position = node.position
[lhs, rhs, position]
ioCall: (node) ->
varType = node.children[0].type
position = node.position
[varType, position]
returnCall: (node) ->
returnNode = node.children[0]
position = node.position
[returnNode, position]
ifBlock: (node) ->
[ifCondition, ifBody...] = node.children
position = node.position
[ifCondition, ifBody, position]
whileBlock: (node) ->
[whileCondition, whileBody...] = node.children
position = node.position
[whileCondition, whileBody, position]
module.exports = Semantics