Свертывание CFG к структурированному коду

Question

Я хотел бы сделать CFG для высокоуровневого кода. Обычно это очень легко; пройдите по дереву, поочередно отнесите каждый базовый блок, приклейте все вместе с gotos.

К сожалению, gotos сегодня не в моде, и большинство современных языков их не поддерживают. Поэтому мне нужно каким-то образом, чтобы склеить мои основные блоки вместе, используя только те операторы управления потоком, которые существуют в языке: for, while, do ... while, if, break и continue. (Я не хочу рассматривать создание конечного автомата с использованием переменных.)

Казалось бы, хотя есть алгоритмы для этого, они будут не работать в каждом случае. То есть возможно построить CFG, который нельзя сгладить для структурированного кода, используя только указанный выше ограниченный набор структур потока управления.

Это кажется интуитивно очевидным для меня, но я не могу это доказать (и документация по найденным алгоритмам не вдавалась в подробности). И я не смог найти пример CFG, который нельзя сгладить таким образом.

Я хотел бы знать, окончательно, если это возможно или нет.

Вариант (a): есть ли у кого-нибудь пример CFG, который не может быть сплющен, как описано выше? (Что скажет мне, что это невозможно.)

Вариант (b): есть ли у кого-нибудь доказательства того, что CFG может сгладить, как описано выше? (Который скажет мне, что это возможно). Алгоритм для этого был бы очень желанным, так как я должен был бы заставить его работать ...

Answer 1

Я думаю, что у меня есть результат.

Ответ кажется: невозможно. Это от Коммуникации ACM, том 9, с 366 по 371, в документе от 1966 года, названном Джузеппе Жакопини «Схемы потока, машины Тьюринга и языки только с двумя правилами формирования». CiteSeer link. (Который, забавно, я нашел ссылку из оригинала Кнута (и, с моей точки зрения, невероятно раздражает) Перейти к заявлению считается вредным.)

Неудовлетворительно, у них нет доказательств, заявив, что они не смогли его найти.

Хорошей новостью является то, что в статье описывается стратегия преобразования произвольного CFG в CFG с использованием только ограниченных механизмов управления потоком эффективным способом, используя как можно меньше состояний. Документ довольно тяжелый, но выглядит многообещающим.

Answer 2

В общем, вы не можете просто сгладить CFG, идя по дереву. Это будет работать для грамматик LL (k), если у вас есть маркеры с надписью k. Однако для более сложных грамматик, таких как грамматики LR (k), требуются более сложные методы. См., Например, http://en.wikipedia.org/wiki/LR_parser.

В общем, нет известного алгоритма, который анализирует ЛЮБОЙ CFG, хотя большинство полезных CFG можно записать в виде грамматики LR (k). Больше исследований улучшает это, и большие классы CFG могут быть проанализированы. Я не думаю, что проблема неразрешима (хотя я не уверен), поэтому, безусловно, это возможно всегда, но я думаю, что это проблема исследования, а не то, на что будет дано ответ «да/нет» ты здесь.

Я также должен добавить, что все достойные языки сегодня являются Turing-complete, что означает, что все, что вы можете сделать с GOTO, можно выполнить с помощью конструкций if/while/for/.... Новые языки не являются ограничением, это теоретические строительные блоки, которые нуждаются в помощи.

На практике, однако, вы не сможете проанализировать любой CFG, который вы хотите. Но это не значит, что мы не будем знать, как в будущем ...

Answer 3

Хотя этот вопрос был задан давно, на самом деле это кажется возможным. Аналогичная проблема возникла при компиляции LLVM в JS (или теперь WebAssembly). JS и WebAssembly допускают только структурированный поток управления, а LLVM - произвольный поток управления.

They'v написал статью об этом, который также используется для WebAssembly:

Эта идея по образцу Relooper алгоритма из 2011. Существует доказательство того, что любой поток управления может быть представлен структурированным способом, используя только доступные конструкции потока управления в JavaScript и используя вспомогательную переменную, такую ​​как метка, упомянутая в семантике Tilt, без дублирования кода (другие подходы разделяют узлы, и имеют плохие худшие ситуации с размером кода). Релопер также был внедрен в Emscripten, и за последние 4 года мы получили много практического опыта с ним, показывая, что он дает хорошие результаты на практике, как правило, с небольшим использованием вспомогательной переменной.