zbMATH — the first resource for mathematics

Derivation of deterministic inverse programs based on LR parsing. (English) Zbl 1122.68394
Kameyama, Yukiyoshi (ed.) et al., Functional and logic programming. 7th international symposium, FLOPS 2004, Nara, Japan, April 7–9, 2004. Proceedings. Berlin: Springer (ISBN 3-540-21402-X/pbk). Lecture Notes in Computer Science 2998, 291-306 (2004).
Summary: We present a method for automatic program inversion of functional programs based on methods of LR parsing. We formalize the transformation and illustrate it with the inversion of a program for run-length encoding. We solve one of the main problems of automatic program inversion – the elimination of nondeterminism – by viewing an inverse program as a context-free grammar and applying to it methods of LR parsing to turn it into a recursive, deterministic inverse program. This improves the efficiency of the inverse programs and greatly expands the application range of our earlier method for program inversion.
For the entire collection see [Zbl 1048.68005].

68N18 Functional programming and lambda calculus
Full Text: DOI