LALR 파서

LALR parser

컴퓨터 과학에서 LALR 파서[a] 또는 Look-Ahead LR 파서는 표준 LR 파서의 단순화된 버전으로, 컴퓨터 언어의 공식 문법에 의해 지정된 일련의 생산 규칙에 따라 텍스트를 구문 분석합니다.("LR"은 왼쪽에서 오른쪽으로, 가장 오른쪽에서 파생된 것을 의미합니다.)

LALR 파서는 1969년 Frank DeRemer가 LR(1) 파서를 구현했을 때의 실제적인 어려움을 다루기 위해 LR([1]k) 언어의 실용적 번역자라는 박사학위 논문에서 발명했습니다.그는 LALR 파서가 LR(0) 파서보다 언어 인식 능력이 뛰어나고, 동시에 양쪽 파서에서 인식할 수 있는 언어의 경우 LR(0) 파서와 동일한 수의 상태를 필요로 한다는 것을 보여주었습니다.이것에 의해, LALR 파서는, LALR인 언어의 LR(1) 파서의 메모리 효율이 높아집니다.또한 LALR이 아닌 LR(1) 언어가 존재한다는 것도 증명되었습니다.이 약점에도 불구하고 [3]LALR 파서는 Java를 포함한 많은 메인스트림 컴퓨터 [2]언어에는 충분하지만, [2]많은 언어의 참조 문법은 모호하기 때문에 LALR이 되지 않습니다.

원래 논문은 형식적인 문법이 주어진 파서를 구성하기 위한 알고리즘을 제시하지 않았다.LALR 파서 생성을 위한 최초의 알고리즘은 1973년에 [4]발표되었다.1982년 DeRemer와 Tom Pennello는 메모리 효율이 높은 LALR [5]파서를 생성하는 알고리즘을 발표했습니다.LALR 파서는 Yacc 또는 GNU Bison 등의 LALR 파서 생성기에 의해 문법에서 자동으로 생성될 수 있습니다.자동으로 생성된 코드를 손으로 쓴 코드로 증강하여 결과 파서의 파워를 높일 수 있습니다.

역사

1965년 Donald Knuth는 LR 파서를 발명했습니다(좌에서 우로, 가장 오른쪽 파생).LR 파서는 [6]선형 경계 시간에 결정론적 컨텍스트프리 언어를 인식할 수 있습니다.대부분의 오른쪽 파생에는 메모리 요건이 매우 크고 LR 파서를 구현하는 것은 당시에는 컴퓨터의 메모리가 제한되어 있었기 때문에 실용적이지 않았습니다.이 단점에 대처하기 위해 1969년 Frank DeRemer는 LR 파서의 두 가지 단순화된 버전인 Look-Ahead LR(LALR;[1] 룩어헤드 LR)과 Simple LR 파서를 제안했습니다.이 파서는 언어 인식 능력이 떨어지지만 가장 강력한 [1]대안입니다.1977년에 LR 파서를 위한 메모리 최적화가 개발되었지만[7] 여전히 LR 파서는 단순화된 대안보다 메모리 효율성이 낮았습니다.

1979년 Frank DeRemer와 Tom Pennello는 LALR 파서의 메모리 [8]효율을 더욱 향상시킬 수 있는 일련의 최적화를 발표했습니다.그들의 작품은 [5]1982년에 출판되었다.

개요

일반적으로 LR 파서가 LR (1) 파서를 참조하듯이 LALR 파서는 LALR (1) 파서를 [b]참조합니다."(1)"은 구문 분석 중 규칙 패턴 간의 차이를 해결하기 위한 단일 토큰 룩어헤드(lookahead)를 나타냅니다.마찬가지로 2토큰 룩업을 사용하는 LALR (2) 파서와 k토큰 룩업을 사용하는 LALR(k) 파서가 있지만 실제로 사용되는 경우는 거의 없습니다.LALR 파서는 LR(0) 파서를 기반으로 하므로 LALR(1) = LA(1)LR(0)로 나타낼 수도 있습니다(Lookahead의 토큰 1개, LR(0) 또는 그 보다 일반적으로 LALR(k) = LR(0)의 토큰).실제로 j와 k의 모든 조합에 [9]대한 LA(k)LR(j) 파서의 2-파라미터 패밀리가 있으며, 이는 LR(j + k) 파서에서 파생될 수 있지만 실제 사용되지는 않는다.

다른 유형의 LR 파서와 마찬가지로 LALR 파서는 백트래킹을 사용할 필요가 없기 때문에 입력 스트림에 대한 왼쪽에서 오른쪽으로의 단일 스캔으로 올바른 상향식 파스를 찾는 데 매우 효율적입니다.정의상 사전 검색 파서이므로 항상 사전 검색을 사용합니다. LALR(1)이 가장 일반적인 경우입니다.

기타 파서와의 관계

LR 파서

LALR (1) 파서는 LR (1) 파서보다 강력하지 않고 SLR (1) 파서보다 강력하지만 모두 같은 생산 규칙을 사용합니다.LALR 파서가 도입하는 단순화는 LR(0) 상태 구축 프로세스 중에 룩헤드를 알 수 없기 때문에 동일한 커널 항목 세트를 가진 병합 규칙에서 이루어집니다.이는 룩어헤드 기호를 모르면 파서가 다음에 어떤 문법 규칙을 선택해야 할지 혼란스러워지고 경합 감소/축소가 발생할 수 있기 때문에 파서의 파워를 감소시킵니다.모호하지 않은 LR(1) 문법에 LALR(1) 파서를 적용할 때 발생하는 모든 충돌은 감소/축소 충돌입니다.SLR(1) 파서는 추가 마지를 수행하므로 추가적인 충돌이 발생합니다.

