제 9 장  의미 분석과 중간 코드 생성.

Presentation on theme: "제 9 장  의미 분석과 중간 코드 생성."— Presentation transcript:

1 제 9 장  의미 분석과 중간 코드 생성

2 제 9 장  의미 분석과 중간 코드 생성 이 장에서는 의미 분석에 필요한 개념과 의미 분석 과정을 살펴본다.

3 9.1 의미 분석 개념 의미 분석은 크게 두 부류로 나눌 수 있다. 기본 자료형이나 자료 구조의 의미 분석
실행문의 의미 분석(중간코드 생성)

4 의미 분석 단계

5 정의 9.1 속성은 프로그램에서 사용하는 객체가 컴퓨터 내부에 어떤 형식으로 표현되는 의미이고, 속성 값은 생성 규칙과 연관되어 있는 의미의 규칙이다.

6 정의 9. 2 의미 규칙은 생성 규칙 A → α에 대한 함수로 Atr = F(Ψ1, Ψ2,. , Ψm) 이다
정의 9.2 의미 규칙은 생성 규칙  A → α에 대한 함수로 Atr = F(Ψ1, Ψ2, ... , Ψm) 이다. 여기에서 F는 여러 속성이 합성하거나 상속하는 함수이며, Atr은 생성규칙의 오른쪽에 있는 문법 심볼의 속성에 따라 생성하는 F의 결과에 의한 합성 속성이거나 상속 속성이다. Ψ1, Ψ2, ... , Ψm 은 합성 속성일 경우에는 생성규칙의 오른쪽에 있는 문법 심볼에 속하는 속성이고, 상속 속성일 경우에는 A 에 속하는 속성이거나 생성 규칙  A → α의 오른쪽에 있는 문법 심볼 중 어느 것에나 속하는 속성이다.

7 자료형과 자료 구조에 대한 의미 분석의 선언문 예
int a; int b[5][6]={ 1, 0, 1, 0, 1, 0,               1, 0, 1, 0, 1, 0,               1, 0, 1, 0, 1, 0 }; 처음 선언 int a; 와 int b[5][6] = { ... } 는 여러 속성을 가진다.

8 실행문에 대한 의미 분석의 수식과 할당문 예 a = b + c * d;
이 수식을 실행 가능하도록 하려면 아래와 같은 중간코드( 혹은 인스트럭션)로 변환한다. lod  b, R1     lod  c, R2     mul d, R2     add  R1, R2   sto  R2, a

9 9.2 구문-직접 번역 이 절에서는 구문-직접 번역이 어떻게 수행하는가를 살펴본다.
 그림 9.2 탁상용 계산기에서 수식 * 4의 구문-직접 실행

10 의미 규칙 구문에서 직접 번역하려면 구문 분석을 수행하는 과정에서 환원이 일어날 때마다 계산을 직접 수행하는 액션이 있어야 한다. 수식을 위한 문법의 생성 규칙과 의미규칙 생성 규칙 의미 규칙         C → E↲          E → E1 + T             E → T         T → T1 * F              T → F         F → ( E )         F → num    output(E.p)    E.p = E1.p + T.p    E.p = T.p    T.p = T1.p ☓ F.p    T.p = F.p    F.p = E.p    F.p = num.p

11 예 9. 1 의미 분석을 좀 더 이해하기 위해 그림 9. 3의 의미 규칙을 그림 9. 4와 같이 변경하고 수식 2 + 3
예 9.1 의미 분석을 좀 더 이해하기 위해 그림 9.3의 의미 규칙을 그림 9.4와 같이 변경하고 수식 * 4↲를 번역해 보자. 생성 규칙 의미 규칙         C → E↲          E → E1 + T             E → T         T → T1 * F              T → F         F → ( E )         F → num  output( "parsing complete" )   output( "add" )  output( "mul" )  output( num ) 그림 9.4 코드를 생성하는 의미 규칙이 들어간 생성 규칙

12 출력된 이 형식은 수식의 후위 표기이며 의미는 아래 신택스 트리와 같다.
그림 9.5 수식 * 4↲의 신택스 트리

13 액션 루틴을 추가한 문법 예 이 문법은 곱하기와 더하기에 대한 산술 수식을 후위 표기로 바꾼다.
  G:   1.   E → T  Elist         2.   Elist → + T {+}     { output( "add" ) }                     Elist         3.   Elist  → ε         4.   T  → F  Tlist         5.   Tlist  → * F {*}    { output( "mul" ) }                      Tlist         6.   Tlist → ε         7.   F → ( E )         8.   F → a {a}         { output( a ) }

14 생성 규칙에 액션 심볼이 추가된 a + a * a 의 파싱 트리

15 9.2.1 액션 루틴을 결합한 리커시브 디센트 파서의 구현
function E( ) {      if ((token == '(') || (token == 'a')) {           /*   생성 규칙 1  */                                       T( );                                      Elist( );                                     }             /*   생성 규칙 1  */       else printf("parsing error");                      }                              /*   함수 E  */  function Elist( )      if ( token == '+' ) {           /*   생성 규칙 2  */                         scanf(token);                              T( );                         printf("add");                        Elist( );                        }           /*   생성 규칙 2  */       else if ((token == ')' ) || (token == '↲' ))  /* do nothing  */ /*   생성 규칙 3  */                               else printf("parsing error");  }  /*   함수 Elist  */

