상위 포인터 트리

Parent pointer tree
"활성" 스택 프레임이 강조 표시된 스파게티 스택

컴퓨터 과학에서 나무 안 또는 부모 포인터 트리는 각 노드가 상위 노드에 대한 포인터를 가지고 있지만 하위 노드에 대한 포인터는 없는 N-ary 트리 데이터 구조다.스택 세트를 구현하기 위해 사용할 때, 이 구조를 스파게티 스택, 선인장 스택 또는 사와로 스택(선인장의 일종인 사와로 스택 다음에)이라고 부른다.[1]상위 포인터 트리는 분리 집합 데이터 구조로도 사용된다.

이 구조는 특히 꼬리의 일부를 공유하는 단일 연결 리스트의 집합으로 간주할 수 있다.어떤 노드에서든 노드의 조상에게는 횡단할 수 있지만 다른 노드는 횡단할 수 없다.

컴파일러에서 사용

C와 같은 언어에 대한 컴파일러는 블록 범위를 나타내는 기호 테이블을 열고 닫을 때 스파게티 스택을 만든다.새 블록 스코프가 열리면 기호 테이블이 스택에 푸시된다.닫히는 곱슬 가새에 부딪히면 스코프가 닫히고 기호 테이블이 펑크난다.하지만 그 상징 테이블은 파괴되기는커녕 기억되고 있다.그리고 물론 그것은 더 높은 수준의 "부모" 기호 표 등을 기억한다.따라서 컴파일러가 나중에 추상 구문 트리를 통해 번역을 수행할 때, 주어진 표현식에 대해 해당 표현식의 환경을 나타내는 기호 표를 가져와 식별자에 대한 참조를 해결할 수 있다.표현식이 변수 X를 참조하는 경우, 가장 안쪽의 어휘적 범위를 나타내는 잎 기호 표에서 먼저 찾고, 그 다음 부모 등에서 찾는다.

콜 스택으로 사용

스파게티 스택이라는 용어는 연속성을 지원하는 프로그래밍 언어의 구현과 밀접한 관련이 있다.스파게티 스택은 가변 바인딩 및 기타 환경적 특징을 포함하는 실제 런타임 스택을 구현하는 데 사용된다.연속성이 지원되어야 하는 경우, 해당 기능이 반환될 때 함수의 로컬 변수는 파괴될 수 없다. 저장된 연속성은 나중에 해당 함수에 다시 진입할 수 있으며, 거기에 있는 변수가 온전할 뿐만 아니라 전체 스택이 존재하여 함수가 다시 돌아올 수 있을 것으로 예상할 수 있다.이 문제를 해결하기 위해, 스택 프레임은 스파게티 스택 구조로 동적으로 할당될 수 있으며, 더 이상 연속적으로 언급되지 않을 때 쓰레기를 수거하도록 방치할 수 있다.이러한 유형의 구조는 또한 위와 아래 모두의 funarg 문제를 해결하는데, 그 결과 그 기질에서 1등급 어휘 폐쇄가 쉽게 구현되기 때문이다.

스파게티 스택을 사용하는 언어의 예는 다음과 같다.

Burroughs Large Systems 아키텍처를 사용하고 MCP 운영 체제를 실행하는 메인프레임 컴퓨터는 동일한 프로그램 내에서 여러 작업을 발생시킬 수 있다.이들은 원래 ALGOL 기반 시스템이었기 때문에 중첩된 기능을 지원해야 하며, 그 결과 Burroughs가 비공식적으로 "사과로 스택"이라고 기술한 스택에 포크가 생긴다.

참고 항목

참조

  1. ^ Clinger, W.; Hartheimer, A.; Ost, E. (1988). "Implementation strategies for continuations". Proceedings of the 1988 ACM conference on LISP and functional programming - LFP '88. pp. 124–131. doi:10.1145/62678.62692. ISBN 089791273X.