결정론적 문맥 자유 문법

Deterministic context-free grammar

형식 문법 이론에서 결정론적 문맥 자유 문법(DCFG)은 문맥 자유 문법의 적절한 부분 집합이다.그것들은 결정론적 푸쉬다운 오토마타에서 파생될 수 있는 문맥 없는 문법의 서브셋이며, 결정론적 문맥 없는 언어를 생성한다.DCFG는 항상 모호하지 않고 모호하지 않은 CFG의 중요한 서브클래스입니다.단, 비결정론적 모호하지 않은 CFG가 있습니다.

DCFG는 선형 시간에 구문 분석할 수 있고 실제로 파서 생성기에 의해 문법에서 파서를 자동으로 생성할 수 있기 때문에 실용적으로 매우 중요합니다.따라서 컴퓨터 과학 전반에 걸쳐 널리 사용되고 있습니다.DCFG의 다양한 제한된 형식은 단순하고 리소스 사용량이 적은 파서로 구문 분석할 수 있기 때문에 자주 사용됩니다.이러한 문법 클래스는 해석하는 파서의 유형에 의해 참조됩니다.중요한 예는 LALR, SLR 및 LL입니다.

역사

1960년대에 정규식과 유한 오토마타에 대한 컴퓨터 과학의 이론적 연구는 문맥이 없는 문법이 비결정론적 푸쉬다운 [1][2][3]오토마타와 동등하다는 것을 발견하게 했다.이 문법들은 컴퓨터 프로그래밍 언어의 구문을 포착하는 것으로 생각되었다.최초의 고급 컴퓨터 프로그래밍 언어는 당시 개발 중이었고(프로그래밍 언어의 역사 참조), 컴파일러 작성은 어려웠다.그러나 컨텍스트 프리 문법을 사용하여 컴파일러의 파싱 부분을 자동화함으로써 작업이 간소화되었습니다.결정론적 문맥 자유 문법은 컴퓨터 메모리 [4]제약으로 인한 요구사항인 결정론적 푸시다운 자동화에 의해 순차적으로 구문 분석될 수 있기 때문에 특히 유용했다.1965년 도널드 커누스는 LR(k) 파서를 발명하여 모든 결정론적 문맥 자유 [5]언어에 LR(k) 문법이 존재한다는 것을 증명했습니다.이 파서는 여전히 많은 메모리가 필요했습니다.1969년에 Frank DeRemer는 LR 파서를 기반으로 한 LALR 파서와 Simple LR 파서를 개발했습니다.또, 언어 인식 능력을 억제하면서, 메모리 요건을 큰폭으로 삭감했습니다.LALR 파서가 [6]더 강력했습니다.이 두 파서는 그 이후로 많은 컴퓨터 언어의 컴파일러에 널리 사용되고 있습니다.최근 연구에서는 Knuth의 테이블 구축 [7]알고리즘에 비해 테이블 요구 사항을 크게 줄인 상태에서 표준 LR 파서를 구현할 수 있는 방법이 확인되었다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Chomsky, Noam (1962). "Context Free Grammars and Pushdown Storage". Quarterly Progress Report, MIT Research Laboratory in Electronics. 65: 187–194.
  2. ^ Evey, R.J. (1963). "Application of Pushdown-Store Machines". 1963 AFIPS Proceedings of the Fall Joint Computer Conference: 215–227.
  3. ^ Schützenberger, Marcel Paul (1963). "On Context-Free Languages and Push-Down Automata". Information and Control. 6 (3): 246–264. doi:10.1016/s0019-9958(63)90306-1.
  4. ^ A. Salomaa; D. Wood; S. Yu, eds. (2001). A Half-Century of Automata Theory. World Scientific Publishing. pp. 38–39.
  5. ^ Knuth, D. E. (July 1965). "On the translation of languages from left to right". Information and Control. 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2.
  6. ^ Franklin L. DeRemer (1969). "Practical Translators for LR(k) languages" (PDF). MIT, PhD Dissertation. Archived from the original (PDF) on 2012-04-05.
  7. ^ X. Chen, LR (1) 파싱 측정 및 확장, 하와이 대학교 박사 학위 논문, 2009.