GNU bison
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
GNU Bison은 Yacc와의 호환성을 가지는 파서 생성기이다. LALR 파싱을 기반으로 하며, 모호한 문법에 대해서는 GLR 파싱이나 IELR 파싱을 지원한다. C, C++, D, 자바 코드를 생성할 수 있으며, flex와 함께 사용되어 컴파일러, 인터프리터 등의 개발에 활용된다. Bison은 재진입 파서를 생성할 수 있으며, 충돌 해결을 돕기 위해 반례를 자동으로 생성하는 기능을 제공한다. 생성된 코드의 라이선스는 GNU 일반 공중 사용 허가서(GPL)에 따르며, Bison을 사용하는 프로젝트는 입력 파일과 생성된 코드를 모두 배포하거나, 생성된 코드만 배포하는 것을 선택할 수 있다.
더 읽어볼만한 페이지
- 구문 분석기 - ANTLR
ANTLR은 EBNF로 표현된 문법을 입력받아 렉서, 파서, 트리 파서 등 다양한 언어 인식기 소스 코드를 생성하는 파서 생성기이며, C#, Java, Python 등 여러 언어를 지원하고 깃허브에 다양한 문법이 공개되어 있다. - 구문 분석기 - Yacc
Yacc은 주어진 문법 규칙에 따라 C 언어 파서를 생성하는 도구로, 컴파일러 개발에 널리 사용되어 다양한 언어 구현에 활용되었으며, Lex와 함께 어휘 및 구문 분석을 수행하며 여러 파생 버전으로 현재까지 활용되고 있다. - 컴파일러 - 바이너리 재컴파일러
- 컴파일러 - 링커 (컴퓨팅)
링커는 여러 모듈로 된 목적 파일을 결합해 실행 가능한 프로그램을 만들고, 정적/동적 링킹으로 라이브러리를 연결하며, 심볼 해결 및 재배치로 변수와 함수를 메모리 주소에 연결하는 소프트웨어 도구이다. - GNU 프로젝트 소프트웨어 - GNU 코어 유틸리티
GNU 코어 유틸리티는 유닉스 계열 운영체제에서 파일, 셸, 텍스트 조작을 위한 기본적인 명령어 모음으로, GNU 파일 유틸리티에서 시작하여 3개의 패키지가 통합되어 발전했으며 셸 스크립트 및 시스템 관리에 필수적인 도구를 제공한다. - GNU 프로젝트 소프트웨어 - GNU 허드
GNU 허드는 유닉스 운영 체제를 대체하는 것을 목표로 개발된 GNU 프로젝트의 커널로, 마이크로커널 기반의 서버-클라이언트 아키텍처를 사용하며, 파일 시스템 기능을 확장하는 트랜슬레이터 개념을 제공한다.
| GNU bison - [IT 관련 정보]에 관한 문서 | |
|---|---|
| 기본 정보 | |
 | |
