Есть ли хорошие шаблоны / идиомы для трансляции / преобразования данных?

Question

Прошу прощения за общее название этого вопроса, но мне хотелось бы сформулировать его менее обобщенно. : -}

Я хотел бы написать программный продукт (в данном случае, использующий C ++), который переводит поток входных токенов в поток выходных токенов. Существует всего пять входных токенов (назовем их 0, 1, 2, 3, 4), и каждый из них может иметь несколько разных атрибутов (например, может быть свойство 4.x или 0.foo). Есть еще несколько выходных токенов, около десяти, назовем их (Out0..Out9), у каждого из них также есть несколько свойств.

Теперь мы работаем над отображением последовательностей из входных токенов в возможные выходные токены, например:

01 -> Out0
34 -> Out1
0101 -> Out3

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

В моем сценарии набор входных токенов фиксирован, но набор выходных токенов - нет - мы могли бы принять решение о введении новых «производств». Мой вопрос:

Кто-нибудь знает, есть ли хорошие образцы и / или идиомы, которые помогают в такой ситуации?

Прямо сейчас у меня есть набор объектов 'Compressor', каждый из которых может использовать входные токены и в конечном итоге создавать выходные токены. Проблема состоит в том, что некоторые входные токены конфликтуют, рассмотрите Out0 и Out3 в вышеупомянутом случае. Вход «0101» должен выдать Out3, но , а не Out0. Однако вход '0104 должен дать Out0, а затем оставить 0 и 4 в очереди.

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

Эта работа по «сокращению» ввода токенов низкого уровня в токены высокого уровня и решению возможных конфликтов распространена среди авторов синтаксических анализаторов, не так ли? Есть ли там полезные паттерны?

UPDATE:

Немного больше информации:

1. в моем конкретном случае входные токены являются структурами C, а выходные - токенами C ++. У меня нет никакого контроля над входным потоком токенов, но я могу поставить их в очередь и затем изменить очередь в случае, если это выгодно.

2. Я решил конфликты (например, Out3 (0101) против Out0 (01)), пытаясь сначала сопоставить Out3, а затем Out0, но это немного уродливо. Возможные производства находятся в списке, и я просто пытаюсь применить их к входному потоку, один за другим

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

Answer 1

Несколько лет назад я бы сразу сказал, посмотрите на Бизона http://www.gnu.org/software/bison/ или Яка, но я ничего подобного не делал в течение некоторого времени, поэтому не знаю, есть ли что-нибудь лучше.

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

Answer 2

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

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

Answer 3

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