Abstract Parsing With String Updates Using LR-Parsing Technology
The authors combine LR (k)-parsing technology and data-flow analysis to analyze, in advance of execution, the documents generated dynamically by a program. Based on the document language's context-free reference grammar and the program's control structure, formatted as a set of flow equations, the analysis predicts how the documents will be generated and simultaneously parses the predicted documents. Recursions in the flow equations cause the analysis to emit a set of residual equations that are solved by least-fixed point calculation in the domain of abstract (folded) LR-parse stacks. Since the technique accommodates LR (k) grammars, it can also handle string-update operations in the programs by translating the updates into finite-state transducers, whose controllers are composed with the LR (k)-parser controller.