Learning semantic string transformations from examples

We address the problem of performing semantic transfor-mations on strings, which may represent a variety of data types (or their combination) such as a column in a relational table, time, date, currency, etc. Unlike syntactic transfor-mations, which are based on regular expressions and which interpret a string as a sequence of characters, semantic trans-formations additionally require exploiting the semantics of the data type represented by the string, which may be en-coded as a database of relational tables. Manually perform-ing such transformations on a large collection of strings is error prone and cumbersome, while programmatic solutions are beyond the skill-set of end-users. We present a pro-gramming by example technology that allows end-users to automate such repetitive tasks. We describe an expressive transformation language for semantic manipulation that combines table lookup opera-tions and syntactic manipulations. We then present a syn-thesis algorithm that can learn all transformations in the language that are consistent with the user-provided set of input-output examples. We have implemented this technol-ogy as an add-in for the Microsoft Excel Spreadsheet system and have evaluated it successfully over several benchmarks picked from various Excel help-forums. 1