추상 구문 트리

Abstract syntax tree
언어학에 사용되는 트리는 해석 트리를 참조하십시오.
유클리드 알고리즘의 다음 코드에 대한 추상 구문 트리:
하는 동안에 b ≠ 0:     한다면 a > b:         a := a - b     또 다른:         b := b - a 돌아가다 a

컴퓨터 과학에서 추상 구문 트리(AST)는 정형 언어로 작성된 텍스트(종종 소스 코드)의 추상 구문 구조를 나타내는 트리입니다.트리의 각 노드는 텍스트에서 발생하는 구성을 나타냅니다.

구문은 실제 구문에 나타나는 모든 세부사항을 나타내는 것이 아니라 구조 또는 내용 관련 세부사항만을 나타낸다는 점에서 "추상"입니다.예를 들어 그룹화 괄호는 트리 구조에 암묵적으로 포함되어 있으므로 별도의 노드로 나타낼 필요가 없습니다.마찬가지로 if-condition-then 문과 같은 구문 구성은 3개의 분기를 가진 단일 노드를 통해 나타낼 수 있습니다.

이는 추상 구문 트리와 구체 구문 트리(기존에는 구문 분석 트리)를 구분합니다.해석 트리는 보통 소스 코드 변환 및 컴파일 프로세스 중에 파서에 의해 구축됩니다.일단 구축되면, 상황 분석과 같은 후속 처리를 통해 추가 정보가 AST에 추가됩니다.

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

컴파일러 응용 프로그램

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

동기

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

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

AST는 프로그래밍 언어의 고유한 특성과 문서화를 위해 필요합니다.언어는 천성이 애매한 경우가 많다.이러한 애매함을 피하기 위해 프로그래밍 언어는 종종 Context-Free Grammar(CFG; 컨텍스트프리 문법)로 지정됩니다.그러나 CFG는 표현할 수 없지만 언어의 일부이며 사양에 기재되어 있는 프로그래밍 언어의 측면이 종종 있습니다.이것들은 타당성과 동작을 판단하기 위해 컨텍스트가 필요한 세부사항입니다.예를 들어 언어에서 새로운 유형을 선언할 수 있는 경우 CFG는 이러한 유형의 이름이나 사용 방법을 예측할 수 없습니다.언어에 미리 정의된 유형 집합이 있더라도 적절한 사용을 수행하려면 일반적으로 컨텍스트가 필요합니다.또 다른 예로는 오리타입을 들 수 있는데, 이 경우 요소의 유형은 컨텍스트에 따라 변경될 수 있습니다.연산자 오버로드는 올바른 사용법과 최종 함수가 상황에 따라 달라지는 또 다른 경우입니다.

설계.

AST의 설계는 컴파일러의 설계 및 예상되는 기능과 밀접하게 관련되어 있습니다.

핵심 요건은 다음과 같습니다.

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

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

일부 연산에서는 항상 두 개의 요소가 필요합니다. 예를 들어 두 개의 추가 항이 있습니다.그러나 명령 셸에서 프로그램에 전달되는 인수 목록과 같이 일부 언어 구성에는 임의로 많은 수의 하위 항목이 필요합니다.그 결과, 그러한 언어로 작성된 코드를 나타내기 위해 사용되는 AST는 미지의 수의 어린이를 신속하게 추가할 수 있도록 충분히 유연해야 한다.

컴파일러 검증을 지원하려면 AST를 소스 코드 형식으로 해석 해제할 수 있어야 합니다.생성된 소스 코드는 재컴파일 시 원본과 외관이 완전히 유사하고 실행이 동일해야 합니다.AST는 의미 분석 중에 집중적으로 사용되며, 여기서 컴파일러는 프로그램 요소 및 언어의 올바른 사용을 확인합니다.또한 컴파일러는 의미 분석 중에 AST를 기반으로 심볼 테이블을 생성합니다.트리를 완전히 통과하면 프로그램의 정확성을 확인할 수 있습니다.

AST가 올바른지 확인한 후 코드 생성의 기반이 됩니다.AST는 코드 생성을 위한 중간 표현(IR)을 생성하기 위해 종종 사용됩니다.


기타 사용법

AST의 차이점

AST 차이점 분석 또는 짧은 트리 차이점 분석의 경우, 두 AST [1]사이의 차이점 목록을 계산하는 것으로 구성됩니다.이 차이점 목록은 일반적으로 편집 스크립트라고 합니다.편집 스크립트는 코드의 AST를 직접 참조합니다.예를 들어 편집 액션은 함수를 나타내는 새로운 AST 노드를 추가할 수 있다.우수한 AST 편집 스크립트를 계산하는 문제는 이동 작업 처리와 수천 개의 [2]노드가 있는 세분화된 AST로 확장해야 하는 두 가지 주요 과제가 있기 때문에 어렵습니다.

구조화된 결합

적절한 AST 차이점을 통해 AST를 버전 및 브랜치 병합에 사용할 수 있습니다. 이를 구조화 병합이라고 합니다.장점은 행과 [3]포맷으로 인한 스플리어스 경합을 피할 수 있다는 것입니다.

클론 검출

AST는 코드 클론 [4]탐지를 수행하기 위한 강력한 추상화입니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Fluri, Beat; Wursch, Michael; PInzger, Martin; Gall, Harald (2007). "Change Distilling:Tree Differencing for Fine-Grained Source Code Change Extraction". IEEE Transactions on Software Engineering. 33 (11): 725–743. doi:10.1109/tse.2007.70731. ISSN 0098-5589. S2CID 13659557.
  2. ^ Falleri, Jean-Rémy; Morandat, Floréal; Blanc, Xavier; Martinez, Matias; Monperrus, Martin (2014-09-15). "Fine-grained and accurate source code differencing". Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering. Vasteras Sweden: ACM: 313–324. doi:10.1145/2642937.2642982. ISBN 978-1-4503-3013-8. S2CID 218737160.
  3. ^ Larsen, Simon; Falleri, Jean-Remy; Baudry, Benoit; Monperrus, Martin (2022). "Spork: Structured Merge for Java with Formatting Preservation". IEEE Transactions on Software Engineering: 1. arXiv:2202.05329. doi:10.1109/TSE.2022.3143766. ISSN 0098-5589. S2CID 246823829.
  4. ^ Koschke, Rainer; Falke, Raimar; Frenzel, Pierre (2006). "Clone Detection Using Abstract Syntax Suffix Trees". 2006 13th Working Conference on Reverse Engineering. IEEE: 253–262. doi:10.1109/wcre.2006.18. ISBN 0-7695-2719-1. S2CID 6985484.

추가 정보

외부 링크

Wikimedia Commons에는 Abstract 구문 트리와 관련된 미디어가 있습니다.