{"id":196,"date":"2018-07-20T06:35:22","date_gmt":"2018-07-20T06:35:22","guid":{"rendered":"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=196"},"modified":"2018-07-20T06:35:35","modified_gmt":"2018-07-20T06:35:35","slug":"three-address-code-symbol-table-and-arrays","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/chapter\/three-address-code-symbol-table-and-arrays\/","title":{"rendered":"THREE ADDRESS CODE, SYMBOL TABLE AND ARRAYS"},"content":{"raw":"
\r\n

In this module, we learn how to write semantic rules for declarations by declaring scope information. The use of symbol tables for declaring scope information for symbol tables is also discussed in this module. In this module, we also discuss the grammar for array declarations.<\/p>\r\n \r\n\r\n23.1 Symbol Table<\/strong>\r\n\r\n \r\n

We have discussed the three address code generation for declarations. The attributes, offset and type helps to keep track of the amount of memory and address information necessary for every variable. In addition to the address and memory information, scope details are necessary for the variables. Consider the following production for declarations:<\/p>\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 P \u00e0 D\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 D \u00e0 D ; D | id= T | proc id ; D ; S\r\n\r\n \r\n\r\nThe moment the compiler encounters proc id; D;S , a new symbol table is created. The details about the scope contents are achieved by the following functions:\r\n\r\n \r\n\r\n\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 mktable (previous) \u2013 This function returns a pointer to a new table that is linked to a previous table in the outer scope. \u201cprevious\u201d is the address of the previous table, and the first table is called with \u201cnull\u201d.\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 enter(table, name, type, offset) \u2013 This function is used to create a new entry in table. \u201ctable\u201d refers to the address of the current table, \u201cname\u201d is the variable name, \u201ctype\u201d refers to the data type of the variable and \u201coffset\u201d is the value used to compute the address of the variable. The attributes \u201ctype\u201d and \u201coffset\u201d are the values generated using the three address code for declarations\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 addwidth(table, width) \u2013 This function is used to determine the total width of all entries in table\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 enterproc(table, name, newtable) \u2013 This function creates a new entry in table for procedure with local scope newtable. Here \u201ctable\u201d refers to the current table, \u201cname\u201d refers to the name of the newtable, \u201cnewtable\u201d refers to the address of the new table\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 lookup (table, name) \u2013 This returns a pointer to the entry in the table for name by following linked tables.\r\n\r\n \r\n\r\nLet us consider an example to demonstrate the linking of the various tables using the above discussed functions. Consider a structure \u201cS\u201d to have two integer variables and let \u2018s\u2019 be an instance of this structure.\r\n\r\n<\/div>\r\n \r\n\r\nstruct S\r\n\r\n{ int a; int b;\r\n\r\n} s;\r\n\r\n \r\n\r\nLet us define a function \u201cswap\u201d with two reference integer variables and the body of the function is defined as follows:\r\n\r\nvoid swap(int& a, int& b)\r\n\r\n \r\n\r\n{ int t; t = a; a = b;\r\n\r\nb = t;\r\n\r\n}\r\n\r\nConsider the following main program which has calls the function swap() and another function foo().\r\n\r\nmain()\r\n\r\n{struct S s; swap(a, b);\r\n\r\nfoo();\r\n\r\n}\r\n\r\n \r\n\r\nThe symbol table integrated information is shown in figure 23.1\r\n\r\n \r\n\r\n\"\"\r\n

As can be seen from figure 23.1, the initial symbol table is created when the compiler encounters the main() function using the mktable(nil) function. Once the structure variable is declared using the table information for structure, another table is created as mktable(main) and thus there is a link from main table to the table of the structure. The variable\u2018s\u2019 of the structure has its own symbol table to have information about its fields. The \u201centerproc\u201d function helps enter the details about the symbol table of \u2018s\u2019 in the current symbol table. The details about\u2018s\u2019 is entered in the current symbol table using the \u201center\u201d function. The width information about the structure variable is computed using addwidth() and in this example it is computed as \u201c8\u201d and s tored in the header field of the symbol table. Similarly, the function swap will have a total width as \u201c12\u201d and is stored in the table corresponding to the function \u201cswap\u201d. Let us see how the compiler builds the symbol table to remember the scope information. Consider the following function having calls to three functions A, B, C and assume function A in turn calls function D.<\/p>\r\n \r\n\r\nVoid foo( )\r\n\r\n \r\n\r\n{\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 call A()\r\n\r\ncall B()\r\n\r\ncall (C)\r\n\r\n}\r\n\r\nVoid A()\r\n\r\n{\r\n\r\ncall D()\r\n\r\n}\r\n\r\n \r\n\r\nThe calling stack phenomenon is given in figure 23.2 (a) through (d)\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n

As can be seen from figure 23 (a), when function A is called, it is pushed into the calling stack and in turn as A calls D, the information about D is pushed onto the stack. Once D returns, it is removed from the stack and so is the case with A. When B is called B is pushed onto the stack and a similar scenario happens with function call to C and is given in figures 23 (b) and (c). When C also terminates, it is also removed from the stack. The address of the symbol tables are maintained as a stack. This information is used to refer to the variables of the functions which are available in the top of the stack thus ensuring scope information. Once, a function terminates, the address of this symbol table is removed from this stack.<\/p>\r\n \r\n

    \r\n \t
  1. 2 Semantic rules for generating Three-address code for scope information<\/strong><\/li>\r\n<\/ol>\r\n

    \u00a0 \u00a0 \u00a0The functions discussed in the previous section are used to generate three-address code for maintaining scope information. Table 23.1 gives the semantic rules for generating three address code for procedures to maintain scope information. The semantic rule makes use of the functions discussed in the previous section. A stack of addresses of the symbol table indicated as \u201ctblptr\u201d is maintained and is useful in accessing the topmost symbol table at any point of time.<\/p>\r\n \r\n\r\nTable 23.1 Semantic rules for maintaining scope information\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n

    The details in Table 23.1 gives the semantic rules for maintaining the scope of symbol tables using two stacks, one of the stack tblptr<\/strong> is used to keep track of the available symbol table and the other one, offse<\/strong>t is used to determine the relative addresses of variables in a function. When a new procedure is called a symbol table is created and its pointer pushed to this stack with offset information in another stack. When the function call seizes this symbol table address is popped off the stack.<\/p>\r\n \r\n\r\n23.3 Semantic rules for Records in Pascal<\/strong>\r\n\r\n \r\n

    After discussing the semantic rules for generating three-address code to maintain scope information, we will conclude with generating three-address code for records. The semantic rules for generating three-address code for records are given in Table 23.2<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n

    This uses a function \u201cemit\u201d which is used to generate three address codes to output file. As can be seen from Figure 23.1, the second statement involves generating a three address code, id.place := E.place whereas a sequence of statements doesn\u2019t involve any code.<\/p>\r\n \r\n\r\n23.5 Three-address code for assignment statements<\/strong>\r\n\r\n \r\n

    Names in the symbol table are the variables which are referred to addresses. The function Lookup(id.name) identifies variable \u201cid\u201d in symbol table. The function emit is used to emit three address statements to output file. Table 23.3 gives the set of semantic rules for the expression grammar using emit function. This is similar to the one already discussed in the previous module with \u201cgen\u201d function replaced with \u201cemit\u201d function.<\/p>\r\n \r\n\r\n\"\"\r\n

    \r\n

    From tables 23.3 and 22.6 of the previous module, it can be seen that if the expression is long, the number of temporary variables involved also increased. To tackle this situation, we keep track of a counter wherein the number of temporary variables could be reused. We modify newtemp<\/em>() to use a \u201cstack\u201d. We keep a counter c <\/em>initialized to 0, and is used to track the number of temporary variables. newtemp<\/em>() increments c<\/em> and returns temporary $c.<\/em> We decrement counter on each use of a $i in a three-address statement.<\/p>\r\n \r\n

    Consider the production E<\/em>1 + E<\/em>2. The correct evaluation is to evaluate E<\/em>1 into t1 and E<\/em>2 into t2 and is shown below.<\/p>\r\n \r\n\r\nt3:= t1 + t2\r\n\r\n<\/div>\r\n

    As t1 is no longer required, we can reuse t1 instead of using new temp t3. This is the fundamental idea. This is explained in the following example.<\/p>\r\n

    Consider the expression x : = a * b + c*d \u2013 e * f. The use and re-use of temporary variables is given in table 23.4<\/p>\r\n \r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n\u2013\u00a0 em = em-1\u00a0 + im\r\n\r\n \r\n\r\n\u2013\u00a0 e1 = i1\r\n\r\n \r\n\r\nThis will be discussed in detail in the next module.\r\n\r\n \r\n

    Summary: <\/strong>This module discussed the three-address code for declarations in the view of maintaining scope information using symbol table and keeping an access of all symbol tables. The grammar for arrays in Pascal has been introduced. The next module will discuss about defining semantic rules for generating three-address code for accessing arrays.<\/p>\r\n \r\n

      \r\n \t
    • Grammar for arrays have been discussed<\/li>\r\n<\/ul>\r\n

      <\/p>","rendered":"

      \n

      In this module, we learn how to write semantic rules for declarations by declaring scope information. The use of symbol tables for declaring scope information for symbol tables is also discussed in this module. In this module, we also discuss the grammar for array declarations.<\/p>\n

       <\/p>\n

      23.1 Symbol Table<\/strong><\/p>\n

       <\/p>\n

      We have discussed the three address code generation for declarations. The attributes, offset and type helps to keep track of the amount of memory and address information necessary for every variable. In addition to the address and memory information, scope details are necessary for the variables. Consider the following production for declarations:<\/p>\n

       <\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 P \u00e0 D<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 D \u00e0 D ; D | id= T | proc id ; D ; S<\/p>\n

       <\/p>\n

      The moment the compiler encounters proc id; D;S , a new symbol table is created. The details about the scope contents are achieved by the following functions:<\/p>\n

       <\/p>\n

      \u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 mktable (previous) \u2013 This function returns a pointer to a new table that is linked to a previous table in the outer scope. \u201cprevious\u201d is the address of the previous table, and the first table is called with \u201cnull\u201d.<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 enter(table, name, type, offset) \u2013 This function is used to create a new entry in table. \u201ctable\u201d refers to the address of the current table, \u201cname\u201d is the variable name, \u201ctype\u201d refers to the data type of the variable and \u201coffset\u201d is the value used to compute the address of the variable. The attributes \u201ctype\u201d and \u201coffset\u201d are the values generated using the three address code for declarations<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 addwidth(table, width) \u2013 This function is used to determine the total width of all entries in table<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 enterproc(table, name, newtable) \u2013 This function creates a new entry in table for procedure with local scope newtable. Here \u201ctable\u201d refers to the current table, \u201cname\u201d refers to the name of the newtable, \u201cnewtable\u201d refers to the address of the new table<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 lookup (table, name) \u2013 This returns a pointer to the entry in the table for name by following linked tables.<\/p>\n

       <\/p>\n

      Let us consider an example to demonstrate the linking of the various tables using the above discussed functions. Consider a structure \u201cS\u201d to have two integer variables and let \u2018s\u2019 be an instance of this structure.<\/p>\n<\/div>\n

       <\/p>\n

      struct S<\/p>\n

      { int a; int b;<\/p>\n

      } s;<\/p>\n

       <\/p>\n

      Let us define a function \u201cswap\u201d with two reference integer variables and the body of the function is defined as follows:<\/p>\n

      void swap(int& a, int& b)<\/p>\n

       <\/p>\n

      { int t; t = a; a = b;<\/p>\n

      b = t;<\/p>\n

      }<\/p>\n

      Consider the following main program which has calls the function swap() and another function foo().<\/p>\n

      main()<\/p>\n

      {struct S s; swap(a, b);<\/p>\n

      foo();<\/p>\n

      }<\/p>\n

       <\/p>\n

      The symbol table integrated information is shown in figure 23.1<\/p>\n

       <\/p>\n

      \"\"<\/p>\n

      As can be seen from figure 23.1, the initial symbol table is created when the compiler encounters the main() function using the mktable(nil) function. Once the structure variable is declared using the table information for structure, another table is created as mktable(main) and thus there is a link from main table to the table of the structure. The variable\u2018s\u2019 of the structure has its own symbol table to have information about its fields. The \u201centerproc\u201d function helps enter the details about the symbol table of \u2018s\u2019 in the current symbol table. The details about\u2018s\u2019 is entered in the current symbol table using the \u201center\u201d function. The width information about the structure variable is computed using addwidth() and in this example it is computed as \u201c8\u201d and s tored in the header field of the symbol table. Similarly, the function swap will have a total width as \u201c12\u201d and is stored in the table corresponding to the function \u201cswap\u201d. Let us see how the compiler builds the symbol table to remember the scope information. Consider the following function having calls to three functions A, B, C and assume function A in turn calls function D.<\/p>\n

       <\/p>\n

      Void foo( )<\/p>\n

       <\/p>\n

      {\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 call A()<\/p>\n

      call B()<\/p>\n

      call (C)<\/p>\n

      }<\/p>\n

      Void A()<\/p>\n

      {<\/p>\n

      call D()<\/p>\n

      }<\/p>\n

       <\/p>\n

      The calling stack phenomenon is given in figure 23.2 (a) through (d)<\/p>\n

       <\/p>\n

      \"\"<\/p>\n

       <\/p>\n

      As can be seen from figure 23 (a), when function A is called, it is pushed into the calling stack and in turn as A calls D, the information about D is pushed onto the stack. Once D returns, it is removed from the stack and so is the case with A. When B is called B is pushed onto the stack and a similar scenario happens with function call to C and is given in figures 23 (b) and (c). When C also terminates, it is also removed from the stack. The address of the symbol tables are maintained as a stack. This information is used to refer to the variables of the functions which are available in the top of the stack thus ensuring scope information. Once, a function terminates, the address of this symbol table is removed from this stack.<\/p>\n

       <\/p>\n

        \n
      1. 2 Semantic rules for generating Three-address code for scope information<\/strong><\/li>\n<\/ol>\n

        \u00a0 \u00a0 \u00a0The functions discussed in the previous section are used to generate three-address code for maintaining scope information. Table 23.1 gives the semantic rules for generating three address code for procedures to maintain scope information. The semantic rule makes use of the functions discussed in the previous section. A stack of addresses of the symbol table indicated as \u201ctblptr\u201d is maintained and is useful in accessing the topmost symbol table at any point of time.<\/p>\n

         <\/p>\n

        Table 23.1 Semantic rules for maintaining scope information<\/p>\n

         <\/p>\n

        \"\"<\/p>\n

         <\/p>\n

        \"\"<\/p>\n

         <\/p>\n

        The details in Table 23.1 gives the semantic rules for maintaining the scope of symbol tables using two stacks, one of the stack tblptr<\/strong> is used to keep track of the available symbol table and the other one, offse<\/strong>t is used to determine the relative addresses of variables in a function. When a new procedure is called a symbol table is created and its pointer pushed to this stack with offset information in another stack. When the function call seizes this symbol table address is popped off the stack.<\/p>\n

         <\/p>\n

        23.3 Semantic rules for Records in Pascal<\/strong><\/p>\n

         <\/p>\n

        After discussing the semantic rules for generating three-address code to maintain scope information, we will conclude with generating three-address code for records. The semantic rules for generating three-address code for records are given in Table 23.2<\/p>\n

         <\/p>\n

        \"\"<\/p>\n

         <\/p>\n

        This uses a function \u201cemit\u201d which is used to generate three address codes to output file. As can be seen from Figure 23.1, the second statement involves generating a three address code, id.place := E.place whereas a sequence of statements doesn\u2019t involve any code.<\/p>\n

         <\/p>\n

        23.5 Three-address code for assignment statements<\/strong><\/p>\n

         <\/p>\n

        Names in the symbol table are the variables which are referred to addresses. The function Lookup(id.name) identifies variable \u201cid\u201d in symbol table. The function emit is used to emit three address statements to output file. Table 23.3 gives the set of semantic rules for the expression grammar using emit function. This is similar to the one already discussed in the previous module with \u201cgen\u201d function replaced with \u201cemit\u201d function.<\/p>\n

         <\/p>\n

        \"\"<\/p>\n

        \n

        From tables 23.3 and 22.6 of the previous module, it can be seen that if the expression is long, the number of temporary variables involved also increased. To tackle this situation, we keep track of a counter wherein the number of temporary variables could be reused. We modify newtemp<\/em>() to use a \u201cstack\u201d. We keep a counter c <\/em>initialized to 0, and is used to track the number of temporary variables. newtemp<\/em>() increments c<\/em> and returns temporary $c.<\/em> We decrement counter on each use of a $i in a three-address statement.<\/p>\n

         <\/p>\n

        Consider the production E<\/em>1 + E<\/em>2. The correct evaluation is to evaluate E<\/em>1 into t1 and E<\/em>2 into t2 and is shown below.<\/p>\n

         <\/p>\n

        t3:= t1 + t2<\/p>\n<\/div>\n

        As t1 is no longer required, we can reuse t1 instead of using new temp t3. This is the fundamental idea. This is explained in the following example.<\/p>\n

        Consider the expression x : = a * b + c*d \u2013 e * f. The use and re-use of temporary variables is given in table 23.4<\/p>\n

         <\/p>\n

        \"\"<\/p>\n

        \"\"<\/p>\n

        \u2013\u00a0 em = em-1\u00a0 + im<\/p>\n

         <\/p>\n

        \u2013\u00a0 e1 = i1<\/p>\n

         <\/p>\n

        This will be discussed in detail in the next module.<\/p>\n

         <\/p>\n

        Summary: <\/strong>This module discussed the three-address code for declarations in the view of maintaining scope information using symbol table and keeping an access of all symbol tables. The grammar for arrays in Pascal has been introduced. The next module will discuss about defining semantic rules for generating three-address code for accessing arrays.<\/p>\n

         <\/p>\n

          \n
        • Grammar for arrays have been discussed<\/li>\n<\/ul>\n

          \n","protected":false},"author":4,"menu_order":23,"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-196","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\/196","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":1,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/196\/revisions"}],"predecessor-version":[{"id":205,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/196\/revisions\/205"}],"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\/196\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/media?parent=196"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapter-type?post=196"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/contributor?post=196"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/license?post=196"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}