×

Improving determinization of grammar programs for program inversion. (English) Zbl 1394.68082

Albert, Elvira (ed.), Logic-based program synthesis and transformation. 22nd international symposium, LOPSTR 2012, Leuven, Belgium, September 18–20, 2012. Revised selected papers. Berlin: Springer (ISBN 978-3-642-38196-6/pbk). Lecture Notes in Computer Science 7844, 155-175 (2013).
Summary: The inversion method proposed by Glück and Kawabe uses grammar programs as intermediate results that comprise sequences of operations (data generation, matching, etc.). The determinization method used in the inversion method fails for a grammar program of which the collection of item sets causes a conflict even if there exists a deterministic program equivalent to the grammar program. In this paper, by ignoring shift/shift conflicts, we improve the determinization method so as to cover grammar programs causing shift/shift conflicts. Moreover, we propose a method to eliminate infeasible definitions from unfolded grammar programs and show that the method succeeds in determinizing some grammar programs for which the original method fails. By using the method as a post-process of the original inversion method, we make the original method strictly more powerful.
For the entire collection see [Zbl 1271.68016].

MSC:

68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
68N18 Functional programming and lambda calculus
68Q42 Grammars and rewriting systems
PDFBibTeX XMLCite
Full Text: DOI