6

私はCで単純なスタックベースの言語を書いていて、ある種のループ構造や先読みシンボルを実装する方法を考えていました。このページのコードは少し長いので（200行以上）、GitHubリポジトリに配置しました。

編集：メインプログラムはファイルにありますstack.c。

words編集：コードは、FORTHのように入力を取り込むだけです。scanf左から右に使用して動作します。次に、一連のifsとstrcmpsを使用して何をするかを決定します。それだけです。

4

4 に答える 4

10

4番目のアプローチは、データスタックと一緒に別のループスタックを追加することです。次に、このループスタックで機能する操作を定義します。例えば：

5 0 DO I . LOOP

印刷します

0 1 2 3 4

これが機能する方法は次のとおりです。

  • DOインデックス（0）とコントロール（5）をループスタックに移動します。
  • Iループスタックの最上位をデータスタックにコピーします。
  • LOOPインデックスをインクリメントします（ループスタックの最上位）。DOインデックスがコントロールよりも小さい場合（ループスタックの最上位より1つ下）、コマンドをに戻って再実行しますLOOP。インデックスが>=の場合、ループスタックからインデックスと制御をポップし、制御は通常どおり再開されます。
于 2011-08-04T22:44:22.837 に答える
7

スタックベースの言語に制御構造を追加する明白な方法は、「制御スタック」を追加することです。私が知っているので、Postscriptメカニズムについて説明しますが、Forthにはいくつかの類似した動作があります（確かに微妙な違いがあります）。

最も単純な制御ループはrepeatループです。技術的には、無限loopはより単純ですが、それを使用するには明示的なexitコマンドが必要であり、それを説明すると事態が複雑になります。

repeatの構文は次のとおりです。

int proc  **repeat**  -

したがって、repeatコマンドが開始されると、オペランドスタックの最上位（実行されるループ本体）と、プロシージャのすぐ下の整数（プロシージャを実行する回数）でプロシージャが検出されることが期待されます。

実行スタックもあるので（Forthでは「リターン」スタックと呼んでいます）、コマンドは他のコマンドを実行スタックにプッシュすることで「実行」でき、現在のコマンドが終了した直後に他のコマンドを実行するようにスケジュールできます。 、ただし、現在のコマンドの呼び出し元を再開する前。それは長い文章ですが、重要なアイデアはそこにあります。

具体的な例として、インタプリタが入力ストリームから実行されていると仮定します。そして、スタックは次のようになります。

operand: -empty-
execute: <stdin>

ユーザーは。と入力します2 {(Hello World!\n) print} repeat。

整数2がスタックにプッシュされます。

operand: 2
execute: <stdin>

quoted（*）プロシージャ本体はスタックにプッシュされます。

operand: 2 {(Hello World!\n) print}
execute: <stdin>

repeatコマンドが実行されます。

operand: 2 {(Hello World!\n) print}
execute: <stdin> repeat

Repeat: expects operands: int proc
    if int<0 Error
    if int==0 return //do nothing
    push `repeat` itself on exec stack
    push quoted proc on exec stack
    push int-1 on exec stack
    push "executable" proc on exec stack

繰り返し手順を（1回）実行すると、スタックは次のようになります。

operand: -empty-
execute: <stdin> repeat {(Hello World!\n) print} 1 **{(Hello World!\n) print}**

インタプリタはexecスタックの最上位でプロシージャを実行し、「Hello World！」を出力してから整数を見つけ、それをopスタックにプッシュします。

operand: 1
execute: <stdin> repeat {(Hello World!\n) print}

インタプリタは、opスタックをプッシュすることにより、引用符で囲まれたプロシージャを実行します。

operand: 1 {(Hello World!\n) print}
execute: <stdin> repeat

そして、私たちは最初に戻ってきました！次の反復の準備ができています（または整数がゼロになっている場合は終了します）。

お役に立てれば。

編集;

実際にあなたのコードを見た後、私は別の提案をします。おそらく、私が上で説明したようなものへの踏み台です。しばらくコードを忘れて、データ構造に集中するべきだと思います。変数の優れたテーブルがありますが、すべてのコマンドはコード全体に散在する埋め込みリテラルです。

テーブルに可変レコードタイプを保持させる場合は、両方に同じルックアップメカニズムを使用できます（さらに、ハッシュまたは三分探索木（私の現在のお気に入り）に移動することもできます）。私はこのようなことを念頭に置いています：

struct object {
    int type;
    union {
        int i;
        void (*command)(context *);
    } u;
};

