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

Question

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

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

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

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

..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 

и может быть записана в виде [Ь (а {3}) V (A {3})> (а {3}) < (а {3})] или .. .

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

Answer 1

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

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

Answer 2

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

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

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

Answer 3

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

Answer 4

Приятная проблема.

Во-первых, спросите себя, можете ли вы ограничить шаблон шаблоном «+», или вам также нужно будет проверить и сопоставить прямоугольники. Например, прямоугольник из [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? Это может иметь значение, если шаблоны соответствуют по-разному с или без жадных суб-матчей.

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