Есть ли хорошие / интересные аналоги регулярных выражений в 2d?

Question

Есть ли хорошие (или хотя бы интересные, но ошибочные) аналоги регулярных выражений в двух измерениях?

В одном измерении я могу написать что-то вроде /aaac?(bc)*b?aaa/, чтобы быстро вытянуть область чередующихся b с и c с с границей не менее трех a с. Возможно, что не менее важно, я могу вернуться через месяц и сразу увидеть, что он ищет.

Я пишу собственный код для аналогичных задач в 2d (некоторые гораздо более сложные / ограниченные), и было бы неплохо иметь более сжатую и стандартизированную нотацию, даже если мне придется самому писать движок.

Второй пример может быть назван "найти +". Цель состоит в том, чтобы найти столбец из 3 или более a с, b заключенный в скобки из 3 или более a с, с тремя или более a с ниже. Должно совпадать:

..7...hkj.k f
7...a  h o j 
----a--------
 j .a,g- 8 9 
.aaabaaaaa7 j
 k .a,,g- h j
 hh a----?  j
    a   hjg 

и может быть записано как [b ^ (a {3}) v (a {3})> (a {3}) <(a {3})] или ... </p>

Предложения

Answer 1

Не будучи экспертом по регулярным выражениям, но находя проблему интересной, я оглянулся и нашел эту интересную запись в блоге . Особенно привлекательным выглядит синтаксис, используемый там для определения 2D-выражения. Связанная с этим статья может рассказать вам больше, чем я.

Обновление от комментария: Вот ссылка на главную страницу автора, где вы можете скачать связанную статью "Двумерные языки" : http://www.mat.uniroma2.it/~giammarr/Research/pubbl.html

Answer 2

Хорошая проблема.

Во-первых, спросите себя, можете ли вы ограничить шаблон шаблоном "+", или вам также необходимо проверить / сопоставить прямоугольники. Например, прямоугольник из [bc] с a границей a будет соответствовать центральному прямоугольнику ниже, но также будет соответствовать форме "+" [c([bc]*a})v([bc]*a)>([bc]*a)<([bc]*a)] (в вашем синтаксисе)

xxxaaaaaxxx
yzyabcba12d
defabcbass3
oreabcba3s3
s33aaaaas33
k388x.egiee

Если вы можете ограничить его знаком "+", тогда ваша задача будет намного проще. Как сказал ShuggyCoUk, синтаксический анализ RE обычно эквивалентен DFSM - но для одного последовательного ввода, который значительно упрощает работу.

В вашем "RE +" движке вам придется отлаживать не только движок, но и каждое место, где вводятся выражения. Я хотел бы, чтобы компилятор ловил любые ошибки, которые он мог. Учитывая это, вы также можете использовать что-то, что было явно четырьмя RE, например:

REPlus engine = new REPlus('b').North("a{3}")
   .East("a{3}").South("a{3}").West("a{3}");

Однако, в зависимости от вашей реализации, это может быть громоздким.

А что касается движка обхода - будут ли шаблоны Север / Запад соответствовать RtL или LtR? Это может иметь значение, если шаблоны соответствуют или не соответствуют жадным подсовпадениям.

Кстати, я думаю, что '^' в вашем примере должен быть одним символом слева, вне скобок.

Answer 3

По сути, вы говорите о языке пространственных запросов . Есть много, если вы посмотрите на пространственный запрос, географический запрос и графический запрос. Пространственная часть обычно сводится к точкам, линиям и объектам в регионе, которые имеют другие заданные атрибуты. Регионы могут быть заданы в виде полигонов, расстояния от точки (например, окружностей), расстояния от линейного объекта, такого как дорога, всех точек на одной стороне линейного объекта и т. Д. Затем можно перейти к более сложным запросам, таким как набор всех ближайших соседей, кратчайшего пути, коммивояжера и тесселяций, таких как диаграммы TIN Делоне и диаграммы Вороного.

Answer 4

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

Можете ли вы использовать регулярные выражения? Это зависит от того, является ли искомое свойство разложенным на компоненты, которые могут быть сопоставлены в одном измерении или нет. Если это так, вы можете запускать свои регулярные выражения для столбцов и строк и искать пересечения в наборах решений из них. В зависимости от конкретной проблемы это может либо решить проблему, либо найти области в вашем 2d-массиве, которые могут быть решениями.

Независимо от того, является ли ваша проблема разложимой или нет, я думаю, что написание некоторого пользовательского кода будет неизбежным. Но, по крайней мере, это звучит как интересная проблема, поэтому работа должна быть приятной.