야카

Yacc
야카
원저작자스티븐 C.존슨
저장소
기입처C
운영 체제Unix, Unix like, Plan 9, Inferno
플랫폼크로스 플랫폼
유형명령어
면허증.계획 9: MIT 라이선스

Yacc(Yet Another Compiler-Compiler)는 Stephen C가 개발한 Unix 운영 체제용 컴퓨터 프로그램입니다. 존슨.Look Ahead Left-to-Right Most Deliveration(LALR; 왼쪽에서 오른쪽으로 가장 오른쪽으로 유도) 파서 생성기로, Backus-Naur Form(BNF)[1]과 유사한 표기로 작성된 형식 문법에 따라 LALR 파서(소스 코드의 구문적 의미를 부여하려는 컴파일러의 일부)를 생성합니다.Yacc는 BSD 및 AT&T [2]Unix에서 표준 유틸리티로 제공됩니다.GNU 기반의 Linux 디스트리뷰션에는 포워드 호환 [3]Yacc 대체품인 Bison이 포함되어 있습니다.

역사

1970년대 초, 스티븐 C. Bell Labs/AT&T의 컴퓨터 과학자인 Johnson은 B 언어 컴파일러(Mcilroy의 TMG 컴파일러를[4] 사용하여 개발됨)에 독점 또는 연산자를 삽입하고 싶었기 때문에 Yacc를 개발했지만 어려운 작업이었습니다.그 결과, 그는 Bell Labs Al Aho의 동료로부터 LR 해석에 관한 Donald Knuth의 작업을 지시받았습니다.이것은 Yacc의 [5]기초가 되었습니다.Yacc는 TMG 컴파일러에 의해 영향을[6] 받아 TMG [7]컴파일러에서 이름을 얻었습니다.

Yacc는 원래 B 프로그래밍 언어로 작성되었지만 곧 [4]C로 다시 작성되었습니다.버전 3 [8]Unix의 일부로서 등장해,[6] Yacc의 완전한 설명은 1975년에 출판되었습니다.

Johnson은 Yacc를 사용하여 Portable C [8]컴파일러를 만들었습니다.Bjarne Strostrup은 또한 Yacc를 사용하여 C++의 정식 사양을 작성하려고 시도했지만 "C의 구문에 의해 패배했습니다."[9]Strustrup은 언어의 정식 사양에 적합하지 않다고 생각하면서도 Yacc를 사용하여 C++[10]의 첫 번째 구현인 Cfront를 구현했습니다.

2008년 인터뷰에서 Johnson은 "Yacc가 Unix와 C의 확산에 기여한 것이 가장 자랑스럽다"[11]고 말했습니다.

묘사

Yacc에 대한 입력은 규칙에 C 코드의 단편("actions")이 첨부된 문법입니다.이 출력은 C의 시프트 리듀스 파서이며, 규칙이 인식되는 즉시 각 규칙과 관련된 C 스니펫을 실행합니다.일반적인 액션에는 해석 트리의 구축이 포함됩니다.Johnson의 예를 사용하여 콜이node(label, left, right)는 지정된 라벨과 자식으로 바이너리 해석 트리노드를 구축한 후 규칙을 설정합니다.

expr : expr '+' expr {$ = node expr+}, $1, $3); }

는 합계식을 인식하고 그 식을 위한 노드를 구성합니다.특수 식별자 $, $1 및 $3은 파서 [6]스택 상의 항목을 나타냅니다.

Yacc는 파서(프레이즈아나라이저)만 생성합니다.완전한 구문 분석을 위해서는 외부 어휘 분석기가 첫 번째 토큰화 단계(워드 분석)를 실행하고 그 다음 적절한 [6]구문 분석 단계를 수행해야 합니다.Lex 또는 Flex와 같은 어휘 분석기 생성기를 널리 사용할 수 있습니다.IEEE POSIX P1003.2 표준은 Lex와 Yacc의 [12]기능과 요건을 정의합니다.

AT&T Yacc의 일부 버전은 오픈 소스가 되었습니다.예를 들어, 소스 코드는 플랜 [13]9의 표준 배포에서 사용할 수 있습니다.

영향

Yacc 및 유사한 프로그램(대부분의 재실장)은 매우 인기가 있습니다.Yacc 자체는 대부분의 Unix 시스템에서 기본 파서 생성기로 사용 가능했지만, 그 이후 Berkeley Yacc, GNU Bison, MKS Yacc 및 Abraxas PCYACC와 같은 최신 프로그램으로 대체되었습니다.오리지널 AT&T Yacc의 최신 버전은 Sun의 OpenSolaris 프로젝트의 일부로 포함되어 있습니다.각각은 원래의 Yacc보다 약간의 개선과 추가 기능을 제공하지만 개념과 기본 구문은 그대로 [14]유지되고 있습니다.