16 function T( ) {      if ((token == '(' ) || (token == 'a')) {        /*   생성 규칙 4  */                                        F( );                                        Tlist( );                                       }        /*   생성 규칙 4  */                              else printf("parsing error"); } /*   함수 T  */  function Tlist( )      if ( token == '*' ) {        /*   생성 규칙 5  */                         scanf(token);                        F( );                         printf("*");                        Tlist( );                        }                      /*   생성 규칙 5  */       else if ((token == '+' ) || (token = ')' || (token == '↲')) /* do nothing, 생성 규칙 6 */                             else printf("parsing error"); } /*   함수 Tlist */

17 function F( ) {      if ( token == '(' ) {         /*   생성 규칙 7  */                         scanf(token);                        E( );                         if (token == ')') scanf (token) else printf('parsing error');                       }                      /*   생성 규칙 7  */       else if (token == 'a'){     /*   생성 규칙 8  */                           scanf(token);                          printf("a")                         }       /*   생성 규칙 8  */     }  /*  함수 F  */

18 9.2.2 액션 루틴을 결합한 LR 파서의 구현 function LR_Parsing_Driver( ) {
   {     input: token sequence, augmented grammar, stack and the parsing table;     output: parsing tree;            /*     초기 스택 상태와 입력 큐 상태, (#s0                :   ai   ai   an ↲)     */                      /*     파싱이 진행 중인 스택과 입력 큐 상태,   (#s1 X1 s1 X2    Xm sm        :   ai   ai   an ↲); /*     스택 톱 심볼(상태번호)와 입력 심볼을 아래처럼 비교한다   */ /*   이동 액션이면 스택 톱에 입력 심볼을 이동하고 상태번호를 넣는다   */ if (ACTION(sm, ai ) == "shift s ")  (#s0 X1 s1 X2    Xm sm ai s       :   ai   an ↲); /* 환원 액션이면 스택에서 상태번호를 포함하여 β를 제거한다   */ if (ACTION(sm, ai ) == "reduce  A →β")           {                                         (#s0 X1 s1 X2    Xm-r sm-r       :   ai ai   an ↲)                    call action_routine for  A →β;  /*  β 안에 있는 액션 심볼(터미널)을 출력한다  */                   (#s0 X1 s1 X2    Xm-r sm-rAs       :   ai ai   an ↲)  /*   (r = |β|, GOTO(sm-r, A) = s)  */           } if (ACTION(sm, ai ) == "accept") printf ("parsing is completed normally"); if (ACTION(sm, ai ) == "error")  ERROR( );  }

19 예 9.2 아래의 의미 규칙이 적용된 문법으로 수식 3 * 4 + 5↲를 LR 파싱하는 단계에서 스택 상태, 입력 큐 상태, 파싱 결과를 보이시오.
              L → E↲            { output( "parsing complete" );}               E → E1 + T        { output( "add" );}               E → T               T → T1 * F         { output( "mul" );}               T → F               F → ( E )               F → num            { output( num );}

20 수식 3 * 4 + 5↲를 파싱하는 단계의 스택 상태,입력 큐 상태

21 9.3 속성 문법 정의 9.3 생성 규칙 A → α에 대한 합성 속성은 생성 규칙의 왼쪽에 있는 넌터미널의 속성 값 A(Atr) 는 오른쪽에 있는 문법 심볼의 각 속성 값인 X(Ψ), Y(Ψ), Z(Ψ)의 합성에 의한 함수이다. X, Y, Z 의 합성 값이 A의 값이다.                    A → XYZ    A(Atr) = F(X(Ψ)Y(Ψ)Z(Ψ))

22 정의 9.4 생성 규칙 A → α에 대한 상속 속성은 생성 규칙의 오른쪽에 있는 넌터미널의 속성 값 X(Ψ), Y(Ψ), Z(Ψ) 은 왼쪽에 있는 넌터미널의 속성 값 A(Atr) 이 전달된다.                    A → XYZ    A(Atr) = F(X(A(Atr)) Y(A(Atr)) Z(A(Atr))) 혹은                    A → XYZ    A(Atr) = F(X(A(Atr)) Y(X(Ψ)) Z(X(Ψ)))

23 예 9. 3 탁상용 계산기에서 입력 값을 계산하도록 하는 아래 문법 G는 더하기와 곱하기 연산이 있는 속성 문법이다
예 9.3 탁상용 계산기에서 입력 값을 계산하도록 하는 아래 문법 G는 더하기와 곱하기 연산이 있는 속성 문법이다. 의미 규칙의 문법 심볼에 있는 .p, .q, .r 는 속성 값을 나타내는데 속성 값이 저장된 곳의 포인터이다. 터미널 num의 속성은 어휘 분석 단계에서 만들어지는 상수 값이다.     G:  E →  + E1  E2   {E.p = E1.q + E2.r }          E →  - E1  E2   { E.p = E1.q - E2.r }          E →  * E1 E2   { E.p = E1.q * E2.r }          E →  / E1  E2   { E.p = E1.q / E2.r }          E →  num       { E.p = num.q }

24 속성 문법에 의한 * 의 파싱 트리  그림 9.7 전위 표기 수식 * 에 대한 속성이 들어간 파스 트리

25 파스 트리에서 속성의 합성 과정  그림 9.8 전위 표기 수식 * 의 파스 트리에서 속성의 합성 과정

26 실습 9. 1 예 9. 3의 문법으로 중위 표기 수식인 7 + 8. 9 를 파싱하시오
실습 9.1 예 9.3의 문법으로 중위 표기 수식인 * 9 를 파싱하시오. 이 문법으로 파싱할 수 있는 수식은 어떤 수식인지 설명하시오.

27 실습 9.2 예 9.3의 문법으로 아래 각 수식에 대한 파스 트리를 구성하시오. 에러가 나는 경우는 어떤 경우인지 설명하시오.
(1)  * (2)  + * (3)  / (4)  - 3  + 4  3  * 2 3

28 실습 9.3 아래 수식을 파싱할 수 있는 속성 문법을 구성하고 파스 트리를 생성하시오. 이 수식은 후위 표기 수식이다.
           3  4  +  5  6  *

29 상속 속성 아래 문법 G는 정수, 유동소수점, 문자 세 개의 자료형을 선언하는 문법으로, 선언한 자료형은 프로그램 내에서 사용하는 변수에 전달(상속)된다.             생성규칙                  의미규칙    G: 1. Decl  → Typep  Idlistq    { Idlist.q = Type.p }         2. Typep → int             { Type.p = 'integer' }         3. Typep → float            { Type.p = 'float' }         4. Typep → char            { Type.p = 'char' }         5. Idlistq → Idlistr , idt      { Idlist.r = Idlist.q; id.t = Idlist.q }         6. Idlistq →  idt             { id.t = Idlist.q }

30 속성이 상속되어 x, y, z 각각은 아래 심볼 테이블과 같이 “정수형” 이라는 속성을 저장한다.
심 볼 식 별 속 성 . x 단순변수 정수형 y z

31 선언문 int x, y 에 대한 속성이 들어간 파스 트리

32 선언문 int x, y 의 파스 트리에서 속성의 상속 과정

33 파서로 합성 속성을 구현하려면 호출한 함수(넌터미널)에 계산 결과 같은 합성정보를 넘겨주어야 하기 때문에 인자 전달은 참조에 의해(인자에 * 를 사용) 이루어진다.
반면에 상속 속성을 구현하려면 상속정보를 호출되어진 함수에 전달하므로 인자 전달은 값에 의해 이루어진다.

34 사용한 문법에서 아래 생성 규칙을 예로 살펴보자.
       Ep →  + Eq  Er     { E.p = E.q + E.r } 이 생성 규칙 E 의 리커시브 디센트 함수는 아래와 같다. function E(int *p); int q, r; {    if (token == '+' ) {          /* 생성 규칙 1  */                    get(token);                    E(&q);                    E(&r);                    p = q + r;    /* E(q)와 E(r)을 호출한 후에 계산한다 */                   }        /* 생성 규칙 1  */          ......

35 아래는 의미 규칙에서 직접 실행이 가능한 리커시브 디센트 파서이다.
    G: 1.   Ep →  + Eq  Er   { E.p = E.q + E.r }          2.   Ep →  - Eq  Er   { E.p = E.q - E.r }          3.   Ep →  * Eq  Er   { E.p = E.q * E.r }          4.   Ep →  / Eq  Er   { E.p = E.q / E.r }          5.   Ep →  numq   { E.p = num.q }

36 get 함수는 입력 토큰의 값 부분을 yylval 이라는 전역 변수에 저장한다.
function E(*p); int *q, *r; {      if (token == '+')  {        /*  생성 규칙 1  */                    get(token);                    E(&q);                    E(&r);                    p = q + r;                   }           /*  생성 규칙 1  */      else if (token == '*')  {    /*  생성 규칙 2 */                          get(token);                          E(&q);                          E(&r);                          p = q * r;                         }              else if (token == 'num')  {       /*  생성 규칙 3  */                               p = yylval;     /*  상수에 대한 토큰 값  */                               get(token);                              }               /* 생성 규칙 3 */                  else printf("parsing error");                           } /*  함수 E  */

37 /*  Recursive_Descent Parser  */
main( ); int yylval, p, token;    {      get(token);      E(&p);      if (token == '↲') printf(p)                  else printf("parsing error");    }  /*  파서 메인 함수  */

38 실습 9. 4 위의 속성 문법을 결합한 리커시브 디센트 파서를 C 프로그래밍 언어로 구현하여 실행하고 결과를 분석하시오

39 실습 9.5 실습 9.4에서 구현한 파서에 그래픽 사용자 인터페이스를 첨부하여 탁상용 계산기를 구현하고 실행하시오.

40 9.4 중간 코드 생성 중간 코드는 컴퓨터, 수퍼 컴퓨터, 휴대용 단말기, 휴대전화 등  특정 기계에 종속하지 않고 어떤 기계어 인스트럭션으로도 번역이 가능한 약속한 형식이다. 이러한 중간 코드를 사용하면 여러 장점이 있다.

41 9.4.1 중간 코드 폴란드식 표기법 주소가 여러 개인 코드 트리 구조 코드 추상화 기계 코드 후위 표기법, 트리의 스택 표기
동작 코드 부분과 피연산자 주소로 구성된 형식 등 트리 구조 코드 추상화 기계 코드 P-코드, EM-코드, U-코드, 바이트 코드

42 피연산자가 없는 경우(0-주소 중간 코드) 중간 코드에 동작 코드만 있고 두 개(혹은 한 개)의 피연산자는 레지스터에 있다.
동작코드

43 피연산자가 한 개인 경우(1-주소 중간 코드) 동작 코드와 피연산자가 한 개만 있고 나머지 피연산자는 레지스터에 있다.
동작코드 피연산자1(주소)

44 피연산자가 두 개인 경우(2-주소 중간 코드) 동작 코드와 피연산자 두 개가 있다. (add R0, R1)
    (add   R1, K) 동작코드 피연산자1(주소) 피연산자2(주소)

45 피연산자가 세 개인 경우(3-주소 중간 코드) 중간 코드에 동작 코드와 피연산자 세 개가 있다. (add C, A, B)
     (sub   K, A, B)   동작코드 피연산자1(주소) 피연산자2(주소) 피연산자3(주소)

46 입력 a = x * y + z + w 인 스트링 예 mul x y t1 add z t1 t2 add w t2 t3
          sto  a   _   t3 중간 코드에서 mul은 곱하기 동작, add 는 더하기 동작 코드, sto는 결과를 지정하는 주소에 할당하는 동작이다. t1, t2, t3 은 연산한 중간 결과는 임시로 저장하는 주소이다.

47 그림 9.11 수식 a = x * y + z + w 의 신택스 트리

48 각 문장 특성 따른 주소가 세 개인 중간코드 형식: x = y Φ z
할당문 할당문은 x = y Φ z 같이 세 개의 주소를 사용하는 형식 goto 문 goto  L if 문 if   x Φ y   goto  L

49 함수 호출문의 인자                  arg a1                  arg a2                     ···                  arg an                  call  f, n          /* f(a1, a2, ... , an), n은 인자의 수 */

50 배열 참조 포인터 배열을 참조하는 중간 코드는 y = x[i]와 x[i] = y 와 같이 표현
주소 할당 중간 코드 x = &y 와 포인터 할당 중간 코드는  x =*y, *x = y 형식이다. x = &y 는 y가 가리키는 위치(즉, 주소)를 x에 할당하라는 의미로 x 는 포인터 이름이다.

51 산술 수식에 대하여 주소가 세 개인 중간 코드를 생성하는 의미 규칙을 첨부한 문법의 예
산술 수식에 대하여 주소가 세 개인 중간 코드를 생성하는 의미 규칙을 첨부한 문법의 예    S → id = E             { S.c = E.c || cogen (id.p ` =`  E.p) }    E → E1 + E2          { E.p =  new(t);                                      E.c = E1.c || E2.c || cogen (E.p  `=`  E1.p) `+`  E2.p) }    E → E1 *  E2          { E.p =  new(t);                                      E.c = E1.c || E2.c || cogen (E.p  ` =`  E1.p `*`  E2.p) }    E → - E1                { E.p =  new(t);                                      E.c = E1.c || cogen (E.p ` = `   `-`  E1.p) } /* 단항 빼기 연산자 */    E → ( E1)               { E.p = E1.p;  E.c = E1.c }    E → id                   { E.p = id.p;  E.c = `  ` }

52 산술 수식 a = b * -c + b * -c 에 대한 의미 규칙이 첨가된 파스 트리
그림 9.12 의미 규칙이 첨가된 파스 트리

53 9.4.2 산술 수식의 번역과 중간 코드 생성 그림 9.13  a = b  - c + b  - c 에 대한 중간 코드 생성 액션 루틴 이 결합된 파스 트리

54 그림 9.14에서② 부분은 단항 빼기 부호를 사용하는 코드를 생성하는 아래 의미 규칙에 해당한다.
E → - E1     { E.p =  new(t);                             E.c = E1.c || cogen (E.p ` = `   `-`  E1.p) }  /* 단항 빼기 */ 그러므로 의미 규칙의 E.c = E1.c || cogen (E.p ` = `   `-`  E1.p) } 에서 E1.c 부분은 아직 코드가 없고, cogen (E.p ` = `   `-`  E1.p) }부분에서 E.p는 이미 E.p =  new(t)에서 생성한 새로운 저장 장소의 주소 t3 가 있다. E1.p는 c 를 가리키므로  생성하는 코드는 t3 = -c 이다.

55 그림 9.14  중간 코드 t3 = -c 의 생성 단계

56 그림 9.15의 오른쪽에서는 아래 의미 규칙이 적용된다.
E → E1 *  E2          { E.p =  new(t);                                    E.c = E1.c || E2.c || cogen (E.p  ` =`  E1.p `*`  E2.p) } 새로운 저장 공간 t4 가 생성되었고, E1.p 은 b, E2.p는 c 를 가리킨다. E1.c(혹은 E2.c)는 이미 생성된 코드 t3 = -c 가 있으므로 t4 = b * t3 코드와 접속하여 아래 코드를 생성한다.     t3 = -c      t4 = b * t3 왼쪽 부분의 넌터미널 심볼 E에 대해서도 아래 코드를 생성한다.     t1 = -c     t2 = b * t1

57 그림 9.15  중간 코드 t1 = -c; t2 = b * t1과 t3 = -c; t4 = b * t3의 생성 단계

58 같은 방법을 반복하면 그림 9.16과 9.17같이 의미 규칙이 적용되어 최종으로 아래 중간 코드를 생성한다.
    t1 = -c     t2 = b * t1     t3 = -c     t4 = b * t3     t5 = t2 + t4     a = t5

59  그림 9.16 E → E +  E 에 대한 중간 코드 생성 단계

60 그림 9.17 최종 S → id =  E 에 대한 중간 코드 생성 단계

61 실습 9.7 위의 산술 수식에 대한 세 개 주소 중간 코드를 생성하는 리커시브 디센트 파서를 구현하고 산술 수식 a = -k + (b + c) * m 의 중간 코드를 생성하시오.

62 9.4.3 제어 구조의 번역과 중간 코드 생성 S → if (B) S | if (B) S1 else S2
         | for  (C)  S1          | while  (B)  S1

63 if 문의 중간코드 if 문은 S →   if (B)  S | if  (B) S1 else  S2

64 먼저  if (B)  S 구조의 if 문을 살펴보자. 불리언 수식이 있는 if 문 구조와 중간 코드로 번역한 예 if (a || b) j = k + tex; j = k - 3; 불리언 수식 부분 (a || b)를 주소가 세 개 있는 중간 코드로 번역하면 아래와 같다. t1 = a or b

65 ‘참’일 때 수행할 수식 j = k + tex 를 번역하면 아래와 같으며,
t2 = k  t3 = tex + t2  j  = t3 ‘거짓’일 때 수행할 수식 j = k - 3 를 번역하면 아래와 같다. t4 = k t5 =  t4 - 3 j  = t5

66 if (B)  S 구조 중간 코드의 메모리 할당 그림 9.18 if (B)  S 구조 중간 코드의 메모리 할당 예

67 if (B) S 구조의 중간 코드 생성 의미규칙 S → if (B) S1 { B.true = new(Label);
                                            B.false = new(Label);                                             S.c = B.c;                                                     || cogen ('label'  B.true) || S1.c;                                                     || cogen ('label'  B.false) || R.c;                                      }

68  if  (B) S1 else  S2 구조의 중간 코드를 살펴보기 위해 아래 구조를 번역해 보자.
if (a || b) j = k + tex           else j = k - 3;

69 if (B) S1 else S2 구조 중간 코드의 메모리 할당

70 S → if (B) S1 else S2 구조의 중간코드 생성 의미 규칙
                                                         B.true = new(Label);                                                          B.false = new(Label);                                                          L = new(Label);                                                          S.c = B.c;                                                                    || cogen ('label'  B.true) || S1.c;                                                                    || cogen ( 'goto'   L) ;                                                                    || cogen ('label'  B.false) || S2.c;                                                                    || cogen ('label'  L) || R.c;                                                   }

