filmov
tv
[SAS23] Reverse Template Processing using Abstract Interpretation
Показать описание
[SAS23] Reverse Template Processing using Abstract Interpretation
Matthieu Lemerre
Template languages transform tree-structured data into text. We study the reverse problem, transforming the template into a parser that returns all the tree-structured data that can produce a given text. Programs written in template languages are generally not injective (they have multiple preimages), not affine (some input variables can appear at several locations in the output), and erasing (they provide only a partial view of the source), which makes the problem challenging. We propose to solve this problem using concepts from abstract interpretation, like the denotational style of abstract semantics, soundness, exactness, or reduction, to reason about the precision and the recovery of all the preimages. This work shows that Abstract Interpretation is a very useful theory when reasoning about the reversal of non-injective programs.
Matthieu Lemerre
Template languages transform tree-structured data into text. We study the reverse problem, transforming the template into a parser that returns all the tree-structured data that can produce a given text. Programs written in template languages are generally not injective (they have multiple preimages), not affine (some input variables can appear at several locations in the output), and erasing (they provide only a partial view of the source), which makes the problem challenging. We propose to solve this problem using concepts from abstract interpretation, like the denotational style of abstract semantics, soundness, exactness, or reduction, to reason about the precision and the recovery of all the preimages. This work shows that Abstract Interpretation is a very useful theory when reasoning about the reversal of non-injective programs.