| 종류 | 파서 생성기 |
| 라이선스 | GPL (자유 소프트웨어) |
| 웹사이트 | GNU Bison 공식 웹사이트 |
| 개발 | |
| 개발자 | 로버트 코벳(Robert Corbett) 및 GNU 프로젝트 |
| 최초 릴리스 | 1985년 6월 |
| 최신 안정화 버전 | 3.8.1 |
| 최신 안정화 버전 출시일 | 2021년 9월 11일 |
| 프로그래밍 언어 | C, m4 |
| 운영 체제 | 유닉스 계열 |
| 플랫폼 | 크로스 플랫폼 |
2. 특징
Bison은 FLex와 함께 로렌스 버클리 국립 연구소의 Vern Paxson이 제작했으며, Yacc와의 상위 호환성을 가지면서도 재진입 가능한 파서 생성을 지원하는 등 많은 확장 기능이 추가되었다.[1]
원래 C 언어 컴파일러인 GCC의 프론트 엔드 구문 분석용으로 제작되었으나, 현재 GCC(버전 4 이후)는 자체적으로 구문 분석을 수행하므로 Bison은 주로 단독 프로그래밍 도구로 사용된다.
Bison은 일반적으로 LALR 파싱 기반 구문 분석기를 생성하지만, 모호한 문법에 대해서는 GLR 파싱이나 IELR 파싱 기반 구문 분석기를 생성할 수도 있다.
Barkeley Yacc 등, Bison 외에도 Yacc와의 상위 호환성을 가진 소프트웨어가 있으며, bison의 상위 호환인 bison++, 그리고 그 상위 호환인 bisonc++도 있다.
2. 1. 반례 생성
LR 파서 생성기의 섬세한 문제 중 하나는 충돌(shift/reduce 및 reduce/reduce 충돌) 해결이다. 많은 LR 파서 생성기에서 충돌을 해결하려면 파서 오토마톤을 분석해야 하며, 이 작업에는 사용자의 전문 지식이 필요하다.Bison은 사용자가 충돌을 더 직관적으로 이해하도록 돕기 위해 자동으로 반례를 생성할 수 있다. 모호한 문법의 경우, Bison은 종종 문법이 모호함을 보여주는 반례를 생성할 수도 있다.
예를 들어, 악명 높은 dangling else 문제를 겪는 문법에서 Bison은 다음과 같이 보고한다.[1]
```
doc/if-then-else.y: 경고: 토큰 "else"에서 shift/reduce 충돌 [-Wcounterexamples]
예시: "if" expr "then" "if" expr "then" stmt • "else" stmt
Shift 유도
if_stmt
↳ "if" expr "then" stmt
↳ if_stmt
↳ "if" expr "then" stmt • "else" stmt
예시: "if" expr "then" "if" expr "then" stmt • "else" stmt
Reduce 유도
if_stmt
↳ "if" expr "then" stmt "else" stmt
↳ if_stmt
↳ "if" expr "then" stmt •
2. 2. 재진입성 (Reentrancy)
재진입성은 바이슨에 추가된 기능으로, Yacc에는 존재하지 않는다.[1]일반적으로 바이슨은 재진입하지 않는 파서를 생성한다.[1] 재진입성을 달성하려면 `%define api.pure` 선언을 사용해야 한다.[1] 바이슨 재진입성에 대한 자세한 내용은 바이슨 매뉴얼에서 확인할 수 있다.[1]
Bison은 FLex와 함께 로렌스 버클리 국립 연구소의 Vern Paxson이 제작했으며,[1] Yacc와의 상위 호환성을 가지면서도, 많은 확장 기능이 추가되어 재진입 가능한 파서의 생성이 가능하다.[1]
2. 3. 출력 언어
Bison은 C, C++, D 및 자바용 코드를 생성할 수 있다.[7] Bison으로 생성된 파서를 다른 언어에서 사용하기 위해 SWIG와 같은 언어 바인딩 도구를 사용할 수 있다.3. 생성 코드의 라이선스 및 배포
Bison은 다른 소프트웨어 프로젝트의 소스 코드에 추가되는 소스 코드를 생성하기 때문에, 간단하지만 흥미로운 저작권 문제를 제기한다.[1]
3. 1. GPL 호환 라이선스
Bison은 다른 소프트웨어 프로젝트의 소스 코드에 추가되는 소스 코드를 생성하기 때문에, 간단하지만 흥미로운 저작권 문제를 제기한다. Bison이 생성한 코드는 Bison 프로젝트 자체의 상당한 양의 코드를 포함하고 있다. Bison 패키지는 GNU 일반 공중 사용 허가서(GPL)에 따라 배포되지만, GPL이 출력물에 적용되지 않도록 예외 조항이 추가되었다.[8][9]Bison의 이전 릴리스에서는 출력물에 원본 소스 코드의 yyparse() 함수가 포함되어 있었기 때문에 출력물의 일부도 GPL에 따라 라이선스가 부여되었다.
3. 2. Bison을 사용하는 패키지 배포
Bison은 다른 소프트웨어 프로젝트의 소스 코드에 추가되는 소스 코드를 생성하기 때문에, 간단하지만 흥미로운 저작권 문제를 제기한다.[1]Bison을 사용하는 자유 소프트웨어 프로젝트는 프로젝트가 Bison에 제공하는 소스 코드 또는 Bison에서 출력된 결과 C 코드를 배포할지 여부를 선택할 수 있다.[1] 두 가지 모두 수신자가 프로젝트 소스 코드를 컴파일할 수 있을 만큼 충분하다.[1] 그러나 입력을 배포하는 것은 수신자가 프로젝트를 컴파일할 때 필요한 C 코드를 생성할 수 있도록 Bison의 호환 가능한 사본을 설치해야 한다는 약간의 불편함을 수반한다.[1] 또한 출력에 C 코드만 배포하면 이 코드가 사람이 ''직접'' 작성한 것도 아니고, 사람 ''을 위해'' 작성된 것도 아니기 때문에 수신자가 파서를 수정하기가 매우 어려워지는 문제가 발생한다.[1] 즉, C 컴파일러에 직접 제공하기 위한 것이다.[1]
이러한 문제는 입력 파일과 생성된 코드를 모두 배포함으로써 피할 수 있다.[1] 대부분의 사람들은 다른 소프트웨어 패키지와 마찬가지로 생성된 코드를 사용하여 컴파일하지만, 파서 구성 요소를 수정하려는 사람은 먼저 입력 파일을 수정하고 컴파일하기 전에 생성된 파일을 다시 생성할 수 있다.[1] 둘 다 배포하는 프로젝트는 일반적으로 생성된 파일을 버전 관리 시스템에 두지 않는다.[1] 파일은 릴리스를 만들 때만 생성된다.[1]
GPL과 같은 일부 라이선스는 소스 코드가 "''작업을 수정하기 위한 선호되는 형식''"이어야 한다고 요구한다.[1] 따라서 Bison을 사용하는 GPL 프로젝트는 Bison의 입력 파일인 파일을 배포해야 한다.[1] 물론 생성된 파일도 포함할 수 있다.[1]
4. 활용
Bison은 Yacc를 대체하기 위해 작성되었고, 광범위하게 호환되므로 Bison을 사용하는 많은 프로젝트의 코드는 Yacc에도 똑같이 제공될 수 있다. 이 때문에 프로젝트가 Bison 고유의 소스 코드를 "사용"하는지 여부를 결정하기가 어렵다. 많은 경우, Bison의 "사용"은 Yacc 또는 다른 파생 제품을 동등하게 사용하는 것으로 간단히 대체될 수 있다.[10]
Bison은 Yacc에서는 찾을 수 없는 기능을 가지고 있으므로, Yacc으로는 충분하지 않기 때문에 일부 프로젝트는 Bison을 실제로 "사용"한다고 말할 수 있다.
다음 목록은 Bison 호환 패키지나 Bison에 제공될 코드를 배포하고, 자유 소프트웨어 개발 도구를 사용한다는 점에서, 느슨한 의미로 Bison을 "사용"하는 것으로 알려진 프로젝트이다.
| 프로젝트 | 설명 |
|---|---|
| Bash 셸 | 명령 입력을 구문 분석하기 위해 yacc 문법을 사용한다. |
| Bison | 자체의 문법 파서는 Bison에 의해 생성된다.[10] |
| CMake | 여러 개의 Bison 문법을 사용한다.[11] |
| GCC | Bison을 사용하기 시작했지만, 2004년(버전 3.4)에 C++용으로, 2006년(버전 4.1)에 C와 Objective-C용으로 손으로 작성된 재귀 하향식 파서로 전환했다.[12][13] |
| Go 프로그래밍 언어 (GC) | Bison을 사용했지만, 버전 1.5에서 손으로 작성된 스캐너와 파서로 전환했다.[14] |
| LilyPond | 파서를 생성하기 위해 Bison이 필요하다.[15] |
| MySQL | [16] |
| GNU Octave | Bison으로 생성된 파서를 사용한다.[17] |
| Perl 5 | 5.10부터 Bison으로 생성된 파서를 사용한다.[18] |
| PHP 프로그래밍 언어(Zend 파서) | |
| PostgreSQL | [19] |
| Ruby MRI, Ruby 프로그래밍 언어의 참조 구현 | Bison 문법에 의존한다.[20] |
| syslog-ng | 함께 조립된 여러 개의 Bison 문법을 사용한다.[21] |
5. 재진입 파서 예제
Bison은 일반적으로 재진입하지 않는 파서를 생성하지만, `%define api.pure` 선언을 통해 재진입성을 확보할 수 있다.[22] 다음은 Bison과 Flex를 사용하여 덧셈과 곱셈 연산을 지원하는 간단한 계산기 프로그램과 추상 구문 트리를 만드는 예제이다.
구문 트리 함수 정의 및 구현을 위한 두 파일(`Expression.h`, `Expression.c`)은 다음과 같다.
/*
#ifndef __EXPRESSION_H__
#define __EXPRESSION_H__
/**
typedef enum tagEOperationType
{
eVALUE,
eMULTIPLY,
eADD
} EOperationType;
/**
typedef struct tagSExpression
{
EOperationType type; /* /< 연산 유형 */
int value; /* /< type이 eVALUE일 때만 유효함 */
struct tagSExpression *left; /* /< 트리의 왼쪽 */
struct tagSExpression *right; /* /< 트리의 오른쪽 */
} SExpression;
/**
SExpression *createNumber(int value);
/**
SExpression *createOperation(EOperationType type, SExpression *left, SExpression *right);
/**
void deleteExpression(SExpression *b);
#endif /* __EXPRESSION_H__ */
/*
#include "Expression.h"
#include
/**
static SExpression *allocateExpression()
{
SExpression *b = (SExpression *)malloc(sizeof(SExpression));
if (b == NULL)
return NULL;
b->type = eVALUE;
b->value = 0;
b->left = NULL;
b->right = NULL;
return b;
}
SExpression *createNumber(int value)
{
SExpression *b = allocateExpression();
if (b == NULL)
return NULL;
b->type = eVALUE;
b->value = value;
return b;
}
SExpression *createOperation(EOperationType type, SExpression *left, SExpression *right)
{
SExpression *b = allocateExpression();
if (b == NULL)
return NULL;
b->type = type;
b->left = left;
b->right = right;
return b;
}
void deleteExpression(SExpression *b)
{
if (b == NULL)
return;
deleteExpression(b->left);
deleteExpression(b->right);
free(b);
}
Bison 파서에 필요한 토큰은 Flex를 사용하여 생성한다(`Lexer.l`).
%{
/*
#include "Expression.h"
#include "Parser.h"
#include
%}
%option outfile="Lexer.c" header-file="Lexer.h"
%option warn nodefault
%option reentrant noyywrap never-interactive nounistd
%option bison-bridge
%%
[ \r\n\t]* { continue; /* 공백을 건너뜁니다. */ }
[0-9]+ { sscanf(yytext, "%d", &yylval->value); return TOKEN_NUMBER; }
"*" { return TOKEN_STAR; }
"+" { return TOKEN_PLUS; }
"(" { return TOKEN_LPAREN; }
")" { return TOKEN_RPAREN; }
. { continue; /* 예상치 못한 문자를 무시합니다. */}
%%
int yyerror(SExpression **expression, yyscan_t scanner, const char *msg) {
fprintf(stderr, "Error: %s\n", msg);
return 0;
}
Flex와 파서 간의 통신에 사용되는 데이터 타입 `YYSTYPE`은 Bison의 `%union` 선언을 사용하여 설정한다. `yylex` 함수에 매개변수를 제공하기 위해 Bison의 `%lex-param` 및 `%parse-param` 선언을 사용한다.[23]
%{
/*
#include "Expression.h"
#include "Parser.h"
#include "Lexer.h"
// Lexer.l에서 제공된 구현을 참조합니다.
int yyerror(SExpression **expression, yyscan_t scanner, const char *msg);
%}
%code requires {
typedef void* yyscan_t;
}
%output "Parser.c"
%defines "Parser.h"
%define api.pure
%lex-param { yyscan_t scanner }
%parse-param { SExpression **expression }
%parse-param { yyscan_t scanner }
%union {
int value;
SExpression *expression;
}
%token TOKEN_LPAREN "("
%token TOKEN_RPAREN ")"
%token TOKEN_PLUS "+"
%token TOKEN_STAR "*"
%token
%type
/* 우선순위(증가) 및 결합성:
a+b+c는 (a+b)+c입니다: 왼쪽 결합성
a+b*c는 a+(b*c)입니다: "*"의 우선순위는 "+"보다 높습니다. */
%left "+"
%left "*"
%%
input
: expr { *expression = $1; }
;
expr
: expr[L] "+" expr[R] { $$ = createOperation( eADD, $L, $R ); }
| expr[L] "*" expr[R] { $$ = createOperation( eMULTIPLY, $L, $R ); }
| "(" expr[E] ")" { $$ = $E; }
| "number" { $$ = createNumber($1); }
;
%%
Bison과 Flex로 생성된 파서와 스캐너를 사용하여 구문 트리를 얻는 코드는 다음과 같다(`main.c`).
/*
#include "Expression.h"
#include "Parser.h"
#include "Lexer.h"
#include
int yyparse(SExpression **expression, yyscan_t scanner);
SExpression *getAST(const char *expr)
{
SExpression *expression;
yyscan_t scanner;
YY_BUFFER_STATE state;
if (yylex_init(&scanner)) {
/* could not initialize */
return NULL;
}
state = yy_scan_string(expr, scanner);
if (yyparse(&expression, scanner)) {
/* error parsing */
return NULL;
}
yy_delete_buffer(state, scanner);
yylex_destroy(scanner);
return expression;
}
int evaluate(SExpression *e)
{
switch (e->type) {
case eVALUE:
return e->value;
case eMULTIPLY:
return evaluate(e->left) * evaluate(e->right);
case eADD:
return evaluate(e->left) + evaluate(e->right);
default:
/* should not be here */
return 0;
}
}
int main(void)
{
char test[] = " 4 + 2*10 + 3*( 5 + 1 )";
SExpression *e = getAST(test);
int result = evaluate(e);
printf("Result of '%s' is %d\n", test, result);
deleteExpression(e);
return 0;
}
프로젝트 빌드를 위한 Makefile은 다음과 같다.
# Makefile
FILES = Lexer.c Parser.c Expression.c main.c
CC = g++
CFLAGS = -g -ansi
test: $(FILES)
$(CC) $(CFLAGS) $(FILES) -o test
Lexer.c: Lexer.l
flex Lexer.l
Parser.c: Parser.y Lexer.c
bison Parser.y
clean:
rm -f *.o *~ Lexer.c Lexer.h Parser.c Parser.h test
6. 같이 보기
- Flex
- yacc
- GLR 파싱
- IELR 파싱
- LALR 파싱
- GCC
참조
[1]
웹사이트
Language and Grammar (Bison 3.8.1)
https://www.gnu.org/[...]
2021-12-26
[2]
문서
Bison Manual: Introduction.
https://www.gnu.org/[...]
[3]
서적
flex & bison
http://oreilly.com/c[...]
O'Reilly Media
2009-08
[4]
학위논문
Static Semantics and Compiler Error Recovery
University of California, Berkeley
1985-06
[5]
웹사이트
AUTHORS
http://git.savannah.[...]
2017-08-26
[6]
문서
Bison Manual: A Pure (Reentrant) Parser
https://www.gnu.org/[...]
[7]
문서
Bison Manual: Bison Declaration Summary
https://www.gnu.org/[...]
[8]
문서
Bison Manual: Conditions for Using Bison
https://www.gnu.org/[...]
[9]
문서
A source code file, parse-gram.c, which includes the exception
http://git.savannah.[...]
[10]
웹사이트
parse-gram.y
http://git.savannah.[...]
2020-07-29
[11]
웹사이트
LexerParser in CMake
https://github.com/K[...]
[12]
문서
GCC 3.4 Release Series Changes, New Features, and Fixes
https://gcc.gnu.org/[...]
[13]
문서
GCC 4.1 Release Series Changes, New Features, and Fixes
https://gcc.gnu.org/[...]
[14]
문서
Golang grammar definition
https://forum.golang[...]
[15]
웹사이트
Parser.yy - GNU LilyPond Git Repository
https://git.savannah[...]
[16]
웹사이트
4. Parsing SQL - flex & bison [Book]
https://www.safaribo[...]
[17]
웹사이트
GNU Octave: Libinterp/Parse-tree/Oct-parse.cc Source File
http://octave.org/do[...]
[18]
웹사이트
What is new for perl 5.10.0?
http://perldoc.perl.[...]
perl.org
[19]
웹사이트
The Parser Stage
https://www.postgres[...]
postgresql.org
2021-09-30
[20]
웹사이트
Ruby MRI Parser
https://github.com/r[...]
[21]
웹사이트
syslog-ng's XML Parser
https://github.com/s[...]
2021-10-14
[22]
문서
Flex Manual: C Scanners with Bison Parsers
http://flex.sourcefo[...]
[23]
문서
Bison Manual: Calling Conventions for Pure Parsers
https://www.gnu.org/[...]
[24]
웹사이트
Bison ダウンロードサイト
https://lists.gnu.or[...]
2020-09-13
[25]
문서
3.0.2版配布物件のpoディレクトリーによる。
[26]
문서
Bisonの仕様のベースとなった「[[Yacc]]」の項を参照。
[27]
학위논문
Static Semantics and Compiler Error Recovery
University of California, Berkeley
1985-06
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com