Код для идентификации языка программирования в текстовом файле

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

Я должен написать это на C++.
Следует признать широкое разнообразие языков - html, php, perl, ruby, C, C++, Java, C# ...
Количество ложных срабатываний (неправильное распознавание) должно быть низким - лучше выводить «неизвестно» "чем неправильный результат. (он будет в списке вероятностей, например, как неизвестно: 100%, см. ниже)
Результат должен быть списком вероятностей для каждого языка, который знает код, поэтому, если он знает C, Java и Perl, вывод должен быть, например: C: 70%, Java: 50%, Perl: 30% (обратите внимание: нет необходимости иметь сумму вероятностей до 100%)
Он должен иметь хорошее соотношение точности/скорости (скорость немного более благоприятствуется)

Было бы очень приятно, если бы код мог быть написан так, что добавление новых языков для распознавания будет довольно простым и включает просто добавление «настроек/данных» для данного конкретного языка. Я могу использовать что угодно - эвристику, нейронную сеть, черную магию. Что-нибудь. Я даже разрешил использовать существующие решения, но: решение должно быть бесплатным, открытым исходным кодом и разрешать коммерческое использование. Он должен быть в виде легко интегрируемого исходного кода или как статическая библиотека - не DLL. Однако я предпочитаю писать свой собственный код или просто использовать фрагменты другого решения, мне надоело интегрировать код других. Последнее примечание: возможно, некоторые из вас предложит FANN (быструю искусственную библиотеку нейронных сетей) - это единственное, что я не могу использовать, так как это то, что мы используем УЖЕ, и мы хотим это заменить.

Теперь возникает вопрос: как бы вы справились с такой задачей, что бы вы сделали? Любые предложения, как реализовать это или что использовать?

EDIT: Основываясь на комментариях и ответах, я должен подчеркнуть некоторые вещи, которые я забыл: скорость очень важна, так как это будет получать тысячи файлов и должно отвечать быстро, поэтому просмотр тысяч файлов должен давать ответы для всех из них в течение нескольких секунд (размер файлов будет небольшим, конечно, по несколько килобайт каждый). Поэтому пытаться скомпилировать каждый из них не может быть и речи. Дело в том, что я действительно хочу вероятности для каждого языка, поэтому я скорее хочу знать, что файл, скорее всего, будет C или C++, но вероятность того, что это сценарий bash, очень низок. Из-за обфускации кода, комментариев и т. Д., Я думаю, что поиск 100% точного кода - плохая идея и на самом деле не является целью этого.

источник

2010-08-30 PeterK

Идея языка в щеке - запустить его через компилятор для каждого языка и выбрать тот, который не является ошибкой? ;). (да, я знаю - возможно, медленный, склонный быть абсолютно неправильным, если код не компилируется, или если пользователь пишет полигоны ... и т. д.) – Stephen

+1: Хороший вопрос. Но я думаю, что часть «вероятности» не имеет смысла: вход либо легален на определенном языке, либо нет. Я не понимаю, что это означает, что он имеет более высокую вероятность принадлежать языку A, чем языку B. – Job

Я ожидал бы, что это будет очень простой проблемой, единственное препятствие, которое является сходством в C/C++. Это сценарий, который можно было бы решить просто или слишком сложно. – Fosco

У вас возникли проблемы document classification. Предлагаю вам прочитать о naive bayes classifiers и support vector machines. В статьях есть ссылки на библиотеки, которые реализуют эти алгоритмы, и многие из них имеют интерфейсы C++.

источник

2010-08-30 12:52:24

Действительно, я бы сказал, что классификатор Naive Bayes с быстрая проверка в начале для определенных слов «должно быть» (например, строки Python или Ruby 'env'). – Stephen

Спасибо, это выглядит многообещающим! – PeterK

Если вы знаете, что исходные файлы соответствуют стандартам, расширения файлов уникальны почти для каждого языка. Я предполагаю, что вы уже рассмотрели это и исключили его на основании другой информации.

Если вы не можете использовать расширения файлов, лучшим способом было бы найти вещи между самыми разными языками и использовать их для определения типа файла. Например, синтаксис оператора цикла не будет сильно отличаться между языками, но пакет должен содержать инструкции. Если у вас есть файл, включая java.util. *, То вы знаете, что это java-файл.

источник

2010-08-30 12:21:15

Вы не можете вычислить вероятность для каждого языка таким образом. –

Удивительно, как бы петля выглядела как в мозге *** или в Haskell. – Leonid

@Lieven Вы не можете рассчитать вероятность, основанную только на моих предложениях, но вы наверняка сможете начать хорошо. Если вы исключаете определенные языки на основе синтаксических различий, это упрощает определение вероятностей. Кроме того, если вы можете определенно идентифицировать язык на основе оператора include, то вероятности не нужны. –

Одним из простых решений, о которых я мог думать, является то, что вы можете просто определить ключевые слова, используемые на разных языках. Каждое идентифицированное слово имеет счет +1. Затем вычислите коэффициент = ident_words/total_words. Победителем является язык, который получает наибольшее количество баллов. Конечно, есть проблемы, такие как использование комментариев e.t.c. Но я считаю, что это очень простое решение, которое должно работать в большинстве случаев.