71 9.4.3.2 불리언 수식 C 프로그래밍 언어에서 불리언 수식을 계산하는 문법은 아래와 같다.
B  → B || B | B && B |  ! B | ( B ) | E R E | true | false R →  < | > | >= | <= | ==  | !=

72 실습 9. 8 불리언 수식을 연산하는 중간 코드를 생성하는 의미 규칙을 구성하시오
실습 9.8 불리언 수식을 연산하는 중간 코드를 생성하는 의미 규칙을 구성하시오. 예를 들어 B  → true | true는 아래와 같다.                         B  → true  { B.c = cogen ('goto'  B.true) }                         B  → false { B.c =  cogen ('goto'  B.false) }

73 9.4.3.3 while 문의 중간코드 sum = 0; k = 1; while(k <= 100) {
sum = sum + k;      k = k + 1; }

74 while 구조의 메모리 할당 그림 9.20  while (B) S1  구조 중간 코드의 메모리 할당 예

75 while 문의 중간 코드를 생성하는 의미 규칙
  S → while (B) S1      {                                          TEST = new(Label);                                           EXIT = new(Label);                                           B.true = new(Label);                                           B.false = new(Label);                                           S.c = cogen ('label'  TEST) || B.c;                                               || cogen ('label'  B.false) || cogen ( 'goto'  EXIT ) ;                                               || cogen ('label'  B.true) || S1.c;                                               || cogen ( 'goto'  TEST ) ;                                               || cogen ('label'  EXIT) || R.c;                                        }

