재귀적 아스센트 파서

Recursive ascent parser

컴퓨터 과학에서 재귀적 아스센트 파싱은 테이블이 아닌 상호재귀적 기능을 사용하는 LALR 파서를 구현하는 기법이다.따라서 파서는 재귀적 강하와 유사한 호스트 언어로 직접 암호화된다.다이렉트 인코딩은 일반적으로 컴파일이 해석보다 빠르다는 것과 같은 이유로 테이블 구동 등가물보다[1] 더 빠른 파서를 산출한다.또한 (공칭적으로) 반복적인 아스센트 파서를 손으로 편집할 수 있는 반면, 표로 된 구현은 평균적인 인간에게는 거의 읽을 수 없다.

재귀적 등반은 토마스 페넬로가 그의 글에서 처음 묘사했다."Very fast LR parsing". 1986년에그는 LR 파서의 편집 가능한 구현을 만들려는 것이 아니라 조립 언어로 구현된 유지 가능하고 효율적인 파서를 만들려는 것이었다.그 기술은 후에 1988년 G.H. 로버츠에[2] 의해 설명되었고 1992년 Leermakers, Augusteijn, Kruseman Arez의[3] 논문에서도 이론 컴퓨터 과학 저널에 상세히 설명되었다.이 기술에 대한 극히 읽기 쉬운 설명은 2003년에 모렐과 미들턴에[4] 의해 쓰여졌다.Sperber와 Tiemann의 TOPLAS 기사에서도 좋은 전시를 찾을 수 있다.[5]

재귀적 등반은 또한 재귀적 하강과 병합되어 재귀적 등반/등반이라고 알려진 기술을 산출한다.이 구현 기법은 상태 감소와 이들 상태 중 일부가 상향식보다는 직관적으로 하향식이기 때문에 거의 틀림없이 수작업 편집이 더 쉽다.또한 기존 재귀 상승에 비해 약간의 성능 개선도 제공할 수 있다.[6]

요약

직관적으로, 재귀적 상승은 LR 파싱 개념을 문자 그대로 구현한 것이다.파서의 각 함수는 단일 LR 자동 상태를 나타낸다.각 기능 내에서 입력 스택에서 튀어나온 현재 토큰을 기준으로 적절한 동작을 선택하기 위해 다중 지점 문을 사용한다.토큰이 식별되면 인코딩되는 상태에 따라 조치를 취한다.문제의 토큰에 기초하여 취할 수 있는 두 가지 기본적인 조치가 있다.

  • Shift - 기능 호출로 인코딩되어 새로운 자동화 상태로 효과적으로 전환
  • 감소 - 관련 생산의 의미 작용 루틴에 따라 다르게 인코딩.이 루틴의 결과는 발신자에게 반환되는 ADT로 포장된다.감소 동작은 감소 전에 이동된 토큰의 수를 기록하여 이 값을 감소 값과 함께 호출자에게 다시 전달해야 한다.이 시프트 카운터는 통화 스택의 어느 지점에서 감소를 처리해야 하는지를 결정한다.

또한 주어진 상태에서 수행할 수 있는 세 번째 LR 자동 작용도 있지만, 시프트 카운터가 0으로 감소된 곳(현재 상태가 결과를 처리해야 함을 나타냄) 후에만 수행할 수 있다.이것이 바로 goto 작용인데, 이것은 본질적으로 생산에서 비종단자를 처리하도록 설계된 특별한 시프트의 경우다.이러한 조치는 다지점 진술 후에 처리되어야 한다. 이 진술은 통화 스택의 더 아래쪽에서 감소 결과가 "재발견"될 것이기 때문이다.

예

들소 구문에서는 다음 문법을 고려하십시오.

expr : expr '+' term   { $ = $1 + $3; }        expr '-' term   { $ = $1 - $3; }        term            { $ = $1; }      ;  term : '(' expr ')'    { $ = $2; }        num             { $ = $1; }      ;  num : '0'              { $ = 0; }       '1'              { $ = 1; }     ;

이 문법은 왼쪽-재귀적이라는 점에서(비단어) LR(0)이지만 외모가 필요하지 않다.또한 재귀성 등반은 테이블 구동 파서들이 그러한 경우를 처리하는 방식과 거의 동일한 방식으로 LALR(1)인 그래머를 처리할 수 있다(가능한 룩어헤드에 기초한 충돌 해결 방법을 사전 계산함).

다음은 위의 문법에 근거한 재귀적 아스센트 파서의 스칼라 구현이다.

