Type checking is the processes of identifying errors in a program based on expli
ID: 3902344 • Letter: T
Question
Type checking is the processes of identifying errors in a program based on explicitly or implicitly stated type information. In the third project, you need to implement a type checker for your C subset. The checker needs to - Create a symbol table - Insert the type of each variable into the symbol table - Perform the type checking for each expression The basic type checking rules are summarized as follows. You can add your rules for your C subset (1) Each variable must be declared before it is used (2) Each identifier can be only declared once (3) The types of the operands of an operator must be the same (4) The types of the two sides of an assignment must be the same The type checker needs to report an error message for each type error detected Each type error message should contain the line number where the error is detected and an explanation of the error. The format for printing a type error message is as follows: "Type Error:" line number ":" the error message. For a sample C program given as follows 1. void main () int num; int s int index; float S; num - index 3.21; The type checker will report the following error messagesExplanation / Answer
import net.bemacized.scriptmaseve.datamodel.DataSymbol;
import net.bemacized.scriptmaseve.datamodel.DataType;
import net.bemacized.scriptmaseve.datamodel.MethodSymbol;
import net.bemacized.scriptmaseve.datamodel.Scope;
import net.bemacized.scriptmaseve.exceptions.CompileException;
import org.antlr.v4.runtime.ParserRuleContext;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
public class TypeChecker extends ScriptmasEveBaseVisitor {
private Scope scope;
private boolean hasMain;
public TypeChecker() {
scope = new Scope();
}
@Override
public Object visitProgram(ScriptmasEveParser.ProgramContext ctx) {
visit(ctx.programBody());
//Assert main
if (!hasMain)
throw new CompileException("This script has no main function declared!");
return null;
}
@Override
public Object visitProgramBody(ScriptmasEveParser.ProgramBodyContext ctx) {
visitChildren(ctx);
return null;
}
@Override
public Object visitDeclarationStatement(ScriptmasEveParser.DeclarationStatementContext ctx) {
//Attempt declaration
String varName = ctx.NAME().getText();
DataType dataType = DataType.getByDatatype(ctx.DATATYPE().getText());
scope.declareVariable(varName, dataType);
return null;
}
@Override
public Object visitInitializedDeclarationStatement(ScriptmasEveParser.InitializedDeclarationStatementContext ctx) {
//Attempt declaration
String varName = ctx.assignment().NAME().getText();
DataType dataType = DataType.getByDatatype(ctx.DATATYPE().getText());
scope.declareVariable(varName, dataType);
//Initialize variable
visit(ctx.assignment());
return null;
}
@Override
public Object visitAssignment(ScriptmasEveParser.AssignmentContext ctx) {
//Resolve assignment
DataType data = (DataType) visit(ctx.expression());
//Obtain destination symbol
String varName = ctx.NAME().getText();
DataSymbol var = scope.getVariable(varName);
if (var == null) throw new CompileException("No variable with name '" + varName + "' has been declared.");
//Check types
if (var.getType() != data)
throw new CompileException("Assignment value did not match variable type. Variable type '" + var.getType().getRepresentation() + "', found type '" + data.getRepresentation() + "'.");
//Initialize variable
var.setInitialized(true);
return null;
}
@Override
public DataType visitAddSubExpression(ScriptmasEveParser.AddSubExpressionContext ctx) {
DataType p1 = (DataType) visit(ctx.expression(0));
DataType p2 = (DataType) visit(ctx.expression(1));
//Concatenate with string
if (!(p1 == DataType.INT_TYPE && p2 == DataType.INT_TYPE) && ctx.AddMinOperator.getText().equals("+")) {
if ((p1 == DataType.VOID_TYPE || p2 == DataType.VOID_TYPE))
throw new CompileException("You can only concatenate !CHILD, @CHILD or #CHILD types to a string!");
return DataType.STRING_TYPE;
}
//Math
if (p1 != DataType.INT_TYPE)
throw new CompileException("You can only add or subtract #CHILD values. " + p1.getRepresentation() + " found instead on first parameter.");
if (p2 != DataType.INT_TYPE)
throw new CompileException("You can only add or subtract #CHILD values. " + p2.getRepresentation() + " found instead on second parameter.");
return DataType.INT_TYPE;
}
@Override
public DataType visitBooleanValueExpression(ScriptmasEveParser.BooleanValueExpressionContext ctx) {
return DataType.BOOL_TYPE;
}
@Override
public DataType visitMultDivModExpression(ScriptmasEveParser.MultDivModExpressionContext ctx) {
DataType p1 = (DataType) visit(ctx.expression(0));
DataType p2 = (DataType) visit(ctx.expression(1));
if (p1 != DataType.INT_TYPE)
throw new CompileException("You can only perform * / and % operations on #CHILD values. " + p1.getRepresentation() + " found instead on first parameter.");
if (p2 != DataType.INT_TYPE)
throw new CompileException("You can only perform * / and % operations on #CHILD values. " + p2.getRepresentation() + " found instead on second parameter.");
return DataType.INT_TYPE;
}
@Override
public DataType visitPriorityExpression(ScriptmasEveParser.PriorityExpressionContext ctx) {
return (DataType) visit(ctx.expression());
}
@Override
public DataType visitStringValueExpression(ScriptmasEveParser.StringValueExpressionContext ctx) {
return DataType.STRING_TYPE;
}
@Override
public DataType visitVarExpression(ScriptmasEveParser.VarExpressionContext ctx) {
//Obtain symbol from scope
DataSymbol symbol = scope.getVariable(ctx.getText());
if (symbol == null)
throw new CompileException("There is no variable with name '" + ctx.getText() + "' declared in the current context.");
if (!symbol.isInitialized())
throw new CompileException("Variable '" + ctx.getText() + "' has potentially not been initialized yet.");
return symbol.getType();
}
@Override
public DataType visitNestedConditionalExpression(ScriptmasEveParser.NestedConditionalExpressionContext ctx) {
//Obtain expression types
DataType p1 = (DataType) visit(ctx.expression(0));
DataType p2 = (DataType) visit(ctx.expression(1));
if (p1 != DataType.BOOL_TYPE)
throw new CompileException("You can only use !CHILD values with nested comparisons. " + p1.getRepresentation() + " found instead on first parameter.");
if (p2 != DataType.BOOL_TYPE)
throw new CompileException("You can only use !CHILD values with nested comparisons. " + p2.getRepresentation() + " found instead on second parameter.");
return DataType.BOOL_TYPE;
}
@Override
public DataType visitConditionalExpression(ScriptmasEveParser.ConditionalExpressionContext ctx) {
//Obtain expression types
DataType p1 = (DataType) visit(ctx.expression(0));
DataType p2 = (DataType) visit(ctx.expression(1));
String operator = ctx.CONDITIONAL_OPERATOR().getText();
switch (operator) {
case "FEWER PRESENTS":
case "FEW PRESENTS":
case "MANY PRESENTS":
case "MORE PRESENTS":
if (p1 != DataType.INT_TYPE)
throw new CompileException("You can only use #CHILD values with the '" + operator + "' operator. " + p1.getRepresentation() + " found instead on first parameter.");
if (p2 != DataType.INT_TYPE)
throw new CompileException("You can only use #CHILD values with the '" + operator + "' operator. " + p2.getRepresentation() + " found instead on second parameter.");
break;
case "IS":
if (p1 != p2)
throw new CompileException("You can only use identically typed variables and values with the 'IS' operator. " + p1.getRepresentation() + " and " + p2.getRepresentation() + " do not match.");
case "ISN'T":
if (p1 != p2)
throw new CompileException("You can only use identically typed variables and values with the 'ISN'T' operator. " + p1.getRepresentation() + " and " + p2.getRepresentation() + " do not match.");
default:
break;
}
return DataType.BOOL_TYPE;
}
@Override
public DataType visitInvertExpression(ScriptmasEveParser.InvertExpressionContext ctx) {
//Obtain expression type
DataType dt = (DataType) visit(ctx.getChild(1));
if (dt != DataType.INT_TYPE)
throw new CompileException("You can only invert #CHILD typed variables and values.");
return DataType.INT_TYPE;
}
@Override
public DataType visitIntegerValueExpression(ScriptmasEveParser.IntegerValueExpressionContext ctx) {
return DataType.INT_TYPE;
}
@Override
public Object visitFunctionStatement(ScriptmasEveParser.FunctionStatementContext ctx) {
//Obtain symbol
String methodName = ctx.NAME().getText();
MethodSymbol ms = scope.getMethod(methodName);
if (ms == null) throw new CompileException("No method with name '" + methodName + "' has been declared.");
//Reference parameter list
List<DataType> parameters = new ArrayList<>();
for (int i = 2; i < ctx.getChildCount() - 1; i++)
parameters.add((DataType) visit(ctx.getChild(i)));
//Check if parameters match
if (parameters.size() < ms.getParameters().size())
throw new CompileException("Too few parameters supplied for method call to method '" + ms.getName() + "'");
else if (parameters.size() > ms.getParameters().size())
throw new CompileException("Too many parameters supplied for method call to method '" + ms.getName() + "'");
for (int i = 0; i < Math.max(ms.getParameters().size(), parameters.size()); i++) {
DataType actualType = new ArrayList<>(ms.getParameters().entrySet()).get(i).getValue();
DataType givenType = parameters.get(i);
if (actualType != givenType)
throw new CompileException("Parameter type mismatch for method call to method '" + ms.getName() + "' at parameter index " + i + ". Expected '" + actualType.getRepresentation() + "' but received '" + givenType.getRepresentation() + "'.");
}
//Return the return type
return ms.getReturnType();
}
@Override
public DataType visitPromptStatement(ScriptmasEveParser.PromptStatementContext ctx) {
return DataType.getByDatatype(ctx.DATATYPE().getText());
}
@Override
public DataType visitPrintStatement(ScriptmasEveParser.PrintStatementContext ctx) {
if (ctx.expression().isEmpty())
throw new CompileException("Global function HO requires at least 1 parameter.");
visitChildren(ctx);
return DataType.VOID_TYPE;
}
@Override
public DataType visitFunctionCallExpression(ScriptmasEveParser.FunctionCallExpressionContext ctx) {
//Handle prompts separately
if (ctx.functionCall() instanceof ScriptmasEveParser.PromptStatementContext)
return (DataType) visit(ctx.functionCall());
//Visit function call first
visit(ctx.functionCall());
//Obtain method name
String methodName = ctx.functionCall().getChild(1).getText();
//Obtain the MethodSymbol (We already visited the call so we are sure it exists
MethodSymbol ms = scope.getMethod(methodName);
//Return returntype
return ms.getReturnType();
}
@Override
public Object visitFiniteLoop(ScriptmasEveParser.FiniteLoopContext ctx) {
//Verify that loop counter is number
DataType expType = (DataType) visit(ctx.expression());
if (expType != DataType.INT_TYPE)
throw new CompileException("The loop value for a finite loop has to be of type #CHILD. Instead found type " + expType.getRepresentation() + ".");
//Visit the body
scope = scope.openScope();
visit(ctx.functionBody());
scope = scope.closeScope();
return null;
}
@Override
public Object visitInfiniteLoop(ScriptmasEveParser.InfiniteLoopContext ctx) {
//Visit the body
scope = scope.openScope();
visit(ctx.functionBody());
scope = scope.closeScope();
return null;
}
@Override
public Object visitBasicCheckStatement(ScriptmasEveParser.BasicCheckStatementContext ctx) {
//Check if expression is boolean
DataType expType = (DataType) visit(ctx.expression());
if (expType != DataType.BOOL_TYPE)
throw new CompileException("Check statements only take on !CHILD expressions. Instead found type " + expType.getRepresentation() + ".");
//Visit the body
scope = scope.openScope();
visit(ctx.functionBody());
scope = scope.closeScope();
return null;
}
@Override
public Object visitCheckOtherwiseStatement(ScriptmasEveParser.CheckOtherwiseStatementContext ctx) {
//Check if expression is boolean
DataType expType = (DataType) visit(ctx.expression());
if (expType != DataType.BOOL_TYPE)
throw new CompileException("Check statements only take on !CHILD expressions. Instead found type " + expType.getRepresentation() + ".");
//Visit the bodies
scope = scope.openScope();
visit(ctx.functionBody(0));
scope = scope.closeScope();
scope = scope.openScope();
visit(ctx.functionBody(1));
scope = scope.closeScope();
return null;
}
@Override
public Object visitAdvancedCheckStatement(ScriptmasEveParser.AdvancedCheckStatementContext ctx) {
//Check if expression is boolean
DataType expType = (DataType) visit(ctx.expression());
if (expType != DataType.BOOL_TYPE)
throw new CompileException("Check statements only take on !CHILD expressions. Instead found type " + expType.getRepresentation() + ".");
//Visit the body
scope = scope.openScope();
visit(ctx.functionBody());
scope = scope.closeScope();
//Visit the next check statement
visit(ctx.check());
return null;
}
@Override
public Object visitMainFunction(ScriptmasEveParser.MainFunctionContext ctx) {
//Check if method name is already declared
String methodName = ctx.NAME().getText();
if (scope.getMethod(methodName) != null)
throw new CompileException("Method name '" + methodName + "' has already been declared!");
this.hasMain = true;
//Visit the body
scope = scope.openScope("");
visit(ctx.functionBody());
scope = scope.closeScope();
return null;
}
@Override
public Object visitTypedFunction(ScriptmasEveParser.TypedFunctionContext ctx) {
//Check if method name is already declared
String methodName = ctx.NAME().getText();
if (scope.getMethod(methodName) != null)
throw new CompileException("Method name '" + methodName + "' has already been declared!");
//Register with scope
DataType returnType = DataType.getByDatatype(ctx.DATATYPE().getText());
ScriptmasEveParser.FunctionParametersContext parameters = ctx.functionParameters();
LinkedHashMap<String, DataType> params = new LinkedHashMap<>();
if (parameters != null)
params = (LinkedHashMap<String, DataType>) visit(ctx.functionParameters());
scope.declareMethod(methodName, returnType, params);
//Visit the body
scope = scope.openScope("");
visit(ctx.functionBody());
scope = scope.closeScope();
return null;
}
@Override
public Object visitVoidFunction(ScriptmasEveParser.VoidFunctionContext ctx) {
//Check if method name is already declared
String methodName = ctx.NAME().getText();
if (scope.getMethod(methodName) != null)
throw new CompileException("Method name '" + methodName + "' has already been declared!");
//Register with scope
ScriptmasEveParser.FunctionParametersContext parameters = ctx.functionParameters();
LinkedHashMap<String, DataType> params = new LinkedHashMap<>();
if (parameters != null)
params = (LinkedHashMap<String, DataType>) visit(ctx.functionParameters());
scope.declareMethod(methodName, DataType.VOID_TYPE, params);
//Visit the body
scope = scope.openScope("");
visit(ctx.functionBody());
scope = scope.closeScope();
return null;
}
@Override
public LinkedHashMap<String, DataType> visitFunctionParameters(ScriptmasEveParser.FunctionParametersContext ctx) {
LinkedHashMap<String, DataType> params = new LinkedHashMap<>();
for (int i = 0; i < ctx.DATATYPE().size(); i++)
params.put(ctx.NAME(i).getText(), DataType.getByDatatype(ctx.DATATYPE(i).getText()));
return params;
}
@Override
public Object visitFunctionBody(ScriptmasEveParser.FunctionBodyContext ctx) {
//Obtain function parameters and introduce them to the scope
ScriptmasEveParser.FunctionParametersContext functionParams = null;
if (ctx.getParent() instanceof ScriptmasEveParser.TypedFunctionContext) {
ScriptmasEveParser.TypedFunctionContext parent = (ScriptmasEveParser.TypedFunctionContext) ctx.getParent();
functionParams = parent.functionParameters();
} else if (ctx.parent instanceof ScriptmasEveParser.VoidFunctionContext) {
ScriptmasEveParser.VoidFunctionContext parent = (ScriptmasEveParser.VoidFunctionContext) ctx.getParent();
functionParams = parent.functionParameters();
}
if (functionParams != null) {
((LinkedHashMap<String, DataType>) visit(functionParams)).entrySet().forEach(entry -> scope.declareVariable(entry.getKey(), entry.getValue()).setInitialized(true));
}
//Visit all content
ctx.children.forEach(child -> {
if (child.getText().equalsIgnoreCase("FINISH DELIVERY")) {
ScriptmasEveParser.LoopContext loopContext = getParentLoopContext(child);
if (loopContext == null)
throw new CompileException("You can only use FINISH DELIVERY inside of a loop");
} else visit(child);
});
//Require GIVE at end if parent is typed function
if (ctx.getParent() instanceof ScriptmasEveParser.TypedFunctionContext && !(ctx.getChild(ctx.getChildCount() - 1) instanceof ScriptmasEveParser.GiveContext))
throw new CompileException("Typed function '" + ((ScriptmasEveParser.TypedFunctionContext) ctx.getParent()).NAME().getText() + "' is missing the required GIVE statement at its end.");
return null;
}
@Override
public Object visitGive(ScriptmasEveParser.GiveContext ctx) {
DataType returnType = (DataType) visit(ctx.expression());
if (returnType == DataType.VOID_TYPE)
throw new CompileException("You cannot return a function that has no return type");
ParserRuleContext parentFunction = ctx.getParent();
while (!(parentFunction instanceof ScriptmasEveParser.FunctionContext) && parentFunction != null)
parentFunction = parentFunction.getParent();
//Only allow within functions
if (parentFunction == null)
throw new CompileException("It is not possible to GIVE outside of a function!");
//Only allow within typed functions
if (!(parentFunction instanceof ScriptmasEveParser.TypedFunctionContext))
throw new CompileException("You cannot GIVE inside of a function without a type!");
//Verify type
DataType functionType = DataType.getByDatatype(((ScriptmasEveParser.TypedFunctionContext) parentFunction).DATATYPE().getText());
if (returnType != functionType)
throw new CompileException("The given give value is of a different type than expected. Expected " + functionType.getRepresentation() + ", instead got " + returnType.getRepresentation() + ".");
return null;
}
//Utility methods
private ScriptmasEveParser.LoopContext getParentLoopContext(org.antlr.v4.runtime.tree.ParseTree ctx) {
org.antlr.v4.runtime.tree.ParseTree current = ctx;
while (current != null) {
if (current instanceof ScriptmasEveParser.LoopContext) return (ScriptmasEveParser.LoopContext) current;
current = current.getParent();
}
return null;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.