Есть ли примеры "движков" подобных движкам регулярных выражений, где с помощью машин конечных автоматов реализуют описание образца для сопоставления по набору данных, но чтоб домен был не строки как в случае с регулярками, а некий другой отличный от строк?
В ANTLR в качестве входа в парсер являются токены. А как ты генерируешь поток токенов - не важно. Обычно используется лексер на строках, но при желании можно создавать эти токены и привязывать к чему угодно. Правда это будет даже не регулярки, а более мощные языки - контекстно-свободные.