1

In the book Compilers: Principles, Techniques, and Tools (2nd Edition), Appendix A, the authors offer a implementation of a compiler front-end that generates three-address code for a very simple language.

Like many other languages, the language in the book has scopes denoted by opening and closing curly braces. To avoid name conflicts when generating three-address code for nested blocks, the parser uses a hierarchal structure of symbol tables.

However, while this works well when generating the code, how are name conflicts avoid in the three-address code its self?

To demonstrate what I mean, consider this example code written according to the grammar in the book:

{
    int a;
    a = 1
    {
        int a;
        a = 2;
    }
    int b;
    b = a;
}

The compiler in the book would generate the following code:

L1: a = 1
L3: a = 2
L4: b = a;
L2:

In the above code, how does the compiler access the correct value of a when translating the instruction b = a;? The variable a declared in the nested scope stomps on the value of the a in the previous scope.

In section 8.4 of the book, the authors mention allocating the three-address code into basic blocks which seemed to solve the problems above. However, upon closer inspection this did not prevent names from different scopes erasing each others values.

Is this normal in three-address code? If so, how does the compiler distinguish between various local and global names? If not, what is the usually syntax used to denote variables in different scopes?

The reason this seems like such a big problem, is because in section 8.6 of the book, the authors introduce a simple code generation algorithm for translating the three-address code to a contrived assembly language. In section 8.6.1, they mention that for the algorithm to work correctly, each variable in the source code needs a variable descriptor. Essentially a data structure to hold all of the address of where the value of the variable can currently be found.

With the structure of the three-address code above, how would those instructions be correctly followed. How would each variable name in the program have a distinct variable descriptor? This simply doesn't seem to be possible.

  • 1
    Generating unique names for variables is an unremarkable problem. You could do it in a compiler by simply appending the current line number to the name. – Robert Harvey Sep 16 '17 at 19:46
  • @RobertHarvey Ah, I see. So your saying normally a compiler would generate a unique name for each variable in the source. I wonder why the "Dragon Book" never mentioned that. Well now it seems unremarkable, but at the time I didn't know if that was the common method. This is my first time doing something like this and I want to make sure I do it 'right'. – Christian Dean Sep 16 '17 at 20:01
  • There are so many ways to create executable code that it's hard to imagine there being "one true way." – Robert Harvey Sep 16 '17 at 20:08
1

The description in the book seems to be misleading. I would have written:

outer_a = 1
inner_a = 2
outer_b = outer_a

You could add some bits to make it clearer:

outer_a.startsexisting
outer_a = 1
inner_a.startsexisting
inner_a = 2
inner_a.endsexisting
outer_b.startsexisting
outer_b = outer_a
outer_b.endsexisting
outer_a.endsexisting

The two a's are different variables. They also have different scopes (ranges where the variable exists), in this case the scopes are nested. The variable b only exists after the inner a stops existing.

A compiler could just use three different memory locations for outer_a, outer_b, and inner_a. With a bit of cleverness it can use the same memory location for outer_b and inner_a because they don't exist at the same time.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.