LINUX.ORG.RU

Доказана невозможность статического парсинга Perl 5

 , неразрешимость, ,


0

0

Формально доказана неразрешимость задачи статического синтаксического анализа Perl 5. В опубликованном доказательстве задача парсинга программы на Perl сводится к задаче остановки, которая, как известно любому школьнику, неразрешима.

Этот факт имеет важное практическое значение — он означает что в общем случае выяснить, что будет делать та или иная программа на Perl, возможно только выполнив саму программу. Методы статического анализа бессильны. Возникают ли подобые проблемы в Perl 6 — неизвестно.

Статьи (pdf): [1], [2], [3].

>>> Подробности

Ответ на: комментарий от Xenius

> А вообще да, интересно, если на такой машине запустить "while (i++);" завершится ли оно за конечное время

Завершится, если i - целочисленное. Сначала достигнет максимального значения, потом станет минимальным (0 или отрицательное число). Затем будет повышаться пока не будет 0, если отрицательным было. А потом while(0) => выход.

Например, вот такая программа исполняется у меня за почти 2 секунды:

<code>

#include <stdio.h>

int main() {

char i = 1;

while (i++) printf("i=%d\n",i);

return 0;

}

</code>

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

anonymous
()
Ответ на: комментарий от anonymous

не char i, а short i - за 2 секунды пробегает. char i - за 0.05 секунд, ошибся.

anonymous
()
Ответ на: комментарий от anonymous

Это был условный код.
Машина бесконечной производительности, а тип -- произвольное целое (т.е. хоть 10^(10^1000))

Xenius ★★★★★
()

Есть ли среди высокоглубокоуважаемых аналитиков математики? Что они могут сказать про "доказательство о трех частях"? Подтвердил ли это доказательство еще кто-нибудь, кроме автора статей?

impfp
()
Ответ на: комментарий от impfp

Поясню, прочел страницу обсуждения №1 - она, как понимаю, была посвящена "perl-RIP", и страницу №9 - в ней шло обсуждение говна, соплей и интеллектуальных импотентов. А вот по теме что-то практически ничего и не было.

impfp
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.