76 9.4.3.3 for 문의 중간코드 sum = 0; for(k =1; k <= 100; k++) {
sum = sum + k; }

77 세 개의 주소가 있는 중간 코드 t1 = sum t2 = k TEST: t2 = t2 + 1
              if t2 <= 100 goto LOOP               goto EXIT LOOP:  t3 = t1 + t2               goto TEST  EXIT:   다른 코드

78  for 구조의 메모리 할당 그림 9.21  for  (C)  S1  구조 중간 코드의 메모리 할당 예

79 for 문의 중간 코드 생성하는 의미 규칙 S → for (C) S1 { TEST = new(Label);
                                            EXIT = new(Label);                                             B.true = new(Label);                                             B.false = new(Label);                                             S.c = cogen ('label'  TEST) || C.c;                                                || cogen ('label'  B.false) || cogen ( 'goto'  EXIT ) ;                                                || cogen ('label'  B.true) || S1.c;                                                || cogen ( 'goto'  TEST ) ;                                                || cogen ('label'  EXIT) || R.c;                                              }

80 실습 9.9 C 프로그래밍 언어의 증감연산자(++, --)의 전위(++k, --k)인 경우와 후위(k++, k--)인 경우의 코드를 생성하는 의미 규칙을 구현하시오.

81 9.4.3.4 함수 호출의 중간코드 S → fn ( Arg_list ) Arg_list → Arg_lis , E
Arg_list → E       아래의 함수 호출 문을 번역해 보자. k = 0; sum(k, j, n, 34); k = k + 1;

