| [[이론 컴퓨터 과학|'''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"]] | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36,#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 · 디지털 물리학 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 정보 엔트로피 · 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타프로그래밍 · 람다 대수 · 유형 이론 · 프로그래밍 언어 의미론 · 어휘 분석 · 파싱 · 구문 트리(완전 구문 트리 · 추상 구문 트리) · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set) · 트리^레드-블랙 트리, B-트리, 힙, 피보나치 힙^ · 큐 · 스택 | ||||
| 수학적 최적화 | <keepall> 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| <keepall> 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| <keepall> 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 · 난수생성 | ||||
| <keepall> 대칭키 암호화 방식 | 블록 암호 알고리즘(파이스텔 네트워크 · DES · AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| <keepall> 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
1. 개요
Syntax Tree, Parse Tree정의된 형식 문법을 따라 주어진 형식 언어에 대해 얻어진 생성 규칙의 트리 형태의 도표 또는 자료구조. 주로 구문 분석의 결과물로써 주어진다.
parse tree라고도 불리는데, 이 경우 보통 CST를 말한다. 반면 syntax tree라고만 쓸 경우 AST를 뜻하는 경우가 더 많다.
2. 완전 구문 트리
Concrete Syntax Tree, CST주어진 형식 언어를 유도(derive)하기 위한 일련의 생성 규칙(production rule)을 전부 나열한 트리로, 각각의 노드가 해당 언어의 생성 규칙에 하나씩 대응된다. 이때 중간(interior) 노드는 non-terminal symbol을, 잎 노드는 terminal symbol을 표현한다.
소스의 순서를 보존하기 때문에 왼쪽부터 오른쪽 끝까지 리프 노드의 terminal symbol들만 순서대로 탐색하면 소스를 재구성할 수 있다. 각각의 subtree 또한 소스 내의 특정 영역을 가리키게 되기 때문에 이를 순회해도 원본 소스상의 연속된 영역을 얻을 수 있다. 각 subtree가 가지는 영역이 연속적이라는 성질을 이용해 각각의 리프 노드에 terminal symbol 대신 원본 소스상의 인덱스 위치만 저장하면 임의의 subtree의 양쪽 끝 리프 노드의 인덱스를 합쳐서 span을 [math(\mathcal O(h))]만에 쉽게 만들 수 있는데, 보통 이걸 이용해서 컴파일러 에러 메세지나 diagnostics, 리팩토링 등 다양한 기능을 구현한다.
주어진 형식 문법이 unambiguous하다면 해당 문법에서 유도되는 언어의 모든 문장은 단 하나의 완전 구문 트리를 가진다. 또한 상술했듯이 완전 구문 트리에서 소스 언어로 항상 되돌릴 수도 있기 때문에 일반적으로 형식 언어 [math(L(G))]에서 완전 구문 트리의 집합 [math({\rm CST}_{L(G)})]로 가는 일대일 대응 함수 [math(f)]가 존재한다. 이 함수의 정체가 바로 파서이다.
3. 추상 구문 트리
Abstract Syntax Tree, AST완전 구문 트리와 같은 semantic을 보존하는 트리로, 언어의 의미(semantic)을 결정하는 데 영향을 미치지 않는 요소들을 제거하거나 적절히 변형하여 추상화시킨 트리를 말한다.
가령 언어의 해석에 아무 영향을 미치지 않는 주석, 공백 등을 제거하는 것이 대표적이다. 또한 각각의 문법에서 해석에 영향을 미치는 변수만 남기고 연산자나 키워드 등을 노드 타입에 포함시키기도 한다. 가령
| [math( \displaystyle \begin{array}{ll} \textbf{If} &\to \texttt{if} \; \texttt ( \; \textbf{Expr} \; \texttt ) \; \texttt \{ \; \textbf{Stmts} \; \texttt \} \\ \textbf{Expr} &\to \textbf{Gt} \mid \dots \\ \textbf{Gt} &\to \textbf{Expr} \; \texttt > \; \textbf{Expr} \\ &\vdots \\ \end{array} )] |
위와 같은 형태의 생성문법이 주어졌을 때,
| [math( \displaystyle \left( \texttt{if}, \texttt (, \left( \left( \right)_\textbf{Expr},\texttt i, \texttt >, \texttt 2 \right)_\textbf{Gt} \texttt ), \texttt \{, \left( \texttt{return} \right)_\textbf{Stmts},\texttt \} \right)_\textbf{If} )] |
과 같이 파싱된 조건문을 나타내는 노드를
| [math( \displaystyle \left( \left( \left( \right)_\textbf{Expr},\texttt i, \texttt 2 \right)_{\textbf{Gt}'} \left( \texttt{return} \right)_\textbf{Stmts}\right)_{\textbf{If}'} )] |
과 같이 단순화된 노드로 바꾸는 식이다. 이때 [math(\textbf{If}')]과 [math(\textbf{Gt}')]는 각각 [math(\textbf{If})]와 [math(\textbf{Gt})]를 추상화하여 해석하는 데 필요한 요소만 남긴 노드라 볼 수 있다. 대개 CST의 경우 각 노드가 일반 n진 트리로 구현되는 반면, AST의 경우 각각의 노드마다 서로 구분되는 자료형을 할당받도록 구현되는 편이다.
각각의 노드 수준에서의 추상화만 수행하는 것뿐 아니라 여러 노드에 걸쳐 표현되는 복잡한 문법을 더 분석하기 좋게 추상화하기도 한다. 가령 C 언어의 포인터 문법 파싱 추상화 등이 있다.
4. 차이
AST와 CST의 가장 큰 차이점은 가역성이다. AST는 언어를 실행하는 데 필요한 최소한의 의미만을 남기거나 연산하기 쉽도록 다양한 최적화를 거친 후의 결과인 반면, CST는 언어 실행에 무관한 화이트스페이스나 주석 등의 정보도 생성 문법에서 명시되었다면 모조리 포함하고 있다. 즉, 소스를 파싱한 AST에서 소스로 가는 역함수가 항상 존재하는 것은 아니며, 따라서 적절한 변환 후 소스를 재구성할 필요가 있는 코드 포매터, LSP 등의 경우 CST를 주로 사용한다. 반대로 언어의 추상적 구조와 의미(semantic)를 분석하고 실행에 필요한 데이터를 빠르게 조회해야 하는 컴파일러, 타입 체커 등의 경우는 주로 AST를 입력으로 사용하게 된다.파서 제너레이터는 CST를 내보내는 것이 일반적이지만, 사실 현대의 파서 제너레이터 기술들은 대부분 바인딩될 언어의 사용자 정의 타입과 내부 문법을 매핑하는 metasyntax DSL을 지원한다. 이 경우 CST를 별도로 생성하지 않거나 파싱 과정에서 내부적으로만 사용하고 AST를 바로 반환하게 된다. 파서를 손으로 짜는 경우 또한 대부분 적당한 heuristic 구현으로 모든 노드를 일일히 파싱해서 트리로 만드는 것을 건너뛰고 바로 직관적인 AST를 유도해 낼 수 있다. 때문에 대부분의 실용적인 구현에서는 CST에서 AST로 변환하는 정석적인 과정 없이 바로 건너뛰어도 충분하다.