GNU 바이슨

GNU Bison
GNU 바이슨
Heckert GNU white.svg
원저작자로버트 코벳
개발자GNU 프로젝트
초기 릴리즈1985년 6월, 37년 전(1985-06)[1]
안정된 릴리스
3[2].8.2 / 2021년 9월 25일
저장소
기입처C 및 m4
운영 체제Unix와 같은
유형파서 발생기
면허증.GPL
웹 사이트www.gnu.org/software/bison/ Edit this on Wikidata

일반적으로 Bison으로 알려진 GNU Bison은 GNU 프로젝트의 일부인 파서 생성기입니다.바이슨은 BNF 표기법(문맥이 없는 언어)[3]의 사양을 읽고 해석의 모호성에 대해 경고하며 토큰 시퀀스를 읽고 시퀀스가 문법에 의해 지정된 구문에 적합한지 여부를 판단하는 파서를 생성합니다.

생성된 파서는 이동 가능하며 특정 컴파일러가 필요하지 않습니다.Bison은 기본적으로 LALR(1) 파서를 생성하지만 표준 LR, IELR(1) 및 GLR [4]파서를 생성할 수도 있습니다.

POSIX 모드에서 바이슨은 Yacc와 호환되지만 이전 프로그램보다 다음과 같은 몇 가지 확장 기능을 가지고 있습니다.

  • 충돌에 대한 반례의 생성
  • 위치 추적(파일, 줄, 열 등)
  • 생성된 파서의 풍부하고 국제화 가능한 구문 오류 메시지
  • 커스터마이즈 가능한 구문 오류 생성,
  • 재진입 파서
  • 푸시 파서, 자동 완성 기능 포함
  • 이름 있는 참조 지원
  • 생성된 파서의 여러 유형의 보고서(그래픽, XML)
  • 여러 프로그래밍 언어(C, C++, D 또는 Java) 지원

자동 어휘 분석기인 Flex는 입력 데이터를 토큰화하고 Bison에게 [5]토큰을 제공하기 위해 Bison과 함께 자주 사용됩니다.

들소는 원래 [1]로버트 코벳에 의해 1985년에 쓰여졌다.이후 1989년, 로버트 코벳은 버클리 야크라는 이름의 또 다른 파서 발생기를 출시했다.바이슨은 리처드 스톨먼에 [6]의해 야크 호환성을 갖게 되었다.

Bison은 자유 소프트웨어이며 GNU General Public License에 따라 이용할 수 있습니다.단, 라이선스의 카피레프트 요건을 트리거하지 않고 생성된 코드를 사용할 수 있습니다(아래에서 설명).

특징들

반례 생성

LR 파서 생성기의 한 가지 미묘한 문제는 충돌(시프트/축소 및 충돌 감소/축소)의 해결입니다.경합을 해결하려면 보통 보고서에서 설명한 바와 같이 파서 자동 분석과 사용자의 전문 지식이 필요합니다.반례는 어떤 갈등을 빠르게 이해하는 데 도움을 주며, 심지어 문법이 실제로 모호하다는 것이 문제라는 것을 증명할 수 있다.

예를 들어, 악명높은 달랑달랑 다른 문제로 고통받는 문법에 대해 Bison은 보고합니다.

doc/if-then-when-displict.y: warning: 토큰 "else" [-Wcounterexamples]의 shift/reduce 충돌 예: "if" expr "then" stmt • "else" stmt shift 파생 if_stmt ↳ "if" expr "then" stmt " "if" stmt "stel" stel" 예 •"stmt "stmt" stmt if if_stmt " " if " expr " then " stmt •

재진입

재진입은 바이슨에 추가된 기능으로 Yacc에는 존재하지 않습니다.

일반적으로 Bison은 재진입하지 않은 파서를 생성합니다.선언을 재진입하기 위해%define api.pure사용해야 합니다.바이슨 재진입에 대한 자세한 내용은 바이슨 [7]매뉴얼을 참조하십시오.

출력 언어

바이슨은 C, C++, D 및 [8]Java 코드를 생성할 수 있습니다.

다른 언어의 Bison 생성 파서를 사용할 경우 SWIG 등의 언어 바인딩 도구를 사용할 수 있습니다.

생성된 코드 라이선스 및 배포

