Lex 와 Yacc

1. Lex와 Yacc

Lex는 어휘 분석기이며

Yacc는 구문 분석기이다.

 

Lex는 특정 패턴의 문자열 토큰을 찾는 것, Yacc는 해당 토큰들의 관계를 분석하여 구문 검사를 하는 것으로 구분 되어있다.

이 2가지를 같이 사용하여 컴파일러와 인터프리터 등을 만들기 위해 사용된다.

 

2. Lex

Lex는 어휘 분석기를 읽어와서, Lexer를 만든 뒤 이를 C 언어로 만들어진 소스 코드의 형태로 출력한다.

Lex는 저작권이 있는 소프트웨어로 시작했지만, AT&T의 소스 코드에 기반하는 버전은 오픈 소스 정책을 따라 오픈 솔라리스 등에서 사용된다. 이외에도 유명한 오픈 소스 버전의 Lex로는 빠른 Lex(Fast Lex)라는 의미의 flex가 존재한다.

 

이 Lex는 3가지의 부분으로 구성된다.

해당 Section들은 아래와 같이 %% 로 분리하며, definition과 C Code Section은 생략될 수 있다.

{Definitions}
%%
{Rules}
%%
{C Code}

2-1. Definition section

아래와 같이 3가지로 구성된다.

2-1-1. Literal block

%{ 로 시작하여 %}로 끝나며, C언어의 include, 변수 선언, 함수 선언 등을 한다.

이 Block 안의 내용은 Lex에 의해 검사하지 않고 c 코드로 들어가게 된다.

예를 들면 아래와 같다.

%{
#include <stdio.h>
%}

2-1-2. Start state code

State를 지정해준다.

%s로 시작하며 띄어쓰기로 각 State의 이름을 구분한다.

여기서 지정된 State들은 Rules Section에서 사용된다. 자세한 내용은 Rules Section을 참조.

%s S_INITIAL S_INT STATE_FINAL

2-1-3. definitions

정규 표현식과 이름을 지정하는 곳이다.

예를 들면 아래와 같다.

varname [A-Za-z_][A-Za-z0-9_]*
integer [0-9]+

%%

해당 부분이 끝나면 새로운 줄에 %% 를 적어 끝났음을 알려준다.

2-2. Rules Section

지정된 토큰을 발견했을 때, 어떻게 처리해야하는지를 정의한다.

먼저 정규표현식을 적고(패턴 파트), 해당 정규표현식을 어떻게 처리할 지를 적는다. (액션파트)

1-3. 에서 정의한 정규 표현식의 이름을 사용할 수 있고,

1-2.에서 정의한 STATE를 사용하여 현재 STATE를 지정할 수 있다.

해당 Section이 끝나면 %% 로 끝났음을 알려준다.

integer  {
            /* yytext is a string containing the matched text. */
            printf("Saw an integer: %s\n", yytext);
            BEGIN S_INT;
        }

varname    ECHO; /* Echo varname. */

.|\n    { /* Ignore all other characters. */ }

%%

2-3. Code Section

C언어로 User Code를 작성한다.

중요한 것은 yylex() 함수이다.

yylex 함수는 lexer를 호출하는 것이다.

아래는 lexer를 호출한 뒤에 종료하는 예제이다.

int main(void)
{
    /* Call the lexer, then quit. */
    yylex();
    return 0;
}

3. Lex와 Yacc의 관계(Lex scanner, Yacc parser)와 yylex()함수

일반적으로 Lex (Scanner)와 Yacc (Parser)는 같이 구현한다.

그리고 Lex의 상위에 Yacc를 구현한다.

Lex는 입력 문자열에 대한 일차적인 검색을 하고 Yacc가 실제적인 분석을 하는 것이다.

Yacc에서 입력에 대한 토큰이 필요하면 Lex에서 제공하는 yylex() 라는 함수를 호출하여 입력된 토큰들의 배열이 주어진 문법에 맞는지 체크하면서 실행을 하는 것이다.

 

그 과정을 정리해보면 yacc에서 yyparse() 라는 함수가 구문분석기를 부르고, yyparse() 함수는 yylex()라는 lexer

yacc의 yyparse() 함수 호출하여 Parser를 부름

