Существует три вида циклов в C:
- «структурированный синтаксис» (, а , для , ...) [ОстерегайтесьGCC, который может скрывать операторы, поэтому выполняет циклы внутри выражений, используя (stmt; exp) синтаксис!]
- специальные циклы, используя goto ;они взаимодействуют со структурированным синтаксисом.
- рекурсия
Чтобы найти первый тип, вы должны найти структурированный синтаксис и вложенность.
Grep, безусловно, может найтиключевые слова (если вы игнорируете ложные срабатывания в комментариях и строках), но он не может найти вложенные структуры.Конечно, вы можете использовать grep, чтобы найти весь синтаксис цикла, а затем просто проверить те, которые встречаются в одном и том же файле, чтобы увидеть, были ли они вложенными.(Если вы хотите сделать это без цены ложных срабатываний, вы можете использовать нашу систему поиска исходного кода , которая знает лексический синтаксис C и никогда не путается с тем, когда строка символов является ключевым словом,число, строка и т. д.)
Если вы хотите найти эти циклы автоматически, вам в значительной степени нужен полный синтаксический анализатор C с выполненной расширенной предварительной обработкой.(В противном случае некоторые макросы могут скрывать критическую часть синтаксиса цикла).Как только у вас есть синтаксическое дерево для C, становится простым (хотя, вероятно, немного неудобным) кодировать что-то, что цепляется за дерево, обнаруживая узлы синтаксического цикла и подсчитывая вложенность циклов в поддеревьях.Вы можете сделать это с помощью любого инструмента, который будет анализировать C и давать вам абстрактные деревья ситнакс. ANTLR может сделать это;Я думаю, что есть грамматика C, доступная для ANTLR, которая довольно хорошо обрабатывает C, но вам придется запустить препроцессор перед использованием ANTLR.
Вы также можете сделать это с помощью DMS Software Reingineering Toolkit с C Front End .Наш C-интерфейс имеет встроенный препроцессор, так что он может читать код напрямую и расширяться при его разборе;он также обрабатывает относительно широкий спектр диалектов 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 может сканировать дерево синтаксиса и находить совпадения.любому члену набора, без кодирования какого-либо конкретного механизма обхода дерева и без знания огромного количества деталей о структуре дерева.(Существует много типов узлов в AST для реального синтаксического анализатора C!) Найти вложенные циклы таким способом было бы довольно просто: отсканируйте дерево сверху вниз для цикла (используя набор шаблонов);любые попадания должны быть петлями верхнего уровня.Сканирование поддеревьев узла AST найденного цикла (легко, когда вы знаете, где находится дерево для внешнего цикла) на наличие дополнительных циклов;любые попадания должны быть вложенными циклами;повторяйте при необходимости подобрать петли с произвольной вложенностью.Это работает и для GCC Loop-with-Statement.Узлы дерева помечены точной информацией о файле / строке / столбце, поэтому легко сгенерировать отчет о местоположении.
Для специальных циклов, построенных с использованием goto (что, ваш код не делаетесть что-то?), вам нужно что-то, что может создать реальный граф потока управления, а затем структурировать этот граф во вложенные области потока управления.Дело в том, что цикл while , содержащий безусловный goto out, на самом деле не является циклом, несмотря на синтаксис;и оператор if , предложение которого затем возвращает код, предшествующий if , вероятно, действительно цикл.Все эти синтаксические элементы цикла на самом деле просто намекают на то, что может иметь цикл!Эти области потока управления содержат реальную вложенность потока управления; DMS будет создавать графы потоков C и создавать эти структурированные области . Он предоставляет библиотеки для построения и доступа к этому графику; таким образом вы можете получить «истинный» поток управления на основе gotos. Найдя пару вложенных областей потока управления, можно получить доступ к AST, связанному с частями региона, чтобы получить информацию о местоположении для отчета.
GCC всегда очень веселый из-за значительно улучшенной версии C. Например, у него есть косвенное выражение goto. (Обычный C имеет это скрытие в setjmp / longjmp!).
Чтобы разобраться в этом цикле, вам нужно точек для анализа , которые также предоставляет DMS. Эта информация используется для анализа вложенных областей. Существуют (консервативные) ограничения на точность анализа точек, но по модулю вы получаете правильный график вложенных областей.
Рекурсию найти сложнее. Для этого вам нужно определить, вызывает ли A вызовы B ..., вызывает ли Z вызовы A, где A и B и ... могут находиться в отдельных единицах компиляции. Вам нужен глобальный граф вызовов , содержащий все единицы компиляции вашего приложения. В этот момент вы, вероятно, ожидаете, что я скажу, что DMS тоже это делает, вуаля, я рад сказать, что делает . Построение этого графа вызовов, конечно, требует точечного анализа для вызовов функций; да, DMS тоже это делает. В графе вызовов вы можете найти циклы в графе вызовов, которые, вероятно, являются рекурсивными. Также в графе вызовов вы можете найти косвенное вложение, например, циклы в одной функции, которые вызывают функцию в другом модуле компиляции, который также содержит циклы.
Для точного поиска структур, таких как циклы, вам нужно много машин (и это потребует некоторых усилий, но тогда C - это сука языка для анализа), и DMS может предоставить его.
Если вас не заботит точность и вас не заботят все виды циклов, вы можете использовать grep и ручные процедуры, чтобы получить полуточную карту только тех циклов, на которые намекают операторы структурированного цикла ,