하향식 구문 분석

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 프로그래밍 언어 응용
- 2.1. 예제
3. 좌재귀 처리
4. 시간 및 공간 복잡도
5. 파서 예시
참조

1. 개요

하향식 구문 분석은 프로그래밍 언어 소스 코드를 내부 표현으로 변환하는 구문 분석 방법으로, 입력된 문자열이 문맥 자유 문법의 최상위 생성 규칙에 일치한다고 가정하고 시작한다. LL(1) 문법과 같이, 특정 조건 하에 효율적인 구문 분석이 가능하지만, 좌측 재귀를 포함하는 문법의 경우 추가적인 처리가 필요하다. 좌측 재귀는 우재귀 형태로 변환하거나, 단축 기법을 활용하여 처리할 수 있으며, 일반화된 LL 파싱 알고리즘은 그래프 구조 스택(GSS)을 사용하여 좌측 재귀를 수용한다. 하향식 구문 분석기는 모호한 문법에 대해 지수적인 시간 및 공간 복잡도를 가질 수 있지만, 메모이제이션을 통해 다항 시간 내에 모든 형태의 문맥 자유 문법을 처리할 수 있다. 다양한 하향식 구문 분석기, 예를 들어 결정 절 문법 파서, 재귀 하향 파서, 예측 파서, 이얼리 파서 등이 존재한다.

더 읽어볼만한 페이지

파싱 알고리즘 - 재귀 하향 파서
재귀 하향 파서는 백트래킹 없이 LL(k) 문법 클래스에서 선형 시간에 동작하며 각 비종단 기호에 대한 프로시저를 가지는 예측 파서이다.
파싱 알고리즘 - CYK 알고리즘
CYK 알고리즘은 촘스키 정규 형식으로 변환된 문맥 자유 문법으로 표현된 언어에 특정 문자열이 속하는지 판별하는 파싱 알고리즘으로, 동적 계획법의 예시이며 자연어 처리 분야에서 문법 구조 분석 및 최적 해석을 찾는데 활용될 수 있다.

하향식 구문 분석
개요
종류	구문 분석
방식	하향식 접근법
설명	상위 레벨의 구문 구조에서 시작하여 입력 문자열과 일치하도록 하위 레벨 규칙을 적용하는 구문 분석 전략
특징	주어진 형식 문법을 갖는 입력 문자열의 가장 좌측 유도(leftmost derivation)를 찾기 위해 시도 LL 파서에서 사용 (Left-to-right, Leftmost derivation)
장점	구현 용이성
단점	백트래킹 필요 좌측 재귀에 취약
파서 종류
재귀 하강 파서 (Recursive descent parser)	각 규칙에 대한 프로시저를 사용하여 구현
LL 파서	예측 파싱 테이블 사용 좌측 재귀 제거 필요 백트래킹 없는 파싱 가능

2. 프로그래밍 언어 응용

컴파일러나 인터프리터는 프로그래밍 언어로 작성된 소스 코드를 구문 분석기를 통해 내부 표현으로 변환한다. 이때 바커스-나우르 표기법(BNF)을 사용하여 생성 규칙을 정의하는 것이 일반적이다.

하향식 구문 분석은 입력 문자열이 문맥 자유 문법(Context-Free Grammar)의 최상위 생성 규칙, 즉 시작 기호에 부합한다고 가정하고 분석을 시작한다. 생성 규칙을 적용할 때는 좌측 기호부터 일치시키며, 비단말 기호가 나타나면 해당 비단말 기호에 대한 생성 규칙을 재귀적으로 적용해 나간다.

이러한 하향식 구문 분석의 일반적인 해결책으로는 LR 파서가 있다. LR 파서는 시프트-리듀스 파서의 한 유형이다.^[1]

2. 1. 예제

컴파일러는 프로그래밍 언어로부터 입력을 받아 들어오는 기호를 생성 규칙에 일치시켜 내부 표현으로 구문 분석한다. 생성 규칙은 일반적으로 바커스-나우르 표기법을 사용하여 정의된다.

예를 들어, 다음과 같은 생성 규칙이 있다고 가정한다.

$A \rightarrow aBC$
$B \rightarrow c \mid cd$
$C \rightarrow df \mid eg$