Bison은 소스 코드를 생성하여 다른 소프트웨어 프로젝트의 소스 코드에 추가하기 때문에 간단하지만 흥미로운 저작권 문제를 제기합니다.

GPL 호환 라이선스는 필요 없습니다.

Bison에 의해 생성된 코드에는 Bison 프로젝트 자체에서 상당한 양의 코드가 포함되어 있습니다.Bison 패키지는 GNU General Public License(GPL) 조건에 따라 배포되지만 GPL이 [9][10]출력에 적용되지 않도록 예외가 추가되었습니다.

Bison의 이전 릴리스에서는 출력에 원래 소스 코드의 yyparse() 함수가 포함되어 있기 때문에 출력의 일부도 GPL로 라이선스가 부여되어 있다고 규정되어 있었습니다.

바이슨을 사용한 패키지 배포

Bison을 사용하는 자유 소프트웨어 프로젝트에서는 프로젝트가 Bison에 공급하는 소스 코드를 배포할 것인지, 또는 결과적으로 Bison에 의해 출력된 C 코드를 배포할 것인지를 선택할 수 있습니다.둘 다 수신자가 프로젝트 소스 코드를 컴파일하기에 충분합니다.그러나 입력만 배포하면 프로젝트 컴파일 시 필요한 C코드를 생성할 수 있도록 수신자가 호환되는 바이슨 복사본을 설치해야 한다는 약간의 불편함이 있습니다.또한 C 코드만 출력에 배포하면 수신자가 파서를 수정하는 것이 매우 어려워집니다.이 코드는 사람이 작성하거나 사람이 작성하지 않았기 때문입니다.그 목적은 C 컴파일러에 직접 입력되는 것입니다.

입력 파일과 생성된 코드를 모두 배포하면 이러한 문제를 방지할 수 있습니다.대부분의 사용자는 생성된 코드를 사용하여 컴파일하지만 파서 컴포넌트를 수정하고 컴파일하기 전에 먼저 입력 파일을 수정하고 생성된 파일을 다시 생성할 수 있습니다.둘 다 배포하는 프로젝트에서는 일반적으로 리비전 제어 시스템에 생성된 파일이 없습니다.파일은 릴리스할 때만 생성됩니다.

GPL과 같은 일부 라이센스는 소스 코드를 "수정하기 위해 선호하는 작업 형식"으로 지정해야 합니다.따라서 바이슨을 사용하는 GPL'd 프로젝트는 바이슨 입력 파일을 배포해야 합니다.물론 생성된 파일도 포함할 수 있습니다.

사용하다

Bison은 Yacc를 대체하기 위해 작성되었으며 대부분 호환성이 있기 때문에 Bison을 사용하는 많은 프로젝트의 코드를 Yacc에 동일하게 입력할 수 있습니다.이로 인해 프로젝트에서 Bison 고유의 소스 코드를 "사용"하는지 여부를 판단하기가 어렵습니다.많은 경우 바이슨의 "사용"은 Yacc 또는 다른 파생상품의 동등한 사용으로 대체될 수 있다.

바이슨은 Yacc에서 찾을 수 없는 기능을 가지고 있기 때문에, Yacc는 충분하지 않기 때문에, 일부의 프로젝트는 정말로 Bison을 「사용」하고 있다고 말할 수 있습니다.

다음 목록은 Bison을 보다 느슨하게 사용하는 것으로 알려져 있으며, 무료 소프트웨어 개발 도구를 사용하고 Bison 또는 Bison 호환 패키지에 공급되는 코드를 배포하는 프로젝트입니다.

  • Bash 쉘은 명령어 입력 해석에 yacc 문법을 사용합니다.
  • 바이슨만의 문법 파서는 바이슨에 [11]의해 생성됩니다.
  • CMake는 몇 가지 바이슨 [12]문법을 사용합니다.
  • GCC는 처음에 Bison을 사용했지만 2004년(버전 3.4),[13] 2006년(버전 4.1)[14]에는 C++, C 및 Objective-C의 수기 재귀적 파서로 전환했습니다.
  • Go 프로그래밍 언어(GC)는 바이슨을 사용했지만 버전 [15]1.5에서 손으로 쓴 스캐너와 파서로 전환했습니다.
  • LilyPond는 Bison에게 파서를 [16]생성하라고 요구합니다.
  • MySQL[17]
  • GNU 옥타브는 바이슨 생성 [18]파서를 사용합니다.
  • Perl 5는 5.10부터 [19]Bison 생성 파서를 사용합니다.
  • PHP 프로그래밍 언어(Zend 파서).
  • 포스트그레스Ql[20]
  • 루비 MRI는 루비 프로그래밍 언어의 레퍼런스 구현으로 바이슨 [21]문법에 의존합니다.
  • syslog-ng에서는 [22]여러 개의 Bison 문법을 조합하여 사용합니다.

