Задача: из текста типа: Код (Text): L_3: if(R1 != 1) goto L_1; R1 = R2; //.... goto L_2; L_1: R1 = 1; //... L_2: //... if(R2 < 5) goto L_3; //... получить: Код (Text): do { if(R1 == 1) { R1 = R2; //... } else { R1 = 1; //... } } while(R2 < 5); //... в общем, нужно избавится от всех goto в тексте, если возможно, и преобразовать в красивые Сишные структуры с использованием if-else, while, do-while, for, switch, return. Может есть готовое описание или исходники такого алгоритма?
_Cyber_ Этому посвящен целый раздел теории графов (CFG - control flow graphs). Для затравочки: http://unicorn.cmc.msu.ru/op/lect/250902.doc
_Cyber_ Инструмент, который делает это для общего случая, представляет из себя часть декомпилятора. Алгоритм существует, но пока не опубликован - не знаю, когда у меня руки дойдут.
KeSqueer Описанный там "Структурный анализ" на практике не имеет смысла, так как нестандартные выходы из statement'a (то есть break и continue) не распознаются никакими шаблонами. Но все равно неплохо, не думал, что в российских ВУЗ'ах вообще как-то касаются этой темы. А откуда лекция?
Stiver Распознаются, в этой лекции есть такие шаблоны. Наткнулся на нее, когда искал что такое "сводимые графы", решил сохранить ссылку.
KeSqueer В том файле, который скачивается по ссылке, их нет (да и в принципе таких шаблонов не существует, насколько мне известно ). Или у файла есть еще продолжение? Лучше все-таки обращаться к первоисточникам: M.S.Hecht, J.D.Ullman, Characterizations of Reducible Flow Graphs В сети этой работы по-моему нет в свободном доступе, но могу выслать.
Stiver Офис у меня сейчас не установлен, проверить не могу. Но все же был уверен, что такие шаблоны есть. Буду очень признателен, никак не мог найти стоящей литературы по этой теме.
KeSqueer Шаблонов таких конечно же нет. Но есть алгоритмы, позволяющие заменить переходы в сводимых графах на циклы с выходами. Это именно алгоритмы, шаблонному распознаванию такие структуры не поддаются. Один и самых старых опубликовала Brenda Baker: "An Algorithm for Structuring Flowgraphs", 1977 год. Рекомендую, очень милая работа. Самое начало развития, тогда еще даже термин "доминатор" не использовался. В сети нет: An Algorithm for Structuring Flowgraphs Более поздний и более известный - алгоритм Ramshaw: http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-4.pdf Он был положен например в основу декомпилятора Krakatoa. У них у всех два недостатка: 1) дают совершенно нечитаемую структуру на выходе 2) что более важно, не умеют обходится со сложными statement'ами (обработчиками исключений например). Поэтому тот же Krakatoa авторы бросили на полпути. Хотя если _Cyber_ собирается работать с чистым С, то они ему вполне могут подойти. Мой собственный алгоритм дает простое и достаточно быстрое иерархическое разложение графа на statement'ы для Явы (то есть вместе с try{}catch{}finally), реализован в декомпиляторе Fernflower. Обещанная статья: Characterizations of Reducible Flow Graphs Кроме того советую почитать работы Cristina Cifuentes, из них главным образом произошел декомпилятор Boomerang.