''A''=''acdf'' 문자열을 생성하기 위해,

A \rightarrow aBC

와 일치하고 다음으로

B \rightarrow c \mid cd

와 일치시키려고 시도한다. 그런 다음

C \rightarrow df \mid eg

가 시도된다.

일부 언어는 다른 언어보다 더 모호하다. 비모호한 언어의 경우, 비단말 기호에 대한 모든 생성 규칙이 서로 다른 문자열을 생성하며, 하나의 생성 규칙에 의해 생성된 문자열은 다른 생성 규칙에 의해 생성된 문자열과 동일한 기호로 시작하지 않는다. 비모호한 언어는 LL(1) 문법으로 구문 분석될 수 있으며, 여기서 (1)은 파서가 한 번에 한 토큰을 미리 읽는다는 것을 의미한다. LL 파서로 구문 분석할 모호한 언어의 경우, 파서는 1개 이상의 기호, 예를 들어 LL(3)을 미리 읽기(lookahead)해야 한다.

3. 좌재귀 처리

형식 문법에서 좌측 재귀를 포함하는 문법은 단순한 재귀 하향 파서로 파싱할 수 없다. 이 경우, 약하게 동등한 우측 재귀 형식으로 변환해야 한다. 그러나 최근 연구에서는 단축(Curtailment)을 사용하여 좌측 재귀 문법(일반적인 모든 형태의 문맥 자유 문법)을 보다 정교한 상향식 파서에서 수용할 수 있음을 보여준다.^[6]

Frost와 Hafiz는 2006년에 모호한 문법을 수용하고 입력 길이 및 현재 입력 위치에 따라 깊이 제한을 적용하여 직접 좌측 재귀 파싱을 단축하는 인식기 알고리즘을 설명했다.^[6] 2007년에는 이 알고리즘을 확장하여 다항식 시간 내에 간접 및 직접 좌측 재귀를 모두 처리하고, 매우 모호한 문법에 대해 압축된 다항식 크기 표현으로 파스 트리를 생성하는 파싱 알고리즘을 제시했다.^[4] 이 알고리즘은 이후 Haskell 프로그래밍 언어로 작성된 파서 콤비네이터로 구현되었다.^[5]

그래프 구조 스택 (GSS)을 사용하여 공통 접두사를 가진 스택을 '병합'하고 무한 재귀를 방지함으로써 좌측 재귀를 처리할 수도 있다. 이는 일반화된 LL 파싱 알고리즘으로 이어진다. 이 알고리즘은 GSS, 좌측 재귀 단축 및 LL(k) 파서를 사용하여 주어진 문맥 자유 문법에 상대적인 입력 문자열을 파싱한다.^[7]^[8]

4. 시간 및 공간 복잡도

하향식 구문 분석기가 모호한 문법에 대해 모호한 입력을 구문 분석할 때, 모든 가능한 구문 분석 트리를 생성하기 위해 모든 대안을 시도해야 하므로 입력 길이에 대해 지수적인 시간이 걸릴 수 있으며, 지수적인 메모리 공간이 필요할 수 있다. 1991년 노르빅은 얼리 알고리즘의 동적 프로그래밍과 상태 집합, 그리고 CYK 알고리즘의 표를 사용하는 것과 유사한 기술을 사용하여 이 문제를 해결했다.^[9]

이 기술의 핵심 아이디어는 파서 `p`를 위치 `j`에 적용한 결과를 저장하고 동일한 상황이 발생할 때마다 결과를 재사용하는 것이다. Frost, Hafiz 및 Callaghan은 메모이제이션을 사용하여 불필요한 계산을 줄이고 다항식 시간 내에(좌측 재귀 문법의 경우 Θ(n⁴), 비 좌측 재귀 문법의 경우 Θ(n³)) 모든 형태의 문맥 자유 문법(CFG)을 처리하는 하향식 구문 분석 알고리즘을 개발했다.^[4]^[5] 이 알고리즘은 또한 '압축 표현' 및 '지역적 모호성 그룹화'를 통해 잠재적으로 지수적인 모호한 구문 분석 트리에 대해 다항식 공간을 필요로 한다. 이 압축 표현은 토미타의 상향식 구문 분석의 압축 표현과 유사하다.^[10]

