Давнишнее
Сегодня ходил и думал над количеством промежуточных результатов при переводе регулярной части грамматики в приблизительно бесконечную фиксированную грамматику.
Сперва про перевод.
Регулярная часть контекстно-свободной грамматики части содержит повторение одного и того же (не)терминала произвольное количество раз. Пример тому выражения: sum ::= mult (('-'|'+') mult)*. Мы может написать сколь угодно длинную цепочку a+b-b+c-c...
Регулярную эту часть, что может быть произвольно длинной, я додумался перевести в приблизительно бесконечную - мы не собираемся разбирать цепочки длины более, чем, допустим, 264-1. Тогда, для какого правила a* мы создаём 63 правила вида a1 ::= a a; a2 ::= a1 a1; ... a63 ::= a62 a62;. И, в завершении, требуем, чтобы у нас было разложение цепочки по длинам: a_star ::= (a63|) (a62|) ... (a2|) (a1|) (a|).
Вот этот самый a_star приводит к тому, что у нас появляется много хвостов. В настоящий момент у меня получается количество промежуточных результатов [log2(n)]3 - каждый ai будет участвовать в i2 хвостов a_star, а максимальный i это log2(n).
То есть, сложность разбора грамматики с такой моей заменой будет O(nlog3n). А не O(nlogn), как я думал.
Тем не менее, надо попробовать.
Сперва про перевод.
Регулярная часть контекстно-свободной грамматики части содержит повторение одного и того же (не)терминала произвольное количество раз. Пример тому выражения: sum ::= mult (('-'|'+') mult)*. Мы может написать сколь угодно длинную цепочку a+b-b+c-c...
Регулярную эту часть, что может быть произвольно длинной, я додумался перевести в приблизительно бесконечную - мы не собираемся разбирать цепочки длины более, чем, допустим, 264-1. Тогда, для какого правила a* мы создаём 63 правила вида a1 ::= a a; a2 ::= a1 a1; ... a63 ::= a62 a62;. И, в завершении, требуем, чтобы у нас было разложение цепочки по длинам: a_star ::= (a63|) (a62|) ... (a2|) (a1|) (a|).
Вот этот самый a_star приводит к тому, что у нас появляется много хвостов. В настоящий момент у меня получается количество промежуточных результатов [log2(n)]3 - каждый ai будет участвовать в i2 хвостов a_star, а максимальный i это log2(n).
То есть, сложность разбора грамматики с такой моей заменой будет O(nlog3n). А не O(nlogn), как я думал.
Тем не менее, надо попробовать.