82 함수 호출 중간코드 중간 코드는 함수 sum와 인자가 k, j, n, 34이며 몇 개인지를 알린다. arg k arg j
중간코드는 k, j, n, 34 는 인자이며, sum은 함수이고, 인자 수는 4 개                  arg  k                  arg  j                  arg  n                  arg  34                  call  sum, 4

83 함수 호출 중간코드의 메모리 할당 그림 9.22 함수 호출 문 중간 코드의 메모리 할당

84 함수 호출문의 중간 코드 생성 의미 규칙 S → fn ( Arg_list ) {
                                  메모리 큐에 있는 각 인자 a 에 대하여, cogen ('arg'  a);                                    cogen ('call' fn.p);                                  } Arg_list → Arg_lis,  E    {메모리 큐의 끝에 수식 E.p 의 코드를 접속한다;} Arg_list → E                   {E.p 에 대해서만 메모리 큐를 할당한다}

85 실습 9.10 switch 문에 대한 중간 코드를 생성하는 의미 규칙을 만들고 아래 switch 문의 중간 코드를 생성하시오.
switch  (a) {       case  1 : k = k + 1;                   break;       case  2 : k = k * 1;                     break;       case  3 : k = k / 1;     case  4 : k = k - 1;                     break;       default : k = 0; }  

