상향식 해석
Bottom-up parsing컴퓨터 과학에서 파싱은 선형 입력 텍스트의 문법 구조를 의미 파악의 첫 단계로서 드러냅니다.상향식 구문 분석에서는 중간 수준 구조 전에 텍스트의 가장 낮은 수준의 작은 세부 정보를 먼저 인식하고 가장 높은 수준의 전체 구조를 [1]계속 유지합니다.
상향식 대 하향식
상향식 이름은 파싱 트리의 개념에서 유래했습니다.파싱 트리는 가장 상세한 부분이 거꾸로 된 트리의 맨 아래쪽에 있고 트리의 맨 위 또는 "루트"에 단일 유닛이 입력 스트림 전체를 나타낼 때까지 그것들로 구성된 더 큰 구조가 연속적으로 상위 계층에 있습니다.상향식 해석은 왼쪽 하단부터 시작하여 트리를 검색 및 처리하여 점차적으로 위쪽 [2]및 오른쪽으로 이동합니다.파서는 실제 데이터 트리를 생성하지 않고 구조 계층의 낮은 수준, 중간 수준 및 가장 높은 수준에서 작동할 수 있습니다. 그러면 트리는 파서의 액션에 암묵적으로만 포함됩니다.상향식 파싱은 조합된 구성이 무엇인지 커밋하기 전에 일부 구성의 모든 부분을 스캔하고 구문 분석할 때까지 끈기 있게 기다립니다.
이와 반대되는 것은 하향식 구문 분석입니다. 이 구문 분석에서는 중간 수준의 부품을 처리하기 전에 입력의 전체 구조가 먼저 결정(또는 추측)되고 모든 하위 수준의 세부 정보는 마지막에 완료됩니다.하향식 파서는 위에서 시작하여 계층 트리를 검출 및 처리하며, 먼저 아래쪽으로, 그 후 오른쪽으로 증분적으로 작용한다.하향식 파싱은 그 구성의 왼쪽 끝 심볼만 스캔하고 그 부분은 아직 구문 분석하지 않은 훨씬 더 이른 단계에서 구성 요소가 무엇인지 열심히 판단합니다.왼쪽 모서리 해석은 각 서브트리의 왼쪽 가장자리를 따라 상향식으로 동작하고 나머지 해석 트리에서 하향식으로 동작하는 하이브리드 방식입니다.
언어 문법이 왼쪽 끝의 같은 기호로 시작하지만 끝이 다른 여러 규칙을 가지고 있는 경우, 그 문법은 결정론적 상향식 해석으로 효율적으로 처리될 수 있지만 추측과 역추적 없이는 하향식으로 처리될 수 없습니다.따라서 실제로 보텀업 파서는 결정론적 하향식 파서보다 컴퓨터 언어 문법의 범위를 다소 더 크게 다루고 있습니다.
상향식 해석은 백트래킹에 의해 수행될 수 있습니다.단, 보다 일반적으로 상향식 해석은 LALR 파서와 같은 시프트 리듀스 파서에 의해 이루어집니다.
예
상향식 해석을 사용하는 파서는 다음과 같습니다.
- 우선 순위 분석기
- Bounded-Context 파서(Bounded-Context Parser)
- LR 파서(왼쪽에서 오른쪽으로, 가장 오른쪽에서 역방향 파생)
- CYK 파서(코크-)영-카사미)
- 재귀 상승 파서
- 시프트 리듀스 파서
레퍼런스
- ^ Arvind Kumar Bansal (14 December 2013). Introduction to Programming Languages. CRC Press. ISBN 978-1-4665-6514-2.
- ^ 컴파일러: Principle, Technologies, and Tools (제2판), Alfred Aho, Monica Lam, Ravi Sethi 및 Jeffrey Ulman, 프렌티스 홀 2006.
- ^ Dick Grune; Ceriel J.H. Jacobs (29 October 2007). Parsing Techniques: A Practical Guide. Springer Science & Business Media. ISBN 978-0-387-68954-8.
