LINUX.ORG.RU

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

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


0

0

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

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

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

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

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

>Ну да, ну да, перловый скрипт тебе с помощью ed править было бы куда как легче.

Ну так, естессно легче. На порядок, вообще-то.

>Однозначность синтаксиса -- хорошее дело, как бы грустно перлофагам по этому поводу не было.

Да нет, не грустно, каждому ж свое. Просто, когда мне нужно выделить кусок кода в Перле, я могу его написать на много строк, со всеми делами, а когда он менее важен, написать покороче. И даже если вдруг забуду откомментировать, потом программа будет читабельней. Ну это как пример.

Gukl ★★★
()

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

Разве это не на любую программу с eval распространяется?

KRoN73 ★★★★★
()
Ответ на: комментарий от stave

+=, .=, *= ... и так далее - шорткаты, не нравится - не пользуй. Так сколько же в Перле операторов присваивания? ;)

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

>Ну так, естессно легче. На порядок, вообще-то.

Я рад что ты, перл и ed нашли друг друга :) Желаю вам совет да любовь и многих трудовых подвигов :)

>Просто, когда мне нужно выделить кусок кода в Перле, я могу его написать на много строк, со всеми делами, а когда он менее важен, написать покороче. И даже если вдруг забуду откомментировать, потом программа будет читабельней.

Ты уж не обижайся, но это бред какой-то бессвязный. Даже лень подробный синтаксический анализ приводить :)

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

>Разве это не на любую программу с eval распространяется?

Да в этом треде на каждой странице повторено, да еще и пос сслыке написано, но всем по* ;)

Gukl ★★★
()
Ответ на: комментарий от anonymous4

>Ты уж не обижайся, но это бред какой-то бессвязный. Даже лень подробный синтаксический анализ приводить :)

Сразу видно не писавшего на Перл. Мысль о том, что один и тот же алгоритм можно записать по разному в зависимости от смысла/значения в программе выбивает парсер ;)

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

Сразу видно писавшего на перл, он и на родном языке начинает изъясняться так, что хрен поймешь, а что же он имеет в виду? ;)

>Мысль о том, что один и тот же алгоритм можно записать по разному в зависимости от смысла/значения в программе выбивает парсер ;)

Ты уже не первый раз пытаешься утверждать, что если программист не пишет на перл -- у него нет алгоритмической подготовки и ничего сложнее хеллоу ворлд написать он не может. Тебе за такой толстый троллинг должно быть стыдно :)

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

>Да в этом треде на каждой странице повторено

Так я же Ъ, тред ещё не читал :)

KRoN73 ★★★★★
()
Ответ на: комментарий от anonymous4

>Учить матчасть, такое есть почти везде

да что вы говорите. раз так утверждаете, посчитайте их количество хотя бы в С(там и правда много, но перл и тут всех превзошел). а то все требуют что-то привести, а сами в лужу садятся.

stave ★★★★★
()
Ответ на: комментарий от Gukl

>Скажу, что это нормально. Вызубрить к экзамену, может, и сложно, а в процессе работы все руки п омнят.

зачем? вы можете ответить на простой вопрос, зачем столько? чтобы запоминать?

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

Да к черту Си, с каких это пор он ЯВУ? Ты бы по ссылке сходил, открыл бы для себя, что составное присваивание есть не только в перле.

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

А какой предел-то? Производительность машины -- алеф0 операций в секунду. В миллисекунду -- тот же алеф0, так что да, с потолка. Если программе не хватило алеф0 операций, она считается зависшей, вот и все.

Xenius ★★★★★
()
Ответ на: комментарий от yk4ever

> Можете привести хоть три примера вида "есть для перла, нет для питона"?

Три модуля наугад:

IO::All со всей его универсальностью и мощью

Net::ARP

XML::Simple (я не нашел для питона _простого_ модуля для работы c XML -- который бы просто парсил XML во встроенные структуры данных, массивы и хэши, и обратно).

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

>а что скажите про 24 уровня приоритетов операций?

скобочки рулят. В Си кстати ЕМНИП тоже 24 уровня приоритета

DNA_Seq ★★☆☆☆
()
Ответ на: комментарий от Hjorn

