Ремесло программиста

Объявление

форум на движке phpBB доступен для тестирования
www.strategia.space
www.strategia.space/forum/
по предложению Лиса - канал на Matrix - #remdev:matrix.org

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.


Вы здесь » Ремесло программиста » Принципы » КС- и регулярные грамматики


КС- и регулярные грамматики

Сообщений 1 страница 5 из 5

1

Павиа написал(а):

КС - грамматику легко свести к регулярной грамматике путём выписывания всех состояний виде правил регулярной грамматики.


Господи, покарай его. Во-первых, произвольная КС-грамматика к регулярной грамматике в принципе не сводится. Во-вторых, дла конкретной грамматики нельзя сделать это легко, так как нельзя проверить, является ли некоторая КС-грамматика регулярной грамматикой (это следствие теоремы Грейнбах).

2

Лис написал(а):

Господи, покарай его. Во-первых, произвольная КС-грамматика к регулярной грамматике в принципе не сводится. Во-вторых, дла конкретной грамматики нельзя сделать это легко, так как нельзя проверить, является ли некоторая КС-грамматика регулярной грамматикой (это следствие теоремы Грейнбах).

Иди,- учись читать. То что КС сводится к регулярной граматике это есть следствие теоремы Грейнбах. Просто для e грамматик число правил в регулярной граматике будет бесконечное число.
И проверяются граматика элементарно по определению.

Отредактировано Павиа (2017-04-18 13:31:42)

3

Павиа написал(а):

То что КС сводится к регулярной граматике это есть следствие теоремы Грейнбах. Просто для e грамматик число правил в регулярной граматике будет бесконечное число. И проверяются граматика элементарно по определению.


Регулярная грамматика отличается тем, что она может быть разобрна без использования стека. А КС-не может. В этом их принципиальная разница. А обнуляемые правила тут не причём.

4

Во-первых регулярная грамматика это подмножество КС-грамматик. Во-вторых замена рекурсия со стеком на массивом с циклом это детская задачка. А массив можно заменить числом.

Мы можем заменить любую рекурсию циклом. Другое дело что рекурсия делиться на 2 типа хвостовая и нет. Хвостовая требует O(1) памяти. Не хвостовая требует массив.
В терминах грамматик это называется укорачивающая грамматика и не укорачивающаяся.
Массив есть некоторое состояние системы. Состояние системы мы можем закодировать как данными так и кодом. Так как по сути это одно и тоже 0 и 1. Гарвардская архитектура вычислительной техники.
Так вот код это ничто иное как правила работы этого вычислителя. А правила языка есть грамматики.
Далее рекурсия бывает двух видов с конечной глубина стека и с бесконечной. Соответственно у нас так же будет программа с конечным числом правил и с бесконечным.

Остановимся на примере с конечным числом состояний.
Это значит что мы знаем все выходные цепочки языка.
Запишем их, затем отсортируем а после пронумеруем. Будем читать из потока терминалы и записывать их в массив. Параллельно передвигая указатель по правилам. Если читаем новый терминал то передвигаем указатель в права по правилу. Если значение в правиле меньше чем терминал переходим к следующему по порядку правилу. Если равен то читаем следующий терминал. Если терминал больше то выходим из автомата с ошибкой. Сообщаем, то что входной поток не соответствует заданной грамматики.
Если дошли до конца правила то выходим с положительным результатом. В качестве целевого массива у нас будет наш массив терминалов.
Как перейти от грамматики к состояниям?
Это просто берём все наши правила и пробуем породить по порядку. С начало по первому варианту первого правила затем по второму варианту первого правила и так до последнего варианта первого правила. Затем порождаем по второму правилу и так далее.
Так как число вариантов и число правил заранее известно. То число это счётное. А  значит мы можем закодировать это разрядом числа. Собственно вариант разбора кодируется некоторым числом: Этого нам достаточно.

Что делать если выходных цепочек бесконечное число?  Тут сложнее.  Но нам надо всего-то найти алгоритм обходить всех наших цепочек.
Но на самом деле он не сложнее можно поменять в предыдущим алгоритме обход сначала обходить правила, а потом варианты правил.
Чуть не забыл у помянуть что делать это мы будем только для циклических правил. И основной цикл нам надо будет повторить Y раз. Где Y равен
НОК от длин циклов графа.
А затем у нас будет второй цикл для не цикличных веток графа. Их размер известен.

Так как размер НОК известен. То грамматика будет регулярной. А пример порождения более детально опишу в другой раз.
Математически мы можем свести любую КС к регулярной грамматике. Проблема за малом требуется очень много памяти и процессор с большой производительности.

5

Не читал, но несогласен.

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

Кроме того,
https://en.wikipedia.org/wiki/Greibach's_theorem
...
Следствие:
it can be shown that the following problems is undecidable:
"Given a context-free grammar, does it describe a regular language?"

Отредактировано Лис (2017-04-19 20:26:32)


Вы здесь » Ремесло программиста » Принципы » КС- и регулярные грамматики