Semantic Analysis in Compilers: Understanding Key Concepts

Compilers: Semantic Analysis CSCI 432 Computer Science Theory

Example What kinds of semantic analysis needs to occur for this simple source code? J = X + 5; Are J and X declared? Since 5 is a number, is X also a number? Is J a number so that it can be assigned the result of the addition? What type of addition is that, int or float? If X or J is a float, then there is implied type casting.

Basic Categories of Semantic Checks Flow of Control Uniqueness Checks Name Related Checks Type Checking page 343 of the dragon book by Aho, Sethi, and Ullman

Flow of Control Example: the "break" command must be in a block that can be broken This is okay for ( ) { if ( ) break; } But what is this break braking? void print_header() { cout << blah blah if ( ) break;

Uniqueness Checks Example: which size are you referencing? class aardvark() { int size; void print_header(int size) { count = size;

Name Related Checks C++ doesn't have any good examples of this. Example 1: Begin sorting End sorting Example 2: function find_value() { find_value = 99;

Type Checking What kinds of type checking needs to occur for this simple source code? for (i=0; i<cnt; i++) X[i] = 1.0; since i is used as an index, is i an integer? is X an array of floats? are i and cnt both integers (what type of comparison is that)? some languages: has cnt been assigned a value?

Type Checking int i; float x; i = 5 / 2; o integer division x = 5 / 2; o what you meant was x = (float)(5 / 2); x = 5 / 2.0; o what you meant was x = (float)5 / 2.0; i = 5 / 2.0 o what you meant was i = (int)((float)5 / 2.0);

expr op PLUS op more about YACC Lex: NUM VAR [0-9]+ { numval = atoi(yytext); return NUMBER; } [a-z]+ { strcpy (varstring, yytext); return VAR; } ============================================= YACC: expr: operand PLUS operand SEMI { $$ = $1 + $3; } operand: VAR { $$ = lookup(varstring); } | NUMBER { $$ = numval; }

Implementation Bit-codes for how a C compiler encodes type boolean = 00 char = 01 integer = 10 float = 11 pointer = 01 array = 10 function = 11 char X; X's type is 0001 float bob[20]; bob's type is 1011

Implementation prog: decls stmts decls: decl | decl decls decl: type VAR SEMI {settype(varsting,$1);} type: int { $$ = integer; } | float { $$ = float; } So, the input "int B;" causes our Symbol Table to be updated, setting the type of B to be an integer.

stmt: VAR ASIGN expr SEMI { if (lookup_type(var) != $3) insert_typecast (lookup_type(var)); } expr: operand operator operand { if ($1 == $3) $$ = $1; else do some typecasting } operand: INT { $$ = integer;} | VAR { $$ = lookup_type(var); } stmt VAR ASIGN expr SEMI X = opnd optr opnd So, given the input: float X; X = B + 2; VAR + INT B 2 The expression "B+2" is evaluated to be an integer. Since the Symbol Table tells us X is a float, we insert a typecast to create X = (float)(5 + 2);

Compiler Design On the previous slides we saw Type Checking of basic types. That same methods could be expanded to Type Check constructed types. Basic Types: int, float, char, Boolean Constructed Types: arrays, pointers, functions Imagine the rules necessary to Type Check more complex data, such as Objects.

Language Theory Type Checking done at compile time is called static checking. Type Checking done during runtime is called dynamic checking. A compiled language that can guarantee execution without any type errors is a strongly typed language.

Next Class Now that we can check syntax and semantics Let's create some code and optimize it and convert it to assembly.