Context-Free Grammars Including Left Recursion using Recursive miniKanren

Abstract

Recursive miniKanren is logic programming language which can deal infinite recursive data structure and a subset of the Scheme language. We define apattern match macro which can use the same syntax of the match macro of the Scheme language using recursive miniKanren. The macro enables to write searching sub-list with a given pattern by only few line code. Using this property, we introduce techniques writing context-free grammar with our match macro. Unlike other specific paraphrasing tools, our technique can combine logical relations of miniKanren with acontext-free grammar. We show the logical relations resolves the ambiguity of a grammar.