1. 다음 구문 지시적 정의를 가지고 $10+5*8$$ 문장에 대한 주석 파스 트리를 만드세요.
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-주소 코드로부터 흐름 그래프를 구성하세요.
4-3. 흐름 그래프에서 루프(loop)를 찾으세요.
{B2, B3, B4,B6}
{B4, B5}
{B12, B13}
{B9, B10, B11, B12, B14, B15}