> CPAN незаменим только когда нужно по-быстрому сляпать что то, не предполагающее поддержку и развитие - прототип или скрипт для собственных нужд.

Ну я, например, Perl и использую только для подобных целей -- скрипты и небольшие программы, которые надо сляпать в ограниченные сроки. И считаю его отличным языком. Это не мешает мне для других целей использовать другие языки (в т.ч. питон) и тоже считать их отличными.

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

ты мне прям рассказываешь очевидное-невероятное. а то я не знал, когда постил. вики мне просто открыло глаза.

stave ★★★★★
()
Ответ на: комментарий от Xenius

Матанализ прогуливал, или еще не проходили? :)

Попробую разъяснить на бытовом уровне, понятном шестикласснику: пусть производительность машины 1000 операций в секунду, а сложность алгоритма -- 1000 операций. Выполнение алгоритма завершится за одну секунду. Если при той же сложности алгоритма производительность машины будет равна бесконечности, алгоритм будет завершаться мгновенно. Если при той же производительности машины сложность будет равна бесконечной, алгоритм не завершится никогда. Если и то и другое очень велико, для того, чтобы определить, что и когда произойдет (и сможет ли машина за конечное время выполнить алгоритм), нужно знать, что таки больше. Если и то и другое бесконечно, имеем неразрешимую задачу типа "сколько нужно работников с бесконечной производительностью, чтобы построить бесконечную стену?"

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

>зачем? вы можете ответить на простой вопрос, зачем столько? чтобы запоминать?

Вообще-то логически неверный вопрос. Приоритеты операций не существуют отдельно от операций как таковых. К тому же, буквально зпоминать их в реальности не приходится, т. к. они подчиняются той же логике, что и в других языках (плюс приоритеты математических опреаций тоже везде одинаковые).

Gukl ★★★
()
Ответ на: комментарий от DNA_Seq

>В Си кстати ЕМНИП тоже 24 уровня приоритета

ЕМНИП, едва за десяток :)

KRoN73 ★★★★★
()
Ответ на: комментарий от anonymous4

>"сколько нужно работников с бесконечной производительностью, чтобы построить бесконечную стену?"

Так вот ты утверждаешь, что десяти будет достаточно, взяв цифру с потолка :)

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

> В том-то и дело, что Питон "неральный" язык, построенный вокруг одной-двух умозрительных концепций.

Ну ваще-то это очень даже мультипарадигменный язык.

> А Перл сделан для реальной работы.

Короче, неструктурированная помойка.

> А когда не пользуюсь, тыкаю такую вот штучку: \ Не знали?

Эх, да знаю конечно. Просто что по дефолту он ведёт себя дебильно, а нормальное поведение надо просить отдельно - это показатель.

> Перл тем и хорош, что что не нужно,

Вот, исправил вашу цитату.

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

>я не знал, когда постил. вики мне просто открыло глаза.

Рад помочь :)

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

>Ты уже не первый раз пытаешься утверждать, что если программист не пишет на перл -- у него нет алгоритмической подготовки

Ни разу не утерждал. И не орал, что Питон должен умереть, кстати, тоже. Мы вроде конкретные языки обсуждаем, а не общие вопросы.

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

> А что вы скажете про неявную перегрузку оператора + в JS? ;)

ECMAScript - тоже стрёмный язык. Но он на порядок лучше перла.

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

>Да к черту Си, с каких это пор он ЯВУ?

Си язык высокого уровня хотя бы потому что трансляция в машинные коды неоднозначна. А прямой доступ к памяти и у Паскаля есть (в версии борланда например)

//К.О.

DNA_Seq ★★☆☆☆
()

Вот инструменты статического анализа кода Perl: Perl::Critic, perltidy, Perl::MinimumVersion, Module::ExtractUse.

Первые два широко используются. Perl::Critic вообще рекомендуется каждому.

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

>Просто что по дефолту он ведёт себя дебильно, а нормальное поведение надо просить отдельно - это показатель.

Я бы не утверждал, что "нормально" во всех случаях следует раскрывать в "как в Питоне". Для меня нормально явно указывать передачу значения по ссылке, потому что это потенциально более рискованная операция.

Gukl ★★★
()
Ответ на: комментарий от DNA_Seq

Кэп, спасибо.

