Description
1 Overview
In this assignment, you will augment your parser to perform type checking for the Simple C language. This assignment is worth 20% of your project grade. Your program is due at 11:59 pm, Sunday, February 26th.
2 Type Checking
2.1 Overview
A very important issue in semantic checking is type checking. Type checking is the process of verifying that the
operands to an operator are of the correct type. Each operator yields a value of a specified type based on the type
of its operands. In Simple C, a type consists of a type specifier (char, int, or void) along with optional declarators
(“function returning T,” “array of T,” and “pointer to T”).
In Simple C, a value of type char may be promoted to type int, and a value of type “array of T” may be
promoted to type “pointer to T.” A type is a predicate type if (after any promotion) it is “pointer to T” or int. Two
types are compatible if (after any promotion) they are identical predicate types, or one is “pointer to T” and the
other is “pointer to void.” An object is an lvalue if it refers to a location that can be used on the left-hand side of
an assignment.
2.2 Semantic Rules
2.2.1 Statements
statement → { declarations statements }
| return expression ;
| while ( expression ) statement
| for ( assignment ; expression ; assignment ) statement
| if ( expression ) statement
| if ( expression ) statement else statement
| assignment ;
assignment → expression = expression
| expression
The type of the expression in a return statement must be compatible with the return type of the enclosing function [E1]. The type of an expression in a while, if, or for statement must be a predicate type [E2]. In an assignment
statement the left-hand side must be an lvalue [E3], and the types of two sides must be compatible [E4].
2.2.2 Logical expressions
expression → logical-and-expression
| expression || logical-and-expression
logical-and-expression → equality-expression
| logical-and-expression && equality-expression
The type of each operand must be a predicate type, after any promotion [E4]. The result has type int and is
not an lvalue.
1
2.2.3 Equality expressions
equality-expression → relational-expression
| equality-expression == relational-expression
| equality-expression != relational-expression
The types of the left and right operands must be compatible, after any promotion [E4]. The result has type int
and is not an lvalue.
2.2.4 Relational expressions
relational-expression → additive-expression
| relational-expression <= additive-expression
| relational-expression >= additive-expression
| relational-expression < additive-expression
| relational-expression > additive-expression
The types of the left and right operands must be identical predicate types, after any promotion [E4]. The result
has type int and is not an lvalue.
2.2.5 Additive expressions
additive-expression → multiplicative-expression
| additive-expression + multiplicative-expression
| additive-expression – multiplicative-expression
If both operands have type int, then the result has type int. If the left operand has type “pointer to T,” where
T is not void, and the right operand has type int, then the result has type “pointer to T.” For addition only, if
the left operand has type int and the right operand has type “pointer to T,” where T is not void, then the result
has type “pointer to T.” For subtraction only, if both operands have type “pointer to T,” where T is not void but
is identical for both operands, then the result has type int. Otherwise, the result is an error [E4]. In all cases,
operands undergo type promotion and the result is never an lvalue.
2.2.6 Multiplicative expressions
multiplicative-expression → prefix-expression
| multiplicative-expression * prefix-expression
| multiplicative-expression / prefix-expression
| multiplicative-expression % prefix-expression
The types of both operands must be int, after any promotion [E4]. The result has type int and is not an lvalue.
2.2.7 Prefix expressions
prefix-expression → postfix-expression
| – prefix-expression
| ! prefix-expression
| & prefix-expression
| * prefix-expression
| sizeof prefix-expression
The operand in a unary * expression must have type “pointer to T,” after any promotion and where T is not
void [E5]. The result has type T and is an lvalue. The operand in a unary & expression must be an lvalue [E3]. If the
operand has type T, then the result has type “pointer to T” and is not an lvalue.
The operand in a ! expression must have a predicate type [E5], and the result has type int. The operand in a
unary – expression must have type int [E5], and the result has type int. The operand of a sizeof expression must
be a predicate type [E5]. The result of the expression has type int. In none of these cases is the result an lvalue.
2
2.2.8 Postfix expressions
postfix-expression → primary-expression
| postfix-expression [ expression ]
The left operand in an array reference expression must have type “pointer to T,” after any promotion and where
T is not void, and the expression must have type int [E4]. The result has type T and is an lvalue.
2.2.9 Primary expressions
primary-expression → id ( expression-list )
| id ( )
| id
| num
| string
| ( expression )
expression-list → expression
| expression , expression-list
The type of an identifier is provided at the time of its declaration. An identifier is an lvalue if it refers to a scalar
(i.e., neither a function nor an array). A number has type int and is not an lvalue. A string literal has type “array of
char” and is not an lvalue. The type of a parenthesized expression is that of the expression, and is an lvalue if the
expression itself is an lvalue.
The identifier in a function call expression must have type “function returning T” and the result has type T [E6].
In addition, the arguments must be predicate types, and if the parameters have been specified then the number of
parameters and arguments must agree and their types must be compatible [E7]. The result is not an lvalue.
3 Assignment
You will write a semantic checker for Simple C by adding actions to your parser, using the given rules as a guide.
Your compiler will be given only syntactically legal programs as input. Your compiler should indicate any errors
by writing the appropriate error messages to the standard error (any output to standard output will be ignored):
E1. invalid return type
E2. invalid type for test expression
E3. lvalue required in expression
E4. invalid operands to binary operator
E5. invalid operand to unary operator
E6. called object is not a function
E7. invalid arguments to called function
4 Hints
Define and implement functions for abstractions such as type compatibility, checking if a type is int, a pointer,
a predicate type, and test them thoroughly: these abstractions form the basis for most of the type checking rules.
Implement the type checking rules in a bottom-up fashion. You will need to modify your parser so that the functions for the rules return the necessary type and lvalue information. A common implementation approach is to
modify your functions for expressions so that they return the type and take a reference parameter through which
to indicate whether the expression is an lvalue:
3
Type expression(bool &lvalue) {
Type left = logicalAndExpression(lvalue);
while (lookahead == OR) {
match(OR);
Type right = logicalAndExpression(lvalue);
left = checkLogicalOr(left, right);
lvalue = false;
}
return left;
}
A more advanced approach is to construct an abstract syntax tree during parsing as you perform the semantic
checks. A tree node for an expression would contain its type and whether the expression is an lvalue. One could
design an entire class hierarchy for the tree, such as statements (including if-statements, while-statements, etc.)
and expressions (including addition, subtraction, etc.).
4