Yacc에서 처음 구현된 언어로는 AWK, C++,[10] eqn 및 [15]Pic이 있습니다.Yacc는 Portable C 컴파일러와 Fortran 77, Ratfor, APL, bc, m4 [8][16]등의 프로그래밍 언어용 파서를 구현하기 위해 Unix에서 사용되기도 했다.

Yacc는 또한 OCaml,[17] Ratfor, ML, Ada, Pascal, Java, Python, Ruby,[18] Go, Common[19] Lisp,[20] Erlang 등의 다른 언어용으로 다시 작성되었습니다.

  • Berkeley Yacc:Berkeley의 Yacc 구현은 성능과 재사용 [21]제한 부족으로 인해 AT&T Yacc 자체보다 빠르게 인기를 끌었습니다.
  • LALR 파서:Yacc 생성 파서의 기본 구문 분석 알고리즘.
  • 바이슨: Yacc의 GNU 버전.
  • Lex(및 Flex 어휘 분석기)는 Yacc(및 Bison)와 함께 일반적으로 사용되는 토큰 파서입니다.
  • BNF는 문맥이 없는 문법을 표현하기 위해 사용되는 메타세스로, 문맥이 없는 언어를 기술하는 형식적인 방법입니다.
  • PLY(Python Lex-Yacc)는 Python에서 Lex와 Yacc를 대체 구현한 것입니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ "The A-Z of Programming Languages: YACC". Computerworld. Archived from the original on 31 January 2013. Retrieved 30 November 2012.
  2. ^ Levine, John (1992). Lex & yacc. Sebastopol, CA: O'Reilly & Associates. p. xx. ISBN 1-56592-000-7.
  3. ^ Levine, John (2009). Flex & bison. Sebastopol, Calif: O'Reilly Media. p. xv. ISBN 978-0-596-15597-1.
  4. ^ a b Ritchie, Dennis M. (April 1993). The Development of the C Language (PDF). Association for Computing Machinery, Inc.
  5. ^ Morris, Richard (1 October 2009). "Stephen Curtis Johnson: Geek of the Week". Red Gate Software. Retrieved 19 January 2018.
  6. ^ a b c d Johnson, Stephen C. (1975). Yacc: Yet Another Compiler-Compiler (Technical report). Murray Hill, New Jersey: AT&T Bell Laboratories. 32. Retrieved 31 January 2020.
  7. ^ "Early Translator Writing Systems". Atlas Computer Laboratory.
  8. ^ a b c McIlroy, M. D. (1987). A Research Unix reader: annotated excerpts from the Programmer's Manual, 1971–1986 (PDF) (Technical report). CSTR. Bell Labs. 139.
  9. ^ Stroustrup, Bjarne. "A History of C++: 1979−1991" (PDF).
  10. ^ a b Stroustrup, Bjarne. "Cfront source code".
  11. ^ Hamilton, Naomi (2008-07-09). "Yacc, Unix, and advice from Bell Labs alumni Stephen Johnson". www.computerworld.com. Archived from the original on 2020-08-22. Retrieved 2020-11-10.
  12. ^ lex – Shell and Utilities Reference, The Open Group의 싱글 UNIX 사양, 버전 4, Shell and Utilities Reference, The Open Group의 싱글 UNIX 사양, 버전 4.
  13. ^ "plan9: UC Berkeley release of Plan 9 under the GPLv2". 26 December 2017. Retrieved 2 January 2018.
  14. ^ 바이슨 매뉴얼:역사
  15. ^ "UNIX Special: Profs Kernighan & Brailsford". Computerphile. September 30, 2015. Archived from the original on 2021-12-11.
  16. ^ Kernighan, Brian W.; Pike, Rob (1984). The Unix Programming Environment. Prentice Hall. ISBN 0-13-937681-X.
  17. ^ "OCaml User's Manual: Chapter 12 Lexer and parser generators (ocamllex, ocamlyacc)". Retrieved 25 Nov 2013.
  18. ^ "Yacc.go: A version of Yacc for the Go Programming Language". Retrieved 15 July 2017.
  19. ^ "CL-Yacc: A Common Lisp version of Yacc".
  20. ^ "yecc: An Erlang implementation of Yacc".
  21. ^ John Levine (August 2009), flex & bison, O'Reilly Media

외부 링크

Wikibook Guide to Unix 에는 다음 항목에 대한 페이지가 있습니다.