86 9.4.4 선언문의 번역과 중간 코드 생성 여기에서는 자료형 선언과 배열의 번역을 살펴본다.

87 9.4.4.1 선언문의 번역과 의미 규칙 Decl → Typ id ; Decl |Typ id Arrtyp ; Decl |ε
   Typ → Styp | Arrtyp    Styp → int |float    Arrtyp → [  num ] Arrtyp |ε 아래 예를 살펴보자. int a; float f, r; int k[4][6]; a 라는 이름으로 16비트(기계에 따라 다름) 정수형 값을 저장할 공간을 확보 32비트(기계에 따라 다름) 유동소수점형 값을 저장하는 공간을 확보 16비트 정수형 값을 저장하는 공간을 24개 확보

88 그림 9.23 정수 선언문 int id;와 배열 선언문 int id[num]; 의 파스 트리

89 배열 선언의 메모리 공간 할당 예 그림 9.24 메모리 공간에 저장할 공간 할당 예

90 배열 선언의 속성 예 int a[5][6]; 이 문장은 아래 속성이 있다. 정수형이다 배열이다 배열 이름은 a 이다 이차원이다
전체 30 개의 원소가 있다 5개 행과 6개열이 있다 원소의 처음과 끝은 [0][0]와 [4][5]이다 초기 값은 알 수 없다 배열이름 a는 이 배열의 첫 번째 원소의 포인터이다 배열이름 a는 이 배열의 첫 번째 원소의 주소이다

91 언문의 문법 구조에 추가한 의미 규칙 t는 타입이며, w는 저장되는 값의 바이트 수이다.
   Decl → Typ id  ; Decl            { cogen( 'entertable'   (id.name, t));}    Decl → Typ id  Arrtyp ; Decl { Decl.type = Arrtyp.type;}    Decl → ε    Typ → Styp                              { t = Styp.type;      w = Styp.width; }  /*  w 바이트의 저장할 값  */    Typ → Arrtyp1                         { t = Arrtyp.type;   w = Arrtyp.width; }  /*  배열 바이트 수  */    Styp → int                                { Styp.type = integer; Styp.width = 2; }  /*  2 바이트  */    Styp → float                             { Styp.type = float;     Styp.width = 4; }  /*  4 바이트  */    Arrtyp → [  num ] Arrtyp1      { array(num.value, Arrtyp1.type);                                                        Arrtyp.width = num.value × Arrtyp1.width; }    Arrtyp → ε               { Arrtyp.type =   t;     Arrtyp.width = w; }  /*  w 바이트  */ t는 타입이며, w는 저장되는 값의 바이트 수이다. { array(num.value, Arrtyp1.type);  Arrtyp.width = num.value × Arrtyp1.width; }는 원소의 수와 그 원소의 타입을 알리고, 배열 전체 크기는 원소의 수와 그 원소의 크기(바이트 수)를 곱한 값이다.

92 단순 선언문 의미 규칙 관찰하기 int a ; float r ;

93 배열 선언문의 의미 규칙 관찰하기 int k[4][6];

94 9.4.4.2 배열원소의 주소 지정 번역 이차원 배열 int m[4][6]; m00 m01 m02 m03 m04 m05 m10

