source: proto/s2k/trunk/framework/src/toolchain/s2k/semanticAnalyzer/SemanticAnalyzer.java @ 4021

Last change on this file since 4021 was 4021, checked in by ksherdy, 5 years ago

Restructure s2k package.

File size: 16.1 KB
Line 
1package toolchain.s2k.semanticAnalyzer;
2import java.util.List;
3
4
5
6import s2k.ast.*;
7import s2k.inputHandler.Locator;
8import s2k.lexicalAnalyzer.Lextant;
9import s2k.logging.ScatterLogger;
10import s2k.tokens.LextantToken;
11import toolchain.s2k.ast.Accessors;
12import toolchain.s2k.lang.builtin.S2KBuiltinsTypeBuilder;
13import toolchain.s2k.lang.signatures.*;
14import toolchain.s2k.lang.type.*;
15
16public class SemanticAnalyzer {
17   
18    //////////////////////////////////////////////////////////////
19    // static interface
20    public static ASTNode analyze(ASTNode ASTree) {
21        SemanticAnalysisVisitor analyzer = new SemanticAnalysisVisitor();
22        ASTree.accept(analyzer);
23        return ASTree;
24    }
25
26    static private class SemanticAnalysisVisitor extends VoidVisitor.Default {
27
28                @Override
29                public void visitLeave(ASTNode node) {
30                        throw new IllegalStateException("unimplemented node type " + node.getClass().getName() + " in SemanticAnalysisVisitor");
31                }
32
33                //
34                // p r o g r a m 
35                //
36                @Override
37                public void visitEnter(ProgramNode node) {
38                        node.setSymbolTable(new SymbolTable());
39                        S2KBuiltinsTypeBuilder.installOn(node);
40                }
41                @Override
42                public void visitLeave(ProgramNode node) {}
43               
44                //
45                // s t r e a m   s t r u c t   d e c l a r a t i o n s 
46                //
47                @Override
48                public void visitEnter(StructDefNode node) {
49                        node.setSymbolTable(new SymbolTable());
50                }
51                @Override
52                public void visitLeave(StructDefNode node) {
53                        Binding binding = bindingForStructDefinition(node);
54                        installOnEnclosingSymbolTable(node, binding);
55                }               
56                private Binding bindingForStructDefinition(StructDefNode node) {
57                        SymbolTable symbolTable = node.getSymbolTable();
58                        Type structType = StructureType.make(symbolTable);
59                        return Binding.make(Accessors.name(node), structType);
60                }
61
62                @Override
63                public void visitLeave(StructDefBodyNode node) {}
64                @Override
65                public void visitLeave(StructMemberNode node) {
66                        Type declarationType = Accessors.declarationType(node);
67                        String variableName = Accessors.name(node);
68                       
69                        Binding binding = Binding.make(variableName, declarationType); 
70                        installOnEnclosingSymbolTable(node, binding);
71                       
72                        node.setType(declarationType);
73                }
74               
75            //
76                // s t r e a m   f u n c t i o n   d e c l a r a t i o n s                                                     
77                //
78                /*
79                @Override
80                public void visitEnter(FuncDefNode node) {
81                        node.setSymbolTable(new SymbolTable());
82                }
83                */
84                /*
85                @Override
86                public void visitLeave(FuncDefNode node) {
87                        Binding binding = bindingForFunctionDefinition(node);
88                        installOnEnclosingSymbolTable(node, binding);
89                }
90               
91                private Binding bindingForFunctionDefinition(FuncDefNode node) {
92                        Type[] types = typeArrayForSignature(node);
93                        FunctionSignature signature = new FunctionSignature(null, types);
94                        Type functionType = FunctionType.make(signature);
95                       
96                        return Binding.make(Accessors.funcName(node), functionType );
97                }
98               
99                private Type[] typeArrayForSignature(FuncDefNode node) {
100                        int numTypes = Accessors.numParameters(node) + 1;
101                        Type[] types = new Type[numTypes];
102                       
103                        if(Accessors.hasParameters(node)) {
104                                for(int i=0; i<numTypes-1; i++) {
105                                        ParameterNode param = Accessors.parameter(node, i);
106                                        types[i] = param.getType();
107                                }
108                        }
109                        Type returnType = Accessors.type(node);
110                        types[numTypes-1] = returnType;
111                       
112                        return types;
113                }
114                */
115                /*
116                @Override
117                public void visitLeave(ParameterListNode node) {}
118                @Override
119                public void visitLeave(ParameterNode node) {
120                        Type declarationType = Accessors.declarationType(node);
121                        String variableName = Accessors.name(node);
122                       
123                        Binding binding = Binding.make(variableName, declarationType);
124                        installOnEnclosingSymbolTable(node, binding);
125                       
126                        node.setType(declarationType);
127                }
128                */
129               
130                //
131                // b l o c k   s t a t e m e n t s
132                //
133                @Override
134                public void visitLeave(BlockStmtNode node) {
135                        for(ASTNode child: node.getChildren()) {
136                                if(isAnExpression(child) && !(child instanceof FuncCallNode)) {
137                                        expressionStatementError(child);
138                                }
139                        }
140                }
141                // this mechanism is fragile w.r.t. additional expression types.
142                private boolean isAnExpression(ASTNode node) {
143                        return (node instanceof BinaryOperatorNode) ||
144                                   (node instanceof UnaryOperatorNode)  ||
145                                   (node instanceof FuncCallNode)       ||
146                                   (node instanceof IdentifierNode)     ||
147                                   (node instanceof CompoundIdentifierNode)  ||
148                                   (node instanceof IntegerConstantNode) ||
149                                   (node instanceof StringConstantNode);
150                }
151
152                //
153                // s t a t e m e n t s
154                //
155                @Override
156                public void visitLeave(VarDeclNode node) {
157                        ASTNode typeNode = Accessors.typeNode(node);
158                       
159                        if(Accessors.hasInitializationExpr(node)) {
160                                ASTNode rhs = Accessors.rhs(node);
161                                typecheckAssignment(node, typeNode, rhs);
162                        }
163                        else {
164                                node.setType(typeNode.getType());
165                        }
166                       
167                        IdentifierNode identifierNode = Accessors.identifier(node);
168                        String variableName = Accessors.lexeme(identifierNode);
169
170                        Binding binding = Binding.make(variableName, typeNode.getType());
171                        installOnEnclosingSymbolTable(node, binding);
172                }
173
174                private void installOnEnclosingSymbolTable(ASTNode node, Binding binding) {
175                        SymbolTable symbolTable = findEnclosingSymbolTable(node);
176                        String variableName = binding.getName();
177                       
178                        if(symbolTable.hasBinding(variableName)) {
179                                multipleDefinitionError(node, variableName);
180                        }
181                        else {
182                                symbolTable.add(binding);
183                        }
184                }
185                // issues error and returns null instance if no symbol table found.
186                // does not search on the given node.
187                private SymbolTable findEnclosingSymbolTable(ASTNode node) {
188                        ASTNode parent = node.getParent();
189                        for(ASTNode ancestor: parent.pathToRoot()) {
190                                if( ancestor instanceof HasSymbolTableNodeType) {
191                                        return ((HasSymbolTableNodeType)ancestor).getSymbolTable();
192                                }
193                        }
194                        notInFunctionBodyError(node, "declaration");
195                        return SymbolTable.getNullInstance();
196                }
197
198
199                private void typecheckAssignment(ASTNode parent, ASTNode lhs, ASTNode rhs) {
200                        Type variableType = lhs.getType();
201                        Type assignedType = rhs.getType();
202                        if(!canBeAssignmentTypes(variableType, assignedType)) {
203                                operatorTypeCheckError(parent, "ASSIGN", variableType, assignedType);
204                        }
205                        parent.setType(variableType);
206                }
207                private boolean canBeAssignmentTypes(Type variableType, Type assignedType) {
208                        return variableType.equals(assignedType);
209                }
210
211                @Override
212                public void visitLeave(AssignNode node) {
213                        typecheckAssignment(node, Accessors.lhs(node), Accessors.rhs(node));
214                }
215                @Override
216                public void visitLeave(IfStmtNode node) {
217                        // TODO - TS: check condition node is type STREAM(1)?
218                }
219                @Override
220                public void visitLeave(WhileStmtNode node) {
221                        // TODO - TS: check condition node is type STREAM(1)?
222                }
223                /*
224                @Override
225
226                public void visitLeave(ReturnStmtNode node) {
227                        FuncDefNode function = findEnclosingFunctionNode(node);
228                        Type functionType = Accessors.type(function);
229                        Type returnType = (node.nChildren() == 0) ? PrimitiveType.VOID
230                                                                              : node.child(0).getType();
231                        if(!canBeAssignmentTypes(functionType, returnType)) {
232                                returnTypecheckError(node);
233                        }
234                       
235                        node.setType(returnType);
236                }
237                */
238                /*
239                // issues error and returns null instance if no function node found.
240                private FuncDefNode findEnclosingFunctionNode(ASTNode node) {
241                        for(ASTNode ancestor: node.pathToRoot()) {
242                                if( ancestor instanceof FuncDefNode) {
243                                        return (FuncDefNode)ancestor;
244                                }
245                        }
246                        notInFunctionBodyError(node, "return ");
247                        return null;
248                }
249                */
250                //
251                // e x p r e s s i o n s
252                //
253
254                @Override
255                public void visitLeave(BinaryOperatorNode node) {
256                        operatorNodeVisit(node);
257                }
258
259                @Override
260                public void visitLeave(UnaryOperatorNode node) {
261                        operatorNodeVisit(node);
262                }
263
264                private void operatorNodeVisit(ASTNode node) {
265                        LextantToken token = (LextantToken)node.getToken();
266                        Lextant operator = token.getLextant();
267                        FunctionSignatures signatures = OperatorSignatures.getSignatures(operator);
268                        List<Type> types = Accessors.childTypes(node);
269                       
270                        if(signatures.accepts(types)) {
271                                FunctionSignature signature = signatures.acceptingSignature(types);
272                                Type returnType = signature.resultType();
273                                ((HasSignatureNodeType)node).setSignature(signature);
274                                node.setType(returnType);
275                        }
276                        else {
277                                operatorTypeCheckError(node, operator.name(), types);
278                                ((HasSignatureNodeType)node).setSignature(FunctionSignature.nullInstance());
279                                node.setType(PrimitiveType.ERROR);
280                        }
281                }
282               
283            //   
284                // f u n c t i o n   c a l l s
285                //
286                @Override
287                public void visitLeave(FuncCallNode node) {
288                        Binding binding = nameBinding(node);
289                        Type bindingType = binding.getType();
290                        if(bindingType instanceof FunctionType) {
291                                FunctionType functionType = (FunctionType)bindingType;
292                                FunctionSignatures signatures = functionType.getSignatures();
293                                List<Type> types = Accessors.argumentTypes(node);
294                               
295                                if(signatures.accepts(types)) {
296                                        FunctionSignature signature = signatures.acceptingSignature(types);
297                                        Type returnType = signature.resultType();
298                                        node.setSignature(signature);
299                                        node.setType(returnType);
300                                }
301                                else {
302                                        functionTypeCheckError(node, types);
303                                        node.setSignature(FunctionSignature.nullInstance());
304                                        node.setType(PrimitiveType.ERROR);
305                                }
306                        }
307                        else {
308                                notAFunctionError(node);
309                                node.setType(PrimitiveType.ERROR);
310                        }       
311                }       
312
313
314                private Binding nameBinding(FuncCallNode node) {
315                        HasBindingNodeType nameNode = (HasBindingNodeType)(Accessors.nameNode(node));
316                        return nameNode.getBinding();
317                }
318                @Override
319                public void visitLeave(FuncCallArgListNode node) {}
320               
321               
322            //   
323                // i d e n t i f i e r s
324                //
325                @Override
326                public void visitEnter(CompoundIdentifierNode node) {
327                        node.skipChildren();
328                }
329                @Override
330                public void visitLeave(CompoundIdentifierNode node) {
331                        Binding binding = findCompoundBinding(node);
332                        node.setBinding(binding);
333                }
334
335                private Binding findCompoundBinding(CompoundIdentifierNode node) {
336                        Binding binding = headBinding(node);
337                       
338                        for(ASTNode child: Accessors.tailChildren(node)) {
339                                if(binding.isCompoundInstance()) {
340                                        binding = nextChildBinding(node, binding, child);
341                                }
342                                else {
343                                        noncompoundError(node, binding, child);
344                                        binding = Binding.getNullInstance();
345                                        break;
346                                }
347                        }
348                        return binding;
349                }
350                private void noncompoundError(CompoundIdentifierNode parent, Binding binding, ASTNode child) {
351                        if(!binding.isNull()) {
352                                semanticError(parent, "subcomponent " + Accessors.nameUpTo(parent, child) + " is not a package or an instance of a compound type." );
353                        }
354                }
355                private Binding nextChildBinding(CompoundIdentifierNode parent, Binding binding, ASTNode child) {
356                        CompoundType leftType = (CompoundType)(binding.getType());
357                        SymbolTable symbolTable = leftType.getSymbolTable();
358                        binding = bindingOrError(parent, symbolTable, child);
359                        return binding;
360                }
361                private Binding bindingOrError(CompoundIdentifierNode parent, SymbolTable symbolTable, ASTNode child) {
362                        String name = Accessors.lexeme(child);
363                        if(symbolTable.hasBinding(name)) {
364                                return  symbolTable.bindingFor(name);
365                        }
366                        else {
367                                semanticError(parent, "subcomponent " + name + " undefined in " + Accessors.nameBefore(parent, child) + ". ");
368                                return  Binding.getNullInstance();
369                        }
370                }
371                private Binding headBinding(CompoundIdentifierNode node) {
372                        ASTNode headChild = Accessors.headChild(node); 
373                        return bindingOrError(node, headChild);
374                }
375                private Binding bindingOrError(ASTNode startNode, ASTNode nameNode) {
376                        String name = Accessors.lexeme(nameNode);       
377                        for(ASTNode ancestor: startNode.pathToRoot()) {
378                                if(ancestor instanceof HasSymbolTableNodeType) {
379                                        SymbolTable symbolTable = ((HasSymbolTableNodeType) ancestor).getSymbolTable();
380                                        if(symbolTable.hasBinding(name)) {
381                                                return symbolTable.bindingFor(name);
382                                        }
383                                }
384                        }
385                        semanticError(startNode, "undefined identifier: " + name);
386                        return Binding.getNullInstance();
387                }
388               
389                @Override
390                public void visitLeave(IdentifierNode node) {
391                        ASTNode parent = node.getParent();
392                        if(parent instanceof CompoundIdentifierNode) {
393                                // let parent handle
394                        }
395                        else if(isBeingDefined(node)) {
396                                // parent creates binding, maybe gives this node a type.
397                        }
398                        else {
399                                Binding binding = bindingOrError(node, node);
400                                node.setBinding(binding);
401                        }
402                }
403                private boolean isBeingDefined(IdentifierNode node) {
404                        return isFunctionBeingDefined(node) || isVariableBeingDefined(node);
405                }
406
407                private boolean isFunctionBeingDefined(IdentifierNode node) {
408                        ASTNode parent = node.getParent();
409                        return ((parent instanceof FilterDefNode) && node == Accessors.funcIdentifier((FilterDefNode) parent));
410                }
411                private boolean isVariableBeingDefined(IdentifierNode node) {
412                        ASTNode parent = node.getParent();
413                        return ((parent instanceof VarDeclNode) && node == Accessors.identifier((VarDeclNode) parent));
414                }
415
416                //   
417                // c o n s t a n t s
418                //
419                @Override
420                public void visitLeave(IntegerConstantNode node) {
421                        node.setType(PrimitiveType.INTEGER);
422                }
423                @Override
424                public void visitLeave(StringConstantNode node) {
425                        node.setType(PrimitiveType.STRING);
426                }
427               
428            //   
429                // t y p e s
430                //
431                @Override
432                public void visitLeave(IntTypeNode node) {
433                        node.setType(PrimitiveType.INTEGER);
434                }
435                @Override
436                public void visitLeave(StreamTypeNode node) {
437                        Type type = StreamType.STREAM(node.getFieldWidth());
438                        node.setType(type);
439                }
440                @Override
441                public void visitLeave(StructTypeNode node) {
442                        ASTNode nameNode = Accessors.nameNode(node);
443                        Binding binding = bindingOrError(node, nameNode);
444                        Type bindingType = binding.getType();
445                       
446                        if(bindingType instanceof StructureType) {
447                                node.setType(bindingType);
448                        }
449                        else {
450                                notStructureTypeError(node, nameNode);
451                        }
452                       
453                }
454               
455            //   
456                // s h o u l d   n e v e r   s e e
457                //
458
459                @Override
460                public void visitLeave(FuncCallOrAssignStmtNode node) {
461                        // TS: I don't think this node ever occurs.
462                        assert(false);
463                }
464                @Override
465                public void visitLeave(ErrorNode node) {
466                        node.setType(PrimitiveType.ERROR);
467                }
468                @Override
469                public void visitLeave(EpsilonNode node) {
470                        node.setType(PrimitiveType.ERROR);
471                }
472               
473            //   
474                // e r r o r s
475                //
476                private void notStructureTypeError(ASTNode node, ASTNode nameNode) {
477                        semanticError(node, Accessors.lexeme(nameNode) + " not declared as struct type.");
478                }
479                private void expressionStatementError(ASTNode node) {
480                        semanticError(node, "expression found where statement or function call expected.");
481                }
482                private void returnTypecheckError(ReturnStmtNode node) {
483                        semanticError(node, "return type not compatible with declared function type.");
484                }
485                private void multipleDefinitionError(ASTNode node, String variableName) {
486                        semanticError(node, "identifier " + variableName + " multiply defined.");
487                }
488                private void notInFunctionBodyError(ASTNode node, String item) {
489                        semanticError(node, item + " outside of function body." );     
490                }
491                private void operatorTypeCheckError(ASTNode node, String operatorName, List<Type> operandTypes) {
492                        semanticError(node, "operator " + operatorName + " not defined for types " + operandTypes.toString() + ".");   
493                }                       
494                private void operatorTypeCheckError(ASTNode node, String operatorName, Type... operandTypes) {
495                        semanticError(node, "operator " + operatorName + " not defined for types " + operandTypes.toString() + ".");   
496                }       
497                private void functionTypeCheckError(FuncCallNode node, List<Type> operandTypes) {
498                        ASTNode nameNode = Accessors.nameNode(node);
499                        String name = Accessors.name((CompoundIdentifierNode)nameNode);
500                       
501                        semanticError(node, "function " + name + " not defined for types " + operandTypes.toString() + ".");   
502                }       
503                private void notAFunctionError(FuncCallNode node) {
504                        ASTNode nameNode = Accessors.nameNode(node);
505                        String name = Accessors.name((CompoundIdentifierNode)nameNode);
506                        semanticError(node, "symbol " + name + " used as a function name but not declared as a function.");
507                }
508                private void semanticError(Locator locator, String errorDescription) {
509                        ScatterLogger log = ScatterLogger.getLogger("s2k.SemanticAnalyzer");
510                        String message = "" + locator.getLocation() + ": " + "semantic error--" + errorDescription;
511                        log.severe(message);
512                }       
513               
514                @SuppressWarnings("unused")
515                private void logError(String message) {
516                        ScatterLogger log = ScatterLogger.getLogger("s2k.semanticAnalyzer");
517                        log.severe(message);
518                }
519                @SuppressWarnings("unused")
520                private String at(Locator locator) {
521                        return " at " + locator.getLocation(); 
522                }
523        }
524}
Note: See TracBrowser for help on using the repository browser.