Во-первых регулярная грамматика это подмножество КС-грамматик. Во-вторых замена рекурсия со стеком на массивом с циклом это детская задачка. А массив можно заменить числом.
Мы можем заменить любую рекурсию циклом. Другое дело что рекурсия делиться на 2 типа хвостовая и нет. Хвостовая требует O(1) памяти. Не хвостовая требует массив.
В терминах грамматик это называется укорачивающая грамматика и не укорачивающаяся.
Массив есть некоторое состояние системы. Состояние системы мы можем закодировать как данными так и кодом. Так как по сути это одно и тоже 0 и 1. Гарвардская архитектура вычислительной техники.
Так вот код это ничто иное как правила работы этого вычислителя. А правила языка есть грамматики.
Далее рекурсия бывает двух видов с конечной глубина стека и с бесконечной. Соответственно у нас так же будет программа с конечным числом правил и с бесконечным.
Остановимся на примере с конечным числом состояний.
Это значит что мы знаем все выходные цепочки языка.
Запишем их, затем отсортируем а после пронумеруем. Будем читать из потока терминалы и записывать их в массив. Параллельно передвигая указатель по правилам. Если читаем новый терминал то передвигаем указатель в права по правилу. Если значение в правиле меньше чем терминал переходим к следующему по порядку правилу. Если равен то читаем следующий терминал. Если терминал больше то выходим из автомата с ошибкой. Сообщаем, то что входной поток не соответствует заданной грамматики.
Если дошли до конца правила то выходим с положительным результатом. В качестве целевого массива у нас будет наш массив терминалов.
Как перейти от грамматики к состояниям?
Это просто берём все наши правила и пробуем породить по порядку. С начало по первому варианту первого правила затем по второму варианту первого правила и так до последнего варианта первого правила. Затем порождаем по второму правилу и так далее.
Так как число вариантов и число правил заранее известно. То число это счётное. А значит мы можем закодировать это разрядом числа. Собственно вариант разбора кодируется некоторым числом: Этого нам достаточно.
Что делать если выходных цепочек бесконечное число? Тут сложнее. Но нам надо всего-то найти алгоритм обходить всех наших цепочек.
Но на самом деле он не сложнее можно поменять в предыдущим алгоритме обход сначала обходить правила, а потом варианты правил.
Чуть не забыл у помянуть что делать это мы будем только для циклических правил. И основной цикл нам надо будет повторить Y раз. Где Y равен
НОК от длин циклов графа.
А затем у нас будет второй цикл для не цикличных веток графа. Их размер известен.
Так как размер НОК известен. То грамматика будет регулярной. А пример порождения более детально опишу в другой раз.
Математически мы можем свести любую КС к регулярной грамматике. Проблема за малом требуется очень много памяти и процессор с большой производительности.
