Abstract parsing with string updateds using LR-parsing technology

Abstract

We 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. (joint work with Kyung-Goo Doh and Hyunha Kim, Hanyang University)

Resources

• talk slide