재귀 강하 파서

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);             기대하다(번호);         } 하는 동안에 (받아들이다(콤마));         기대하다(세미콜론);     }     한다면 (받아들이다(시스템)) {         하다 {             기대하다(식별하다);         } 하는 동안에 (받아들이다(콤마));         기대하다(세미콜론);     }     하는 동안에 (받아들이다(시스템)) {         기대하다(식별하다);         기대하다(세미콜론);         블록();         기대하다(세미콜론);     }     진술(); }  무효 프로그램.(무효) {     다음 시스템();     블록();     기대하다(기간); } 

일부 재귀 강하 파서 생성기:

「 」를 참조해 주세요.

레퍼런스

  1. ^ Burge, W.H. (1975). Recursive Programming Techniques. ISBN 0-201-14450-6.
  2. ^ Watson, Des (22 March 2017). A Practical Approach to Compiler Construction. Springer. ISBN 978-3-319-52789-5.
  3. ^ Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey (1986). Compilers: Principles, Techniques and Tools (first ed.). Addison Wesley. p. 183.

일반 참고 자료

외부 링크