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

Presentation on theme: "제 8 장  파서 생성기 YACC 사용하기."— Presentation transcript:

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

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

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

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

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

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

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

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

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

10 규칙 기술부 구성 예 %% 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;

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

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

13 정수를 읽어서 사칙 연산을 수행하는 탁상용 계산기에 대한 파서와 의미 분석을 수행하는 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();  }

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

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

16 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); %}

17 연산자와 액션 %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; }

18 여러 함수 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);

19 여러 함수(계속) 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; }

20 여러 함수(계속) 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);

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

22 단계 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;

23 단계 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

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

25 단계 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 파일을 입력으로 실행한 결과를 출력한다.

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

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

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

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

30 실습 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)

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

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

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

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

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

36 제 8 장 끝