95 일반적인 m[i][j] 까지 변위를 구하는 공식
   int m[R][C];   위와 같이 선언한 행렬(행은 0에서 R까지, 열은 0에서 C까지 이다)에서 한 원소 m[i][j] 까지 변위를 구하는 공식을 만들 수 있다.            m[i][j] = (i - 0) × C + (j - 0) 그러므로 이 원소 m[i][j]는 시작 주소 start 에서부터 (i - 0) × C + (j - 0)번째에 있는 원소이므로 m[i][j]의 주소는 아래와 같다.       m[i][j]의 주소 = start + (i - 0) × C + (j - 0) 이 공식은 배열의 한 원소 m[i][j] 가 한 바이트인 경우이다.

96 한 원소가 w 바이트인 경우 실제의 한 원소 m[i][j]의 주소는 한 원소가 차지하는 바이트 수 w를 곱해야 하므로 아래처럼 계산하고 모든 배열에 마찬가지로 적용한다.       m[i][j]의 주소 = start + ((i - 0) × C + (j - 0)) × w

97 삼차원 배열 int m[4][6][3]; 의 선언 예
일반적으로 int m[R][C][P]; 로 선언한 삼차원 배열에서 한 원소 m[i][j][k]를 참조하려면 변위는 공식 (k - 0) × R × C + (i - 0) × C + (j - 0) 로 계산한다.

98 N-차원 배열 m[l1:n1][l2:n2]....[lm:nm] 처럼 각 차원이 l1, l2, ... lm 에서 시작하는 프로그래밍 언어에서는 아래처럼 각 인덱스에서 l1, l2, ... lm 를 각각 뺀다. 원소 m[i1] [i2] [i3] ... [im]의 변위 = (i1 - l1) × n2 × n3 × n4 × ... × nm                  + (i2 - l2) × n3 × n4 × ... × nm                  + (i3 - l3) × n4 × ... × nm                                    + (im-1 - lm-1) × nm                  + (im - lm)

99 배열 참조를 정의하는 문법과 의미 규칙 1. S → id = E { .... 생략.......}
     2. S → A = E      { cogen (A.p.base  '['  A.p   ']'  '='  E.p );}        3. E → E + T      { .... 생략 }             4. E → T          { .... 생략 }        5. T → T * F      { .... 생략 }        6. T → F          { .... 생략 }          7. F → id          { .... 생략 }        8. F → number      { .... 생략 }        9. F → A          { F.p = new( );                                                    cogen (F.p  '='  A.array.base   '['   A.p  ']');}         10. A → A1 [ E ]    { A.array = A1.array;                                                    A.type = A1.type.elem;                                                    t = new ( );                                                    A.p = new( );                                                    cogen ( t  '='  E.p   '*'   A.type.width);                                                    cogen (A.p  '='  A1.p   '+'  t);}     11. A → id [ E ]    {  A.array = get(id.p);                                                    A.type = A.array.type.elem;                                                    cogen (A.p  '='  E.p   '*'   A.type.width);}

100 넌터미널 A 는 합성 속성이 있다. A.p 는 배열을 참조를 위해 원소 m[i1] [i2] [i3] ... [im]의 변위를 계산하는 동안 사용되는 일시적인 주소를 나타낸다. A.array는 심볼 테이블에서 각 식별자로 있는 배열 이름을 가리키는  포인터이다. 또한 시작 주소 A.array.base(배열 원소의 0 번째이다)는 인덱스의 모든 수식이 분석되고 난 후에 배열 참조의 실제 값을 결정하는데 사용한다. A.type는 A로 생성된 부분 배열의 타입이다. 어떤 타입 t 에 대해 크기가 t.width 로 주어지면 크기보다는 타입을 검사하는데 사용한다. 어떤 배열 타입 t에 대해 t.elem은 원소 타입을 나타낸다. 생성 규칙 S → A = E는 배열 참조 위치 A.array.base[A.p]로 계산되어 E.p 주소의 값을 A 위치에 할당하는 중간코드를 생성한다.

101 x[i][j] = x[3][5] - k; 의 파스트리와 중간 코드 생성 과정
          t1 = i * 14               t2 = j * 12               t3 = t1 + t2               t4 = 3 * 14               t5 = 5 * 12               t6 = t4 + t5               t7 = x [ t6 ]               t8 = t7 + k               x [ t3 ] = t8

102 그림 9.27 배열 참조 x[i][j] = x[3][5] - k의 파스 트리와 중간 코드 번역 과정

103 실습 9.11 C 프로그래밍 언어의 일차원 배열 선언 int x[40];에서 a = x[4]; 같이 배열을 참조할 때 배열 참조하는 부분에 대한 중간 코드를 생성하시오.

104 실습 9.12 C 프로그래밍 언어의 삼차원 배열 선언 int x[10][20][30];에서 x[3][6][14]; 를 파싱할 때 배열을 참조하는 중간 코드들 생성하는 과정을 보이시오(위의 문법을 적용하시오).

105 9.5 타입 검사 여기에서는 의미 분석 과정에서 연산 결과가 어떤 타입을 가지는지를 검사하는 방법을 알아본다.

