0

プログラミング言語が AST を評価するために使用するアルゴリズムは何ですか?

つまり、4 つの基本関数 があるとし/*+-ます。たとえば、次の形式で AST を正しく評価する基本的なアルゴリズムは何ですか。

(+ (- (* 3 2) (+ (/ 5 2))) (* 2 4))

私の疑問は、ノードの評価がまだ評価されなければならない何かを返す場合、実際に何が起こるかということです。たとえば、Scheme では、 の評価は((lambda (a) (+ a 2)) 3)になります(+ 3 2)。しかし、これは再び 5 に評価される可能性があります。では、言語はフォームの評価をいつ停止するかをどのように決定するのでしょうか?

4

4 に答える 4

2

あなたはScheme/Lisp評価がどのように機能するかを完全に誤解しています。あなたが与えた例を使用します：

(+ (- (* 3 2) (+ (/ 5 2))) (* 2 4))

リストを評価するために、各要素を評価します。最初のものはプロシージャを返すことが期待されており（構文演算子の特殊なケースは無視しています）、残りは任意の値を返すことができます。残りを引数としてプロシージャを呼び出します。

トップレベルでは、これは3つの要素のリストです。

  1. +
  2. (- (* 3 2) (+ (/ 5 2)))
  3. (* 2 4)

これらのそれぞれが評価されます。1つ目は、値がプロシージャ（Schemeの組み込み加算関数）である変数です。リストである他のものは、評価アルゴリズムへの再帰を必要とします。複雑さがあるため、2番目の説明はスキップし、3番目の説明に進みます(* 2 4)。

これは、*、2、および4の3つの要素のリストです。上記のように、*は乗算関数です。2と4はリテラルであるため、それらは自分自身に評価されます。したがって、引数2と4を使用して乗算関数を呼び出すと、8が返されます。

複雑な2番目の引数は同じプロセスを経ますが、再帰のレベルがさらにいくつかあります。最終的には4を返します。したがって、引数4と8を使用して乗算関数を呼び出すと、32が返されます。

2番目の例も同様に処理されます。上部には、次の2つの要素のリストがあります。

  1. (lambda (a) (+ a 2))
  2. 3

これらのそれぞれが評価されます。Lambdaは、その内容を解析し、パラメーター変数が引数にバインドされているコンテキストで本体を評価するプロシージャを返す特別な構文です。したがって、最初の構文は、引数に2を追加してそれを返すプロシージャを返します。3はリテラルであるため、数値3を返します。次に、引数3を指定してプロシージャを呼び出し、それに2を加算して、5を返します。

于 2012-10-09T01:43:06.907 に答える
0

あなたが与えた場合、それはリテラル値であり、それ自体を表すため、実行は 5 で停止します。これをテストするのは難しくありません。リストを詳細にトラバースする関数が停止方法をどのように知っているかを尋ねることもできます (実際、Scheme ではこれは同じことなので、停止する必要があります)。

Scheme では、複合式は、無限ループに陥らない限り、最終的に 7 つのプリミティブ データ型のいずれか、または空のリストに解決されます。式が解決するかどうかを事前に知りたい場合は、興味深い問題です: http://en.wikipedia.org/wiki/Halting_problem

于 2012-10-09T00:06:08.930 に答える
0

多くの異なるアルゴリズムがあります。

代替案 1: AST をより線形な中間表現にコンパイルできます。コードは次のようにコンパイルできます。

a <- 3 * 2
b <- 5 / 2
c <- a - b
d <- 2 * 4
e <- c + d
return e

これは単なる一連の命令であるため、評価は簡単です。ほとんどの命令は同じ形式:X <- Y OP Zであるため、エバリュエーターは非常に単純になります。

代替案 2:代替案 #1 をマシン コードまたはバイト コードにコンパイルできます。

li      r3, 3
muli    r3, 2
li      r4, 5
divi    r4, r5, 2
subf    r3, r3, r4
li      r4, 2
muli    r4, r4, 4
add     r3, r3, r4
blr

代替案 3:代替案 #1 を SSA と呼ばれる特別な形式、または #1 に似ている「単一の静的割り当て」にコンパイルできますが、すべての割り当ての LHS は一意であり、特別な「ファイ」ノードを使用して値を結合します。異なる枝。その後、SSA をマシン コードまたはバイト コードにコンパイルできます。

代替案 4:再帰降下によって AST を評価できます。これは、Scheme / Lisp に関するほとんどの本で徹底的にカバーされています。

代替案 5:再帰降下を使用してコードをスタック マシン コードに変換し、それを評価することができます。何かのようなもの：

push 3
push 2
mul
push 5
push 2
div
sub
push 2
push 4
mul
add
ret

代替∞：他にもたくさんのテクニックがあります。この主題について書かれた本は分厚い。

于 2012-10-09T00:53:09.497 に答える
0

間違った質問をしているかもしれませんが、試してみます：

使える結果が出るまで。あなたの例では、インターピーターがいつ式の評価を停止するかについて尋ねています...その100％言語依存であり、コンパイラについて尋ねると、まったく異なる答えになります。Scheme の例では、Scheme 仕様 ( R5RS )を読む必要があります。

したがって、インタプリタの作成者によって定義されます。私の言語では、単一のリテラル (または変数) が式の期待される結果である場合、そこで停止します。

于 2012-10-09T00:30:24.980 に答える