Ну и отлично.

Во-первых, надо разрешить искать подстроки по всему тексту, а не только последовательно.

Во-вторых, если 2 выражения зацепились за непересекающиеся подстроки, то результат они втыкают на то место, где нашли свои подстроки. Тут нет никаких проблем.

Если же подстроки пересекаются, то вся машина делает branch, и каждый branch продолжает жить своей собственной жизнью.

Кроме того, должна быть операция добавить результат выражения в конец текста в родительском бранче. Это способ вернуть из бранча результат. Разумеется, если есть несколько бранчей, их выдача добавляется в том порядке, в каком повезет, но выдача одного выражения всегда добавляется атомарно.