106 9.5.1 타입 검사의 의미 표현 아래 같이 선언한 경우에는 a, b 가 정수형이고 c, d는 유동소숫점형이므로 c와 d는 유동소수점형으로 곱하기 연산을 수행하여 결과는 유동소수점형 값이다.          int a, b;          float c, d;          a = b + c * d; c 나 d 의 타입에 따라 c * d 의 타입이 정해지고, 또한 b와 c * d의 각 타입에 따라 b + c * d 의 타입이 결정된다. 그러므로 a의 타입은 b + c * d 의 타입에 따라 최종으로 결정된다.

107 타입의 합성 방식 합성에 의한 최종 타입은 아래와 같다.
      Type(x1, x2,...., xn) = Type (((((Type(Type(x1), x2) ... xn))))) xi, i = 1,..., n 가 변수나 부분 수식이고 Type(x1, x2,...., xn)는 i = 1,..., n 의 각 i 에 대한 Type(xi) 의 타입이다. 그러므로 Type(x1, x2, ...., xn)는 각 부분 수식의 타입 합성에 의한 최종 타입이다. 문법 E → E1 + E2 의 최종 타입은 Type(E) = Type(Type(E1), E2)이다.

108 타입의 추론 방식 추론 방식은 언어가 사용되는 방법에 따라 타입을 결정하는 것이다. 이 추론 방식을 살펴보기 위해 아래 선언문을 살펴보자.               int a, b, c;               a = b + c; 여기에서는 int a, b, c; 로 선언한 변수의 타입인 “정수형”이 그 다음 문장인 a = b + c; 의 각 변수에 전달되어 Type(a) = Type(b) = Type(c) = "정수형“ 으로 타입이 결정된다. 그러므로 이런  추론에 의한 최종 타입은 아래와 같다.                 f : Type(x) → Type(y)

109 9.5.2 타입 검사의 의미 규칙 구현 Decl → Typ id ; Decl |Typ id Arrtyp ; Decl |ε
   Typ → Styp | Arrtyp    Styp → int |float    Arrtyp → [  num ] Arrtyp |ε 이 문법으로 아래와 같은 문장을 만들 수 있다.     int k, knu;     float f, real_number, p;     int ar[3][4];

110 할당문과 제어문의 타입 검사 의미 규칙     S → id = E            { if  (id.type == E.type) S.type = E.type else  cogen ("type_error");}     S → if ( C ) S1       { if  (C.type == boolean) S.type = S1.type else cogen ("type_error");}     S → while ( C ) S1 { if  (C.type == boolean) S.type = S1.type else cogen ("type_error");} 7.

111 수식 할당문의 타입 검사 의미 규칙 수식 할당문의 할당기호(=)오른쪽에는 상수, 변수, 수식, 배열원소, 함수 등이 올 수 있기 때문에 이 문법 구조는 아래와 같다.    E → char   E → num    E → num.num     E → id       E → E1 ao E2

112 타입 변환 예 이 문법에서 생성하는 간단한 수식에서 ao가 산술 연산자(+, -, *, /)  중 하나라면 피연산자 두 개의 타입에 따라 연산 결과는 아래와 같다.                 정수형 ao 정수형  → 정수형                 정수형 ao 유동소수점형  → 유동소수점형                 유동소수점형 ao 정수형  → 유동소수점형                 유동소수점형 ao 유동소수점형  → 유동소수점형

113 의미 규칙 E → char {E.type = character;} E → num {E.type = integer;}
            E → num. num         {E.type =  float;}             E → id                      {E.type = get(id.name);}             E → E1 ao E2           {E.p  = new(t);                                                 if (E1.type == integer  &&   E2.type == integer)                                                        {                                                       cogen (E.p  `=` E1.p   `int ao`  E2.p);  /* 정수형 연산 */                                                       E.type = integer;                                                      }                                                 else if (E1.type == float  &&   E2.type == float)                                                         {                                                       cogen (E.p  `=` E1.p  `float ao`  E2.p); /* 유동소수점 연산 */                                                       E.type = float;                                                       }

114 의미 규칙 else if (E1.type == integer && E2.type == float) { r = new(t);
                                                      {                                                        r  = new(t);                                                       cogen(r `=` `(float)` E1.p); /* 정수를 유동소수점으로 변환 */                                                        cogen( E.p   `=`   r   `float ao`  E2.p ) ; /* 유동소수점 연산 */                                                         E.type = float;                                                        }                                                 else if (E1.type == float  &&   E2.type == integer)                                                         {                                                        r  = new(t);                                                       cogen(r `=` `(float)`  E2.p); /* 정수를 유동소수점으로 변환 */                                                        cogen( E.p   `=`   E1.p   `float ao` r); /* 유동소수점 연산 */                                                        E.type = float;                                                       }                                               }

115 의미 규칙 따른 할당문과 수식의 예 int c, d; float a, b, e; .... a = b + c * d + e;
                ....              a = b + c * d + e; 수식 a = b + c * d + e;은 아래와 같은 중간 코드로 번역된다.              t1 = c  int*  d              t3 = (float)  t1       /*  정수형  t1 을  유동소수점으로 변환   */              t2 = b float+  t3    /*  유동소수점 더하기 연산   */              t4 = t2  + e              a = t4

116 제 9 장 끝