AST를 평가하기 위해 프로그래밍 언어에서 사용되는 알고리즘은 무엇입니까?AST를 평가하기 위해 프로그래밍 언어에서 사용되는 알고리즘은 무엇입니까?
즉 4 개의 기본 함수, /*+-이 있다고 가정합니다.
(+ (- (* 3 2) (+ (/ 5 2))) (* 2 4))
내 의심의 여지가 노드의 평가는 여전히 평가해야 할 뭔가를 반환하는 경우 무슨 실제로 : 제대로 예를 들어,의 형태로 어떤 AST를 평가 후면하는 기본 알고리즘은 무엇입니까. 예를 들어, Scheme에서 ((lambda (a) (+ a 2)) 3)의 평가는 (+ 3 2)입니다. 그러나 이것을 다시 5로 평가할 수 있습니다. 그러면 언어가 양식 평가를 중단 할 시점을 어떻게 결정합니까?
줄 경우 리터럴 값이고 자체를 나타 내기 때문에 실행이 5에서 중단됩니다. 테스트하기가 어렵지 않습니다. 당신은 깊이있는 목록을 가로 지르는 함수가 어떻게 멈추는지를 안다는 것을 물을지도 모른다. (실제로 Scheme에서 이것은 같은 것이다.
Scheme에서 모든 복합 표현식은 무한 루프에 갇히지 않는 한 결국 7 개의 원시 데이터 유형 중 하나 또는 빈 목록으로 해석되어야합니다. 당신이 표현이 해결할 사전에 알고 싶은 경우에, 음, 흥미로운 문제입니다 : 내가 잘못된 질문을 할 수있다 생각 http://en.wikipedia.org/wiki/Halting_problem
, 그러나 나는 시도 할 것이다 :
는 결과를 얻을 때까지 그것은 함께 일할 수 있습니다. 귀하의 예제에서 인터 피터가 표현을 평가하는 것을 중단 할 때 묻는 것입니다 ... 컴파일러에 대해 물어 본다면 100 % 언어가 도움이 될 것입니다. Scheme 예제의 경우 Scheme 사양 (R5RS)을 읽어야합니다.
따라서 인터프리터 작성자가 정의합니다. 단일 리터럴 (또는 변수)이 내 언어로 된 표현식의 예상 결과라면, 거기에서 멈출 것입니다.
다양한 알고리즘이 있습니다.
대체 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 그러나 모든 과제의 LHS입니다 독특한 유사하다 SSA, 또는 "단일 정적 할당"라는 특별한 형태로 대안 # 1을 컴파일 및 특수 수 있습니다 " phi "노드는 다른 분기의 값을 결합하는 데 사용됩니다. 그러면 SSA는 기계 코드 또는 바이트 코드로 컴파일 될 수 있습니다.
대체 4 : 재귀 적 강하로 AST를 평가할 수 있습니다. 이것은 Scheme/Lisp에 관한 대부분의 책에서 철저히 다루어진다.
대체 5 : 재귀 적 강하를 사용하여 코드를 스택 머신 코드로 변환 한 다음이를 평가할 수 있습니다. 뭔가 같이 :
push 3
push 2
mul
push 5
push 2
div
sub
push 2
push 4
mul
add
ret
대체 ∞ : 다른 기술의 많음이있다. 이 주제에 쓰여진 책은 두께가 입니다.
당신은 Scheme/Lisp 평가가 어떻게 작동하는지 완전히 오해하고 있습니다. 난 당신이 준 예를 사용합니다 : 목록을 평가하기 위해
(+ (- (* 3 2) (+ (/ 5 2))) (* 2 4))
을, 우리는 각 요소를 평가한다. 첫 번째는 프로 시저를 반환 할 것으로 예상되며 (나머지는 구문 연산자의 특별한 경우는 무시합니다) 나머지는 임의의 값을 반환 할 수 있습니다. 나머지는 인수로 프로 시저를 호출합니다.
최상위에이 3 개 요소의 목록이다 :
+(- (* 3 2) (+ (/ 5 2)))(* 2 4)이들 각각
평가된다. 첫 번째는 값이 프로 시저 인 변수입니다 (Scheme의 기본 제공 추가 기능). 리스트가되는 다른 것들은 평가 알고리즘으로 재귀해야한다. 복잡성 때문에 두 번째 설명을 건너 뛰고 세 번째로 이동하십시오 :(* 2 4).
이것은 3 요소의 목록입니다 : *, 2 및 4 위와 같이 *는 곱하기 함수입니다. 2와 4는 리터럴이므로 평가할 수 있습니다. 따라서 우리는 인수 2와 4로 곱셈 함수를 호출하고 8을 반환합니다.
복잡한 두 번째 인수는 여러 단계의 재귀만으로 동일한 프로세스를 거칩니다. 결국 4를 반환합니다. 따라서 인수 4와 8로 곱셈 함수를 호출하면 32를 반환합니다.
두 번째 예제도 비슷하게 처리됩니다. 이들 각각은 평가
(lambda (a) (+ a 2))3: 상단에, 당신은 두 가지 요소의 목록을 가지고있다. Lambda는 내용을 파싱하고 파라미터 변수가 인수에 바인딩되는 컨텍스트에서 본문을 평가하는 프로 시저를 반환하는 특수 구문이므로 첫 번째 인수는 인수에 2를 더한 프로 시저를 반환하고이를 반환합니다. 3은 리터럴이므로 3 번만 반환합니다. 3 번 인수로 프로 시저를 호출하고 2를 더하고 5를 반환합니다.