Обобщение для регулярного выражения в любом списке

Ответ 1

Регулярные выражения соответствуют только строкам, по определению.

Конечно, теоретически вы можете построить эквивалентную грамматику, например, для списков чисел. С новыми токенами, такими как \e для четных чисел, \o для нечетных чисел, \s для квадратных чисел, \r для действительных чисел и т.д., Так что

[1, 2, 3, 4, 5, 6]

будет соответствовать

^(\o\e)*$

или

[ln(3), math.pi, sqrt(-1)]

будет соответствовать

^\R*$

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

Ответ 2

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

"Маленький" пример в python:

def choice(*items):
  return ('choice',[value(item) for item in items])

def seq(*items):
  return ('seq',[value(item) for item in items])

def repeat(min,max,lazy,item):
  return ('repeat',min,max,lazy,value(item))

def value(item):
  if not isinstance(item,tuple):
    return ('value',item)
  return item

def compile(pattern):
  ret = []
  key = pattern[0]
  if key == 'value':
    ret.append(('literal',pattern[1]))
  elif key == 'seq':
    for subpattern in pattern[1]:
      ret.extend(compile(subpattern))
  elif key == 'choice':
    jumps = []
    n = len(pattern[1])
    for i,subpattern in enumerate(pattern[1]):
      if i < n-1:
        pos = len(ret)
        ret.append('placeholder for choice')
        ret.extend(compile(subpattern))
        jumps.append(len(ret))
        ret.append('placeholder for jump')
        ret[pos] = ('choice',len(ret)-pos)
      else:
        ret.extend(compile(subpattern))
    for pos in jumps:
      ret[pos] = ('jump', len(ret)-pos)
  elif key == 'repeat':
    min,max,lazy,subpattern = pattern[1:]
    for _ in xrange(min):
      ret.extend(compile(subpattern))
    if max == -1:
      if lazy:
        pos = len(ret)
        ret.append('placeholder for jump')
        ret.extend(compile(subpattern))
        ret[pos] = ('jump',len(ret)-pos)
        ret.append(('choice',pos+1-len(ret)))
      else:
        pos = len(ret)
        ret.append('placeholder for choice')
        ret.extend(compile(subpattern))
        ret.append(('jump',pos-len(ret)))
        ret[pos] = ('choice',len(ret)-pos)
    elif max > min:
      if lazy:
        jumps = []
        for _ in xrange(min,max):
          ret.append(('choice',2))
          jumps.append(len(ret))
          ret.append('placeholder for jump')
          ret.extend(compile(subpattern))
        for pos in jumps:
          ret[pos] = ('jump', len(ret)-pos)
      else:
        choices = []
        for _ in xrange(min,max):
          choices.append(len(ret))
          ret.append('placeholder for choice')
          ret.extend(compile(subpattern))
          ret.append(('drop,'))
        for pos in choices:
          ret[pos] = ('choice',len(ret)-pos)
  return ret

def match(pattern,subject,start=0):
  stack = []
  pos = start
  i = 0
  while i < len(pattern):
    instruction = pattern[i]
    key = instruction[0]
    if key == 'literal':
      if pos < len(subject) and subject[pos] == instruction[1]:
        i += 1
        pos += 1
        continue
    elif key == 'jump':
      i += instruction[1]
      continue
    elif key == 'choice':
      stack.append((i+instruction[1],pos))
      i += 1
      continue
    # fail
    if not stack:
      return None
    i,pos = stack.pop()
  return pos

def find(pattern,subject,start=0):
  for pos1 in xrange(start,len(subject)+1):
    pos2 = match(pattern,subject,pos1)
    if pos2 is not None: return pos1,pos2
  return None,None

def find_all(pattern,subject,start=0):
  matches = []
  pos1,pos2 = find(pattern,subject,start)
  while pos1 is not None:
    matches.append((pos1,pos2))
    pos1,pos2 = find(pattern,subject,pos2)
  return matches

# Timestamps: ([01][0-9]|2[0-3])[0-5][0-9]
pattern = compile(
  seq(
    choice(
      seq(choice(0,1),choice(0,1,2,3,4,5,6,7,8,9)),
      seq(2,choice(0,1,2,3)),
    ),
    choice(0,1,2,3,4,5),
    choice(0,1,2,3,4,5,6,7,8,9),
  )
)

print find_all(pattern,[1,3,2,5,6,3,4,2,4,3,2,2,3,6,6,5,3,5,3,3,2,5,4,5])
# matches: (0,4): [1,3,2,5]; (10,14): [2,2,3,6]

Несколько улучшений:

• Другие конструкции: классы с отрицанием, диапазоны
• Классы вместо кортежей

Ответ 3

Если вам действительно нужна свободная грамматика, как в регулярных выражениях, вам нужно идти так, как описано в ответе Тима. Если у вас есть только фиксированное количество шаблонов для поиска, тогда самый простой и быстрый способ - написать собственные функции поиска/фильтрации.

Ответ 4

Интересная проблема.

Боковое мышление: загрузите . Исходный код Net Framework, поднимите исходный код Regex и адаптируйте его для работы с целыми числами, а не с символами.

Просто идея.

Ответ 5

Ну, у Erlang есть шаблонное совпадение (вашего типа), встроенное прямо. Я сделал что-то подобное в Ruby - немного, вероятно, не слишком хорошо выполняющего хакерство, см. http://radiospiel.org/0x16-its-a-bird

Ответ 6

Вы можете попробовать pamatcher, это библиотека JavaScript, которая обобщает понятие регулярных выражений для любой последовательности элементов (любого типа).

Пример для "[abc] {3,}. ([ab]? [^ a] {4,7})" сопоставление шаблонов, где a, b, c являются целыми числами:

var pamatcher = require('pamatcher');

var a = 10;
var b = 20;
var c = 30;

var matcher = pamatcher([
  { repeat: 
      { or: [a, b, c] }, 
    min: 3
  },
  () => true,
  { optional: 
    { or: [a, b] } 
  },
  { repeat: (i) => i != a,
    min: 4,
    max: 7
  }
]);

var input = [1, 4, 8, 44, 55];
var result = matcher.test(input);
if(result) {
  console.log("Pattern matches!");
} else {
  console.log("Pattern doesn't match.");
}

Примечание. Я создатель этой библиотеки.