Circular dependency problem

Question

"Single item in a set depends on the whole set. Set depends on that item."

I'm creating a compiler (https://github.com/SuperJMN/Plotty). In the last stage, the Intermediate Code is converted to Machine Instructions. I have them represented with the IntermediateCode and MachineCode classes.

To do it, I'm using the Visitor Pattern, that visits each of the elements of the list of Intermediate Codes. Each Intermediate Code can emit one or more MachineCodes.

It's working perfectly, but I have a big problem: one of the instructions that must be generated is dependent on the whole result! Concretely, there is an instruction that needs to know the index (ordinal) of another instruction has not been generated yet.

In other words, I have to emit an instruction that means "push the address of label X", when label X hasn't been emitted yet. The address of that label will only be known when all the instructions have been emitted.

The illustrate the problem better, this is similar to the creation of table of contents in a document. If you want to be able to create the TOC, where you want to specify the page number of a given section, first you have to generate the all the document, so you can then know the page of a given section.

Can you please tell me an algoritmo or a pattern to solve my problem? I don't know how to emit those pending-fix instructions.

Big thanks!

Answer 1

You can do a two pass compilation. In the first pass emit the machine instructions as you do now. When you encounter a label record its address in a symbol table. When you encounter a reference to a label, check the symbl table. If it has no entry for the label, create an entry for the label but leave its address blank and emit a placeholder in the stream of machine instructions. In the second pass fill in the label references that you didn't know during the first pass.

By introducing the extra concepts symbol table, label and address you break the circular dependencies.