14

GOTO任意のステートメントを使用せずに、構造化プログラミング構造 (条件、ループとループ ブレーク、およびサブルーチン呼び出し) のみを使用して、チューリング完全言語で任意の制御フローを表現することが理論的に可能であることが証明されていると聞いたことがあります。GOTOその理論を使用して、 s を含むコードを含まないコードへのリファクタリングを自動化する方法はありますか?

C や Pascal などの単純な命令型言語で、任意の単一のサブルーチンがあるとします。このサブルーチンが有効であることを検証し、そこから抽象構文ツリーを生成できるパーサーもあります。ただし、コードにはGOTOs と Labels が含まれており、条件ブロックやループ ブロックの内外を含め、任意のポイントに前後にジャンプできますが、サブルーチン自体の外にはジャンプできません。

GOTOこの AST を取り、それを意味的に同一であるがラベルやステートメントを含まない新しいコードに作り直すアルゴリズムはありますか?

4

3 に答える 3

10

結果はきれいではないかもしれませんが、原則として、これを行うことは常に可能です。

goto を常に排除する 1 つの方法は、次のようにプログラムを変換することです。元のプログラムのすべての命令に番号を付けることから始めます。たとえば、次のプログラムがあるとします。

start:
    while (true) {
        if (x < 5) goto start;
        x++
    }

次のようにステートメントに番号を付けることができます。

0 start:
1     while (x < 3) {
2         if (x < 5) goto start;
3         x++
      }

すべての goto を排除するために、while ループ、プログラム カウンターを保持する明示的な変数、および一連の if ステートメントを使用して、この関数を介した制御の流れをシミュレートできます。たとえば、上記のコードを次のように変換できます。

int PC = 0;
while (PC <= 3) {
    if (PC == 0) {
         PC = 1;             // Label has no effect
    } else if (PC == 1) {
         if (x < 3) PC = 4;  // Skip loop, which ends this function.
         else PC = 2;        // Enter loop.
    } else if (PC == 2) {
         if (x < 5) PC = 0;  // Simulate goto
         else PC = 3;        // Simulate if-statement fall-through
    } else if (PC == 3) {
         x++;
         PC = 1;             // Simulate jump back up to the top of the loop.
    }
}

これは、翻訳を行うには本当に悪い方法ですが、理論上は常に可能であることを示しています。これを実際に実装するのは非常に面倒です。おそらく、関数の基本ブロックに番号を付けてから、基本ブロックをループに入れるコードを生成し、現在実行中の基本ブロックを追跡し、基本ブロックの実行の効果をシミュレートし、その基本ブロックから適切な次の基本ブロックへの移行。

お役に立てれば！

于 2012-12-27T22:24:53.263 に答える
5

Erosa と Hendren による 1994 年のTaming Control Flowを読みたいと思います( Google 学者の以前のリンク)。

ちなみに、ループブレイクも簡単に解消できます。ブール状態変数の作成とネストされた条件の再構築を含む単純な機械的手順があり、直線的な制御フローを作成します。それはきれいなコードを生成しません:)

ターゲット言語に末尾呼び出しの最適化 (および、理想的にはインライン化) がある場合、ループを末尾再帰関数に変えることで、中断と継続の両方を機械的に削除できます。(インデックス変数がループ本体によって変更されている場合は、これをさらに強化する必要があります。ここでは、最も単純なケースのみを示します。) 単純なループの変換を次に示します。

for (Type Index = Start;        function loop(Index: Type):    
     Condition(Index);              if (Condition)
     Index = Advance(Index)){           return                      // break
   Body                             Body
}                                   return loop(Advance(Index))     // continue
                                loop(Start)

return「継続」および「中断」とラベル付けされたステートメントは、まさにcontinueおよびの変換ですbreak。実際、手順の最初のステップは、ループを元の言語で同等の形式に書き直すことだった可能性があります。

{
    Type Index = Start;
    while (true) {
        if (!Condition(Index))
            break;
        Body;
        continue;
    }
}
于 2012-12-28T14:38:24.920 に答える
1

Polyhedron の spag と広大な 77to90 のいずれかまたは両方を使用して、fortran をリファクタリングし、それを matlab ソースに変換するプロセスを開始します。ただし、これらのツールは常に goto の 1/4 から 1/2 をプログラムに残します。

私はあなたが説明していたものと同様のことを達成するgoto removerを書きました:それはfortranコードを取り、プログラムから残りのすべてのgotoをリファクタリングし、それらを条件付きで置き換え、その後、matlabのような他の言語に変換できるdo/cycle/exitに置き換えます. ここで使用するプロセスの詳細を読むことができます。

http://engineering.dartmouth.edu/~d30574x/consulting/consulting_gotorefactor.html

このプログラムは他の言語で動作するように適応させることができますが、私はまだそこまで到達していません.

于 2013-09-25T14:14:20.327 に答える