하향식 구문 분석

컴퓨터 과학에서의 하향식 파싱은 해석 트리의 가장 높은 수준을 먼저 보고 형식 문법의 ^[1]다시 쓰기 규칙을 사용하여 해석 트리를 아래로 작업하는 해석 전략입니다.LL 파서는 하향식 구문 분석 전략을 사용하는 구문 분석기의 한 유형입니다.

하향식 파싱은 일반적인 파싱 트리 구조를 가정하고 알려진 기본 구조가 가설과 호환되는지 여부를 검토하여 알려지지 않은 데이터 관계를 분석하는 전략입니다.자연어와 컴퓨터 언어 분석에서 모두 발생합니다.

하향식 해석은 지정된 형식 문법 규칙의 하향식 확장을 사용하여 해석 트리를 검색함으로써 입력 스트림의 가장 왼쪽 파생 항목을 찾으려는 시도라고 볼 수 있습니다.포괄적 선택은 문법 ^[2]규칙의 모든 대안적인 오른쪽을 확장함으로써 모호함을 수용하기 위해 사용됩니다.

하향식 파싱의 간단한 실장은 왼쪽 반복식 문법에 대해서는 종료되지 않습니다.또한 백트래킹을 사용한 하향식 파싱은 애매한 CFG의 ^[3]입력 길이에 대해 기하급수적으로 시간이 복잡해질 수 있습니다.그러나 Frost, Hafiz 및 Callaghan에^[4][5] 의해 보다 정교한 하향식 파서가 생성되었으며, 이는 모호성과 다항식 시간에서의 왼쪽 재귀를 수용하고 잠재적으로 기하급수적인 수의 구문 분석 트리에 대한 다항식 크기 표현을 생성합니다.

프로그래밍 언어 응용 프로그램

컴파일러는 입력된 심볼을 생산규칙에 대응시킴으로써 프로그래밍 언어에서 내부표현에 대한 입력을 해석한다.생산 규칙은 일반적으로 Backus-Naur 형식을 사용하여 정의됩니다.LL 파서는 각 생산 규칙을 착신 심볼에 적용하여 하향식 해석을 수행하는 파서의 일종으로, 생산 규칙에서 산출된 맨 왼쪽 심볼에서 작업한 후 발견된 각 비터미널 심볼에 대해 다음 생산 규칙으로 진행합니다.이와 같이 해석은 프로덕션 규칙의 결과 측면(오른쪽)의 왼쪽에서 시작하여 왼쪽에서 비종단을 평가한 후 새로운 비종단자별로 해석 트리를 아래로 이동한 후 프로덕션 규칙의 다음 기호로 계속 진행합니다.

예를 들어 다음과 같습니다.

• ${\displaystyle A\오른쪽 화살표 aBC)$
• ${\style B\오른쪽 화살표 c\mid cd}$
• ${\displaystyle C\오른쪽 화살표 df\mid eg}$

문자열 A=acdf를 생성합니다.

A ${\displaystyle \to }$ ${\displaystyle B}$ ${\displaystyle C}${\$displaystyle$ A$\right$ 화살표 $aBC}$와 일치하고 $다음$으로 B ${\displaystyle \to }$ c${\displaystyle c}$ ${\displaystyle c}$ ${\displaystyle d}${\$displaystyle$ B$\right 화살표$ c$\mid$ cd}를 일치시킵니다$.$$그런{\displaystyle }$ 다음 C ${\displaystyle \to }$ ${\displaystyle d}$ ${\displaystyle fe}$ e$$ \ $displaystyle$C \ $rightarrow$df \ $mid$ eg$$} 이$$ 시행됩니다.예상할 수 있듯이, 어떤 언어들은 다른 언어들보다 더 모호하다.비단말기용 모든 프로덕션이 구별되는 문자열을 생성하는 모호하지 않은 언어의 경우, 한 프로덕션에 의해 생성된 문자열은 다른 프로덕션에 의해 생성된 문자열과 동일한 기호로 시작되지 않습니다.애매하지 않은 언어는 LL(1) 문법에 의해 해석될 수 있다.여기서 (1)은 파서가 한 번에 1개의 토큰을 미리 읽는 것을 나타낸다.모호한 언어를 LL 파서로 구문 분석하려면 파서가 LL(3)과 같이 두 개 이상의 기호를 미리 검색해야 합니다.

이 문제에 대한 일반적인 해결책은 시프트 리듀스 파서의 일종인 LR 파서를 사용하여 상향식 파싱을 수행하는 것입니다.

