{"id":177,"date":"2018-07-20T06:04:51","date_gmt":"2018-07-20T06:04:51","guid":{"rendered":"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=177"},"modified":"2018-07-20T06:05:20","modified_gmt":"2018-07-20T06:05:20","slug":"type-checking","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/chapter\/type-checking\/","title":{"rendered":"TYPE CHECKING"},"content":{"raw":"
\r\n

In this module, we will discuss about the important function of the semantic phase of the compiler namely type checking.<\/strong> Type checking involves identifying and prompting if incompatible operands are being operated<\/p>\r\n \r\n\r\n21.1 Types of Check<\/strong>\r\n\r\n \r\n

The compiler needs to verify whether the source program follows the syntactic and semantic conventions. This is done with the help of static checking. Static checking helps in reporting programming errors during compile time. Dynamic checking is done during run time to identify and handle errors as they occur.\u00a0 The various static checking that are done by the compiler are listed as follows:<\/p>\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Type\u00a0 Checking: <\/strong>This check determines and\u00a0 handles\u00a0 if an operator\u00a0 is applied to an\r\n\r\n \r\n\r\nincompatible operand. Example: The compiler would prompt an error if array variable is added with function variable. Consider the following declarations and the statements that follow it.\r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 int op(int), op(float);\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0 int f(float);\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0 int a, c[10], d;\r\n\r\n \r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
4.<\/td>\r\nd = c+d;<\/td>\r\n\/\/ FAIL<\/td>\r\n<\/tr>\r\n
5.<\/td>\r\n*d = a;<\/td>\r\n\/\/ FAIL<\/td>\r\n<\/tr>\r\n
6.<\/td>\r\na = op(d);<\/td>\r\n\/\/ OK: overloading (C++)<\/td>\r\n<\/tr>\r\n
7.<\/td>\r\na = f(d);<\/td>\r\n\/\/ OK: coercion<\/td>\r\n<\/tr>\r\n
8.<\/td>\r\nvector<int> v;\/\/OK: template instantiation<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n

Line numbers 1 to 3 declares some variables and functions. Line number 4 adds an array variable (address) with an integer variable. This is prompted as an error. Line number 5 tries to dereference an integer variable and is prompted as an error. Line number 6 is accepted as it is similar to operator overloading. Line number 7 passes as integer to function \u2018f\u2019 which takes a float but implicit conversion can be considered and hence is an accepted statement. Similarly, line 8 is similar to a template instantiation and hence is an accepted type check.<\/p>\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Flow of control check: <\/strong>This would verify whether the statements that results in a branch\r\n\r\n \r\n\r\nare terminated correctly. Example: Break statements.\r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 myfunc()\r\n\r\n{ \u2026\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 while (n)\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 { \u2026\r\n\r\n<\/div>\r\n

\r\n\r\n\u00a0 \u00a0 4.\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 if (i>10)\r\n\r\n5.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 break; \/\/ OK\r\n\r\n}\r\n\r\n}\r\n\r\n6.\u00a0\u00a0\u00a0\u00a0\u00a0 myfunc1()\r\n\r\n{ \u2026\r\n\r\n \r\n\r\n7.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 break; \/\/ ERROR\r\n\r\n}\r\n\r\n \r\n

Consider the functions myfunc() and myfunc1(). myfunc() has a while loop and in the body of this while loop there is a if() conditional statement. The body of the if() is a break statement where nothing is done if the condition is met. This is an accepted control flow as only in the event that the if() statement is true, we come out of the body of the if() without doing anything. On the other hand, consider myfunc1() where there is no loop construct and we see a break. This is considered as error because if the program breaks the location to jump to is not defined.<\/p>\r\n \r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Uniqueness check: <\/strong>This ensures that an object must be defined exactly once\u00a0 in the\u00a0 situation that is demanded by some programming language. Example: labels in case statements need to be unique in pascal, identifiers need to be unique in programming languages.<\/p>\r\n \r\n\r\nmyfunc2()\r\n\r\n \r\n\r\n{ int i, j, i; \/\/ ERROR\r\n\r\n \r\n\r\n\u2026\r\n\r\n \r\n\r\n}\r\n\r\n \r\n\r\nThe above function myfunc2() has two variables with the same name \u2018i\u2019 and hence is considered error.\r\n\r\n \r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Name-related checks: <\/strong>This checks whether the same name appears more than once in\u00a0 programming languages that does not support. Example: In Ada, a name should not appear more than once and compiler needs to verify this. The following example has two arguments with the same name and hence is prompted as error.<\/p>\r\n \r\n\r\ncnufym(int a, int a) \/\/ ERROR<\/strong>\r\n\r\n{\u00a0 \u2026<\/strong>\r\n\r\n \r\n\r\n}<\/strong>\r\n\r\n \r\n\r\n21.\u00a0 <\/strong>2 Position of type checker<\/strong>\r\n\r\n \r\n

After understanding the types of static checking that are necessary, the compiler does type checking as against any other type of static checking. Typically type checking is being done after successfully parsing the input sentence. The position of the type checker is given in figure 21.1\u00a0 \u00a0\u00a0where the syntax tree is used to verify the type checking information and is given later to the intermediate code generator for generating intermediate representation.<\/span><\/p>\r\n\"\"\r\n

\r\n

Thus as can be seen from figure 21.1 the type checker is part of the semantic phase of the compiler. Type checking information is added with the semantic rules. Basic type checking is performed which is further extended to type checking of complex attributes.<\/p>\r\n \r\n\r\n21.3 Type Checking<\/strong>\r\n\r\n \r\n

In general a language\u2019s type system specifies the validity of the operation depending on the type of the operand. Type checking is done to ensure that operations with correct types are operated upon. Type systems define semantic rules to perform type checking. Type expressions can be defined as follows:<\/p>\r\n

1.\u00a0\u00a0\u00a0\u00a0\u00a0 A basic type is a type expression. Integer, float, type_error all are type expression. Statements will have void as their type which is also a basic type expression.<\/p>\r\n

2.\u00a0\u00a0\u00a0\u00a0\u00a0 A type constructor applied to a type expressions is a derived type expression<\/p>\r\n

a.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Arrays: If T is a type expression then array(A, T) is a type expression denoting the type of the array with elements of type T and index A<\/p>\r\n

b.\u00a0\u00a0\u00a0\u00a0\u00a0 Products: If T1 and T2 are type expressions then their Cartesian product T1 X T2 is a type expression<\/p>\r\n

c.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Pointers: If T is a type expression then pointer(T) is a type expression indicating the type pointer to an object of type T<\/p>\r\n

d.\u00a0\u00a0\u00a0\u00a0\u00a0 Functions: Functions gets value from some domain and maps it to a range. This mapping is a type<\/p>\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0 Type expressions contain variables which are also derived type expressions\r\n\r\n \r\n\r\nAfter knowing what to check as type in each of the programming construct, now let us discuss the semantic rules that are necessary for type checking of the different programming constructs of Pascal language.\r\n\r\n \r\n\r\n21.3.1 Type checking of Expressions<\/strong>\r\n\r\n \r\n

Expressions are to be compatible to be operated on. Every expression is governed by a data type and this \u2018type\u2019 is an attribute associated with it. For type checking of expressions, we will be\u00a0having <\/span>semantic rule that verifies this \u201ctype\u201d attribute. Table 21.1 summarizes the semantic rule for type checking of expressions.<\/span><\/p>\r\n\r\n<\/div>\r\n \r\n\r\nTable 21.1 Semantic rules for type checking expressions\r\n\r\n\"\"\r\n\r\n21.3.2 Type checking of Statements<\/strong>\r\n\r\n \r\n

Statements can be simple assignment statements, conditional statements, sequence of statements or loops. The attribute of the statements is also type and the value of this is void if the statements are correct. The set of semantic rules to perform type checking of statements is given in Table 21.2.<\/p>\r\n\r\n<\/div>\r\n\"\"\r\n\r\n21.3.3 Type checking of functions\r\n\r\n \r\n

Functions will do some processing and computations based on its parameters. The type checking of functions verifies whether the function uses arguments that have been passed and checks if there is a mapping between the arguments and the computations of the function. Table 21.3 summarizes the check.<\/p>\r\n\"\"\r\n\r\n\"\"\r\n

\r\n\r\nIntermediate code can be represented in the following ways:<\/strong>\r\n\r\n \r\n

\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Graphical representations: The input is represented as an abstract syntax tree (AST). We have already discussed the construction of the AST which is a binary tree in the previous modules. This AST is the output of the semantic phase of the compiler which can serve as an intermediate representation for generating target code. A directed acyclic graph can also be used to represent the AST. Consider the exa mple AST and its corresponding DAG representation in figure 21.3 for the input a:=b*-c + b*-c<\/p>\r\n \r\n

The construction of the AST is already discussed in the previous module using the functions mknode() and mkleaf(). The construction of the DAG is the same as AST except for the fact that the common terms are represented only once in the graphical representation. The procedure to construct DAG for an expression is to initially, search the array for a node M with label op, left child l and right child r. If there is such a node,\u00a0return the value number M. If not create in the array a new node N with label op, left child l, and right child r and return its value<\/span><\/p>\r\n\r\n<\/div>\r\n\"\"\r\n\r\n\"\"","rendered":"

\n

In this module, we will discuss about the important function of the semantic phase of the compiler namely type checking.<\/strong> Type checking involves identifying and prompting if incompatible operands are being operated<\/p>\n

 <\/p>\n

21.1 Types of Check<\/strong><\/p>\n

 <\/p>\n

The compiler needs to verify whether the source program follows the syntactic and semantic conventions. This is done with the help of static checking. Static checking helps in reporting programming errors during compile time. Dynamic checking is done during run time to identify and handle errors as they occur.\u00a0 The various static checking that are done by the compiler are listed as follows:<\/p>\n

 <\/p>\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Type\u00a0 Checking: <\/strong>This check determines and\u00a0 handles\u00a0 if an operator\u00a0 is applied to an<\/p>\n

 <\/p>\n

incompatible operand. Example: The compiler would prompt an error if array variable is added with function variable. Consider the following declarations and the statements that follow it.<\/p>\n

 <\/p>\n

1.\u00a0\u00a0\u00a0\u00a0\u00a0 int op(int), op(float);<\/p>\n

2.\u00a0\u00a0\u00a0\u00a0\u00a0 int f(float);<\/p>\n

3.\u00a0\u00a0\u00a0\u00a0\u00a0 int a, c[10], d;<\/p>\n

 <\/p>\n\n\n\n\n\n\n\n
4.<\/td>\nd = c+d;<\/td>\n\/\/ FAIL<\/td>\n<\/tr>\n
5.<\/td>\n*d = a;<\/td>\n\/\/ FAIL<\/td>\n<\/tr>\n
6.<\/td>\na = op(d);<\/td>\n\/\/ OK: overloading (C++)<\/td>\n<\/tr>\n
7.<\/td>\na = f(d);<\/td>\n\/\/ OK: coercion<\/td>\n<\/tr>\n
8.<\/td>\nvector<int> v;\/\/OK: template instantiation<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

 <\/p>\n

Line numbers 1 to 3 declares some variables and functions. Line number 4 adds an array variable (address) with an integer variable. This is prompted as an error. Line number 5 tries to dereference an integer variable and is prompted as an error. Line number 6 is accepted as it is similar to operator overloading. Line number 7 passes as integer to function \u2018f\u2019 which takes a float but implicit conversion can be considered and hence is an accepted statement. Similarly, line 8 is similar to a template instantiation and hence is an accepted type check.<\/p>\n

 <\/p>\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Flow of control check: <\/strong>This would verify whether the statements that results in a branch<\/p>\n

 <\/p>\n

are terminated correctly. Example: Break statements.<\/p>\n

 <\/p>\n

1.\u00a0\u00a0\u00a0\u00a0\u00a0 myfunc()<\/p>\n

{ \u2026<\/p>\n

2.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 while (n)<\/p>\n

3.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 { \u2026<\/p>\n<\/div>\n

\n

\u00a0 \u00a0 4.\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 if (i>10)<\/p>\n

5.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 break; \/\/ OK<\/p>\n

}<\/p>\n

}<\/p>\n

6.\u00a0\u00a0\u00a0\u00a0\u00a0 myfunc1()<\/p>\n

{ \u2026<\/p>\n

 <\/p>\n

7.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 break; \/\/ ERROR<\/p>\n

}<\/p>\n

 <\/p>\n

Consider the functions myfunc() and myfunc1(). myfunc() has a while loop and in the body of this while loop there is a if() conditional statement. The body of the if() is a break statement where nothing is done if the condition is met. This is an accepted control flow as only in the event that the if() statement is true, we come out of the body of the if() without doing anything. On the other hand, consider myfunc1() where there is no loop construct and we see a break. This is considered as error because if the program breaks the location to jump to is not defined.<\/p>\n

 <\/p>\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Uniqueness check: <\/strong>This ensures that an object must be defined exactly once\u00a0 in the\u00a0 situation that is demanded by some programming language. Example: labels in case statements need to be unique in pascal, identifiers need to be unique in programming languages.<\/p>\n

 <\/p>\n

myfunc2()<\/p>\n

 <\/p>\n

{ int i, j, i; \/\/ ERROR<\/p>\n

 <\/p>\n

\u2026<\/p>\n

 <\/p>\n

}<\/p>\n

 <\/p>\n

The above function myfunc2() has two variables with the same name \u2018i\u2019 and hence is considered error.<\/p>\n

 <\/p>\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Name-related checks: <\/strong>This checks whether the same name appears more than once in\u00a0 programming languages that does not support. Example: In Ada, a name should not appear more than once and compiler needs to verify this. The following example has two arguments with the same name and hence is prompted as error.<\/p>\n

 <\/p>\n

cnufym(int a, int a) \/\/ ERROR<\/strong><\/p>\n

{\u00a0 \u2026<\/strong><\/p>\n

 <\/p>\n

}<\/strong><\/p>\n

 <\/p>\n

21.\u00a0 <\/strong>2 Position of type checker<\/strong><\/p>\n

 <\/p>\n

After understanding the types of static checking that are necessary, the compiler does type checking as against any other type of static checking. Typically type checking is being done after successfully parsing the input sentence. The position of the type checker is given in figure 21.1\u00a0 \u00a0\u00a0where the syntax tree is used to verify the type checking information and is given later to the intermediate code generator for generating intermediate representation.<\/span><\/p>\n

\"\"<\/p>\n

\n

Thus as can be seen from figure 21.1 the type checker is part of the semantic phase of the compiler. Type checking information is added with the semantic rules. Basic type checking is performed which is further extended to type checking of complex attributes.<\/p>\n

 <\/p>\n

21.3 Type Checking<\/strong><\/p>\n

 <\/p>\n

In general a language\u2019s type system specifies the validity of the operation depending on the type of the operand. Type checking is done to ensure that operations with correct types are operated upon. Type systems define semantic rules to perform type checking. Type expressions can be defined as follows:<\/p>\n

1.\u00a0\u00a0\u00a0\u00a0\u00a0 A basic type is a type expression. Integer, float, type_error all are type expression. Statements will have void as their type which is also a basic type expression.<\/p>\n

2.\u00a0\u00a0\u00a0\u00a0\u00a0 A type constructor applied to a type expressions is a derived type expression<\/p>\n

a.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Arrays: If T is a type expression then array(A, T) is a type expression denoting the type of the array with elements of type T and index A<\/p>\n

b.\u00a0\u00a0\u00a0\u00a0\u00a0 Products: If T1 and T2 are type expressions then their Cartesian product T1 X T2 is a type expression<\/p>\n

c.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Pointers: If T is a type expression then pointer(T) is a type expression indicating the type pointer to an object of type T<\/p>\n

d.\u00a0\u00a0\u00a0\u00a0\u00a0 Functions: Functions gets value from some domain and maps it to a range. This mapping is a type<\/p>\n

3.\u00a0\u00a0\u00a0\u00a0\u00a0 Type expressions contain variables which are also derived type expressions<\/p>\n

 <\/p>\n

After knowing what to check as type in each of the programming construct, now let us discuss the semantic rules that are necessary for type checking of the different programming constructs of Pascal language.<\/p>\n

 <\/p>\n

21.3.1 Type checking of Expressions<\/strong><\/p>\n

 <\/p>\n

Expressions are to be compatible to be operated on. Every expression is governed by a data type and this \u2018type\u2019 is an attribute associated with it. For type checking of expressions, we will be\u00a0having <\/span>semantic rule that verifies this \u201ctype\u201d attribute. Table 21.1 summarizes the semantic rule for type checking of expressions.<\/span><\/p>\n<\/div>\n

 <\/p>\n

Table 21.1 Semantic rules for type checking expressions<\/p>\n

\"\"<\/p>\n

21.3.2 Type checking of Statements<\/strong><\/p>\n

 <\/p>\n

Statements can be simple assignment statements, conditional statements, sequence of statements or loops. The attribute of the statements is also type and the value of this is void if the statements are correct. The set of semantic rules to perform type checking of statements is given in Table 21.2.<\/p>\n<\/div>\n

\"\"<\/p>\n

21.3.3 Type checking of functions<\/p>\n

 <\/p>\n

Functions will do some processing and computations based on its parameters. The type checking of functions verifies whether the function uses arguments that have been passed and checks if there is a mapping between the arguments and the computations of the function. Table 21.3 summarizes the check.<\/p>\n

\"\"<\/p>\n

\"\"<\/p>\n

\n

Intermediate code can be represented in the following ways:<\/strong><\/p>\n

 <\/p>\n

\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Graphical representations: The input is represented as an abstract syntax tree (AST). We have already discussed the construction of the AST which is a binary tree in the previous modules. This AST is the output of the semantic phase of the compiler which can serve as an intermediate representation for generating target code. A directed acyclic graph can also be used to represent the AST. Consider the exa mple AST and its corresponding DAG representation in figure 21.3 for the input a:=b*-c + b*-c<\/p>\n

 <\/p>\n

The construction of the AST is already discussed in the previous module using the functions mknode() and mkleaf(). The construction of the DAG is the same as AST except for the fact that the common terms are represented only once in the graphical representation. The procedure to construct DAG for an expression is to initially, search the array for a node M with label op, left child l and right child r. If there is such a node,\u00a0return the value number M. If not create in the array a new node N with label op, left child l, and right child r and return its value<\/span><\/p>\n<\/div>\n

\"\"<\/p>\n

\"\"<\/p>\n","protected":false},"author":4,"menu_order":21,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-rajeswari-sridhar"],"pb_section_license":""},"chapter-type":[],"contributor":[59],"license":[],"class_list":["post-177","chapter","type-chapter","status-publish","hentry","contributor-dr-rajeswari-sridhar"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/177","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/users\/4"}],"version-history":[{"count":2,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/177\/revisions"}],"predecessor-version":[{"id":186,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/177\/revisions\/186"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/177\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/media?parent=177"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapter-type?post=177"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/contributor?post=177"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/license?post=177"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}