источник

2010-08-30 12:25:34 Leonid

Следуя этой идее, вы можете попробовать наивный байесовский классификатор, например, ранние фильтры спама. Это может также дать очень хорошие результаты? –

+1 как для оригинала, так и для комментария - это лучший способ, которым я знаю, чтобы получить быструю и разумную точность. –

Единственным недостатком этого подхода я вижу, что некоторые ключевые слова гораздо более характерны для некоторых языков, чем другие. Поэтому потребуется предварительный статистический анализ. Но я могу сделать именно это, кажется, это может работать очень хорошо. – PeterK

Возможно, вы попытаетесь подумать о различиях языков и смоделируете их с помощью двоичного дерева, например «есть функция X, найденная?», Если да, действуйте в одном направлении, если нет, действуйте в другом направлении.

Построив это дерево поиска эффективно, вы можете закончить довольно быстрый код.

источник

2010-08-30 12:27:34

Не каждая программа Perl демонстрирует каждую функцию Perl. Нет такой функции Perl X, что каждая действительная программа Perl имеет X. –

. Тогда вы обнаружите, что, исключив другие возможности –

, программы perl будут отображаться несколько раз в двоичном дереве. В результате двоичное дерево не будет иметь гарантированного размера O (logN). –

Посмотрите на nedit. Он имеет систему распознавания синтаксиса под Подсветка синтаксиса-> Шаблоны распознавания. Вы можете просматривать шаблоны распознавания образцов here или загружать программу и проверять стандартные.

Описание: highlighting system.

источник

2010-08-30 12:28:41

Утилита 'file' unix имеет собственный набор эвристик, хотя они могут быть слишком простыми. – dmckee

@dmckee, правда, но для действительно коротких программ это не удастся:/ –

Это не быстро и может не удовлетворить ваши требования, а просто идея. Он должен быть легко реализован и должен давать 100% результат.

Вы можете попытаться скомпилировать/выполнить входной текст с помощью разных компиляторов/интерпретаторов (с открытым исходным кодом или бесплатно) и проверить наличие ошибок за сценой.

источник

2010-08-30 12:39:51 grigy

Что делать, если он компилируется как несколько языков? например. http://www.nyx.net/~gthompso/poly/micah.txt работает как C, так и perl – Hasturkun

Тогда вы говорите 50% вероятности C, 50% - Perl. Это нормально в соответствии с автором вопроса. – DmitryK

Точно. Если он компилирует, то кто может доказать обратное? – grigy

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

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

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

источник

2010-08-30 12:41:44 DmitryK

+1: это, вероятно, было бы довольно точным, но достаточно быстрым, учитывая тысячи файлов? –

Спасибо Axel. Вы, вероятно, можете объединить 2 этапа: когда вы извлекаете зарезервированные слова, немедленно их кормите. В некоторых случаях вы обнаружите язык до достижения исходного кода. Самая медленная часть на самом деле применяет правила синтаксиса для всех языков (т. Е. Необходимо построить много L-строк и т. Д. - это почти похоже на парсер для всех поддерживаемых языков). – DmitryK

Алгоритм Sequitur содержит контекстно-свободные грамматики из последовательностей терминальных символов. Возможно, вы могли бы использовать это для сравнения с набором известных правил производства для каждого языка.

источник

2010-08-30 12:47:46 Gian

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

Похоже, что у вас есть тысячи файлов исходного кода, и вы не знаете, на каком языке программирования они были написаны. В какой среде программирования вы работаете? (Исправление возможности искусственного требования к домашнему заданию). Я имею в виду, что одна из основ разработки программного обеспечения, на которую я всегда могу положиться, - это то, что файлы кода C++ имеют расширение .cpp, что в java-файлах кода есть расширение .java, это c-файлы кода иметь расширение .c и т. д. Является ли ваша компания быстро и свободно играть с этими стандартами? Если так, я был бы очень обеспокоен.

источник

2010-08-30 13:01:38

+1 Я должен согласиться, похоже, этот простой подход, вероятно, будет «достаточно хорошим» –

Кто сказал, что его «файлы» - это файлы с именами? Возможно, он пытается сделать правильную подсветку синтаксиса на фрагментах кода на форуме, таком как SO. Или, может быть, он пытается выяснить, есть ли у некоторых файлов кода неправильное расширение! – Gabe

Извините, но использование расширений файлов здесь невозможно. В любом случае спасибо за ваше предложение! – PeterK

Как предложил dmckee, вы можете посмотреть программу Unix file, чья source is available. Эвристика, используемая этой утилитой, может стать отличным источником вдохновения. Поскольку он написан на C, я предполагаю, что он подходит для C++. :) Вы не получаете процент доверия напрямую; возможно, они используются внутри страны?

источник

2010-08-30 13:39:24 EOL

Код для идентификации языка программирования в текстовом файле

ответ

Смежные вопросы