Как применить CYK или любой другой алгоритм разбора без изменения моей грамматики?

Question

Таким образом, у меня есть грамматика внутри одномерного массива, заданного формой

struct array
{
    char left;
    char right[3];
    char number;
}

Пример:

array.left = 'A';
array.right = "BC";
array.number = insert_some_conventional_null_character_here

Это переводится на:

A->BC

------

Другие примеры:

A->3
C->BDE
X->9

Кроме того, array.number ограничен [0, 9].

array.right и array.left являются литералами в интервале [A, Z].

Мне нужно вернуть связанный список, содержащий все правила (компоненты грамматики), примененные для получения из входной строки, называемой startString, в другую входную строку, называемую stopString.

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

Как мне поступить? Как и в Post-Scriptum, в грамматике не более 1000 таких правил, поэтому я предполагаю, что рекурсивный синтаксический анализатор не может быть подходящим вариантом. Я уже спрашивал, и мне сказали прочитать об алгоритме CYK, что я и сделал. Это проблема, которую мне дали в качестве проекта. Пожалуйста, имейте в виду, я только начал этот уровень программирования. Тем не менее, у меня есть все базовые знания.