재귀 강하 파서
Recursive descent parser![]() |
컴퓨터 과학에서, 재귀 강하 파서는 상호 재귀적 프로시저(또는 비재귀적 등가물) 집합에서 만들어진 일종의 하향식 파서이며, 이러한 프로시저는 각 프로시저가 문법의 비말단 중 하나를 구현한다.따라서 결과 프로그램의 구조는 그것이 인식하는 [1]문법의 구조와 밀접하게 일치한다.
예측 파서는 [2]역추적이 필요하지 않은 재귀적 하강 파서입니다.예측 해석은 LL(k) 문법의 클래스에 대해서만 가능합니다.LLL(k) 문법은 재귀 강하 파서가 입력의 다음 k개의 토큰만 검사하여 사용할 생산을 결정할 수 있는 몇 가지 양의 정수 k가 존재하는 컨텍스트 프리 문법입니다.따라서 LL(k) 문법은 왼쪽 재귀가 포함된 모든 문법과 마찬가지로 모든 애매한 문법을 제외합니다.문맥이 없는 문법은 왼쪽 재귀가 없는 동등한 문법으로 변환할 수 있지만 왼쪽 재귀가 제거된다고 해서 항상 LL(k) 문법이 생성되는 것은 아닙니다.예측 파서는 선형 시간으로 실행됩니다.
역추적 재귀 하강은 각 생산을 차례로 시도하여 사용할 생산을 결정하는 기술입니다.백트래킹을 사용한 재귀 강하 기능은 LL(k) 문법에 한정되지 않지만 문법이 LL(k)이 아니면 종료되지 않습니다.파서가 종료되더라도 백트랙킹과 함께 재귀 강하를 사용하는 파서는 지수 시간이 필요할 수 있습니다.
예측 파서는 널리 사용되며 파서를 손으로 쓰는 경우 자주 선택되지만 프로그래머들은 종종 파서 [citation needed]생성기에 의해 생성된 테이블 기반 파서를 LL(k) 언어 또는 LALR 또는 LR과 같은 대체 파서를 사용하는 것을 선호합니다.이것은 특히 문법이 LL(k) 형식이 아닌 경우에 해당하며, 예측 해석에 적합하도록 문법을 LL로 변환해야 하기 때문입니다.ANTLR과 같은 도구를 사용하여 예측 파서를 자동으로 생성할 수도 있습니다.
예측 파서는 초기 상태와 최종 상태 사이의 가장자리가 생산 [3]규칙 우측의 기호(종단 및 비종단)에 의해 라벨링되는 각 비종단 심볼에 대한 전이도를 사용하여 나타낼 수 있다.
파서의 예
다음 EBNF 유사 문법(알고리즘 + 데이터 구조 = 프로그램에서 Niklaus Worth의 PL/0 프로그래밍 언어의 경우)은 LL(1) 형식입니다.
프로그램.= 블록"." . 블록= ["항상" 식별하다"=" 숫자{"," 식별하다"=" 숫자} ";"] ["var" 식별하다{"," 식별하다} ";"] {"실패" 식별하다";" 블록";"} 진술. 진술= 식별하다":=" 표현 "콜" 식별하다 "실패" 진술{";" 진술} '종료' "만약" 조건."그럼" 진술 '중' 조건.'도' 진술. 조건.= '홀수' 표현 표현("=" "#" "<" "<=" ">" ">=") 표현. 표현= ["+" "-"] 용어{("+" "-") 용어} . 용어= 인자{("*" "/") 인자} . 인자= 식별하다 번호 "(" 표현")" .
단말기는 따옴표로 나타냅니다.각 비터미널은 문법의 규칙에 의해 정의됩니다.단, id 및 number는 암묵적으로 정의된 것으로 간주됩니다.
C의 실장
다음은 C에서 상기 언어에 대한 재귀 강하 파서의 구현입니다.파서는 소스 코드를 읽고 코드가 해석되지 않으면 오류 메시지와 함께 종료되며 코드가 올바르게 해석되면 자동으로 종료됩니다.
아래의 예측 파서가 위의 문법을 얼마나 밀접하게 반영하는지 주목하십시오.문법의 각 비말단에는 순서가 있습니다.해석은 최종 비터미널이 처리될 때까지 하향식으로 이루어집니다.프로그램 조각은 입력의 현재 기호를 포함하는 전역 변수인 sym과 호출 시 sym을 업데이트하는 함수 nextsym에 따라 달라집니다.
단순화를 위해 다음 시스템 및 오류 기능의 구현은 생략됩니다.
유형화된 열거하다 {식별하다, 번호, 모니터, rparen, 시대, 베다, 플러스, 마이너스, eql, 니크, lss, 레크, gtr, geq, 콜심, 시작, 세미콜론, 종말, 시스템, 동작하다, 된다, 시스템, 시스템, 컨시스, 콤마, 시스템, 시스템, 기간, 확률} 기호.; 기호. 심볼; 무효 다음 시스템(무효); 무효 에러(컨스턴트 차 메시지[]); 인트 받아들이다(기호. s) { 한다면 (심볼 == s) { 다음 시스템(); 돌아가다 1; } 돌아가다 0; } 인트 기대하다(기호. s) { 한다면 (받아들이다(s)) 돌아가다 1; 에러("예상치 않은 기호: 예기치 않은 기호); 돌아가다 0; } 무효 인자(무효) { 한다면 (받아들이다(식별하다)) { ; } 또 다른 한다면 (받아들이다(번호)) { ; } 또 다른 한다면 (받아들이다(모니터)) { 표현(); 기대하다(rparen); } 또 다른 { 에러("요인: 구문 오류"); 다음 시스템(); } } 무효 용어(무효) { 인자(); 하는 동안에 (심볼 == 시대 심볼 == 베다) { 다음 시스템(); 인자(); } } 무효 표현(무효) { 한다면 (심볼 == 플러스 심볼 == 마이너스) 다음 시스템(); 용어(); 하는 동안에 (심볼 == 플러스 심볼 == 마이너스) { 다음 시스템(); 용어(); } } 무효 조건.(무효) { 한다면 (받아들이다(확률)) { 표현(); } 또 다른 { 표현(); 한다면 (심볼 == eql 심볼 == 니크 심볼 == lss 심볼 == 레크 심볼 == gtr 심볼 == geq) { 다음 시스템(); 표현(); } 또 다른 { 에러("조건: 잘못된 연산자"); 다음 시스템(); } } } 무효 진술(무효) { 한다면 (받아들이다(식별하다)) { 기대하다(된다); 표현(); } 또 다른 한다면 (받아들이다(콜심)) { 기대하다(식별하다); } 또 다른 한다면 (받아들이다(시작)) { 하다 { 진술(); } 하는 동안에 (받아들이다(세미콜론)); 기대하다(종말); } 또 다른 한다면 (받아들이다(시스템)) { 조건.(); 기대하다(시스템); 진술(); } 또 다른 한다면 (받아들이다(동작하다)) { 조건.(); 기대하다(시스템); 진술(); } 또 다른 { 에러("문: 구문 오류"); 다음 시스템(); } } 무효 블록(무효) { 한다면 (받아들이다(컨시스)) { 하다 { 기대하다(식별하다); 기대하다(eql); 기대하다(번호); } 하는 동안에 (받아들이다(콤마)); 기대하다(세미콜론); } 한다면 (받아들이다(시스템)) { 하다 { 기대하다(식별하다); } 하는 동안에 (받아들이다(콤마)); 기대하다(세미콜론); } 하는 동안에 (받아들이다(시스템)) { 기대하다(식별하다); 기대하다(세미콜론); 블록(); 기대하다(세미콜론); } 진술(); } 무효 프로그램.(무효) { 다음 시스템(); 블록(); 기대하다(기간); }
예
일부 재귀 강하 파서 생성기:
- TMG – 1960년대와 1970년대 초반에 사용된 초기 컴파일러/컴파일러
- 자바CC
- 코코/R
- 앤티엘
- Spirit 파서 프레임워크 – 사전 컴파일 단계가 필요 없는 C++ 재귀 강하 파서 생성기 프레임워크
- parboiled(Java) – Java용 재귀 강하 PEG 구문 분석 라이브러리
「 」를 참조해 주세요.
- 파서 콤비네이터 – 재귀 강하 파서 설계를 인수화하는 방법인 조합 파싱에서 사용되는 고차 함수
- 구문 분석 식 문법 – 재귀 강하 문법을 나타내는 또 다른 형식
- 재귀 상승 파서
- 테일 재귀 파서– 재귀 강하 파서의 변형
레퍼런스
- ^ Burge, W.H. (1975). Recursive Programming Techniques. ISBN 0-201-14450-6.
- ^ Watson, Des (22 March 2017). A Practical Approach to Compiler Construction. Springer. ISBN 978-3-319-52789-5.
- ^ Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey (1986). Compilers: Principles, Techniques and Tools (first ed.). Addison Wesley. p. 183.
일반 참고 자료
- 컴파일러: 원칙, 기술, 도구, 초판, 알프레드 V Aho, Ravi Sethi 및 Jeffrey D Ulman, 특히 섹션 4.4.
- Java에서의 Modern Compiler Implementation, Second Edition, Andrew Appel, 2002, ISBN 0-521-82060-X.
- 재귀 프로그래밍 기법, W.H. Burge, 1975, ISBN 0-201-14450-6
- C, Charles N Fischer 및 Richard J LeBlanc, 1991년 ISBN 0-8053-2166-7과 함께 컴파일러 제작.
- C# 및 Java와의 컴파일, Pat Terry, 2005, ISBN 0-321-2660-X, 624
- 알고리즘 + 데이터 구조 = 프로그램, Niklaus Worth, 1975, ISBN 0-13-022418-9
- 컴파일러 구축, Niklaus Worth, 1996, ISBN 0-201-40353-6
외부 링크
- 파싱 소개 - 읽기 쉬운 파싱 소개로, 재귀 강하 파싱에 대한 포괄적인 섹션이 포함되어 있습니다.
- 문법을 C 코드로 변환하는 방법 - 재귀 강하 파서 구현에 대한 간단한 튜토리얼
- Ruby의 간단한 수식 파서
- Python의 간단한 하향식 구문 분석
- 잭 W. 크렌쇼: 컴파일러를 빌드하자(1988-1995), 어셈블리 언어 출력을 갖춘 Pascal에서 "간단하게 유지" 접근 방식을 사용합니다.
- 기능 펄: Haskell의 Monadic 구문 분석