반대하다 ExprParser {   사유의 타자를 치다 결과 = (논터미널, 인트)      사유의 봉인된 특성 논터미널 {     발랄하게 하다 v: 인트   }      사유의 케이스 계급 NTexr(v: 인트, 에: 스트림[차르]) 연장하다 논터미널   사유의 케이스 계급 NTterm(v: 인트, 에: 스트림[차르]) 연장하다 논터미널   사유의 케이스 계급 NTnum(v: 인트, 에: 스트림[차르]) 연장하다 논터미널      계급 파스Exception(음스그: 끈) 연장하다 RuntimeException(음스그) {     반항하다 이() = 이("")          반항하다 이(c: 차르) = 이(c.토스트링)   }      반항하다 파스를 치다(에: 스트림[차르]) = state0(에)._1.v      /* * 0달러 수락: . expr $end * * '(') 교대 후 상태 1로 이동 * '0' 교대 후 상태 2로 이동 * '1'교대 후 상태 3으로 이동 * * Exper는 상태 4로 이동 * 기간은 상태 5로 이동 * num go to state 6 */   사유의 반항하다 state0(에: 스트림[차르]) = 에 짝을 맞추다 {     케이스 꾸러미 #:: 꼬리를 치다 => {       반항하다 고리를 틀다(터플: 결과): 결과 = {         발랄하게 하다 (재방송하다, 에 가다) = 터플                  만일 (에 가다 == 0) {           고리를 틀다(재방송하다 짝을 맞추다 {             케이스 NTexr(v, 에) => 주4(에, v)             케이스 NTterm(v, 에) => state5(에, v)             케이스 NTnum(v, 에) => 주6(에, v)           })         } 다른 (재방송하다, 에 가다 - 1)       }              고리를 틀다(꾸러미 짝을 맞추다 {         케이스 '(' => state1(꼬리를 치다)         케이스 '0' => 주2(꼬리를 치다)         케이스 '1' => 주3(꼬리를 치다)         케이스 c => 던지다 새로운 파스Exception(c)       })     }          케이스 스트림() => 던지다 새로운 파스Exception   }      /* * 4항: '(' . expr ')' * * '(') 교대 후 상태 1로 이동 * '0' 교대 후 상태 2로 이동 * '1'교대 후 상태 3으로 이동 * * Exper가 상태 7로 이동 * 기간은 상태 5로 이동 * num go to state 6 */   사유의 반항하다 state1(에: 스트림[차르]): 결과 = 에 짝을 맞추다 {     케이스 꾸러미 #:: 꼬리를 치다 => {       반항하다 고리를 틀다(터플: 결과): 결과 = {         발랄하게 하다 (재방송하다, 에 가다) = 터플                  만일 (에 가다 == 0) {           고리를 틀다(재방송하다 짝을 맞추다 {             케이스 NTexr(v, 에) => 주7(에, v)             케이스 NTterm(v, 에) => state5(에, v)             케이스 NTnum(v, 에) => 주6(에, v)           })         } 다른 (재방송하다, 에 가다 - 1)       }              고리를 틀다(꾸러미 짝을 맞추다 {         케이스 '(' => state1(꼬리를 치다)         케이스 '0' => 주2(꼬리를 치다)         케이스 '1' => 주3(꼬리를 치다)         케이스 c => 던지다 새로운 파스Exception(c)       })     }          케이스 스트림() => 던지다 새로운 파스Exception   }      /* * 6자리: '0' 입니다. * * 규칙 6을 사용하여 $기본값 절감(숫자) */   사유의 반항하다 주2(에: 스트림[차르]) = (NTnum(0, 에), 0)      /* * 7 num: '1' . * * 규칙 7을 사용하여 $기본값 절감(숫자) */   사유의 반항하다 주3(에: 스트림[차르]) = (NTnum(1, 에), 0)      /* * 0달러 수락: expr . $end * expr: expr . '+' 용어 * 2 expr . '-' 용어 * * $end shift, state 8로 이동 * '+' 교대 후 상태 9로 이동 * '-' 교대 후 상태 10으로 이동 */   사유의 반항하다 주4(에: 스트림[차르], arg1: 인트): 결과 = 에 짝을 맞추다 {     케이스 꾸러미 #:: 꼬리를 치다 => {       노쇠하다(꾸러미 짝을 맞추다 {         케이스 '+' => 주9(꼬리를 치다, arg1)         케이스 '-' => state10(꼬리를 치다, arg1)         케이스 c => 던지다 새로운 파스Exception(c)       })     }          케이스 스트림() => 주8(arg1)   }      /* * 3 expr: 용어 . * * 규칙 3을 사용하여 $기본값 절감(확장) */   사유의 반항하다 state5(에: 스트림[차르], arg1: 인트) = (NTexr(arg1, 에), 0)      /* * 5항: 숫자. * * 규칙 5(기간)를 사용하여 $default 절감 */   사유의 반항하다 주6(에: 스트림[차르], arg1: 인트) = (NTterm(arg1, 에), 0)      /* * expr: expr . '+' 용어 * 2 expr . '-' 용어 * 4항: '(' expr. ')' * * '+' 교대 후 상태 9로 이동 * '-' 교대 후 상태 10으로 이동 * ''' 교대조, 상태 11로 이동 */   사유의 반항하다 주7(에: 스트림[차르], arg1: 인트): 결과 = 에 짝을 맞추다 {     케이스 꾸러미 #:: 꼬리를 치다 => {       노쇠하다(꾸러미 짝을 맞추다 {         케이스 '+' => 주9(꼬리를 치다, arg1)         케이스 '-' => state10(꼬리를 치다, arg1)         케이스 ')' => state11(꼬리를 치다, arg1)         케이스 c => 던지다 새로운 파스Exception(c)       })     }          케이스 스트림() => 던지다 새로운 파스Exception   }      /* * 0달러 수락: expr $end. * * $default 수락 */   사유의 반항하다 주8(arg1: 인트) = (NTexr(arg1, 스트림()), 1)      /* * 1 expr: expr '+' . 용어 * * '(') 교대 후 상태 1로 이동 * '0' 교대 후 상태 2로 이동 * '1'교대 후 상태 3으로 이동 * * 기간은 상태 12로 이동 * num go to state 6 */   사유의 반항하다 주9(에: 스트림[차르], arg1: 인트) = 에 짝을 맞추다 {     케이스 꾸러미 #:: 꼬리를 치다 => {       반항하다 고리를 틀다(터플: 결과): 결과 = {         발랄하게 하다 (재방송하다, 에 가다) = 터플                  만일 (에 가다 == 0) {           고리를 틀다(재방송하다 짝을 맞추다 {             케이스 NTterm(v, 에) => state12(에, arg1, v)             케이스 NTnum(v, 에) => 주6(에, v)             케이스 _ => 던지다 새로운 어설션에러           })         } 다른 (재방송하다, 에 가다 - 1)       }              고리를 틀다(꾸러미 짝을 맞추다 {         케이스 '(' => state1(꼬리를 치다)         케이스 '0' => 주2(꼬리를 치다)         케이스 '1' => 주3(꼬리를 치다)         케이스 c => 던지다 새로운 파스Exception(c)       })     }          케이스 스트림() => 던지다 새로운 파스Exception   }      /* * expr: expr '-' . 용어 * * '(') 교대 후 상태 1로 이동 * '0' 교대 후 상태 2로 이동 * '1'교대 후 상태 3으로 이동 * * 기간은 상태 13으로 이동 * num go to state 6 */   사유의 반항하다 state10(에: 스트림[차르], arg1: 인트) = 에 짝을 맞추다 {     케이스 꾸러미 #:: 꼬리를 치다 => {       반항하다 고리를 틀다(터플: 결과): 결과 = {         발랄하게 하다 (재방송하다, 에 가다) = 터플                  만일 (에 가다 == 0) {           고리를 틀다(재방송하다 짝을 맞추다 {             케이스 NTterm(v, 에) => 주13(에, arg1, v)             케이스 NTnum(v, 에) => 주6(에, v)             케이스 _ => 던지다 새로운 어설션에러           })         } 다른 (재방송하다, 에 가다 - 1)       }              고리를 틀다(꾸러미 짝을 맞추다 {         케이스 '(' => state1(꼬리를 치다)         케이스 '0' => 주2(꼬리를 치다)         케이스 '1' => 주3(꼬리를 치다)         케이스 c => 던지다 새로운 파스Exception(c)       })     }          케이스 스트림() => 던지다 새로운 파스Exception   }      /* * 4항: '(' expr '') . * * 규칙 4(기간)를 사용하여 $default 절감 */   사유의 반항하다 state11(에: 스트림[차르], arg1: 인트) = (NTterm(arg1, 에), 2)      /* * 1 expr: expr '+' 용어 . * * 규칙 1을 사용하여 $기본값 절감(확장) */   사유의 반항하다 state12(에: 스트림[차르], arg1: 인트, arg2: 인트) = (NTexr(arg1 + arg2, 에), 2)      /* * 2 expr: expr '-' 용어 . * * 규칙 2(확장)를 사용하여 $default 절감 */   사유의 반항하다 주13(에: 스트림[차르], arg1: 인트, arg2: 인트) = (NTexr(arg1 - arg2, 에), 2)      사유의 반항하다 노쇠하다(터플: 결과) = {     발랄하게 하다 (재방송하다, 에 가다) = 터플     주장하다(에 가다 != 0)     (재방송하다, 에 가다 - 1)   } }

다음은 위의 문법에 근거한 재귀적 아스센트 파서의 프롤로그 실행이다.

주(S), [S] --> [S]. 주(S0, S), [S] --> [S0].   /* 0. S --> E$ 1. E --> E + T 2. E --> E - T 3. E -> T 4. T --> (E) 5. T --> N 6. N --> 0 7. N --> 1 */ 받아들이다 --> 주(s([], [e(_)])). r(1) --> 주(s(TS, [t(A1), '+', e(A0)Ss]), s(TS, [e(A0+A1)Ss])). r(2) --> 주(s(TS, [t(A1), '-', e(A0)Ss]), s(TS, [e(A0-A1)Ss])). r(3) --> 주(s(TS, [t(A)Ss]), s(TS, [e(A)Ss])). r(4) --> 주(s(TS, [')', e(A), '(' Ss]), s(TS, [t(A)Ss])). r(5) --> 주(s(TS, [n(A)Ss]), s(TS, [t(A)Ss])). r(6) --> 주(s(TS, ['0' Ss]), s(TS, [n(0)Ss])). r(7) --> 주(s(TS, ['1' Ss]), s(TS, [n(1)Ss])). t(T) --> 주(s([T TS], Ss), s(TS, [T Ss])).   /* S --> .E$ E --> .E + T E --> .E - T E --> .t T --> .(E) T --> .n N --> .0 N --> .1 */ s0 --> t('('), s3, s2, s1. s0 --> t('0'), s11, s10, s2, s1. s0 --> t('1'), s12, s10, s2, s1.  /* S --> E.$ E --> E. + T E --> E. - T */ s1 --> 받아들이다. s1 --> t('+'), s7, s1. s1 --> t('-'), s8, s1.  /* E --> T. */ s2 --> r(3).  /* T --> (.E) E --> .E + T E --> .E - T E --> .t T --> .(E) T --> .n N --> .0 N --> .1 */ s3 --> t('('), s3, s2, s4. s3 --> t('0'), s11, s10, s2, s4. s3 --> t('1'), s12, s10, s2, s4.  /* T --> (E.) E --> E .+ T E --> E .- T */ s4 --> t(')'), s9. s4 --> t('+'), s7, s4. s4 --> t('-'), s8, s4.  /* E --> E + T. */ s5 --> r(1).  /* E --> E - T. */ s6 --> r(2).  /* E --> E + .t T --> .(E) T --> .n N --> .0 N --> .1 */ s7 --> t('('), s3, s5. s7 --> t('0'), s11, s10, s5. s7 --> t('1'), s12, s10, s5.  /* E --> E - .t T --> .(E) T --> .n N --> .0 N --> .1 */ s8 --> t('('), s3, s6. s8 --> t('0'), s11, s10, s6. s8 --> t('1'), s12, s10, s6.  /* T --> (E) */ s9 --> r(4).  /* T --> N. */ s10 --> r(5).  /* N --> '0'. */ s11 --> r(6).  /* N --> '1' */ s12 --> r(7).  파서(Cs, T) :-     길이(Cs, _),     구절(s0, [s(Cs, [])], [s([], [e(T)])]).  % 상태(S0, S), [S] --> [S0, S]. %?- S0 = [s("(1+1)", [] _), 구문(s0, S0, [S]), 지도 목록(portray_clause, S0)

참고 항목

참조

  1. ^ Thomas J Penello (1986). "Very fast LR parsing".
  2. ^ G.H. Roberts (1988). "Recursive ascent: an LR analog to recursive descent".
  3. ^ Leermakers, Augusteijn, Kruseman Aretz (1992). "A functional LR parser".{{cite web}}: CS1 maint : 복수이름 : 작성자 목록(링크)
  4. ^ Larry Morell & David Middleton (2003). "Recursive-ascent parsing". Journal of Computing Sciences in Colleges. Vol. 18, no. 6. pp. 186–201.
  5. ^ Sperber and Thiemann (2000). "Generation of LR parsers by partial evaluation".
  6. ^ John Boyland & Daniel Spiewak (2009). "ScalaBison Recursive Ascent-Descent Parser Generator" (PDF). Archived from the original (PDF) on 2009-07-18.