Код для определения языка программирования в текстовом файле
Я должен написать код, который при вводе текстового файла (исходный код) в качестве ввода будет выводить, какой это язык программирования. Это самое основное определение проблемы. Далее следуют дополнительные ограничения:
- Я должен написать это на C++.
- Следует распознавать самые разные языки - html, php, perl, ruby, C, C++, Java, C#...
- Количество ложных срабатываний (неправильное распознавание) должно быть низким - лучше выводить "неизвестно", чем неправильный результат. (он будет в списке вероятностей, например, как неизвестно: 100%, см. ниже)
- Выходными данными должен быть список вероятностей для каждого языка, который знает код, поэтому, если он знает C, Java и Perl, выходные данные должны быть, например: C: 70%, Java: 50%, Perl: 30% (обратите внимание, что не нужно, чтобы вероятность составляла до 100%)
- У него должно быть хорошее соотношение точности и скорости (скорость более предпочтительна)
Было бы очень хорошо, если бы код мог быть написан таким образом, чтобы добавление новых языков для распознавания было бы довольно простым и включало бы просто добавление "настроек / данных" для этого конкретного языка. Я могу использовать все что угодно - эвристику, нейронную сеть, черную магию. Что-нибудь. Мне даже разрешено использовать существующие решения, но: решение должно быть бесплатным, открытым и разрешать коммерческое использование. Он должен иметь форму легко интегрируемого исходного кода или статической библиотеки - без DLL. Однако я предпочитаю писать свой собственный код или просто использовать фрагменты другого решения, мне надоело интегрировать код других. Последнее замечание: возможно, некоторые из вас предложат FANN (быстрая библиотека искусственных нейронных сетей) - это единственное, что я не могу использовать, поскольку это то, что мы используем УЖЕ, и мы хотим заменить это.
Теперь вопрос: как бы вы справились с такой задачей, что бы вы сделали? Любые предложения, как это реализовать или что использовать?
РЕДАКТИРОВАТЬ: основываясь на комментариях и ответах, я должен подчеркнуть некоторые вещи, которые я забыл: скорость очень важна, так как она получит тысячи файлов и должна отвечать быстро, поэтому просмотр тысячи файлов должен дать ответы на все из них в максимум несколько секунд (размер файлов, конечно, будет небольшим, по несколько кбайт каждый). Так что попытка скомпилировать каждый из них исключена. Дело в том, что мне действительно нужны вероятности для каждого языка, поэтому я хочу знать, что файл, вероятно, будет C или C++, но вероятность того, что это скрипт bash, очень мала. Из-за запутывания кода, комментариев и т. Д. Я думаю, что поиск 100% точного кода - плохая идея, и на самом деле это не является целью.
10 ответов
У вас проблема с классификацией документов. Предлагаю вам прочитать о наивных байесовских классификаторах и опорных векторных машинах. В статьях есть ссылки на библиотеки, которые реализуют эти алгоритмы, и многие из них имеют интерфейсы C++.
Одно простое решение, о котором я могу подумать, это то, что вы можете просто определить ключевые слова, используемые на разных языках. Каждое идентифицированное слово будет иметь оценку +1. Затем рассчитайте коэффициент = идентифицированные_ слова / всего_слов. Язык, который получает наибольшее количество баллов, является победителем. Конечно, есть проблемы, такие как использование комментариев и т. Д. Но я думаю, что это очень простое решение, которое должно работать в большинстве случаев.
Извините, но если вам нужно проанализировать тысячи файлов, то лучше всего посмотреть на расширение файла. Не переоценивайте простую проблему и не ставьте обременительные требования на простую задачу.
Похоже, у вас есть тысячи файлов исходного кода, и вы не представляете, на каком языке программирования они были написаны. В какой среде программирования вы работаете? (Исключая возможность искусственного домашнего задания) Я имею в виду одну из основ разработки программного обеспечения, на которую я всегда могу положиться, это то, что файлы кода C++ имеют расширение.cpp, что файлы кода java имеют расширение.java, что файлы кода c есть расширение.c и т. д. Играет ли ваша компания быстро и свободно с этими стандартами? Если так, то я был бы очень обеспокоен.
Как предположил dmckee, вы можете взглянуть на Unix file программа, источник которой доступен. Эвристика, используемая этой утилитой, может стать отличным источником вдохновения. Поскольку он написан на C, я думаю, что он подходит для C++.:) Вы не получаете процент доверия напрямую, хотя; может они используются внутри?
Если вы знаете, что исходные файлы будут соответствовать стандартам, расширения файлов уникальны практически для каждого языка. Я предполагаю, что вы уже рассмотрели это и исключили это на основании некоторой другой информации.
Если вы не можете использовать расширения файлов, лучшим способом было бы найти различия между языками, которые наиболее различны, и использовать их для определения типа файла. Например, синтаксис операторов цикла не будет сильно различаться в зависимости от языка, но операторы включения пакета должны. Если у вас есть файл, включающий java.util.*, То вы знаете, что это файл java.
Поскольку список языков известен заранее, вы знаете синтаксис / грамматику для каждого из них. Следовательно, вы можете, например, написать функцию для извлечения зарезервированных слов из предоставленного исходного кода.
Создайте двоичное дерево, в котором будут все зарезервированные слова для всех языков, которые вы поддерживаете. А затем просто пройдитесь по этому дереву с извлеченными зарезервированными словами из предыдущего шага.
Если в итоге у вас останется только 1 возможность - это ваш язык. Если вы достигнете конца программы слишком рано - тогда (с того места, где вы остановились) - вы можете проанализировать свою позицию на дереве, чтобы определить, какие языки все еще возможны.
Этот не быстрый и может не удовлетворить ваши требования, но просто идея. Это должно быть легко реализовано и должно дать 100% результат.
Вы можете попытаться скомпилировать / выполнить входной текст с разными компиляторами / интерпретаторами (с открытым исходным кодом или бесплатно) и проверить наличие ошибок за кулисами.
Возможно, вы можете попытаться подумать о различиях языков и смоделировать их с помощью бинарного дерева, например, "найдена ли особенность X? ", Если да, продолжайте в одном направлении, если нет, продолжайте в другом направлении.
Эффективно построив это дерево поиска, вы можете получить довольно быстрый код.
Алгоритм Sequitur выводит бесконтекстные грамматики из последовательностей терминальных символов. Возможно, вы могли бы использовать это для сравнения с набором известных правил производства для каждого языка.