하향식 구문 분석에서 왼쪽 재귀 수용

왼쪽 재귀가 포함된 형식 문법은 약한 등가의 오른쪽 재귀 형식으로 변환되지 않는 한 순한 재귀 하강 파서로 구문 분석할 수 없습니다.그러나 최근 연구에 따르면 축소를 사용하여 보다 정교한 하향식 파서에서 좌회귀 문법(다른 모든 형태의 일반 CFG와 함께)을 수용할 수 있다.입력 길이와 현재 입력 위치에 대해 깊이 제한을 가함으로써 모호한 문법을 수용하고 계속 성장하는 직접 좌회귀 해석을 줄이는 인식 알고리즘은 2006년에 프로스트와 하피즈에 의해 기술되었다.^[6]이 알고리즘은 (이전까지 계산한 콘텍스트와 현재의 콘텍스트를 비교함으로써) 간접적인 왼쪽 재귀뿐만 아니라 다항식 시간에서의 직접적인 왼쪽 재귀도 수용하고, 프로스트에 의한 매우 애매한 문법에 대해 잠재적으로 지수적인 수의 파싱 트리의 콤팩트한 다항식 크기 표현을 생성하기 위해 완전한 파싱 알고리즘으로 확장되었다.2007년 Hafiz와 Callaghan.^[4]이후 알고리즘은 해스켈 프로그래밍 언어로 작성된 파서 조합기 세트로 구현되었습니다.이러한 새로운 조합기 세트의 구현에 대한 자세한 내용은 PADL'08에 제시된 저자의 논문에서^[5] 확인할 수 있습니다.X-SAIGA 사이트에는 알고리즘과 구현에 대한 자세한 내용이 있습니다.

또한 공통 프레픽스를 가진 스택을 '머지'함으로써 왼쪽 재귀에 대응하고 무한 재귀를 방지함으로써 각 스택의 수와 내용을 줄임으로써 파서의 시간과 공간의 복잡성을 줄이기 위해 앞서 말한 축소에 더하여 Graph-Structured Stack(GSS)을 사용할 수 있다.이것에 의해, Generalized LL parsing이라고 불리는 알고리즘이 생깁니다.여기서 GSS, 좌측 재귀 축소 및 LL(k) 파서를 사용하여 특정 CFG에 ^[7][8]상대적인 입력 문자열을 해석합니다.

하향식 파싱의 시간과 공간의 복잡성

하향식 파서가 모호한 CFG에 관해 모호한 입력을 해석하려고 할 때 가능한 모든 해석 트리를 생성하기 위해 CFG의 모든 대체를 시도하기 위해 (입력 길이에 대해) 지수적인 스텝이 필요할 수 있습니다.이 경우 최종적으로 지수적인 메모리 공간이 필요합니다.상호 재귀 함수의 집합으로 구성된 하향식 파서의 기하급수적 시간 복잡성 문제는 1991년 ^[9]Norvig에 의해 해결되었다.그의 기법은 얼리 알고리즘(1970년)의 동적 프로그래밍과 상태 집합의 사용과 Coke, Younger 및 Kasami의 CYK 알고리즘의 표와 유사하다.

핵심 아이디어는 파서를 적용한 결과를 저장하는 것입니다.p위치에j동일한 상황이 발생할 때마다 결과를 재사용할 수 있습니다.또한 Frost, Hafiz 및^[4][5] Callaghan은 다항식 시간에 CFG의 모든 형식을 수용하기 위해 다중 계산을 억제하기 위해 메모화를 사용합니다(좌재 문법의 경우 δ(n⁴), 좌재귀 문법의 경우 δ(n³)).이들의 하향식 구문 분석 알고리즘은 또한 '콤팩트 표현' 및 '로컬 모호성 그룹화'에 의한 잠재적으로 지수적인 모호성 구문 분석 트리를 위한 다항식 공간을 필요로 한다.그 콤팩트한 표현은 토미타의 콤팩트한 상향식 ^[10]해석에 필적한다.

packrat parser는 문법의 또 다른 표현인 PEG를 사용하여 우아하고 강력한 구문 분석 알고리즘을 제공합니다.표현식 구문 분석을 참조하십시오.

예

하향식 해석을 사용하는 파서는 다음과 같습니다.

• 한정절 문법^[11] 파서
• 재귀 강하 파서
• 예측 파서
• 얼리 파서

「 」를 참조해 주세요.

• 상향식 해석
• 해석
• 구문 분석식 문법

레퍼런스

외부 링크

• X-SAIGA - eXecable SpecificAtGrammars 이온