여기서 작성하는 계산기는 커맨드라인에서 기동시켜 키보드에서 식을 입력하면 값을 출력하는 프로그램이다. 커맨드명은 mycalc로 한다. 실행 예는 아래와 같다.

 

입력

1 + 2 * 3

 

실행

% mycalc     ←mycalc의 기동
1+2              ←식 입력
>>3.000000   ←결과 출력
1+2*3           ←가산과 승산의 혼재
>>7.000000   ←우선순위를 판단해서 계산

정수를 사용했는데 출력이 「3.000000」가 되는 것은 mycalc는 내부적인 계산을 모두 double로 하기 때문이다.

 

lex

lex는 어휘 분석을 자동으로 해 주는 툴이다. 「.l」이라는 확장자 파일을 입력해 C 소스를 출력한다. 이것의 GNU판이 flex이다.

어휘 분석은 입력된 문자열을 토큰으로 분할하는 프로그램이므로, lex의 정의 파일에서는 mycalc가 사용하는 토큰을 정의해야 한다.

mycalc가 사용하는 토큰은 아래와 같다.

 

 ①연산자. mycalc에서는 사칙연산을 사용하므로 「+」,「-」,「*」,「/」です。 
 ②정수치.「123」등. 
 ③실수치.「123.456」등 
 ④개행. 하나의 식을 입력하고 개행(엔터)을 입력하면 계산을 실행하는데, 이 개행도 하나의 토큰으로 간주한다.

lex에서는 정규표현으로 토큰을 정의한다.

mycalc의 lex 입력파일 「mycalc.l」은 아래와 같다.

1:  %{
2:  #include <stdio.h>
3:  #include "y.tab.h"
4: 
5:  int
6:  yywrap(void)
7:  {
8:      return 1;
9:  }
10:  %}
11:  %%
12:  "+" return ADD;
13:  "-" return SUB;
14:  "*" return MUL;
15:  "/" return DIV;
16:  "\n" return CR;
17:  [1-9][0-9]* {
18:      double temp;
19:      sscanf(yytext, "%lf", &temp);
20:      yylval.double_value = temp;
21:      return DOUBLE_LITERAL;
22:  }
23:  [0-9]*\.[0-9]* {
24:      double temp;
25:      sscanf(yytext, "%lf", &temp);
26:      yylval.double_value = temp;
27:      return DOUBLE_LITERAL;
28:  }
29:  %%

 

11행의 %% 부분까지를 가르켜 정의부(定義部) 라고 한다. 정의부에는 스타트 상태의 정의나 정규표현의 명명 등을 실행할 수 있지만, 여기서는 C의 코드를 기술하고 있다.

1행에서 10행의 %로 둘러쌓인 부분은 생성되는 어휘 분석기에서 그대로 출력된다. 따라서 이후의 부분에서 필요한 헤더파일의 #include 등을 여기서 실행한다. 3행의 「y.tab.h」이라는 헤더파일을 인클루드하고 있는데, 이것은 나중에 yacc가 자동생성하는 헤더파일이다. 그 아랫부분에 있는 ADD, SUB, MUL, DIV, CR, DOUBLE_LITERAL 등은 y.tab.h 안에서 #define되어있다.

5행에서 9행까지는 yywrap() 이라는 함수를 정의하고 있다. 이것을 쓰지않으면 lex의 라이브러리를 링크해야하므로 환경에 따라서는 컴파일이 귀찮아질 수도 있어서 일단 추가해둔다.

12행부터 28행까지는 규칙부(規則部)이다. 정규표현으로 토큰을 표현하고 있다.

12행에서 16행까지는 사칙연산의 연산자 및 개행에 대해 각각 정의된 심볼을 return하고 있다. 이 심볼들은 토큰의 종류를 표현하며, y.tab.h 안에서 #define되어있다.

여기서, 토큰이라 하는것은 토큰이 가진 의미로서 3종류가 있다.


 ①토큰의 종류. 이 계산기에서「123.456」이라고 하는 토큰의 종류는 실수치(DOUBLE_LITERAL)이다.
 ②토큰의 문자열. 토큰에는 입력 그대로의 문자열 표현이 있다.「123.456」이라는 토큰의 문자열은 "123.456" 이다. 
 ③토큰의 값.「123.456」이라는 토큰에는「실수 123.456이라는 값」이라는 의미도 있다.


「+」나「-」라면 토큰의 종류만 신경쓰면 되지만, DOUBLE_LITERAL의 경우 토큰의 값도 넘겨야 한다. 위의 토큰의 3요소 중 토큰의 문자열은 액션 안에서는 yytext라고 하는 글로벌 변수에서 참조 가능하다. 18~21행에서 sscanf()에서 그걸 분석하고 있다.

