There are two features of the expression language of C that we did not account
for. The first is use of the increment and decrement operators ++ and --.
The second is the use of assignments as expressions (that is, and assignment
is considered to be an expression whose value is the value assigned). Show
how to
modify the class notes on code generation to account for these two features.
(You do not need to show how type checking changes). Show the IC code that
would be generated for the following C program:
main() {
int A, B;
A = 3;
++A;
A--;
B = ( ( A = ++A ) + ( B = A-- ) );
}
The obvious solution is simply to add this syntax to the expression language, and to generate the assignments as these are encountered (first rule is as before, just to show where to put the new stuff):
E --> E + E E.place = newtemp()
AddQuad("plus", E.place, E1.place, E2.place)
E --> ++E E.place = newtemp()
AddQuad("plus", E1.place, E1.place, 1)
AddQuad("move", E.place, -, E1.place)
E --> --E E.place = newtemp()
AddQuad("sub", E1.place, E1.place, 1)
AddQuad("move", E.place, -, E1.place)
E --> E++ E.place = newtemp()
AddQuad("move", E.place, -, E1.place)
AddQuad("plus", E1.place, E1.place, 1)
E --> E-- E.place = newtemp()
AddQuad("move", E.place, -, E1.place)
AddQuad("sub", E1.place, E1.place, 1)
E --> id = E E.place = newtemp()
AddQuad("move", id.lexval, -, E1.place)
AddQuad("move", E.place, -, E1.place)
Note that for ++E and --E you could simply assign E.place the value of E1.place; I have used another temp here to be consistent with the third and fourth rules. Unfortunately, this is not sufficient, as you will have a reduce/reduce conflict if you leave the usual rule for assignments in place; instead, you must replace the rule for statements:
S --> id = E AddQuad("move", id.lexval, -, E.place)
S.breaklist = NULL;
with:
S --> E S.breaklist = NULL;
Note that the place attribute for this E will be simply ignored. This allowed arbitrary expressions to be listed as statements, but that is what C is about! Here is the translation of the code above:
move A, -, 3 add A, A, 1 move T1, -, A // could be removed by optimizer move T2, -, A // ditto sub A, A, 1 add A, A, 1 move T3, -, A move A, -, T3 move T4, -, T3 move T5, -, A sub A, A, 1 move B, -, T5 move T6, -, T5 add T7, T4, T6 move B, -, T7Clearly there is alot of redundancy here, and room for improvement in the use of temporaries!
We also did not account for the switch statement in our translation scheme. Show how to modify the code generation attribute grammar to account for switch statements, and provide a short example of source code and IC translation according to your translation scheme.
S --> while Dum1 Dum1.temp = nextQuad; // Location of start of E
( E ) Dum2 Dum2.temp = nextQuad // Location of unfilled jump
AddQuad("beq", E.place, "0", -)
S AddQuad(jump, -, -, Dum1.temp)
code[Dum2.temp].arg3 = nextQuad // local backpatch!
BackPatch(S1.breaklist, nextQuad) // backpatch breaklists
S.breaklist = NULL
S --> switch ( E ) Dum5 Dum5.temp = nextQuad; // location of jump to branch list
AddQuad(j, -, -, -)
{ CaseList } code[Dum5.temp].arg3 = nextQuad+1 // local backpatch!
For (every instruction I in TempCode)
if I is in form (beq -, n, k)
AddQuad(beq E.place, n, k)
else
AddQuad( I ) // must be jump
BackPatch(CaseList.breaklist, nextQuad) // backpatch breaklists
S.breaklist = NULL
CaseList --> Case CaseList.breaklist = Case.breaklist
CaseList --> Case CaseList CaseList.breaklist = Append( Case.breaklist, CaseList1.breaklist )
Case --> case intnum : Add to TempCode the statement (beq -, intnum.value, nextQuad) // first argument left blank
L Case.breaklist = L.breaklist // L is list of statements, defined in rest of grammar
Case --> default : Add to TempCode the statement (j -, -, nextQuad)
L Case.breaklist = L.breaklist
switch (N + 8)
{
case 1:
M = M - 2;
Q = 4;
case 2:
M = M + 5;
Q = 5;
break;
default:
M = M + 3;
}
0: add T1, N, 8
1: jump 9
2: sub M, M, 2 // case 1
3: move Q, -, 4
4: add M, M, 5 // case 2
5: move Q, -, 5
6: jump 10
7: add M, M, 3 //default
8: jump 10
9: beq T1, 1, 2 // list of branches
10: beq T1, 2, 4
11: j 7
12:
Union types are similar to structs, except the members are assumed to be alternatives, i.e., at most one of them is used at a time, and only enough storage is allocated for the largest of the members. You can read more about Unions here. For example, here is a union declaration:
union sample {
int A;
float B;
char C;
} X
You can refer to X.A or X.B or X.C, but there is only one word of storage allocation to any of these. The interesting thing here is that you can do an implicit cast from one type to another, for example, you can assign 3.4 to X.B and then print out X.A to see the integer corresponding to the floating-point representation for 3.4.
For type-checking, you proceed just as if the union were a normal struct. For code generation, the data layout here is extremely simple. You just need to determine the maximum size of any of the components (this was done in the section on type checking when building symbol tables), and this would be the size for the union type variable. The offset for any of the components is 0 (as if they were all the first field of a struct). That's it!
In C, function definitions are allowed only in file scope, that is, a C program consists of a list of function and variable declarations, and no function can be defined inside another function or inside a struct. Some language do allow this, for example in Java you may define a function inside a class, and in Pascal you can define a function inside another function.
Explain what would be necessary to change in our translation scheme to account for both functions defined within functions, and functions defined within structs. Be sure to discuss what would change in the type-checking process (i.e., how does scoping work for these extensions) and in the code generation process. Again, confine your answer to about a page in length, and be as precise as possible. You do not need to give the attribute grammar for this.
The type-checking question here was a trick question, because it is really no different than type-checking for variables in functions and structs. You can put function names into symbol tables whether they are the global symbol table, or a symbol table on the stack (whether in a nested function or inside a struct). The scoping rules for functions are the same as for variables, so you will look up functions and find the appropriate symbol tables and check uses of function names as you do for variables.
For code generation, there is a little bit of a problem if you want to generate code for all functions as you make one pass through the source code, if you allow functions to be defined inside structs that are part of arbitrary declarations (i.e., you might be in the middle of generating code for one function, and then have to start generating code for another). Usually, the language is defined in such a way that this can not happen. If it is not, then you will need to generate code in temporary code arrays and paste them in later.
Other than that, again, there remarkably little difference in the basic code generation process. A function defined inside another function or inside a struct is really just a function with a restricted scope, and scoping is just part of the type checking process, and does not affect code generation that much. There are some optimizations you can perform on the run-time stack to speed up the accessing of global variables inside nested functions (the so-called "display" technique), but I would not expect you to have thought of this!
Whenever you submit a piece of academic work and sign your name to it, you are verifying that this work is the result of your own intellectual efforts; it is Plagiarism to submit work solely under your own name in which:
In this course, I will not allow you to submit any joint work, although in other courses and in other contexts you may be permitted to do this. In general, you must always provide proper attribution of authorship by naming all persons, books, or resources that provided intellectual content towards the final result. In some cases, you will need to describe the extend of the contribution, particularly when literally copying the words or artistic artifacts of another. To fail to provide proper attribution is plagiarism. Plagiarism demeans the seriousness of what we do in class, and does not allow you as a student to obtain a fair grade for the results you worked hard for.
I will discuss the issue of plagiarism with the grader, and use, when appropriate, automated tools to check submitted programs and files for copying. I don't like to be involved in this, but it is necessary in order to provide a fair environment for your work. In cases of suspected plagiarism, I will discuss the matter with the student(s) involved and, when warrented, submit the case to the Academic Conduct Committee (of which I was chairman for three years). Unfortunately, students in my classes violate these policies several times a year on average; it is my hope that by being completely clear and straight-forward about my policy that I can reduce this number. Please take this issue serious and talk to me if you have any concerns or questions.