An important application of dynamically and partially reconfigurable computing platforms is in dynamic task allocation and execution. On-line synthesis, on-line placement and on-line routing are the three essential steps in implementing an incoming task on the FPGA during run-time. Whereas there has been some research in on-line placement, on-line synthesis received relatively little attention. In this paper, we present what is believed to be the first on-line synthesis methodology for partially reconfigurable FPGAs. In on-line synthesis, time for synthesis should be kept low while ensuring the placeability of the synthesized design on the FPGA in the available empty area and meeting the performance requirements. We ensure placeability by considering and maintaining the available area on the FPGA surface as a collection of maximal empty rectangles. The proposed synthesizer allocates the FPGA resources adaptively and is incremental in nature. The algorithm is designed to be linear in terms of the number of operations to ensure its on-line usage. Our experimental results demonstrate the advantages of the proposed approach.