[프로그래밍 언어론/Programming Language] flex & bison 으로 파서 만들기

728x90

프로그래밍 언어를 처리하는 과정에서 가장 중요한 단계 중 하나는 입력을 분석하는 것이다.
이때 입력을 의미 있는 단위로 나누고, 문법에 맞게 해석하는 과정이 필요하다.

이벌 글에서는 flex와 bison을 활용한 파서 생성 과정을 단계별로 정리해보고자 한다.

 

1. flex란 무엇인가?

flex는 어휘 분석기(Lexical Analyzer)를 생성하는 도구이다.

즉, 입력 문자열을 읽어서 다음과 같은 과정을 수행한다.

• 문자열을 lexeme(어휘 단위)로 분해
• 각 lexeme을 토큰(token)으로 변환

예를 들어:

input: a = b + 3

 

→ 토큰 단위로 분해

ID(a), ASSIGN, ID(b), PLUS, NUMBER(3)

 

이 과정이 바로 lexical analysis이다.

 

2. flex 파일 구조 (.l)

flex는 .l 파일을 기반으로 동작하며, 구조는 다음과 같다.

%{
    // 정의절 1 (C 코드)
%}
    // 정의절 2 (정규식 매크로)

%%
    // 규칙절
%%
    // 사용자 코드 (main 등)

 

2.1 정의절

• 헤더파일, 전역 변수 정의
• 정규식 패턴을 이름으로 정의

%{
#include <stdio.h>
%}

DIGIT   [0-9]

 

2.2 규칙절

 

핵심 부분이다.
패턴 → 실행 코드 형태로 작성한다.

[0-9]+ { printf("NUMBER\n"); }
[a-zA-Z]+ { printf("ID\n"); }

 

특징:

• 위에서부터 순서대로 매칭
• yytext를 통해 현재 토큰 접근 가능

2.3 사용자 서브루틴

• main() 정의
• yylex() 호출 → 어휘 분석 시작

int main() {
   yylex();
   return 0;
}

 

 

3. flex 컴파일 방법

리눅스 기준:

flex -o lex.yy.c ex01.l
gcc -o ex01 lex.yy.c
./ex01

 

4. bison이란 무엇인가?

bison은 구문 분석기(Parser)를 생성하는 도구이다.

• CFG(Context-Free Grammar) 기반
• LR(1) 파서 생성

flex가 토큰을 만든다면,
bison은 그 토큰을 이용해서 문법 구조를 해석한다.

 

 

5. flex + bison 동작 구조

전체 흐름은 다음과 같다.

입력 → flex → 토큰 → bison → 파싱 결과

 

조금 더 자세히 보면:

• yylex() → 토큰 생성
• yyparse() → 문법 분석

5.1 파서 생성 과정

1. 파서 생성 시 .y 파일에 main() 함수와 토큰 정의 포함. .l 파일에는 #include “y.tab.h”
2. “bison -d” 명령어 입력 ⇒ y.tab.h 파일에 토큰 리스트 생성
   따라서 , flex 파일과 bison 파일이 동일한 토큰을 사용 가능
3. bison의 출력 파일인 y.tab.c을 C언어 컴파일러로 컴파일 => yyparse() 사용 가능

 

6. bison 파일 구조 (.y)

bison 파일은 .y 확장자를 사용하며 다음과 같은 구조를 가진다.

6.1 헤더파일 및 함수 선언부

6.2 토큰, 타입, 값 타입 정의

 

6.3 문법 규칙 작성

예시:

expr:
expr '+' expr { printf("add\n"); }
| NUMBER
;

• CFG 기반으로 문법 정의
• 각 규칙마다 action 코드 작성 가능

액션 정의

• C 함수 정의부

7. 전체 컴파일 과정

예: ex02.l, ex02.y

bison -d ex02.y
flex ex02.l
gcc lex.yy.c y.tab.c -o parser
./parser

 

8. 핵심 정리

• flex
  • 입력 → 토큰
  • 어휘 분석 담당
• bison
  • 토큰 → 문법 구조
  • 구문 분석 담당
• 둘을 함께 사용하면:
  • 간단한 프로그래밍 언어 파서 구현 가능

 

 

flex와 bison 에 대해서 알아보았다.

프로그래밍 언어 강의를 수강하면서 어렵고 헷갈리는 부분이 많았는데 공부하면서 새롭게 알게된 부분이 있다면 수정해 놓을 예정이다.