A method and apparatus is provided for partial evaluation of XML queries for program analysis. An executable version of a first body of instructions that conforms to an XML computer language, such as XSLT, is generated. The executable version may include trace instructions for collecting information about executing the executable version against representative data, such as an XML schema document. This execution causes the generation of an execution graph, which may be optimized by the collected information. Based on the execution graph, a second body of instructions is generated that conforms to a different computer language, such as XQuery. Subsequently, the second body of instructions may be applied against XML documents that conform to the same schema as the representative data. By generating the second body of instructions before source XML documents are received, several optimizations may be made that greatly decrease the time for querying and/or transforming XML documents.