완전한 재진입 파서의 예

다음으로 Bison과 flex를 사용하여 간단한 계산 프로그램(더하기 및 곱하기 전용)과 추상 구문 트리를 만드는 프로그램을 작성하는 예를 나타냅니다.다음 두 파일은 구문 트리 함수의 정의 및 구현을 제공합니다. 

/* * Expression.h * 구문 트리를 작성하는 데 사용되는 구조의 정의입니다. */ #ifndef __EXPRESSION_H__ #정의 __EXPRESSION_H__  /** * @brief 동작 유형 */ 유형화된 열거하다 태그 처리유형 {     가치,     멀티플라이,     추가 } EPERATORPERATION유형;  /** * @brief 표현 구조 */ 유형화된 구조 태그 표현 {     EPERATORPERATION유형 유형; /* /< 조작 타입 */      인트 가치; /* /< 유형이 eVALUE */인 경우에만 유효합니다.     구조 태그 표현 *왼쪽; /* /< 트리 왼쪽 */     구조 태그 표현 *맞다; /* /< 트리 우측 */ } 섹션;  /** * @brief 식별자를 만듭니다. * @param value 숫자 값 * @return 메모리가 없는 경우 표현식 또는 NULL */ 섹션 *create Number(작성번호)(인트 가치);  /** * @brief 조작을 만듭니다. * @param type 작업 유형 * @param left 왼쪽 오퍼랜드 * @param right 적절한 오퍼랜드 * @return 메모리가 없는 경우 표현식 또는 NULL */ 섹션 *createOperation(작동작(EPERATORPERATION유형 유형, 섹션 *왼쪽, 섹션 *맞다);  /** * @brief 식을 삭제합니다. * @param b 식 */ 무효 deleteExpression(삭제식)(섹션 *b);  #엔디프/* __EXPRESSION_H_*/ 
/* * Expression.c * 구문 트리를 구축하는 데 사용되는 함수 구현. */  #실패하다 '표현상.h"  #실패하다 <stdlib.h>  /** * @brief 식을 위한 공간을 할당합니다. * @return 표현식 또는 메모리가 부족할 경우 NULL */ 정적인 섹션 *allocateExpression(allocateExpression)() {     섹션 *b = (섹션 *)마로크(크기(섹션));      한다면 (b == 특수한 순서)         돌아가다 특수한 순서;      b->유형 = 가치;     b->가치 = 0;      b->왼쪽 = 특수한 순서;     b->맞다 = 특수한 순서;      돌아가다 b; }  섹션 *create Number(작성번호)(인트 가치) {     섹션 *b = allocateExpression(allocateExpression)();      한다면 (b == 특수한 순서)         돌아가다 특수한 순서;      b->유형 = 가치;     b->가치 = 가치;      돌아가다 b; }  섹션 *createOperation(작동작(EPERATORPERATION유형 유형, 섹션 *왼쪽, 섹션 *맞다) {     섹션 *b = allocateExpression(allocateExpression)();      한다면 (b == 특수한 순서)         돌아가다 특수한 순서;      b->유형 = 유형;     b->왼쪽 = 왼쪽;     b->맞다 = 맞다;      돌아가다 b; }  무효 deleteExpression(삭제식)(섹션 *b) {     한다면 (b == 특수한 순서)         돌아가다;      deleteExpression(삭제식)(b->왼쪽);     deleteExpression(삭제식)(b->맞다);      공짜(b); }

바이슨 파서에 필요한 토큰은 flex를 사용하여 생성됩니다. 