17행부터 시작하는 규칙에서는 정수의 해석을, 23행부터 시작하는 규칙에서는 실수의 해석을 하고 있다. mycalc에서는 정수를 입력해도 실수로 해석하기 때문에 같은 코드를 카피했다.

해석한 값은 yylval 이라고 하는 글로벌 변수에 셋팅한다. 이 yylval 글로벌 변수는 각종 토큰값을 격납해야되기 때문에 공용체로 되어있다. 공용체의 정의는 yacc의 정의 파일에서 한다.

29행에 또다시 %%가 나오는데 이것은 규칙부의 끝을 나타낸다. 이 후 부분은 유저코드부가 된다. 여기에는 임의의 C코드를 기술할 수 있다. 정의부와는 달리 %{ %}로 감쌀 필요는 없다.

 

yacc

yacc는 파서를 자동생성하는 툴이다. 「.y」라는 확장자 파일을 입력해 C 소스를 출력한다. 이것의 GNU판이 bison이다.

mycalc의 yacc 입력파일 「mycalc.y」는 아래와 같다.

1: %{

2: #include <stdio.h>

3: #include <stdlib.h>

4: #define YYDEBUG 1

5: %}

6: %union {

7: int int_value;

8: double double_value;

9: }

10: %token <double_value> DOUBLE_LITERAL

11: %token ADD SUB MUL DIV CR

12: %type <double_value> expression term primary_expression

13: %%

14: line_list

15: : line

16: | line_list line

17: ;

18: line

19: : expression CR

20: {

21: printf(">>%lf\n", $1);

22: }

23: expression

24: : term

25: | expression ADD term

26: {

27: $$ = $1 + $3;

28: }

29: | expression SUB term

30: { 31: $$ = $1 - $3;

32: } 33: ; 34: term 35: : primary_expression

36: | term MUL primary_expression 37: { 38: $$ = $1 * $3; 39: } 40: | term DIV primary_expression 41: { 42: $$ = $1 / $3; 43: } 44: ; 45: primary_expression 46: : DOUBLE_LITERAL

47: ; 48: %% 49: int 50: yyerror(char const *str) 51: { 52: extern char *yytext; 53: fprintf(stderr, "parser error near %s\n", yytext); 54: return 0; 55: } 56: 57: int main(void) 58: {

59: extern int yyparse(void); 60: extern FILE *yyin; 61: 62: yyin = stdin; 63: if (yyparse()) { 64: fprintf(stderr, "Error ! Error ! Error !\n"); 65: exit(1); 66: } 67: }


1~5행은 lex와 마찬가지로 %{ %}로 감싸 C코드를 기술하고 있다.

3행에 #define YYDEBUG 1 은 글로벌 변수 yydebug를 디버그 등에서 비제로로 하기 위해 구문분석 상태를 실행시 볼 수 있다.

6~8행은 토큰과 비단말기호(non-terminal symbol)의 형 선언이다. 위에 쓴 것처럼 토큰은 그 종류와 값을 가지고 있어야 한다. 토큰의 형은 여러가지가 있지만 공용체로 선언하고 있다. 여기서는 설명을 위해 int형의 int_value와 double형의 double_value와의 공용체로 선언하고 있지만, int_value는 사용하고 있지 않다.

비단말기호는 토큰을 조합해서 만드는 것으로 리스트 안에 있는 line_list나 line, expression, term이 이에 해당된다. 또한 비단말기호를 분할해가면 결국 토큰이 되기때문에 토큰을 종단기호(Terminal symbol) 라고도 부른다.

10~11행은 토큰을 선언한다. mycalc에서 사용하는 토큰의 종류를 여기서 정의하고 있다. ADD, SUB, MUL, DIV, CR에 관해서는 단순히 토큰의 종류만 알면 되지만, DOUBLE_LITERAL은 값을 가진 토큰이기 때문에 그 형을 <double_value>로서 지정하고 있다. 이 double_value는 바로 위의 %union의 멤버명이다.

12행은 비단말기호의 형 선언을 하고 있다.

lex와 마찬가지로 13행의 %% 부터 뒷부분은 규칙부이다. 규칙부는 구문규칙과 C로 기술된 액션으로 구성되어있지만 규칙 중 액션이 섞여있으면 해독이 어렵기 때문에 구문규칙만 따로 추출해 코멘트를 달면 아래와 같다.

1: line_list /* 「행 나열」とは… */

2: : line /* (하나의)행、*/

3: | line_list line /* 또는、「행 나열」뒤에 「행」을 나열한 것*/

4: ;

5: line /* 「행」이란… */

6: : expression RETURN_T /* 식의 뒤에 개행을 넣은 것 */

