2

Я студент и в рамках обучения передо мной стоит задача поиска клонов исходного кода в некотором проекте на Си.

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

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

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

Или какие-нибудь библиотеки для С++, при помощи которых я могу получить представление упомянутых произвольных фрагментов внутри моей программы?

1

1 ответ 1

4

Как правильно подсказывает @PinkTux в комментарии, вам не стоит пытаться писать парсер самостоятельно: это большая и сложная работа, которая не имеет прямого отношения к вашему заданию.

Для разбора языков в синтаксическое дерево традиционно используются утилиты lex и yacc (более современные их версии — flex и bison). Вам придётся выучить их форматы, но, поверьте, это пригодится в жизни не раз. Flex и bison бесплатны, развиваются и поддерживаются.

Есть несколько готовых грамматик для языка C, интернет, кажется, считает лучшей эту пару: http://www.quut.com/c/ANSI-C-grammar-l-2011.html + http://www.quut.com/c/ANSI-C-grammar-y.html. Поэтому не стоит изобретать велосипед. Возьмите готовую грамматику, добавьте построение классы для синтаксического дерева, и можно приступать к вашему главному заданию.

[Вам придётся добавить к правилам наподобие WHILE '(' expression ')' statement код построения части дерева, например:

WHILE '(' expression ')' statement { $$ = new while_statement($3, $5) }

что означает «результату разбора выражения ($$) присвоить new while_statement с параметрами $3 (третье выражение в списке, expression) и $5 (пятое выражение в списке, statement) », но это тривиально.]

Дерзайте! У вас прекрасная задача!

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.