추상 구문 트리 - Abstract syntax tree

Euclidean 알고리즘 의 다음 코드에 대한 추상 구문 트리 :
반면 b ≠ 0 
이면 a> b
a : = a − b
else
b : = b − a
반환 a

에서 컴퓨터 과학 , 추상 구문 트리 ( AST ), 아니면 그냥 구문 트리 , A는 나무 의 표현 추상 구문 의 구조 소스 코드 에 작성하는 프로그래밍 언어 . 트리의 각 노드는 소스 코드에서 발생하는 구성을 나타냅니다.

구문은 실제 구문에 나타나는 모든 세부 사항이 아니라 구조적 또는 내용 관련 세부 사항 만 나타내는 의미에서 "추상적"입니다. 예를 들어, 그룹화 괄호 는 트리 구조에 내재되어 있으므로 별도의 노드로 표시 할 필요가 없습니다. 마찬가지로 if-condition-then 표현식과 같은 구문 구조는 3 개의 분기가있는 단일 노드를 통해 표시 될 수 있습니다.

이는 추상 구문 트리를 전통적으로 지정된 구문 분석 트리 인 구체적인 구문 트리와 구별합니다 . 파스 트리는 일반적으로 소스 코드 번역 및 컴파일 프로세스 중에 파서에 의해 빌드됩니다 . 일단 구축되면 후속 처리 (예 : 컨텍스트 분석) 를 통해 추가 정보가 AST에 추가됩니다 .

추상 구문 트리는 프로그램 분석프로그램 변환 시스템 에서도 사용 됩니다.

컴파일러에서의 응용

추상 구문 트리는 프로그램 코드의 구조를 나타 내기 위해 컴파일러 에서 널리 사용되는 데이터 구조 입니다. AST는 일반적으로 컴파일러 구문 분석 단계의 결과입니다 . 종종 컴파일러가 요구하는 여러 단계를 통해 프로그램의 중간 표현으로 사용되며 컴파일러의 최종 출력에 강한 영향을 미칩니다.

자극

AST에는 컴파일 프로세스의 추가 단계를 지원하는 몇 가지 속성이 있습니다.

  • AST는 포함 된 모든 요소에 대한 속성 및 주석과 같은 정보를 사용하여 편집하고 향상시킬 수 있습니다. 프로그램의 소스 코드로는 이러한 편집과 주석이 불가능합니다. 변경을 의미하기 때문입니다.
  • 소스 코드 와 비교할 때 AST에는 필수 구두점 및 구분 기호 (중괄호, 세미콜론, 괄호 등)가 포함되지 않습니다.
  • AST는 일반적으로 컴파일러에 의한 분석의 연속 단계로 인해 프로그램에 대한 추가 정보를 포함합니다. 예를 들어, 소스 코드에 각 요소의 위치를 ​​저장하여 컴파일러가 유용한 오류 메시지를 인쇄 할 수 있습니다.

AST는 프로그래밍 언어와 설명서의 고유 한 특성 때문에 필요합니다. 언어는 종종 본질적으로 모호합니다. 이러한 모호함을 피하기 위해 프로그래밍 언어는 종종 문맥없는 문법 (CFG)으로 지정됩니다. 그러나 CFG가 표현할 수 없지만 언어의 일부이며 사양에 문서화되어있는 프로그래밍 언어의 측면이 종종 있습니다. 유효성과 동작을 결정하기 위해 컨텍스트가 필요한 세부 정보입니다. 예를 들어, 언어가 새로운 유형의 선언을 허용하는 경우 CFG는 이러한 유형의 이름이나 사용 방법을 예측할 수 없습니다. 언어에 미리 정의 된 유형 집합이 있더라도 적절한 사용을 적용하려면 일반적으로 컨텍스트가 필요합니다. 또 다른 예는 오리 타이핑입니다., 요소의 유형은 컨텍스트에 따라 변경 될 수 있습니다. 연산자 오버로딩 은 컨텍스트에 따라 올바른 사용과 최종 기능이 결정되는 또 다른 경우입니다. Java는 '+'연산자가 숫자 추가 및 문자열 연결 인 훌륭한 예를 제공합니다.

