EXERCISES

1. For a reasonably complete semantic check on the variables in a program, the following information may need to be associated with each variable a, by keeping it in its Symbol Table entry.
   • Does the program include a declaration for a?
   • Does the program include a definition for a?
   • What is the type of a?
   • Has a been properly initialized (before use)?
   • Does any function or statement ever use a?
   • What is the storage address of a?
   • Is a in the current scope?

   Considering the Node definition used by us, suggest ways in which this requirement be satisfied.

2. Consider the grammar G_b given in the exercises of Chapter 4 for “Boolean expression calculator”. Express its attribute grammar in yacc format.
3. Prepare an attribute grammar in yacc format for the grammar G_p of the “Parentheses Language” given in the exercises of Chapter 4. The attribute we want to express is the depth of parenthesis.
4. Draw and annotate a tree for input ((a)+(b)) given a grammar with the following rules:

   E –> E + T	$$ = mknode(″+″,$1,$3)
   E –> E – T	$$ = mknode(″–″,$1,$3)
   E –> T	        $$ = $1;
   T –> ( E )	$$ = $2;
   T –> id	        $$ = mkleaf(id,$1)
   T –> num	$$ = mkleaf(num,$1)
   

   mknode(op,left,right) creates an operator node with the label op and two pointers: left and right.
5. Consider the following grammar:

   S –> L . L
   S –> L
   L –> L B
   L –> B
   B –> 0
   B –> 1
   

   Let the synthesized attribute val gives the value of the binary number generated by S in the grammar. For example, on input 101.101, S.va1 = 5.625. Use synthesized attributes to determine S.val.
6. Using yacc, implement a syntax-directed translator that translates the sequences of postfix polish expressions into infix notation. For example, your translator should map 345+* into 3*(4+5)
7. Optimize your translator so it does not generate any redundant parentheses. For example, your translator should still map 345+* into 3*(4+5), but it should map 345*+ into 3+4*5.
8. You are required to develop a program similar to the indent utility in Unix-like systems. This utility re-formats a C source code according to a specified coding style, especially, it provides nice indentations. For example, given a source file:

   #include <stdio.h>
   int main(){int i; printf(″Start
   ″); if(i < 10) printf(″OK
   ″);}
   

   it converts it into one looking like:

   #include <stdio.h>
   int
   main()
   {
    int i;
    printf(″Start
   ″);
    if(i < 10)
      printf(″OK
   ″);
   }
   

   Your program will have to parse the input file for at least the control constructs in C. Write the yacc grammar with required action terms to develop this utility.
9. In this exercise you are required to write a syntax highlighter program, which prints a given C source code, with all the keywords in bold–face and conditions within IF-THEN and WHILE-DO in italics. Your program will have to do some minimal parsing. You can assume that inserting <bf> </bf> around a word will make it display/print in bold-face and, similarly, <it> </it> will make a string display in italics. Write the required yacc grammar with proper action terms to achieve this utility.
10. School children are taught a simple, graphics-based programming language called LOGO. Obtain details of this language, if possible install it on your computer and play with it and then write an interpreter for LOGO.
11. In this exercise you are required to prepare the SDT scheme for a column-major organization of an array. Indicate the attributes of your SDT scheme along with the auxiliary functions you are using. Define a grammar and its semantic actions for this translation. Show the annotated parse tree and generated code for the assignment x = A[y, z] under the assumption that A is 10 × 20 array with starting index 0 and sizeof(baseType(A)) = sizeof(int) = 4-bytes.