Python

The George Washington University School of Engineering and Applied Science

Department of Computer Science CSci 4223 – Software Paradigms – Spring 2016

Programming Assignment # 3: A Static Type Checker Due Date: April 24, 2016 -- Midnight

Instructor: A. Bellaachia

The following represents the EBNF grammar for a very simple language, called C--:

program ----> {stmt} stmt ----> var_dec ";" | assign ";" | read_stat ";" | write_stat ";" | if_stmt ";" | while_stmt ";" var_dec ----> type var assign ----> var "=" expr expr ----> add_expr add_expr ----> mul_expr {("+"|"-") mul_expr} mul_expr ----> simple_expr {("*"|"/"|"%") simple_expr } simple_expr ----> id | var | "(" expr ")" read_stat ----> "READ" "(" expr ")" write_stat ----> "PRINT" "(" expr ")" type ----> "int" | "float" | "boolean" id ----> intnumber | floatnumber

intnumber ----> Digit | Digit intnumber floatnumber: ----> intnumber "." intnumber

Digit ----> [0-9]+ boolean ----> "0" | "1"; var ----> [A-Z, a-z]+ block ----> program [ block ] if_stmt ----> "if" bool_stmt ":" [block] [ "else:" [block] ] "end if" while_stmt ----> "while" bool_stmt "do" [block] "end while" bool_stmt ----> and_stmt | rel_stmt |boolean and_stmt ----> bool_stmt {("and"|"or") bool_stmt} rel_stmt ----> simple_expr (">"|"<"|">="|"==") simple_expr In this project, you would like to implement, in Python, a strict static type checker, we call STC for C--. Remember, you only need to check the types of all statements. STC reads a C--program and should:

x You can use the lexical analyzer you developed in assignment 2. x Print “Your program is type error free”, if there are no type errors in the program, or Print a

brief, accurate description (including line numbers) of each error, if there are any type errors in the program.

x Your type checker should statically detect all of the following type errors: o Incorrect or inconsistent type of expressions (for example, using a floating-point value as

the loop condition in a while loop). o Incompatible types used within expressions (for example, adding an integer and a floating-

point value). o Legal operations for each type, e.g., cannot multiply character type.

x Sample input data: {

Int x ; Int y ; Int z ; X = 10 ; Y = 20 ; print (x); print (x+y); read(z) z = z + x + y; print (z);

} {

if 5 > 1: {

if (4>3) and (2 <5) : {

print 1; print 2;

} else:

{ print 3; print (3+1)

} end if;

} end if;

}

x Notes: o All variables are declared at the beginning of your program. o During type checking, if there is an error at a given statement, you should not stop the

processing of your input program. Do the following: � Get the line number of the statement, � Give an explanation of the error, � Continue the processing of the remaining statements in the input program.

o Your type checker would need a set of classes (or Subprograms) to handle the rules of the grammar.

o For example, you will need a class for the following rule: //The next token is in nextToken variable.

if_stmt ----> "if" bool_stmt ":" [block] [ "else:" [block] ] "end if"

//The following pseudo-code gives an idea about the processing of an // if statement. void if_stmt( ) { //The nextToken is already set by the calling method. if (nextToken == IF_CODE) { //Make sure the first work is

//the IF reserved keyword Call your lexical analyzer (); //to get the next token. bool_stmt(); if (nextToken != COLON_CODE) errors() else { //This is the THEN part

block(); Call your lexical analyzer (); //to get the next token.

if (nextToken == ELSE_CODE) // the ELSE part Call your lexical analyzer (); block(); } } If (nextToken != ENDIF_CODE) errors();

} else //This function was called, but the first keyword is not IF errors( ); } � Another pseudo-code of the simple expression rule :

simple_expr ----> id | var | "(" expr ")"

void simple_expr () { /* Check each component on the right hand side of the rule */ if (nextToken == DIGIT_CODE) // is it a number?

Call your lexical analyzer (); //to get the next token. else if (nextToken == VAR_CODE) //is it a variable?

Call your lexical analyzer (); //to get the next token. else if (nextToken == LEFT_PAREN_CODE) {

Call your lexical analyzer (); expr(); if (nextToken == RIGHT_PAREN_CODE)

Call your lexical analyzer (); else

errors(); } else

errors(); /* The expression has an error. */