컴파일러의 내부 작업과 관련된 다른 데이터 구조 가 있지만 AST는 고유 한 기능을 수행합니다. 첫 번째 단계 인 구문 분석 단계에서 컴파일러는 구문 분석 트리를 생성합니다. 이 구문 분석 트리는 구문 지향 번역을 통해 컴파일러의 거의 모든 기능을 수행하는 데 사용할 수 있습니다. 이 방법은보다 효율적인 컴파일러로 이어질 수 있지만 프로그램 작성 및 유지 관리의 소프트웨어 엔지니어링 원칙에 위배됩니다 [ 인용 필요 ] . AST가 구문 분석 트리에 비해 갖는 또 다른 이점은 크기, 특히 AST의 높이와 요소 수가 적다는 것입니다.

디자인

AST의 디자인은 종종 컴파일러의 디자인 및 예상되는 기능과 밀접하게 연결됩니다.

핵심 요구 사항은 다음과 같습니다.

  • 변수 유형은 물론 소스 코드의 각 선언 위치도 유지해야합니다.
  • 실행 가능한 명령문의 순서는 명시 적으로 표현되고 잘 정의되어야합니다.
  • 이진 연산의 왼쪽 및 오른쪽 구성 요소를 저장하고 올바르게 식별해야합니다.
  • 식별자와 할당 된 값은 할당 문에 저장되어야합니다.

이러한 요구 사항은 AST의 데이터 구조를 설계하는 데 사용할 수 있습니다.

일부 작업에는 덧셈을위한 두 용어와 같이 항상 두 가지 요소가 필요합니다. 그러나 일부 언어 구조에는 명령 쉘 에서 프로그램으로 전달되는 인수 목록과 같이 임의의 많은 수의 하위 항목이 필요합니다 . 결과적으로 이러한 언어로 작성된 코드를 나타내는 데 사용되는 AST는 알 수없는 수의 하위 항목을 빠르게 추가 할 수있을만큼 유연해야합니다.

컴파일러 검증을 지원하려면 AST를 소스 코드 형식으로 파싱 할 수 있어야합니다. 생성 된 소스 코드는 재 컴파일시 원본과 모양이 충분히 유사하고 실행이 동일해야합니다.

용법

AST는 컴파일러가 프로그램 요소와 언어의 올바른 사용을 확인 하는 의미 분석 중에 집중적으로 사용 됩니다. 컴파일러는 의미 분석 중에 AST를 기반으로 기호 테이블 도 생성 합니다. 트리를 완전히 순회하면 프로그램의 정확성을 확인할 수 있습니다.

정확성을 확인한 후 AST는 코드 생성의 기반 역할을합니다. AST는 종종 코드 생성을 위해 중간 언어 라고하는 중간 표현 (IR)을 생성하는 데 사용됩니다 .

또한보십시오

참고 문헌

  • 이 기사는 2008 년 11 월 1 일 이전에 무료 온라인 컴퓨팅 사전 에서 가져온 자료를 기반으로 하며 버전 1.3 이상의 GFDL 의 "신뢰"조건에 통합되었습니다 .

추가 읽기

  • 존스, 조엘. "추상 구문 트리 구현 관용구" (PDF) . Cite journal requires |journal= (help) (다양한 언어 군의 AST 구현 개요)
  • Neamtiu, Iulian; 포스터, Jeffrey S .; Hicks, Michael (2005 년 5 월 17 일). 추상 구문 트리 매칭을 사용한 소스 코드 진화 이해 . MSR'05. 미주리 주 세인트루이스 : ACM. CiteSeerX 10.1.1.88.5815 .
  • Baxter, Ira D .; Yahin, Andrew; Moura, Leonardo; Sant 'Anna, Marcelo; Bier, Lorraine (1998 년 11 월 16 ~ 19 일). 추상 구문 트리를 사용한 클론 감지 (PDF) . ICSM'98의 절차 . 메릴랜드 주 베데스다 : IEEE .
  • Fluri, Beat; Würsch, Michael; Pinzger, Martin; Gall, Harald C. "변경 증류 : 세분화 된 소스 코드 변경 추출을위한 트리 차이" (PDF) . Cite journal requires |journal= (help) ( PDF로 직접 링크 )
  • Würsch, Michael. Improving Abstract Syntax Tree based Source Code Change Detection (Diploma thesis).
  • Falleri, Jean-Rémy; Morandat, Floréal; Blanc, Xavier; Martinez, Matias; Monperrus, Martin. Fine-grained and Accurate Source Code Differencing (PDF). Proceedings of ASE 2014. doi:10.1145/2642937.2642982.
  • Lucas, Jason. "Thoughts on the Visual C++ Abstract Syntax Tree (AST)".

External links