LALR (1) 파서로 해석할 수 없는 LR (1) 문법의 표준 예는 다음과 같습니다.이러한 축소/축소 경합은 다음과 같습니다.[10][11]

S → a E c → a F d → b F c → b E d E → e F → e

LALR 테이블 구성에서는 두 개의 상태가 하나의 상태로 병합되고 나중에 룩헤드가 모호하다는 것을 알게 됩니다.룩헤드가 있는 상태는 다음과 같습니다.

E → e. {c,d} F → e. {c,d}

LR(1) 파서는 2개의 다른 상태(경합하지 않는 룩어헤드 포함)를 작성합니다.이 상태는 어느 쪽도 애매하지 않습니다.LALR 파서에서는 이 하나의 상태가 모순되는 액션(예측 c 또는 d가 주어지면 E 또는 F로 감소)을 가지고 있습니다.즉, 위의 문법은 LALR 파서 제너레이터에 의해 애매하다고 선언되어 충돌이 보고됩니다.

이 모호성은 문법상 F보다 먼저 발생하기 때문에 회복하려면 E를 선택하면 해결됩니다.그러나 결과 파서는 유효한 입력 시퀀스를 인식할 수 없습니다.b e c모호한 시퀀스가 있기 때문에e c로 환원되다(E → e) c올바른 것이 아니라(F → e) c,그렇지만b E c문법에 없습니다.

LL 파서

LALR(j) 파서는 LL(k) 파서와 비교할 수 없습니다.j와 k가 모두 0보다 크면 LL(k) 문법 이외의 LALR(j) 문법이 있습니다.실제로 특정 (1) 문법이 > 0 k[2]에 대해 LALR(k)인지 아닌지는 판단할 수 없습니다.

빈 파생어의 존재에 따라 LL(1) 문법은 SLR(1) 또는 LALR(1) 문법과 같을 수 있습니다.LL(1) 문법에 빈 파생이 없으면 SLR(1)이고, 빈 파생이 있는 모든 기호가 비어 있지 않으면 LALR(1)입니다.빈 파생만 있는 기호가 존재할 경우 문법은 [12]LALR(1)일 수도 있고 아닐 수도 있다.

「 」를 참조해 주세요.

메모들

  1. ^ 'LALR'은 이니셜리즘 'el-ay-el-arr'로 발음된다.
  2. ^ 'LALR(1)'은 이니셜리즘 'el-ay-el-arr-one'으로 발음된다.

레퍼런스

  1. ^ a b c 1969년 디리머
  2. ^ a b c LR 해석: 이론과 실천, 나이젤 P.채프먼, 86~87페이지
  3. ^ "Generate the Parser". Eclipse JDT Project. Retrieved 29 June 2012.
  4. ^ Anderson, T.; Eve, J.; Horning, J. (1973). "Efficient LR(1) parsers". Acta Informatica (2): 2–39.
  5. ^ a b DeRemer, Frank; Pennello, Thomas (October 1982). "Efficient Computation of LALR(1) Look-Ahead Sets" (PDF). ACM Transactions on Programming Languages and Systems. 4 (4): 615–649. doi:10.1145/69622.357187.
  6. ^ Knuth, D. E. (July 1965). "On the translation of languages from left to right" (PDF). Information and Control. 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2. Archived from the original (PDF) on 15 March 2012. Retrieved 29 May 2011.
  7. ^ Pager, D. (1977), "A Practical General Method for Constructing LR(k) Parsers", Acta Informatica 7, vol. 7, no. 3, pp. 249–268, doi:10.1007/BF00290336
  8. ^ Frank DeRemer, Thomas Pennello (1979), "Efficient Computation of LALR(1) Look-Ahead Sets", Sigplan Notices - SIGPLAN, vol. 14, no. 8, pp. 176–187
  9. ^ 해석 기술: Dick Grune과 Ceriel J. H. Jacobs의 실용 가이드, "9.7 LALR (1)", 페이지 302
  10. ^ "7.9 LR (1) (LALR (1)이 아닌 아카이브 완료) 2010년 8월 4일 웨이백 머신", CSE 756: 컴파일러 설계 및 구현 아카이브 완료 2010년 7월 23일, Eitan Gurari, 2008년 봄
  11. ^ "이 LR(1) 문법이 LALR(1)이 아닌 이유는 무엇입니까?"
  12. ^ (1982년 비트)

외부 링크

  • 파싱 시뮬레이터 이 시뮬레이터는 파싱 테이블 LALR을 생성하고 책의 연습 문제를 해결하기 위해 사용됩니다.
  • 웹 브라우저 또는 명령줄에서 실행할 수 있는 LALR(1) 파서 제너레이터의 JS/CC JavaScript 기반 구현.
  • Wayback Machine에서의 LALR (1) 튜토리얼(2021년 5월 7일 아카이브).LALR (1) 해석에 관한 플래시 카드와 같은 튜토리얼입니다.