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

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

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 из regex. Я нахожусь на правильном пути (с формой rpn) или есть другой (и/или более простой) способ?

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

Ответы

Ответ 1

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

Ответ 2

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

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

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
}

Ответ 3

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

  • 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'

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