struct dict {
    int sz;
    struct rec {
        char *key;
        object val;
    }  data[]; //think resizable!
};

このようにして、各コマンドは独自の機能を果たします。ボーナスは次のとおりです。小さな機能。画面上ですべてを同時に見ることができるように、関数を十分に小さくするようにしてください。一度にすべてをスキャンすることで、右脳が問題のある領域を検出する作業の一部を実行できるようになります。

次に、コマンドのシーケンスを保持するために別のタイプが必要になります。配列またはリストが機能するはずです。シーケンスを定義できると、シーケンスをはるかに簡単に繰り返すことができます。

ここでのボーナスは、チューリング完全から1つだけ離れていることです。シーケンス、反復、決定（または選択）：計算可能な関数をプログラムするために必要なのはそれだけです！

*。コメンテーターによって発見されたように、Postscriptには、実際には、ここで説明に使用しているのと同じ引用の概念がありません。ここでは、Lispの用語から概念を借りています。Postscriptには、代わりに、設定またはテストできるリテラル/実行可能フラグがあります。実行スタック上の実行可能配列が実行されます。したがって、「引用符で囲まれた」procedure-bodyの場合、実際にはリテラルのprocedure-body（つまり配列）です。このため、次の反復の前に実行される呼び出しもプッシュする必要があります。したがって、のポストスクリプト実装のより正確な擬似コードは次のとおりです。cvx cvlitxcheckrepeatcvxrepeat

Repeat: expects operands: int proc
    if int<0 Error
    if int==0 return //do nothing
    push `repeat` itself on exec stack
    push 'cvx' on the exec stack
    push cvlit(proc) on exec stack
    push int-1 on exec stack
    push "executable" proc on exec stack

これにより、プロシージャを実行スタック上のデータとして渡すために必要なフラグの調整が実行されます。

この制御構造が実装されているのを見たもう1つの方法は、2つの関数、repeat同じエントリポイント、および理論的には名前を必要としない内部継続演算子を使用することです。ghostscriptはそれを@repeat-continue@のようなものと呼んでいると思います。別のcontinue関数を使用すると、スタック上のものの順序にそれほど注意する必要はなく、文字通りのフラグをいじる必要もありません。代わりに、execスタックの再帰呼び出しの下に永続データを格納できます。しかし、あなたもそれをきれいにしなければなりません。

したがって、代替案は次のrepeatようになります。

int proc  **repeat**  -
    if int<0 Error
    if int==0 return //do nothing
    push null on exec stack   <--- this marks our "frame"
    push int-1 on exec stack
    push proc on exec stack
    push '@repeat-continue' on exec stack
    push executable proc on exec stack

継続には、より単純な仕事もあります。

@repeat-continue
    peek proc from exec stack
    peek int from exec stack
    if int==0 clear-to-null and return
    push '@repeat-continue' on exec stack
    push executable proc on exec stack

最後に、exitオペレーターはループに密接に接続されており、ループオペレーターの「フレーム」までexecスタックをクリアします。2関数スタイルの場合、これはnullオブジェクトなどです。1関数スタイルの場合、これはループ演算子自体です。

于 2011-08-05T05:31:41.580 に答える
2

あなたの言語はForthにまったく似ていないので、Forthの（コンパイルのみ-あなたの言語にとって意味のない区別）ループ構造をコピーしないでください。

untilコードを見て、条件付きの再起動評価ワードとして追加します。つまり、rangeandと一緒に通常の単語として追加しjump、スタックをポップさせます。スタックの一番上がtrueの場合は、stack.ccmdを最初に戻します。

0
dup . 1 + dup 5 > until
.

、あなたの言語では、0 1 2 3 4 5 63つの評価にわたって出力を生成し、2行目を数回再評価します。これは、評価全体で状態を保持し、評価が行指向であることを前提としています。あなたはこのようなより多くのアイデアのためにLSE64を採掘するかもしれません。

于 2011-08-05T02:32:38.750 に答える
1

これは、DO / LOOP、BEGIN / UNTIL、WHILE / REPEATなどが私の小さなTransForthプロジェクトに含まれているブログ投稿です：http：//blogs.msdn.com/b/ashleyf/archive/2011/02/06/ loopty-do-i-loop.aspx

しかし、私はその後気が変わって、そのようなループする言葉がなく、再帰に完全に依存しています。

お役に立てば幸いです。楽しんでください。

于 2012-08-09T21:34:51.863 に答える