C - Как найти все внутренние петли с помощью grep?

Ответ 1

Regex для обычных языков, то, что вы описываете, похоже на Context-Free, и я уверен, что это невозможно сделать с помощью регулярных выражений. См. Ответ на аналогичный вопрос здесь. Вы должны искать другие типы автоматов, такие как язык сценариев (python или так).

Ответ 2

Это хороший пример для конкретных расширений компилятора. недавний компилятор GCC (то есть версия 4.6 GCC) может быть расширен плагинами (болезненно закодированными на C) или MELT расширения; MELT - это высокоуровневый доменный язык для кодирования расширений GCC, а MELT очень прост в использовании, чем C.

Большое преимущество работы в рамках GCC (через плагины на C или расширениях в MELT) заключается в том, что ваши расширения работают с теми же данными, что и компилятор.

Вернемся к вопросу об обнаружении вложенных циклов, не считайте его чисто синтаксическим (поэтому grep не может работать). Внутри компилятора GCC на некотором уровне внутренних представлений цикл, реализованный for, или while, или do, или даже с goto -s, по-прежнему считается циклом, а для GCC эти вещи может быть вложен (и GCC знает о вложенности!).

Ответ 3

Без синтаксиса C вы можете получить эвристическое решение в лучшем случае.

Если вы можете полагаться на определенные правила, которые последовательно выполняются в коде (например, no goto, нет циклов через рекурсию,...), вы можете сканировать предварительно обработанный код C с помощью регулярных выражений. Конечно, grep недостаточно сложный, но с несколькими строками Perl или аналогичным возможно.

Но технически лучший и гораздо более надежный подход - использовать настоящий C-парсер.

Ответ 4

В C есть три типа циклов:

• "структурированный синтаксис" ( в то время как, для,...) [Остерегайтесь GCC, который может скрывать утверждения, поэтому циклы внутри выражений используются синтаксисом (stmt; exp)!]
• ad hoc с использованием goto; они взаимодействуют со структурированным синтаксисом.
• рекурсии

Чтобы найти первый тип, вам нужно найти структурированный синтаксис и вложенность.

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

Если вы хотите автоматически найти эти циклы, вам в значительной степени нужен полный синтаксический анализатор C с расширенной предварительной обработкой. (В противном случае некоторые макросы могут скрыть критический фрагмент синтаксиса цикла). После того, как у вас есть синтаксическое дерево для C, просто (хотя, вероятно, немного неудобно) кодировать что-то, что clambers над деревом, обнаружение узлов синтаксиса цикла и подсчет вложенности циклов в поддеревьях. Вы можете сделать это с помощью любого инструмента, который будет анализировать C и давать вам абстрактные деревья sytnax. ANTLR может это сделать; Я думаю, что для ANTLR доступна C-грамматика, которая хорошо справляется с C, но перед использованием ANTLR вам нужно будет запустить препроцессор.

Вы также можете сделать это с помощью нашего DMS Software Reengineering Toolkit с его C Front End. Наш C Front End имеет полный препроцессор, встроенный, чтобы он мог читать код напрямую и расширяться по мере его анализа; он также обрабатывает относительно широкий спектр диалектов C и кодировок символов (когда-либо рассматривал C, содержащий японский текст?). DMS предоставляет дополнительное преимущество: с учетом языка (например, C) переднего конца вы можете писать шаблоны для этого языка, используя синтаксис языка. Поэтому мы можем выразить фрагменты того, что мы хотим найти легко:

 pattern block_for_loop(t:expression,l:expression,i:expression, s: statements): statement
     " for(\t,\l\,\i) { \s } ";

 pattern statement_for_loop(t:expression,l:expression,i:expression, s: statement): statement
     " for(\t,\l\,\i)  \s ";

 pattern block_while_loop(c:expression, s: statements): statement
     " while(\c) { \s } ";

 pattern statement_while_loop(c:expression): statement
     " for(\c)  \s ";

 ...

и сгруппируйте их вместе:

 pattern_set syntactic_loops
     { block_for_loop,
       statement_for_loop,
       block_while_loop,
       block_statement_loop,
       ...
     }

Учитывая набор шаблонов, DMS может сканировать дерево синтаксиса и находить совпадения с любым элементом набора без кодирования какого-либо конкретного механизма обхода дерева и не зная большого количества деталей о структуре дерева. (Существует много типов node в AST для реального C-парсера!) Поиск вложенных циклов таким образом будет довольно простым: сканирование дерева сверху вниз для цикла (с использованием набора шаблонов); любые хиты должны быть петлями верхнего уровня. Сканировать поддеревья найденного цикла AST node (просто, когда вы знаете, где дерево для внешнего цикла) для дополнительных циклов; любые хиты должны быть вложенными петлями; при необходимости переустанавливайте петли с произвольным вложением. Это работает и для элементов GCC loop-with-statements. Узлы дерева имеют точную информацию о файле/строке/столбце, поэтому его легко создать отчет о местоположении.

Для специальных циклов, построенных с использованием goto (что у вашего кода не существует?), вам нужно что-то, что может привести к фактическому графику потока управления, а затем структурировать этот граф в вложенный элемент управления. Дело в том, что цикл while, содержащий безусловный goto, на самом деле не является циклом, несмотря на синтаксис; и оператор if, чье предложение возвращается к коду выше , если, скорее всего, является циклом. Весь этот материал синтаксиса в цикле - это всего лишь хулиганские подсказки, которые могут иметь цикл! Эти области управляющего потока содержат реальное вложение управляющего потока; DMS построит поточные графы C и создаст эти структурированные области. Он предоставляет библиотеки для построения и доступа к этому графику; таким образом, вы можете получить "истинный" поток управления на основе gotos. Найдя пару вложенных областей потока управления, можно получить доступ к AST, связанным с частями региона, для получения информации о местоположении.

GCC всегда очень забавна из-за его значительно расширенной версии C. Например, у нее есть косвенная инструкция goto. (Обычный C имеет это скрытие под setjmp/longjmp!). Чтобы определить циклы перед этим, вам нужно анализ точек, который также предоставляет DMS. Эта информация используется анализом вложенных областей. Существуют (консервативные) пределы точности анализа точек, но по модулю, что вы получаете правильный граф вложенных областей.

Рекурсия сложнее найти. Для этого вам нужно определить, звонит ли A B B... вызывает Z-вызовы A, где A и B и... могут быть в отдельных единицах компиляции. Вам нужен глобальный график вызовов, содержащий все единицы компиляции вашего приложения. На данный момент вы, вероятно, ожидаете, что я скажу, что DMS тоже это делает, вуаля, я рад сказать, что это так. Для построения этого графика вызовов, конечно, требуются точки-anlaysis для вызовов функций; да, DMS тоже это делает. С помощью графика вызовов вы можете найти циклы в графике вызовов, которые, вероятно, являются рекурсивными. Также с графом вызовов вы можете найти косвенное вложение, например, петли в одной функции, которые вызывают функцию в другом компиляционном блоке, который также содержит циклы.

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

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

Ответ 5

Я подозреваю, что найти что-то подобное было бы невозможно с помощью только grep:

public void do(){
    for(...){
        somethingElse();
    }
}

... Insert other code...

public void somethingElse(){
    for(.....){
        print(....);
    }
}