Type checking is the processes of identifying errors in a program based on expli
ID: 3902343 • 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
*********************************************************
myChecker.g
grammar myChecker;
@header {
// import packages here.
import java.util.HashMap;
}
@members {
boolean TRACEON = false;
HashMap<String,Integer> symtab = new HashMap<String,Integer>();
}
program : prog|;
prog : Header prog {if (TRACEON) System.out.println("Header");}| type MAIN OParen CParen OBrace declarations statements CBrace{if (TRACEON) System.out.println("Type MAIN () {declarations statements}");};
type returns [int attr_type]:INT { if (TRACEON) System.out.println("type: INT"); $attr_type = 1;}
| CHAR { if (TRACEON) System.out.println("type: CHAR"); $attr_type = 4;}
| DOUBLE { if (TRACEON) System.out.println("type: DOUBLE");$attr_type = 3;}
| VOID { if (TRACEON) System.out.println("type: VOID"); $attr_type = 5;}
| FLOAT {if (TRACEON) System.out.println("type: FLOAT"); $attr_type = 2;};
declarations:type Identifier Line_sym declarations
{
if (TRACEON) System.out.println("declarations: type Identifier : declarations");
if (symtab.containsKey($Identifier.text)) {
System.out.println("Type Error: " +
$Identifier.getLine() +
": Redeclared Identifier.");
} else {
/* Add Identifier and its attr_type into the symbol table. */
symtab.put($Identifier.text, $type.attr_type);
}}
| type Identifier Assign primary_expression Line_sym declarations
{
if (TRACEON) System.out.println("declarations: type Identifier Assign primary_expression: declarations");
if (symtab.containsKey($Identifier.text)) {
System.out.println("Type Error: " +
$Identifier.getLine() +
": Redeclared Identifier.");
} else {
/* Add Identifier and its attr_type into the symbol table. */
if($type.attr_type != $primary_expression.attr_type)
{System.out.println("Type Error: " +$Identifier.getLine() +": Type mismatch for the two silde operands in an assignment statement.");}
else
{symtab.put($Identifier.text, $type.attr_type);}
}}
|{ if (TRACEON) System.out.println("declarations: ");} ;
statements:statement statements
|;
arith_expression returns [int attr_type]:a = arith_term { $attr_type = $a.attr_type; }
(Add b = arith_term
{ if ($a.attr_type != $b.attr_type || $attr_type == -2) {
System.out.println("Type Error: " +
$a.start.getLine() +
": Type mismatch for the operator + in an expression.");
$attr_type = -2;
}
}
| Subtract c = arith_term
{ if ($a.attr_type != $c.attr_type || $attr_type == -2) {
System.out.println("Type Error: " +
$a.start.getLine() +
": Type mismatch for the operator - in an expression.");
$attr_type = -2;
}
}
|op_statement d = arith_term
{ if ($a.attr_type != $d.attr_type || $attr_type == -2) {
System.out.println("Type Error: " +
$a.start.getLine() +
": Type mismatch for the operator op_statement in an expression.");
$attr_type = -2;
}
}
)*;
arith_term returns [int attr_type]:a = arith_factor { $attr_type = $a.attr_type; }
(Multiply b = arith_factor
{ if ($a.attr_type != $b.attr_type || $attr_type == -2) {
System.out.println("Type Error: " +
$a.start.getLine() +
": Type mismatch for the operator * in an expression.");
$attr_type = -2;
}
}
| Divide c = arith_factor
{ if ($a.attr_type != $c.attr_type || $attr_type == -2) {
System.out.println("Type Error: " +
$a.start.getLine() +
": Type mismatch for the operator / in an expression.");
$attr_type = -2;
}
}
)*;
arith_factor returns [int attr_type]: Subtract primary_expression { $attr_type = $primary_expression.attr_type; }
| primary_expression { $attr_type = $primary_expression.attr_type; };
primary_expression returns [int attr_type]:Number { $attr_type = 1; }
| Float_Number { $attr_type = 2; }
| Identifier {if (symtab.containsKey($Identifier.text)) {
$attr_type = symtab.get($Identifier.text);
} else {
/* Add codes to report and handle this error */
$attr_type = -2;
return $attr_type;
}}
| Operate_variable { $attr_type = 6; }
| Single_Quotation primary_expression Single_Quotation { $attr_type = 4; }
| OParen arith_expression CParen
{ $attr_type = $arith_expression.attr_type; };
statement : statement1 | statement2;
statement1 returns [int attr_type]: Identifier Assign (arith_expression Line_sym
{
if (symtab.containsKey($Identifier.text)) {
$attr_type = symtab.get($Identifier.text);
} else {
/* Add codes to report and handle this error */
System.out.println("Type Error: " +
$Identifier.getLine() +
": Undeclared Identifier.");
$attr_type = -2;
return $attr_type;
}
if ($attr_type != $arith_expression.attr_type) {
System.out.println("Type Error: " +
$arith_expression.start.getLine() +
": Type mismatch for the two silde operands in an assignment statement.");
$attr_type = -2;
}
}
| Printf Line_sym
{
if (symtab.containsKey($Identifier.text)) {
$attr_type = symtab.get($Identifier.text);
} else {
/* Add codes to report and handle this error */
$attr_type = -2;
return $attr_type;
}
if ($attr_type != $arith_expression.attr_type) {
System.out.println("Type Error: " +
$arith_expression.start.getLine() +
": Type mismatch for the two silde operands in an assignment statement.");
$attr_type = -2;
}
}
);
statement2 returns [int attr_type]: key_function OParen parameter CParen statement3;
statement3 : OBrace statements CBrace {if (TRACEON) System.out.println("statement : key function(loop,while,if)");}
| Line_sym {if (TRACEON) System.out.println("statement : common function");};
key_function: Determine {if (TRACEON) System.out.println("statement : if ");}
| Loop {if (TRACEON) System.out.println("statement : for or while ");}
| Printf;
parameter : Double_Quotation (Identifier | Number | Float_Number | Operate_variable | cal_statement | Special_String) Double_Quotation parameter{if (TRACEON) System.out.println("parameter style1.1");}
|(Identifier | Number | Float_Number | Operate_variable | cal_statement | Special_String) parameter{if (TRACEON) System.out.println("parameter style1.2");}
| Line_sym (Identifier | Number | Float_Number | Operate_variable | cal_statement | Special_String) parameter{if (TRACEON) System.out.println("parameter style2");}
|',' (Identifier | Number | Float_Number | Operate_variable | cal_statement | Special_String) parameter{if (TRACEON) System.out.println("parameter style3");}|;
cal_statement : x = primary_expression (cal_op | op_statement | Assign)
y = primary_expression
{
if($x.attr_type != $y.attr_type) System.out.println("Type Error::Type mismatch for the operator logical in an expression.");
if (TRACEON) System.out.println("function in parameter");};
cal_op : Subtract|Add|Multiply|Divide;
op_statement : Operate | Logical;
/* description of the tokens */
FLOAT : 'float';
INT : 'int';
DOUBLE : 'double';
CHAR : 'char';
MAIN : 'main';
VOID : 'void';
Printf : 'printf';
Return : 'return';
Special_type : '%'('d' | 'f' | 'c' | 's' | 'lf' | 'ld');
Operate_variable : (Operate)(Number | Float_Number | Identifier);
Operate : Increase | Decrease | Not | Modulus;
Assign : '=';
Logical : '<<'|'>>'|'<'|'>'|'||'|'&&'|'=='|'<='|'>='|'!='|'=';
fragment And : '&&';
fragment Or : '||';
fragment Modulus : '%';
fragment Equal : '==';
fragment LTEquals :'<=';
fragment GTEquals : '>=';
fragment Not_equal : '!=';
fragment Not : '!';
fragment Increase : '++';
fragment Decrease : '--';
Add : '+';
Subtract : '-';
Multiply : '*';
Divide : '/';
fragment Shift_Right : '<<';
fragment Shift_Left : '>>';
fragment LT : '<';
fragment GT : '>';
OBrace : '{';
CBrace : '}';
OBracket : '[';
CBracket : ']';
OParen : '(';
CParen : ')';
Line_sym : ';';
Comma : ',';
Single_Quotation : (''')*;
WS:( ' ' | ' ' | ' ' | ' '|'\''n'|'\i''t'|'\''r' )+ {$channel=HIDDEN;};
Number : ('0' | ('1'..'9')(Digit)*);
Loop : 'While' | 'for';
Determine : ('if' | 'else if' | 'else') | Switch_Case;
Header : (Include_System | Include_Lib);
Identifier : (Charactor)(Charactor | Digit)*;
Special_String : (Charactor | Digit | Special_type | Logical)*;
Float_Number: Float_Number1 | Float_Number2;
fragment Float_Number1: (Digit)+'.'(Digit)*;
fragment Float_Number2: '.'(Digit)+;
Comment1 : '//'(.)*' ' {$channel=HIDDEN;};
Comment2 : '/*' (options{greedy=false;}: .)* '*/' {$channel=HIDDEN;};
fragment Digit : '0'..'9';
fragment Include_System : '#include'(WS)*'<'Identifier'.h''>';
fragment Include_Lib : '#include'(WS)*'"'Identifier'.h''"';
fragment Switch_Case : 'switch' | 'case';
fragment Charactor : 'a'..'z' | 'A'..'Z' | '_';
Double_Quotation : ('"');
*********************************************************
myChecker_test.java
import org.antlr.runtime.*;
public class myChecker_test {
public static void main(String[] args) throws Exception {
CharStream input = new ANTLRFileStream(args[0]);
myCheckerLexer lexer = new myCheckerLexer(input);
CommonTokenStream tokens = new CommonTokenStream(lexer);
myCheckerParser parser = new myCheckerParser(tokens);
parser.program();
}
}
*********************************************************
example.c
#include <stdio.h>
void main(){
int num;
int s;
int index;
float s;
k = 3;
num = index +3.21;
}
*********************************************************
typecheck.c
#include <stdio.h>
void main(){
int a;
float b;
int result;
a = 20;
b = 20.5;
d = 3;
result = a+b;
result = a-b;
result = a*b;
result = a/b;
}
*********************************************************
typecheck2.c
#include <stdio.h>
void main(){
int a;
float b;
char n;
a = 20.5;
b = 20;
d = 3;
result = a+d;
n = a*b;
}
*********************************************************
readme.txt
How to Compile and Execute:
1. The "make" command will compile myChecker.g & myChecker_test.java
2. Make "make program1" will check example.c this test file
3. Make "make program2" check typecheck.c this test file
4. Make "make program3" check typecheck2.c this test file
If there is a type error in the program, you will see which line of the program has an error and shows what type error it is.
-------------------------------------------------- --------------
1. make (compile myChecker.g and myChecker_test.java)
2. make program1 (check example.c)
3. make program2 (check typecheck.c)
4. make program3 (check typecheck2.c)
*********************************************************
Makefile.txt
all:
java -cp antlr-3.5.1-complete-no-st3.jar org.antlr.Tool myChecker.g
javac -cp antlr-3.5.1-complete-no-st3.jar:. myChecker_test.java
program1:
java -cp antlr-3.5.1-complete-no-st3.jar:. myChecker_test example.c
program2:
java -cp antlr-3.5.1-complete-no-st3.jar:. myChecker_test typecheck.c
program3:
java -cp antlr-3.5.1-complete-no-st3.jar:. myChecker_test typecheck2.c
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.