Sub-wavelength lithography in modern fabrication processes has resulted in a tremendous increase in the number of design rules. Of these, the context dependent design rules are especially hard to adhere to during manual layout creation. Layout legalization or automatic correction of design rule violation, therefore, has attained prime importance. Layout legalization can be modeled as a modified layout compaction problem. Generation of constraints from a given layout is a crucial step in compaction. In this paper, we propose a systematic framework for constraint generation that identifies context dependent rules and ensures legal layout upon compaction. In addition, we suggest practical schemes for reducing the legalization problem size that results in subsequent efficient solution.