Для возмущенных: я имел в виду, что сравнивать в лоб Си с языками вроде перла, python и т.п. признак недалекости сравнивающего.

anonymous4
()

А перл -- хороший язык, хотя dc мне больше нравится тем, что я его уже выучил.

Xenius ★★★★★
()
Ответ на: комментарий от anonymous4

Ну как бы Си был взят за образец синтаксиса при разработке Перла так что многие "проблемы" перетекли оттуда

DNA_Seq ★★☆☆☆
()
Ответ на: комментарий от DNA_Seq

>Ну значит добавились всякие eq для сравнения строк. Не фатально.

Уровень
приоритета	Операция	
 1	левосторонние списковые операции	
 2	->	
 3	++ --	
 4	**	
 5	! ~ \ + (унарный) - (унарный)	
 6	=~ !~	
 7	* / % x	
 8	+ - .	
 9	<< >>	
10	именованные унарные операции	
11	< > <= >= lt gt le ge	
12	== != <=> eq ne cmp	
13	&
14	| ^
15	&&
16	||
17	.. ...
18	?:
19	= += -= *= /= %= **= &= |= ^= <<= >>= &&= ||= .= x=
20	, =>
21	правосторонние списковые операции
22	not
23	and
24	or xor

stave ★★★★★
()
Ответ на: комментарий от DNA_Seq

>Ну как бы Си был взят за образец синтаксиса при разработке Перла так что многие "проблемы" перетекли оттуда

особенно хороши использование в идентификаторах "'", или определения чисел через "_" (9_3434_____4324 например)

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

Ну и? В чем проблема? Добавилось несколько отсутствующих в Си операций вроде возведения в степень и =~. А || и or и в Си разным приоритетом обладал

DNA_Seq ★★☆☆☆
()
Ответ на: комментарий от anonymous4

>Попробую разъяснить на бытовом уровне, понятном шестикласснику: пусть производительность машины 1000 операций в секунду, а сложность алгоритма -- 1000 операций. Выполнение алгоритма завершится за одну секунду.

наверное это касается только реалтайм ОС и соотв. приложений уровня ведра с наивысшим приоритетом на простой архитектуре, а если она современная то все это посчитать сложнее, я имею ввиду не математическую модель сферического коня в вакууме, а некий конечный автомат - там ведь обычно в лучшем случае дается некое максимальное время реакции гарантированное. (весь тред не читал, лень, и ЧСВ :-)

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

>Можете привести хоть три примера вида "есть для перла, нет для питона"?

Начнём с одного. Мой любимый пример. Библиотека для работы с графами есть?

JackYF ★★★★
()
Ответ на: комментарий от KRoN73

> Да к черту Си, с каких это пор он ЯВУ?

> Вот и выросло... :)

Во-первых, Си иронично относился к "среднему уровню" в 70-ые (по сравнению с Fortran, скажем). Во-вторых, как ни крути, относить в одну категорию Си, Питон и Яву -- глупо, и классификация ЯВУ/ассемблер в 21 веке совершенно недостаточная.

sv75 ★★★★★
()
Ответ на: комментарий от anonymous4

>Да к черту Си, с каких это пор он ЯВУ? Ты бы по ссылке сходил, открыл бы для себя, что составное присваивание есть не только в перле.

ява устроит? 14 уровней приоритета. и 12 операторов присваивания, которые кстати работают в яве действительно быстрее, в отличии от перла, где это просто сахар.

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

Ну двенадцать против шестнадцати. Нашел к чему придраться.

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

>А с учётом [...] кучи модулей.

это ты сынку cpan в анабиозе проспал (или в школе пропустил)

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

см. "Перл, сборник рецептов" с бараном на обложке. Там довольно интересные модули описаны, например сравнение слов с учетом схожести фонетического звучания

DNA_Seq ★★☆☆☆
()
Ответ на: комментарий от yk4ever

> есть для перла, нет для питона

Возможность написать чисто процедурную программу (и выиграть в скорости еще больше, чем Перл обычно выигрывает у Питона ;) что иногда критично)

Gukl ★★★
()
Ответ на: комментарий от anonymous4

>>Библиотека для работы с графами есть?

>Да.


Пожалуйте ссылку на документацию к ней, хочу взглянуть.

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