7: expression /* 「식」이란… */

8: : term /* 「항」、 */

9: | expression ADD term /* 또는、「식」 + 「항」 */

10: | expression SUB term /* 또는、「식」 - 「항」 */

11: ;

12: term /* 「항」이란、 */

13: : primary_expression /* 「일차식」、 */

14: | term MUL primary_expression /* 또는、「항」 * 「일차식」 */

15: | term DIV primary_expression /* 또는、「항」 / 「일차식」 */

16: ;

17: primary_expression /* 「일차식」이란… */

18: : DOUBLE_LITERAL /* 실수 리터럴 */

19: ;


1~4행과 같은 서식은 구문규칙에 있어 1회 이상 반복을 표현하기 위한 정석이다. mycalc은 1행의 식을 입력하고, 엔터(개행)를 치면 계산이 실행되지만, 그 후에 반복식이 입력가능하기 때문에 반복 구조로 되어있다.

또한 위의 구문규칙은 구문규칙 자체가 연산자의 우선순위와 결합규칙을 포함하고 있는 것에 주의한다.


이런 구문규칙을 바탕으로 yacc가 어떤 움직임을 하는지 한마디로 말하자면, 테트리스와 비슷하다.

먼저, yacc가 생성한 파서는 내부적으로 스택을 보유하고 있다. 이 스택에 테트리스의 블록과 같이 토큰이 쌓이게 된다.

예를 들어 1+2*3 이라는 입력이 있다면, 어휘 분석기(Lexical Analyzer) 에서 분할된 토큰(처음은 1)이 오른쪽에서 내려온다.

 


토큰이 내려와서 쌓이는 것을 shift 라고 한다. mycalc에서는 모든 계산을 double로 하기 때문에 1이라는 토큰은 DOUBLE_LITERAL이다. 토큰이 떨어지는 동시에 위 규칙 중

45: primary_expression

46: : DOUBLE_LITERAL

에 걸려, 「primary_expression」로 변환된다.

 


이처럼, 어떤 규칙에 걸려 변환되는 것을 reduce(환원) 이라고 한다.

「primary_expression」은 그 다음

34: term 

35: : primary_expression 

에 걸려, 「term」으로 reduce되고

 


 그 후

23: expression

24: : term

에 의해 「expression」으로 reduce된다.

 


그다음, +가 내려온다. 이 상태에서는 어느 규칙에도 매칭되지 않기 때문에 얌전히 shift된다.

 


그다음 2가 내려온다.

 


아까와 같은 규칙에 의해 「2」(DOUBLE_LITERAL)는、 「primary_expression」을 경유해「term」으로 reduce된다.

 


여기서 다음 규칙에 매칭되지만

 expression

      | expression ADD term


yacc는 테트리스와 마찬가지로 다음에 내려올 토큰이 뭔지를 딱 하나 미리 읽어들인다. 여기서는 다음에 내려올 토큰이 *라는걸 알기때문에

 term

      | term MUL primary_expression 

에 매칭될 가능성이 있다고 판단해, 또한번 shift 한다.

 


그다음 3이 내려와서

 


「primary_expression」으로 reduce되면

 


「term」「*」「primary_expression」의 부분이

 term

      | term MUL primary_expression 

에 매칭되어 term」으로 reduce된다.

 


거기에 「expression」「+」「term」은

 expression

       | expression ADD term

에 매칭되므로, 최종적으로는 「expression」으로 reduce된다.

 


여기서, reduce가 발생할 때마다 yacc는 그 규칙의 액션을 실행한다. 예를들어 곱셈을 실행하는 규칙은 아래와 같다.

34: term

36: | term MUL primary_expression

37: {

38: $$ = $1 * $3; 

39: } 

액션은 C코드로 기술하지만, 보통의 C코드에서는 볼수없는 $$, $1, $3과 같은 표현이 섞여있다.

그 중 $1, $3은 각각 term과 primary_expression가 보유하고 있는 값을 의미한다. 즉, yacc가 파서의 소스를 만들어낼 때 스택의 그 위치의 요소를 나타내는 코드로 변환한다는 것이다. 그리고 $2는 아스타리스크(*)이기 때문에 값을 갖지 않는다.

$1과 $2로 곱셈을 하고 $$에 대입하면 그 값이 스택에 남는다. 이번 예에서는 2 * 3의 계산을 하고 6을 스택에 남긴다.

 


여기서 $1과 $3에 대응하고 있는 것은 term과 primary_expression이고 2나 3과 같은  DOUBLE_LITERAL이 아니지않나? 근데 왜 2 * 3이라는 계산이 되지?