5. 파서 예시

재귀 하향 파서
예측 파서
얼리 파서^[11]

5. 1. 결정 절 문법 파서

결정 절 문법(DCG) 파서^[11]는 논리 프로그래밍 언어에서 사용되는 구문 분석 기법이다.

5. 2. 재귀 하향 파서

재귀 하향 파서는 각 비단말 기호에 대해 재귀적인 함수 호출을 사용하여 구문 분석을 수행하는 파서이다.^[11] 하향식 구문 분석에서는, 입력 전체가 문맥 자유 문법의 최상위 생성 규칙의 좌변의 비단말 기호에 일치할 것이라고 먼저 가정하고 구문 분석을 시작한다. 그리고 입력 문자열에 생성 규칙을 적용해 갈 때, 좌단 기호부터 매칭시키고, 비단말 기호가 나타날 때마다 추가로 생성 규칙을 적용해 간다.

예를 들어, 다음과 같은 생성 규칙이 있다고 가정한다.

$A \rightarrow aBC$
$B \rightarrow c|cd$
$C \rightarrow df|eg$

A에서 시작하는 경우, 처음에

A \rightarrow aBC

에 매치하고, 다음에 (그 우변을 왼쪽부터 평가해 가는 과정에서)

B \rightarrow c|cd

에 매치한다. 그 후,

C \rightarrow df|eg

가 적용된다.

어떤 비단말 기호에 관한 생성 규칙의 우변의 기호열군에서, 기호열의 선두에 나타나는 단말 기호에 의해 유일한 기호열을 결정 가능하다면, LL(1) 문법으로 구문 분석할 수 있다. 여기서 (1)은 구문 분석기가 미리 읽어볼 필요가 있는 토큰의 수를 나타낸다. 단말 기호 하나로 결정할 수 없는 언어에서는, LL법을 사용하여 구문 분석하려면 하나 이상의 미리 읽기가 필요하게 된다.

5. 3. 예측 파서

예측 파서는 미리 읽기(lookahead)를 통해 다음에 적용할 생성 규칙을 예측하는 하향식 파서이다.^[11] LL(1) 문법은 예측 파서로 구문 분석할 수 있는 문법의 한 종류이며, 여기서 (1)은 미리 읽어야 할 토큰의 수를 의미한다. 단말 기호 하나로 생성 규칙을 결정할 수 없는 언어에서는 LL 파싱을 위해 하나 이상의 미리 읽기가 필요하다.

5. 4. 이얼리 파서

이얼리 파서는 동적 계획법을 사용하여 모든 가능한 구문 분석 트리를 저장하고, 중복 계산을 피하는 하향식 파서이다.^[11]

참조

_[1] 서적 Parsing Techniques: A Practical Guide https://books.google[...] Springer Science & Business Media 2007-10-29
_[2] 서적 Compilers, principles, techniques, and tools https://archive.org/[...] Addison-Wesley Pub. Co.
_[3] 서적 The Theory of Parsing, Translation, and Compiling (Volume 1: Parsing.) https://archive.org/[...] Prentice-Hall
_[4] 간행물 Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars https://aclanthology[...] 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE 2007-06
_[5] 간행물 Parser Combinators for Ambiguous Left-Recursive Grammars http://scholar.uwind[...] 10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN 2008-01
_[6] 간행물 A New Top-Down Parsing Algorithm to Accommodate Ambiguity and Left Recursion in Polynomial Time http://richard.myweb[...] ACM SIGPLAN Notices 2006
_[7] 웹사이트 GLL Parsing http://dotat.at/tmp/[...] University of London
_[8] 웹사이트 Structuring the GLL parsing algorithm for performance https://pure.royalho[...] University of London
_[9] 간행물 Techniques for automatic memoisation with applications to context-free parsing https://aclanthology[...] Journal - Computational Linguistics 1991
_[10] 서적 Efficient Parsing for Natural Language https://books.google[...] Kluwer, Boston, MA 1985
_[11] 간행물 Definite clause grammars for language analysis—a survey of the formalism and a comparison with augmented transition networks http://cgi.di.uoa.gr[...] Artificial intelligence 1980

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com