제 8 장  파서 생성기 YACC 사용하기

제 8 장  파서 생성기 YACC 사용하기 컴파일러를 프로그래밍 언어마다 각각 따로 만드는 것이 아니라, 문법만 있으면 LR 파싱 테이블을 자동으로 생성하는 도구인 YACC(Yet Another Compiler-Compiler)의 구조와 사용 방법을 살펴본다.

8.1 YACC 개요 그림 8.1 지금까지 살펴본 LR 파서 개념

문법에 따라 파싱 테이블 자동 생성 그림 8.2 파싱 테이블 자동 생성 개념이 포함된 LR 파서

YACC와 LEX의 연관 구동 그림 8.3 LEX와 YACC에 의한 프로그램 생성과 컴파일

YACC와 LEX 사이의 제어와 데이터 흐름 그림 8.4 YACC와 LEX 함수 사이의 제어와 데이터 흐름

8.2 YACC 스팩 YACC 스팩은 아래와 같이 선언부, 규칙 기술부, 지원 루틴부의 세부분으로 구성한다. 선언부 %%               선언부               %%               규칙 기술부

8.2.1 선언부 아래는 선언부를 구성하는 예이다. % { ... % } %token ID %left '+'  '-' %left '*' '/'   ....... 위는 토큰으로 받아들이는 것은 식별자 ID이며, 연산자는 *, /, +, -이며 왼쪽부터 차례로 우선순위를 가지는데 *, /를 같은 우선순위로,  +, -를 같은 우선순위로 사용한다.

8.2.2 규칙 기술부 넌터미널  :    α  {액션}               |β  {액션}                 |γ  {액션}                 .                 .                ;

