Compiler Design 12th Homework Solution

       

1. 다음 구문 지시적 정의를 가지고 $10+5*8$$ 문장에 대한 주석 파스 트리를 만드세요.

img

   

2. 다음 두 식을 각각 트리플(triple), 간접 트리플, 쿼드러플(quadruple)로 변환하세요.

2-1. $A=B+C*/E-F$

  • 트리플

    번호 연산자 op 피연산자1 피연산자2
    [0] * C D
    [1] / [0] E
    [2] + B [1]
    [3] - [2] F
    [4] = A [3]
  • 간접 트리플

    수행순서 번호 연산자 op 피연산자1 피연산자2
    1.[0] [0] * C D
    2.[1] [1] / [0] E
    3.[2] [2] + B [1]
    4.[3] [3] - [2] F
    5.[4] [4] = A [3]
  • 쿼드러플

    번호 연산자 op 피연산자1 피연산자2 결과
    [0] * C D T1
    [1] / T1 E T2
    [2] + B T2 T3
    [3] - T3 F T4
    [4] = T4   A

2-2. $G=C*D/E$

  • 트리플

    번호 연산자 op 피연산자1 피연산자2
    [0] * C D
    [1] / [0] E
    [2] = G [1]
  • 간접 트리플

    수행순서 번호 연산자 op 피연산자1 피연산자2
    1.[0] [0] * C D
    2.[1] [1] / [0] E
    3.[2] [2] = G [1]
  • 쿼드러플

    번호 연산자 op 피연산자1 피연산자2 결과
    [0] * C D T1
    [1] / T1 E T2
    [2] = T2   G

   

3. 다음 구문 지시적 정의를 사용하여 산술식 $(4*7+1)$$ 에 대한 스택 기반 구문 지시적 번역을 수행하고 그 결과를 아래 표에 적으세요.
단계 상태 스택 기호 스택 값 스택(VAL) 입력 기호 적용 규칙
1 0     $(4*7+1)$$ 이동 4
2 0 4 $($ _ $4*7+1)$$ 이동 5
3 0 4 5 $(4$ _4 $*7+1)$$ 감축 $F \rightarrow digit$
4 0 4 3 $(F$ _4 $*7+1)$$ 감축 $T \rightarrow F$
5 0 4 2 $(T$ _4 $*7+1)$$ 이동 7
6 0 4 2 7 $(T*$ _4_ $7+1)$$ 이동 5
7 0 4 2 7 5 $(T*7$ _4_7 $+1)$$ 감축 $F \rightarrow digit$
8 0 4 2 7 10 $(T*F$ _4_7 $+1)$$ 감축 $T \rightarrow T1*F$
9 0 4 2 $(T$ _28 $+1)$$ 감축 $E \rightarrow T$
10 0 4 8 $(E$ _28 $+1)$$ 이동 6
11 0 4 8 6 $(E+$ _28_ $1)$$ 이동 5
12 0 4 8 6 5 $(E+1$ _28_1 $)$$ 감축 $F \rightarrow digit$
13 0 4 8 6 3 $(E+F$ _28_1 $)$$ 감축 $T \rightarrow F$
14 0 4 8 6 9 $(E+T$ _28_1 $)$$ 감축 $E \rightarrow E1+T$
15 0 4 8 $(E$ _29 $)$$ 이동 11
16 0 4 8 11 $(E)$ _29_ $ 감축 $F \rightarrow (E)$
17 0 3 $F$ 29 $ 감축 $T \rightarrow F$
18 0 2 $T$ 29 $ 감축 $E \rightarrow T$
19 0 1 $E$ 29 $ 수락
20   $S$ 29    

   

4. 다음은 행렬 곱셈을 위한 프로그램을 C로 작성한 것입니다.
for(i=0; i<n; i++)
    for(j=0; j<n; j++)
        c[i][j] = 0.0;
for(i=0; i<n; i++)
    for(j=0; j<n; j++)
        for(k=0; k<n; k++)
            c[i][j] = c[i][j] + a[i][k] * b[k][j];

4-1. 위 프로그램을 3-주소 코드로 변환하세요. 이 때, 배열의 자료형은 int이며, C 언어는 행 우선 순서로 배열을 저장합니다. 배열의 크기는 $n \times n$로 선언되었다고 가정합니다.

번호 코드 리더
1 i=0 리더 1
2 if i >= n goto 13 리더 2
3 j=0 리더 3
4 if j >=n goto 11 리더 4
5 t1 = n * i 리더 5
6 t2 = t1 + j  
7 t3 = t2 * 4  
8 c[t3] = 0.0  
9 j = j + 1  
10 goto 4  
11 i = i + 1 리더 6
12 goto 2  
13 i=0 리더 7
14 if i >= n goto 40 리더 8
15 j=0 리더 9
16 if j>=n goto 38 리더 10
17 k=0 리더 11
18 if k>=n goto 36 리더 12
19 t1 = n * i 리더 13
20 t2 = t1 + j  
21 t3 = t2 * 4  
22 t4 = c[t3]  
23 t5 = n * i  
24 t6 = t5 + k  
25 t7 = t6 * 4  
26 t8 = a[t7]  
27 t9 = n * k  
28 t10 = t9 + j  
29 t11 = t10 * 4  
30 t12 = a[t11]  
31 t13 = t8 * t12  
32 t14 = t4 + t13  
33 c[t3] = t14  
34 k = k + 1  
35 goto 18  
36 j = j + 1 리더 14
37 goto 16  
38 i = i + 1 리더 15
39 goto 14  
40 halt 리더 16

4-2. 위에서 작성한 3-주소 코드로부터 흐름 그래프를 구성하세요.

Entry B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 B15 B16 Exit

4-3. 흐름 그래프에서 루프(loop)를 찾으세요.

{B2, B3, B4,B6}

{B4, B5}

{B12, B13}

{B9, B10, B11, B12, B14, B15}