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

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

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

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

Второй пример можно назвать "найти +". Цель состоит в том, чтобы найти столбец из 3 или более a s, 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})] или...

Предложения?

Ответ 1

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

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

Ответ 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}");

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

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

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

Ответ 3

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

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

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

Ответ 4

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