11

数年前、私はプログラマー定義の関数を含む小さなドメイン固有言語のインタープリターを書き始めました。

最初に、単純なシンボル テーブルのスタックを使用して変数スコープを実装しました。しかし、今は適切なレキシカル スコープに移行したいと考えています (クロージャのオプションを使用)。レキシカルスコープの背後にあるデータ構造とアルゴリズムを説明できる人はいますか?

4

5 に答える 5

10

インタプリタで正しいレキシカル スコープとクロージャを取得するには、次のルールに従うだけで済みます。

  • インタープリターでは、変数は常に呼び出し元から渡された環境テーブルで検索されるか、変数として保持されます。グローバルな環境スタックではありません。eval 操作の署名は次のようになりeval(expression, env) => valueます。
  • 解釈されたコードが関数を呼び出すとき、環境はその関数に渡されません。関数アプリケーション操作の署名は次のようになりapply(function, arguments) => valueます。
  • 解釈された関数が呼び出されると、その本体が評価される環境は、関数定義が作成された環境であり、呼び出し元とは何の関係もありません。したがって、ローカル関数がある場合、それはクロージャ、つまりフィールドを含むデータ構造{function definition, env-at-definition-time}です。

Python 風の構文で最後のビットを拡張するには、次のようにします。

x = 1
return lambda y: x + y

であるかのように実行する必要があります

x = 1
return make_closure(<AST for "lambda y: x + y">, {"x": x})

ここで、2 番目の dict 引数は、その時点で構築されたデータ構造ではなく、単なる current-env である可能性があります。(一方、閉じた変数だけでなく環境全体を保持すると、プログラムで驚くべきメモリ リークが発生する可能性があります。これは、クロージャが必要のないものを保持しているためです。これは、「実用的な」言語実装で修正する価値がありますが、そうではありません。言語のセマンティクスを試しているだけの場合。)

于 2010-03-05T02:47:56.747 に答える
7

レキシカルスコープを実装するには、さまざまな方法があります。ここに私のお気に入りのいくつかがあります：

于 2010-03-05T03:33:02.333 に答える
2

たとえば、Lua 5.0 の実装を参照してください。

于 2010-03-05T03:02:46.850 に答える
1

Stroustrupは、これを最初のC ++コンパイラで、スコープごとに1つのシンボルテーブルと、定義が見つかるまでスコープを外側にたどるチェーンルールを使用して実装しました。これがどのように機能するかは、正確なセマンティクスによって異なります。あなたが最初にそれらを釘付けにすることを確認してください。

The Art of Computer Programming、 Vol 1のKnuthは、スコープがリンクを介して行われるCOBOLシンボルテーブルのアルゴリズムを提供します。

于 2010-03-05T03:42:00.007 に答える
1

これを行うための唯一の正しい方法はありません。重要なことは、提供しようとしているセマンティクスを明確に述べることです。そうすれば、データ構造とアルゴリズムが続きます。

于 2010-03-05T02:30:35.550 に答える