Виртуальная машина из регулярного выражения

Question

Я прочитал " Сопоставление регулярных выражений: подход виртуальной машины" и теперь пытаюсь разобрать регулярное выражение и создать из него виртуальную машину. Токенизатор работает и создает свои токены. После этого шага я создаю обратную польскую запись из потока токенов, так что в конце я получаю

a b c | |

из регулярного выражения a|(b|c), Хорошо, теперь шаг, где я застрял: я хочу получить массив

0: split 1, 3
1: match 'a'
2: jump 7
3: split 4, 6
4: match 'b'
5: jump 7
6: match 'c'
7: noop

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

output              stack
------------------- ------
0: match 'a'        0: 0
1: match 'b'        1: 1
2: match 'c'        2: 2

С |, Я выталкиваю последние 2 позиции из стека и вставляю split а также jump на конкретных позициях. Значения рассчитываются на основе текущей длины стека и количества добавляемых элементов. В конце я добавляю новую стартовую позицию последнего элемента в стек (в этом случае остается такой же).

output              stack
------------------- ------
0: match 'a'        0: 0
1: split 2, 4       1: 1
2: match 'b'
3: jump 5
4: match 'c'

Это выглядит нормально. Теперь следующий | выскочил...

output              stack
------------------- ------
0: split 1, 3       0: 0
1: match 'a'
2: jump 7
3: split 2, 4
4: match 'b'
5: jump 5
6: match 'c'

И вот проблема. Я должен обновить все адреса, которые я вычислил ранее (строки 3 и 5). Это не то, что я хочу. Я думаю, относительные адреса имеют ту же проблему (по крайней мере, если значения являются отрицательными).

Итак, мой вопрос, как создать VM из регулярных выражений. Я на правильном пути (с rpn-формой) или есть другой (и / или более простой) способ?

Выходной массив хранится в виде целочисленного массива. split-команде фактически нужно 3 записи, jump нужно два,...

Answer 1

Вместо этого было бы проще использовать относительные прыжки и шпагаты.

• a - Нажмите match в стек

  0: match 'a'
  

• b - Нажмите match в стек

  0: match 'a'
  --
  0: match 'b'
  

• c - Нажмите match в стек

  0: match 'a'
  --
  0: match 'b'
  --
  0: match 'c'
  

• | - Вытащить два кадра из стека и вместо этого нажать split <frame1> jump <frame2>

  0: match 'a'
  --
  0: split +1, +3
  1: match 'b'
  2: jump +2
  3: match 'c'
  

• | - Вытащить два кадра из стека и вместо этого нажать split <frame1> jump <frame2>

  0: split +1, +3
  1: match 'a'
  2: jump +5
  3: split +1, +3
  4: match 'b'
  5: jump +2
  6: match 'c'
  

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

Answer 2

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

Answer 3

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

Answer 4

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

Допустим, у вас был узел OR, например, с двумя дочерними элементами "left" и "right". Каждый узел реализует метод generate(OutputBuffer)и реализация для узла OR будет выглядеть так:

void generate(OutputBuffer out)
{
int splitpos = out.length();
out.append(SPLIT);
out.append(splitpos+3); //L1
out.append(0); //reservation 1
//L1
left.generate(out);
int jumppos = out.length();
out.append("JUMP");
out.append(0); //reservation 2
//L2
out.set(splitpos+2, out.length()); //reservation 1 = L2
right.generate(out);
//L3
out.set(jumppos+1, out.length()); //reservation 2 = L3
}