%{  /* * Lexer.l 파일 * 어휘 분석기를 생성하려면: "플렉스 Lexer.l" */  #실패하다 '표현상.h" #실패하다 파서.h"  #실패하다 <stdio.h>  %}  %선택 아웃파일="Lexer.c" 머리글자-파일="Lexer.h" %선택 경고하다 디폴트  %선택 재진입하다 nyywrap 절대.-상호적인 명사 리스트 %선택 바이슨-다리  %%  [ \r\n\t]*   { 계속하다.; /* 공백은 생략합니다.*/ } [0-9]+       { 스캔(텍스트, %d, &yyrval->가치); 돌아가다 토큰 번호; }  "*"          { 돌아가다 토큰_스타; } "+"          { 돌아가다 토큰_PLUS; } "("          { 돌아가다 토큰_LPAREN; } ")"          { 돌아가다 토큰_RPAREN; }  .            { 계속하다.; /* 예기치 않은 문자는 무시합니다.*/}  %%  인트 에러(섹션 **표현, 할 수 없다 스캐너, 컨스턴트 차 *메시지) {     인쇄(하드, "오류: %s\n", 메시지);     돌아가다 0; }

토큰의 이름은 보통 중립입니다. "TOKEN_ADD" 및 "TOKEN_MULTIPLY"가 아니라 "TOKEN_PLUS" 및 "TOKEN_STAR"입니다.예를 들어 단항 "+" ("+1"과 같이)를 지원한다면 이 "+" "TOKEN_ADD"라는 이름을 붙이는 것은 잘못된 것입니다.C와 같은 언어에서 "int *ptr"은 제품이 아닌 포인터의 정의를 나타냅니다.이 "*" "TOKEN_MULTIPLY"라는 이름을 붙이는 것은 잘못된 것입니다.

토큰은 플렉스에 의해 제공되므로 파서와 렉서 간의 [23]통신 수단을 제공해야 합니다.통신에 사용되는 데이터 유형인 YYSTYPE은 Bison %union 선언을 사용하여 설정합니다.

이 예에서는 flex와 yacc의 재입력 버전을 사용하므로 yyparse에서 [23]호출할 때 yylex 함수에 대한 파라미터를 제공해야 합니다.이는 Bison %lex-param [24]및 %parse-param 선언을 통해 수행됩니다. 

%{  /* * Parser.y 파일 * 파서 실행을 생성하려면: "bison 파서.y" */  #실패하다 '표현상.h" #실패하다 파서.h" #실패하다 "Lexer.h"  // Lexer.l에서 제공되는 구현을 참조합니다. 인트 에러(섹션 **표현, 할 수 없다 스캐너, 컨스턴트 차 *메시지);  %}  %코드 필요. {   유형화된 무효* 할 수 없다; }  %산출량  파서.c" %정의하다 파서.h"  %정의하다 API.순수하다 %렉스-PARAM.   { 할 수 없다 스캐너 } %해석-PARAM. { 섹션 **표현 } %해석-PARAM. { 할 수 없다 스캐너 }  %조합 {     인트 가치;     섹션 *표현; }  %상품권 토큰_LPAREN   "(" %상품권 토큰_RPAREN   ")" %상품권 토큰_PLUS     "+" %상품권 토큰_스타     "*" %상품권 < >가치> 토큰 번호 "숫자"  %유형 < >표현> expr  /* 우선순위(증가) 및 연관성: a+b+c는 (a+b)+c: 왼쪽 연관성 a+b*c는 a+(b*c): "*"의 precedence가 "+"의 precedence보다 높습니다. */ %왼쪽 "+" %왼쪽 "*"  %%  입력     : expr { *표현 = $1; }     ;  expr     : expr[L] "+" expr[R] { $ = createOperation(작동작( 추가, L달러, R달러 ); }       expr[L] "*" expr[R] { $ = createOperation(작동작( 멀티플라이, L달러, R달러 ); }       "(" expr[E] ")"     { $ = E달러; }       "숫자"            { $ = create Number(작성번호)($1); }     ;  %%

바이슨에서 생성한 파서와 flex에서 생성된 스캐너를 사용하여 구문 트리를 얻는 데 필요한 코드는 다음과 같습니다. 

/* * main.c 파일 */  #실패하다 '표현상.h" #실패하다 파서.h" #실패하다 "Lexer.h"  #실패하다 <stdio.h>  인트 yyparse(섹션 **표현, 할 수 없다 스캐너);  섹션 *취득하다(컨스턴트 차 *expr) {     섹션 *표현;     할 수 없다 스캐너;     YY_BUFFER_상태 주;      한다면 (yylex_init(&스캐너)) {         /* 를 초기화할 수 없습니다.* /         돌아가다 특수한 순서;     }      주 = yy_scan_string(expr, 스캐너);      한다면 (yyparse(&표현, 스캐너)) {         /* 에러 해석 */         돌아가다 특수한 순서;     }      yy_delete_module(주, 스캐너);      yylex_module(스캐너);      돌아가다 표현; }  인트 평가하다(섹션 *e) {     전환하다 (e->유형) {         사례. 가치:             돌아가다 e->가치;         사례. 멀티플라이:             돌아가다 평가하다(e->왼쪽) * 평가하다(e->맞다);         사례. 추가:             돌아가다 평가하다(e->왼쪽) + 평가하다(e->맞다);         체납:             /*는 여기 있으면 안 돼요*/             돌아가다 0;     } }  인트 주된(무효) {     차 시험[] = " 4 + 2*10 + 3*( 5 + 1 )";     섹션 *e = 취득하다(시험);     인트 결과 = 평가하다(e);     인쇄물("%s의 결과는 %d입니다.\n", 시험, 결과);     deleteExpression(삭제식)(e);     돌아가다 0; }

프로젝트를 빌드하기 위한 간단한 makefile은 다음과 같습니다. 

# MakeFILE = Lexer.c Parser.c Expression.c main.c CC = g++ CFLAGS = -g -flash 테스트: $(FILES) $(CFLAGS) $(FILES) -o 테스트 Lexer.c: L플렉서 파서:

「 」를 참조해 주세요.

  • Berkeley Yacc(byacc) – GNU Bison과 동일한 작성자를 공유하는 또 다른 무료 소프트웨어 Yacc 대체 소프트웨어
  • ANTLR ANother Tool for Language Recognition, 또 다른 오픈 소스 파서 생성기

레퍼런스

  1. ^ a b Corbett, Robert Paul (June 1985). Static Semantics and Compiler Error Recovery (Ph.D.). University of California, Berkeley. DTIC ADA611756.
  2. ^ Akim Demaille (25 September 2021). "Bison 3.8.2".
  3. ^ "Language and Grammar (Bison 3.8.1)". www.gnu.org. Retrieved 2021-12-26.
  4. ^ 바이슨 매뉴얼:소개.
  5. ^ Levine, John (August 2009). flex & bison. O'Reilly Media. ISBN 978-0-596-15597-1.
  6. ^ "AUTHORS". bison.git. GNU Savannah. Retrieved 2017-08-26.
  7. ^ 바이슨 매뉴얼: 퓨어(리엔트런트) 파서
  8. ^ 바이슨 매뉴얼:바이슨 선언 개요
  9. ^ 바이슨 매뉴얼:바이슨 사용 조건
  10. ^ 예외 포함 소스 코드 파일 parse-gram.c
  11. ^ "parse-gram.y". bison.git. GNU Savannah. Retrieved 2020-07-29.
  12. ^ "LexerParser in CMake". github.com.
  13. ^ GCC 3.4 릴리즈 시리즈의 변경, 신기능 및 수정
  14. ^ GCC 4.1 릴리즈 시리즈의 변경, 신기능 및 수정
  15. ^ 골랑 문법 정의
  16. ^ "Parser.yy - GNU LilyPond Git Repository". git.savannah.gnu.org.
  17. ^ "4. Parsing SQL - flex & bison [Book]".
  18. ^ "GNU Octave: Libinterp/Parse-tree/Oct-parse.cc Source File".
  19. ^ "What is new for perl 5.10.0?". perl.org.
  20. ^ "The Parser Stage". postgresql.org. 30 September 2021.
  21. ^ "Ruby MRI Parser". github.com.
  22. ^ "syslog-ng's XML Parser". github.com. 14 October 2021.
  23. ^ a b Flex 매뉴얼: 웨이백 머신에 2010-12-17년 보관된 바이슨 파서를 갖춘 C 스캐너
  24. ^ 바이슨 매뉴얼: Pure Parser 호출 규칙

추가 정보

외부 링크