규칙 기술부 구성 예 %% line : expression { printf("%d \n,$1); }; expression :  expression  '+'  expression   { $$ = $1 + $3; }                        |   expression  '-'  expression   { $$ = $1 - $3; }                        |   expression  '*'  expression   { $$ = $1 * $3; }                        |   expression  '/'  expression   { $$ = $1 /  $3; }                        |   '(' expression ')'   { $$ = $2; }                        |   a;

이 규칙 기술은 지금까지 본문에서 많이 사용하던 산술 수식 문법을 YACC에서 읽을 수 있도록 구성한 것이다.      E → E  +  E | E  -  E | E *  E | E /  E | ( E ) | a { 액션 } 부분의 { $$ = $1 - $3; } 파싱 도중에 생성 규칙을 환원할 때 의미 분석을 위해 호출되는 부분

8.2.3 지원 루틴부 지원 루틴부는 규칙 기술 규칙 기술부의 { 액션 }에서 호출하는 함수를 기술한다. 의미 분석을 위한 루틴 { 액션 }에서 지원 루틴부에 있는 해당 함수가 호출되어 구동

정수를 읽어서 사칙 연산을 수행하는 탁상용 계산기에 대한 파서와 의미 분석을 수행하는 YACC 스팩 예 % {      C 코드가 들어가는 부분 % } %token NUMBER %left '+'  '-' %left '*' '/' %% line :  expression  { printf("%d \n,$1); }; expression :  expression  '+'  expression   { $$ = $1 + $3; }                        |   expression  '-'  expression   { $$ = $1 - $3; }                        |   expression  '*'  expression   { $$ = $1 * $3; }                        |   expression  '/'  expression   { $$ = $1 /  $3; }                        |   '(' expression ')'   { $$ = $2; }                        |   NUMBER; main() {        yyparse();  }

입력 스트링 5 + 4 * 3를 파싱한 스택과 실행한 결과 값

8.2.4 YACC 스팩 예 수식에 대한 중간 코드를 생성하는 LEX와 YACC의 전체 스팩 LEX 프로그램 %% [a-zA-Z]       {yylval = alloc(TOKEN); return OPERAND;} [∖t]            ;               return  yytext[0]; ∖n           {lineno++;  return yytext[0];}

YACC 시작 /*  아래는 YACC 프로그램이다. YACC 에는 구문 에러를 수정하는 기능이 있지만 이 예에서는 취급하지 않는다.  */ %{ #include <stdio.h> #include <alloc.h> typedef char  * string; #define YYSTYPE  string;     /* 파싱 스택에 넣을 자료형(타입) 검사  */ #define  TOKEN  1 #define  TEMP 0 int  temp = 0; struct node  {                char  name[3];  /*  "Th" 혹은 a, b, c, ...*/                struct  node  * next;   /* 연결 리스트 */               }; struct node  * tlist = NULL;     /* 리스트 헤드  */ char  * alloc  (int type); %}

연산자와 액션 %token OPERAND %left '+' '-' %left '*' '/' %left UMINUS UPLUS %% list:                               /*  빈 리스트  */            | list  '∖n'            | list  expr  '∖n'    { clear( ); }            ; expr:      '+'  expr  %prec  UPLUS   { $$ = $2; }            | '-' expr  %prec  UMINUS   { $$ = alloc(TEMP); codegen ("umin", $2, $$, 0); }            | expr '+' expr   { $$ = alloc(TEMP); codegen ("add", $1, $3, $$); }            | expr '-' expr    { $$ = alloc(TEMP); codegen ("sub", $1, $3, $$); }            | expr '*' expr   { $$ = alloc(TEMP); codegen ("mul", $1, $3, $$); }            | expr '/' expr    { $$ = alloc(TEMP); codegen ("div", $1, $3, $$); }            | '('  expr  ')'    { $$ = $2; }            | OPERAND     { $$ = $1; }

여러 함수 char *progname; int lineno = 1; #include "lex.yy.c" main (int argc, char  *argv[ ]) {   progname = argv[0];   yyparse( ); } yyerror ( char *s)   fprintf(stderr, "%s[%d]: %s∖n", progname, lineno, s);

여러 함수(계속) char * alloc ( int type) { static struct node * last = NULL;   struct  node  * ptr;   static  char  t[3] = "  "; ptr = (struct  node  *) malloc (sizeof  (struct  node)); ptr->next = NULL; if (last != NULL)  {last->next = ptr; last  = ptr;}     else  tlist  = last  =  ptr; if (type == TEMP)     {       t[0] = 'T';       t[1] = '0'  + temp++;       strcpy (last->name, t);     }    else strcpy (last->name, yytext);    return (char  *)  last; }

여러 함수(계속) clear ( ) /* 할당된 메모리를 해제하고 다음 expr 을 위하여 카운터를 리셋한다 */ { struct node * ptr;   while (tlist)     { ptr = tlist->next;       free (tlist);       tlist = ptr;     }   temp = 0; } codegen (char * operation, * operand1, * operand2, * result) /* 중간코드를 출력하기  */ {   if (result)  /*  umin 가 한 개의 피연산자와 결과만 가지면  */        printf ("∖t %s  %s  %s  %s∖n",  operation, operand1, operand2, result);   else printf("∖t %s  %s  %s∖n",  operation, operand1, operand2);

8.3 YACC 실행하는 방법 YACC 실행을 위해 아래 산술 수식 문법을 인식하는 LEX와 YACC 스팩을 작성하고 실행하여 보자.              G : E → E  +  T                    E → T                    T → T  *  F                    T → F                    F → ( E )                    F → id

단계 1. 어휘 분석을 수행하기 위해 아래와 같은 test.l 이라는 LEX 스팩 파일을 만든다. cs% vi test.lex         %{         #include <stdio.h>         %}         ID [A-Za-z][A-Za-z0-9]*         %%         [\t ];         {ID}         {printf("%s : Identifier\n", yytext);}         "*"|"+"|"("|")"  {printf("%s : Operator \n", yytext);}         void main()         {           yylex();         }         int yywrap()           return 1;

단계 2. 어휘 분석을 수행하기 위해 아래와 같이 LEX를 실행한다.          cs% lex test.l ( lex.yy.c 라는 파일이 생성된다) 단계 3. 단계 2에서 생성한 lex.yy.c 라는 C 파일을 컴파일한다.          cs% cc lex.yy.c –ll ( a.out 이라는 파일이 생성된다) 단계 4. 문장 temp * ((i + j) * yy) 을 예로 하여 입력 파일 input.dat 을 작성한다.          cs% vi input.dat

단계 5. 입력 파일 input.dat 을 이용하여 a.out 를 실행한다. cs% a.out < input.dat 단계 6. 다음에는 구문 분석을 위해서 아래와 같이 test.y 라는 YACC 스팩 파일을 만든다.      cs% vi test.y

단계 7. 구문 분석을 수행한다.          cs% yacc -d  test.y ( y.tab.h, y.tab.c 파일을 생성한다) 단계 8. 위의 LEX 과정과 YACC 과정에서 생성된 C 파일을 컴파일한다.         cs% cc y.tab.c  lex.yy.c -ly -ll 이 결과에서 생성한 실행파일을 input.dat 파일을 입력으로 실행한 결과를 출력한다.

temp* ((i + j) * yy) 를 실행하는 과정 예

실습 8.1 위에서 사용한 문법을 아래와 같이 첨가 문법으로 수정하여 LEX와 YACC를 단계별로 다시 실행하고 결과를 분석하시오. 또 위의 예와 비교하시오.        G : E ' → E                    E → E  +  T                    E → T                    T → T  *  F                    T → F                    F → ( E )                    F → id 실습 8.1의 결과를 스스로 관찰하시오.

실습 8.2 실습 8.1에서 작성한 문법으로 아래 문장을 인식하는 LEX와 YACC 스팩을 작성하여 단계별로 실행하고 결과를 분석하시오.            a + k * ( b *(i + j)) 실습 8.2의 결과를 스스로 관찰하시오.

8.4 YACC 실습하기 실습 8.3 아래 YACC과 LEX를 실행하고 각 입력 스트링에 대한 출력 결과를 보이시오. 또 어느 입력 스트링에 대하여 구문 에러를 탐지하는지 실행하고 결과를 분석하시오. (1)  ㄱㄴ (2)  ㄴㄱㄷㄷ (3)  ㄱㄴㄴㄱㄷㄴㄷㄴ (4)  ㄴㄴㄱㄷㄴc  (5)  ㄴㄴㄱㄷㄴㄴ

실습 8. 4 다음 형식의 언어를 인식하는 파서를 생성하는 LEX 스팩과 YACC 스팩이다 E → E + T | T  T → T * F F → ( E) | id         (1)  a + k * ( b * (i + j)         (2)  a + b + c * knu         (3)  d + (as + j * l)

실습 8.5 정수 연산을 수행하는 탁상용 계산기를 LEX와 YACC 프로그램으로 구현하고 아래 각 수식을 입력하여 수행한 결과를 분석하시오. (1) 2 + 4 (2) 4 + 5 * 4 (3) ( 6 - 5 + 4) - (3 * 5 + 2) * 5 (4) -5 + 4 + (-3 - 2)

실습 8. 6 아래는 유동소수점 연산을 수행하는 탁상용 계산기를 LEX와 YACC 프로그램으로 구현하였다 실습 8.6 아래는 유동소수점 연산을 수행하는 탁상용 계산기를 LEX와 YACC 프로그램으로 구현하였다.아래 각 수식을 입력으로 계산하고 결과를 분석하시오. 그러나 이 프로그램은 여러 곳에 에러가 있어서 올바르게 작동하지 않을 것이다. LEX와 YACC의 구문 에러, C 프로그래밍 언어의 구문 에러, 실행 에러, 에러 메시지를 출력하지 않는 것 등이다. 이 에러를 찾아 수정하고 실행하시오. (1) 6 + 4.2e-2     (2) 4 * 3 - 2 / 0      (3) (4 + 8) * 6 / 3  (4) 6 / (12 * 4 - 7 * 2.3)

실습 8. 7 어떤 수식을 파스 트리로 변환하는 YACC 프로그램을 작성하시오 실습 8.7 어떤 수식을 파스 트리로 변환하는 YACC 프로그램을 작성하시오. 피연산자는 단일 문자나 숫자이고, 연산자는 일반적인 우선순위를 가지는 더하기, 빼기, 곱하기, 나누기이다. yylex( ) 함수는 LEX로 만들거나 C로 직접 작성한다. 입력은 아래 각 줄에 있는 수식이고 stdout 에 파스트리를 전위 표기 형식으로 출력하시오(아래와 같이 출력하여야 한다). 입력(중위 수식)       파스 트리출력 (전위 수식) (1)  (8 + a) * b           * + 8 a b (2)  7 + a * b            + 7 * a b

실습 8.8 아래와 같은 형식의 언어를 인식하는 구문 분석기를 작성하시오.    Exp → Exp Op Exp | ( Exp ) | Number         Op → + | - | * Number →  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

실습 8.10 일반적으로 많이 사용하는 데이터베이스 명령어의 문법을 검사하는 구문 분석기를 YACC와 LEX를 이용하여 구현하시오. 이 구문 분석기에서는 최소한 아래 명령어는 취급하여야 한다.        RETRIEVE  학생성적파일        DISPLAY  FOR  성적  >=  90        PRINT FOR  이름 = "최하늘"

제 8 장 끝