라고 의문을 갖는 사람이 있을지 모른다. 이것은 액션을 기술하지 않았을 경우, yacc는 자동적으로 { $$ = $1 } 이라는 액션을 보충하기 때문이다. 따라서 DOUBLE_LITERAL이 primary_expression으로 reduce되거나 primary_expression이 term으로 reduce되는 시점에 값이 계승되고 있다는 것이다.

34: term

35: : primary_expression

    {

         $$ = $1; /* 보충된 액션 */

     }

45: primary_expression

46: : DOUBLE_LITERAL

     {

         $$ = $1; /* 보충된 액션 */

     }


또한, $$ 나 $1 의 데이터형은 각각 대응하는 토큰이나 비단말기호의 형과 일치한다. 예를들어 DOUBLE_LITERAL이라는 토큰은

 10: %token <double_value> DOUBLE_LITERAL

로 선언되어 있고 expression, term, primary_expression은

 12: %type <double_value> expression term primary_expression

이다. 여기서 형을 <double_value>로 지정하고 있기 때문에 %union에서 선언되어 있는 공용체의 double_value라고 하는 멤버가 사용되고 있다는 것이다.

이 예에서는 계산기이기 때문에 액션에서 그대로 계산을 하고 있지만 프로그래밍 언어를 만들 경우는 그렇게는 할 수 없다. 프로그래밍 언어에는 루프라는 처리가 있는데 구문해석은 한번밖에 안하기 때문에 같은 개소에 대해서는 액션이 반복 실행되지않기 때문이다.

따라서 액션에서는 구문 트리를 구축하게 된다. 그 처리에 대해서는 다음장에서.


실행형식의 작성

이제 실제 계산기를 컴파일/링크해서 실행형식을 작성한다.

표준적인 UNIX에서는 아래와 같은 커맨드로 실행하면 된다. 그러면 mycalc 이라는 이름의 실행형식이 출력된다.

% yacc -dv mycalc.y ←yacc의 실행

% lex mycalc.l ←lex의 실행

% cc -o mycalc y.tab.c lex.yy.c ←C컴파일러로 컴파일

 참고1 : lex 실행 시 mycalc.l:31: premature EOF 에러가 나는 경우

            %} 앞에 스페이스가 들어가있는지 확인한다. (스페이스에 민감함)

 참고2 : 맥에서 cc로 컴파일 시 에러날 경우 gcc를 사용


이 과정에서 몇개의 파일이 생성된다. 그 흐름을 그림으로 하면 아래와 같다.

 

 참고3 : 맥에서 정상 컴파일 시 생성되는 파일들


y.tab.c가 yacc가 생성하는 구문해석기의 소스이고 lex.yy.c가 어휘 분석기의 소스이다. crowbar.y로 정의한 토큰이나 공용체를 lex.yy.c에 전달하기 위해 yacc가 생성하는 것이 y.tab.h 라는 헤더파일이다.

또한, C프로그램에서는 당연히 main() 함수가 필요한데, mycalc에서는 main()을 mycalc.y의 유저코드부(47행 이후)에 기술하고 있다. 물론 이것은 다른 .c파일로 나눠도 상관없다. 그리고 yacc 대신 bison을 사용하면 y.tab.c, y.tab.h이 아니라 mycalc.tab.c, mycalc.tab.h이라는 파일명으로 파일을 생성한다. --yacc옵션을 사용하면 yacc와 같은 파일명을 생성하는 것도 가능하다.
이번 샘플은 지극히 단순한 계산기지만, 이정도 계산기에서도 Windows에 딸려있는 GUI의 계산기보다 훨씬 쓸만하다.


 참고4 : 생성된 mycalc 실행 예



참고사이트 : http://kmaebashi.com/programmer/devlang/yacclex.html


저작자 표시 비영리 변경 금지
신고

'♣Develop♣ > ☞Lex, Yacc' 카테고리의 다른 글

프로그래밍 언어 만들기  (0) 2015.03.24
yacc/lex로 계산기 만들기  (1) 2015.03.20
yacc와 lex  (0) 2015.03.19
GCC, LEX, YACC를 맥에서 사용하기  (0) 2015.03.19
Posted by 토마도이

댓글을 달아 주세요

  1. 질문~! 2017.06.01 18:28  댓글주소  수정/삭제  댓글쓰기

    관리자의 승인을 기다리고 있는 댓글입니다


공지사항

블로그 이미지
도쿄에서 살고 있는 10년차 IT엔지니어의 요모조모 관심거리 끄적임. "일&맛난음식&오와라이" 너무너무 좋아해요♡
토마도이
Yesterday308
Today345
Total450,634
Statistics Graph
free counters

달력

 « |  » 2017.09
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30

최근에 달린 댓글

글 보관함