Yacc (Yet Another Compiler-Compiler)는 Stephen C. Johnson에 의해 개발된 유닉스 운영 시스템에 대해 컴퓨터 프로그램입니다. 그것은 Look Ahead Left-to-Right (LALR) parser generator이며, Backus–Naur Form (BNF)와 유사한 표기법으로 쓰인, 형식 문법을 기반으로 LALR 파서 (소스 코드의 구문적 의미를 만들려고 시도하는 컴파일러의 일부)를 생성합니다. Yacc는 BSD 및 AT&T 유닉스에서 표준 유틸리티로 제공됩니다. GNU-기반 리눅스 배포판은 전진방향-호환가능한 Yacc 대체품, Bison을 포함합니다.
History
1970년대 초기에, Bell Labs / AT&T에서 컴퓨터 과학자, Stephen C. Johnson은 B 언어 컴파일러 (McIlroy의 TMG 컴파일러-컴파일러를 사용하여 개발됨)에 exclusive or 연산자를 삽입하기를 원했기 때문에 Yacc를 개발했지만, 그것은 어려운 임무로 밝혀졌습니다. 결과적으로, 그는 Bell Labs Al Aho의 동료에 의해 Yacc에 대해 기초로 역할을 한 LR 구문 분석에 대한 Donald Knuth의 연구로 안내되었습니다. Yacc는 TMG 컴파일러-컴파일러에 영향을 받았고 그것을 참조하여 이름을 받았습니다.
Yacc는 원래 B 프로그래밍 언어로 작성되었지만, 곧 C로 다시 작성되었습니다. 그것은 버전 3 유닉스의 일부로 등장했었고, Yacc의 전체 설명은 1975년에 출판되었습니다.
Johnson은 Yacc를 Portable C Compiler를 만들기 위해 사용했습니다. Bjarne Stroustrup은 역시 C++에 대한 초기 작업에 Yacc를 사용하려고 시도했지만, "C의 구문에 의해 실패했습니다" (그것은, 예를 들어, 접두사와 후위 연산자가 모두 포함합니다).
2008년 인터뷰에서, Johnson은 "Yacc가 유닉스와 C의 보급에 기여한 것이 내가 가장 자랑스러워하는 것"이라고 말했습니다.
Description
Yacc에 대한 입력은 규칙에 첨부된 C 코드 ("동작"이라고 함) 단편을 갖는 문법입니다. 그 출력은 규칙이 인식되는 즉시 각 규칙과 결합된 C 단편을 실행하는 C에서 shift-reduce 파서입니다. 전형적인 동작은 구문 분석 트리의 구성을 포함합니다. Johnson으로부터 예제를 사용하여, 만약 호출 node(label, left, right)가 지정된 label과 자식으로 이진 구문 분석 트리 노드를 구성하면, 다음 규칙은
expr : expr '+' expr { $$ = node('+', $1, $3); }
합계 표현식을 인식하고 그것들에 대한 노드를 구성합니다. 특수 식별자 $$, $1 및 $3은 파서 스택의 항목을 참조합니다.
Yacc는 오직 파서 (구문 분석기)를 생성합니다; 완전한 구문 분석에 대해, 이것은 외부 어휘 분석기에게 첫 번째 토큰화 단계 (단어 분석)를 수행하고, 그런-다음 적절한 구문 분석 단계를 수행하는 것을 요구합니다. Lex 또는 [[Flex (lexical analyser generator)|Flex]와 같은 어휘 분석기 생성기는 널리 사용 가능합니다. IEEE POSIX P1003.2 표준은 Lex와 Yacc 모두에 대한 기능과 요구 사항을 정의합니다.
AT&T Yacc의 일부 버전은 오픈 소스가 되었습니다. 예를 들어, source code는 Plan 9의 표준 배포판과 함께 사용할 수 있습니다.
Impact
Yacc 및 이와 유사한 프로그램 (대부분 재구현)은 매우 인기가 있습니다. Yacc 자체는 대부분의 유닉스 시스템에서 기본 파서 생성기로 사용 가능했지만, 이후 Berkeley Yacc, GNU Bison, MKS Yacc, 및 Abraxas PCYACC와 같은 보다 최근에 호환성이 높은 프로그램으로 대체되었습니다. 원래 AT&T Yacc의 업데이트된 버전은 Sun의 OpenSolaris 프로젝트의 일부로 포함됩니다. 각각은 원래 Yacc에 비해 약간의 개선 사항과 추가 기능을 제공하지만, 개념과 기본 구문은 동일하게 유지되었습니다.
Yacc로 처음 구현된 언어 중에는 AWK, eqn 및 Pic이 있습니다. Yacc는 역시 FORTRAN 77, Ratfor, APL, bc, m4, 등과 같은 프로그래밍 언어를 위한 파서뿐만 아니라 Portable C 컴파일러를 구현하기 위해 Unix에서 사용되었습니다.
Yacc는 역시 OCaml, Ratfor, ML, Ada, Pascal, Java, Python, Ruby, Go, Common Lisp 및 Erlang을 포함한 다른 언어에 대해 다시 작성되었습니다.
- Berkeley Yacc: 버클리에서 구현한 Yacc는 성능과 재사용 제한이 없기 때문에 AT&T Yacc 자체보다 빠르게 인기를 얻었습니다.
- LALR parser: Yacc-생성된 파서의 기본 구문 분석 알고리듬입니다.
- Bison: Yacc의 GNU 버전.
- Lex (및 Flex lexical analyser), Yacc (및 Bison)와 함께 공통적으로 사용되는 토큰 파서.
- BNF는 컨텍스트-자유 문법을 표현하기 위해 사용되는 메타구문입니다; 그것은 컨텍스트-자유 언어를 설명하는 형식적인 방법입니다.
- PLY (Python Lex-Yacc)는 Python에서 Lex와 Yacc의 대안적인 구현입니다.
External links
- yacc – Commands & Utilities Reference, The Single UNIX Specification, Issue 7 from The Open Group
- yacc(1) – Plan 9 Programmer's Manual, Volume 1
- yacc(1) – Inferno General commands Manual