-> 구문분석기는 yylex() 함수 호출하여 Scanner (어휘분석기, lexer)를 부름

-> Scanner는 처리 단위의 토큰을 돌려줌.

-> Parser는 해당 토큰에 대한 처리를 함.

이러한 과정이 반복되는 것이다.

 

여기서 yylex() 함수가 Entry point를 지정해주어서 새로 호출할 때마다, 해당 위치에서 시작할 수 있도록 해준다.

 

4. Yacc

기본적인 구조는 Lex와 같은 구조를 가진다.

{Definitions}
%%
{Rules}
%%
{C Code}

단, Yacc는 Lex의 yylex() 함수를 호출하여 토큰(스캔된 결과물)을 넘겨 받는다.

4-1. Definitions

Definitions에서는 다음과 같은 정의를 한다.

4-1-1. Literal Block

Lex와 마찬가지로 Literal Block을 정의할 수 있다. Lex와 동일하게 이 Block 안의 내용은 Yacc가 검사하지 않고 C 코드에 들어가게 된다.

%{
#include <stdio.h>
%}

4-1-2. Union

구조체를 정의하며, 이 구조체는 union 구조체 형태로 C 파일에서 선언된다.

이 것을 사용하지 않으면 기본 타입으로 int를 사용한다.

여기서 지정되는 type의 이름은 %token, %type 에서 지정할 수 있다.

%union {
    const char* str;
    Token* token;
}

4-1-2. Token

Yacc는 Lex와 커뮤니케이션 하기 위해 여러 개의 토큰 아이디를 지정한다.

yylex() 함수에서 이 토큰 값들을 리턴 값으로 사용 될 수 있으며, 이 아이디에 따라 액션을 지정 할 수 있다.

%token <str> VARNAME COMMENT INTEGER FLOAT
%token CLASS JAVA OBJECT COLON SEMI_COLON

이 경우 첫 번째 줄 처럼 data type을 지정해주는 경우, Union에 등록되어 있는 것만 사용이 가능하다.

이 토큰 아이디들은 yylex() 함수에서 리턴 값으로 사용 될 수 있으며, Yacc는 아이디에 따라 액션을 달리 지정 할 수 있다.

4-1-3. Type

토큰과 토큰의 관계를 정의한 규칙 혹은 이 규칙의 집합을 statement라고 한다.

Type은 statement의 데이터를 저장 할 수 있는 데이터 타입을 지정해준다.

%type <token> classStmt choiceStmt setStmt includeStmt typedefStmt
%type vartype varDeclare VarDeclares

%%

Token과 마찬가지로 data type이 지정되는 경우에는 Union에 등록되어 있는 것만 사용할 수 있다.

 

새로운 줄에 %%를 넣어 Definition Section 종료를 알린다.

 

4-2. Rules Section

Lex와 마찬가지로 지정된 토큰을 발견하였을 때, 처리하는 법을 정의한다.

단, Yacc에서는 Lex로 부터 넘어온 토큰 중 앞서 정의했던 관계를 발견했을 때 액션을 실행한다.

 

아래와 같이 지정된 문법을 파싱 하였을 때 어떻게 동작해야 하는 지에 대해서 정의한다.

이름

  : TOKEN 관계 1 { 액션 1 }

  : TOKEN 관계 2 { 액션 2 }

;

STATEMENTNAME
    : TOKEN1 TOKEN2 TOKEN3 { printf("yacc : action1 : %s, %d, %s\n", $1, $2, $3); $$ = $1; }
    | TOKEN1 TOKEN3 TOKEN2 { printf("yacc : action2 : %s, %s, %d\n", $1, $2, $3); $$ = $1; }
;

STATEMENTNAME에 이름을 정의한다.

2번쨰 줄의 TOKEN1 TOKEN2 TOKEN3은 관계를 의미한다.

여기서는 이 순서로 왔을 때, action1을 출력하도록 했다.

$1 $2 $3는 순서대로 각 토큰의 값을 저장한 값이다.

$$는 

 

4-3. C Code Section

Lex와 같다. 단, yyparse()가 yylex()를 호출한다.

 

 

 

참고: ko.wikipedia.org/wiki/Lex (Lex 위키피디아) ko.wikipedia.org/wiki/Yacc (Yacc 위키피디아)