Lec14.IR Translation (1) - 14주차 1강

부제: Automatic Translation

12월 2일, 14주차 1강

* 개인 공부를 위해 정리한 것입니다. 정확한 내용은 꼭 본인이 공부하는 교재를 참고하시기 바랍니다.

컴파일러 디자인의 복잡도를 줄이기 위해 IR을 사용한다

• x=0, t1=0
• x에 t1 값을 할당
• t3에 x값을 할당
• t4에 1을 할당
• t2에 t3과 t4의 합을 할당
• t2를 write한 후 정지

• 초기화, sum=0, i=0
• 2:SKIP: 반복문 시작
• 조건 검사
  • t4에 i값 복사
  • t5에 10 복사
  • t3에 t4<t5 결과 저장
  • 조건이 거짓이면 3으로 점프
• 반복문 본문
  • sum=sum+i를 계산해 sum에 저장
  • i++ 연산을 수행
  • 반복문 시작으로 돌아가기 위해 goto2
• 3:SKIP: 반복문 종료
• 출력 및 종료
  • sum값을 출력하고 HALT

 

• 소스 언어과 타겟언어 사이의 자동변환 절차를 정의
  • S: 변환하려는 소스 언어로 작성된 프로그램, T: 변환 결과로 얻어진 타겟언어로 작성된 프로그램
  • 변환 절차를 통해 소스 프로그램 S를 타겟 프로그램 T로 변환
  • 변환된 프로그램 T는 의미적으로 동등해야 함. 프로그램 S와 T는 같은 동작을 수행해야 함

• 프로그래밍 언어의 정의
  • 구문 syntax: 프로그램의 구조를 정의하는 규칙의 집합
    • 문법을 이해할 수 잇으며, 올바른 프로그램이 어떻게 작성되어야 하는지 명시
    • concrete syntax: 프로그램의 완전한 구조를 정의. 사람이 읽고 작성할 때 사용하는 실제 구문
      • 조건문 if(b) {c1} else {c2}처럼 완전한 문법. 프로그램을 작성하거나, 코드를 읽고 이해하는 데 사용
    • abstract syntax: 추상적 구문, 프로그램의 핵심 구조만 정의. 구체적인 문법 요소 생략
      
      • if b c1 c2처럼 간소화된 형태. 프로그램을 자동 생성, 분석, 최적화하는데 사용. 컴파일러 등에서 사용
  • 의미 Semantics: 프로그램이 실행될 때의 의미를 정의하는 규칙의 집합
    • 프로그램의 동작을 설명
    • 특정 조건에서 실행 흐름이 어떻게 변화하는지 명시

 

구체적인 문법과 추상적인 문법을 비교해보면 정말 최소화해서 설명하고 있음을 알 수 있음

 

 

• +는 서로소 합집합을 나타냄. 두 개의 겹치지 않는 집합을 더함

• inference rule
• 만약 A가 참이라면, B도 참이다. A: 가정, B: 결론
  
  • 단순 가정: A가 참이면, B를 도출
  • 공리 Axiom: 가정 없이 B가 참
  • 다중 가정: A와 B가 둘 다 참이면 C가 참.
•  Big-Step Operational Semantics
  • 프로그램 실행의 전체 결과를 기반으로 의미를 정의
  • 프로그램의 입력과 출력 상태를 바로 연결하여 설명

gpt가 말아준 예시

 

• 조건이 참일 때
  • 메모리 상태 M에서 표현식 e를 평가해 값 n을 얻음
  • 조건 확인: n!=0이면 e는 참
  • 문장 실행: stmt1을 실행해 새로운 메모리 상태 M1으로 변환
  • 결론: 전체 조건문은 M1 상태를 결과로 가짐
• 조건이 거짓일 때
  • 메모리 상태 M에서 표현식 e를 형가해 값 0을 얻음
  • 조건 확인: e=0이면 e는 거짓
  • 문장 실행: stmt2를 실행해 새로운 메모리 상태 M1으로 전환
  • 결론: 전체 조건문은 M1 상태를 결과로 가짐
• 추론 규칙의 기본 구조: 메모리 상태 M에서 문장 stmt를 실행했을 때 새로운 메모리 상태 M'을 얻는다
  • 선언 decl: 선언을 수행하면 M'로 전환
  • 왼쪽 값: lv을 평가해 위치 l을 얻음
  • 표현식: 표현식을 평가해 값 v를 얻음

• 맨 위부터 순서대로
•  declaration
  • 변수 선언: 변수 x 선언 시, 현재 메모리 상태 M에 x를 0으로 초기화해 추가
  • 배열 선언: 배열 x 선언하고, 크기를 표현식 e로 평가해 n을 얻음. 새로운 메모리 공간을 n만큼 할당하고 0으로 초기화
• statement 실행
  
  • 할당: lv 왼쪽값을 평가해 위치 l을 갖고 표현식 e를 평가해 값 v를 얻는다. 메모리 M의 l 위치에 v를 저장한다
  • 조건문
    • 참인 경우: 조건 e를 평가해 n을 얻고, n!=0이면 stmt1을 실행해 M1으로 전환
    • 거짓인 경우: 조건 e를 평가해 0이면 stmt2를 실행해 M1으로 전환
  • 반복문
    • 참인 경우: 조건 e를 평가해 참이면 stmt 실행, 다시 조건을 확인해 반복
    • 거짓인 경우: 조건 e가 거짓이면 실행 종료
  • 복합문: 첫 번째 문장을 실행해 M1 상태로 전환 후, 두 번째 문장을 실행해 최종상태 M2로 전환
  • do-while 반복문: 본문 stmt를 먼저 실행한 후, 조건 e를 평가해 참이면 반복
  • 읽기: 사용자 입력 값을 변수 x에 저장
  • 쓰기: 표현식 e를 평가하고 결과를 출력. 메모리 M 상태는 변하지 않음

• lv: l value 왼쪽 값
  
  • 변수: 변수 x는 메모리에서 변수 이름과 동일한 위치를 가리킴
  • 배열:
    • 배열 x[e]의 인덱스 e를 평가해 n1을 얻음
    • x가 메모리 M에서 (a,n2)로 매핑된 배열임을 확인함
    • n1이 배열 범위 내에 있는지 확인함
    • 배열의 주소 a와 인덱스 n1을 리턴함
• expression: 왼쪽 값 lv를 평가해 위치 l을 찾음. 메모리 M에서 해당 위치의 값을 반환함
• 덧셈: 두 표현식 e1과 e2를 평가해 각각 n1,n2를 얻고, 두 값을 더함.
• 음수: 표현식 e를 평가해 음수를 계산
• 같음: 두 표현식 결과가 같으면 1(참)을 반환. 다름: 두 표현식 결과가 다르면 0(거짓)을 반환
• 크다: e1이 e2보다 크면 1을 반환
• 논리 합: e1 또는 e2 중 하나라도 참이면 1을 반환
• 논리곱: e1과 e2 모두 참이면 1을 반환
• 논리 부정: e가 거짓이면 참으로 반환

• skip: 아무것도 하지 않는 명령어, nop 역할
• 메모리 할당: alloc, 크기 n만큼 메모리 할당하고, 시작 주소를 변수 x에 저장
• 산술 연산: x=y bop z, x=y bop n, y와 z의 값을 이항 연산자(bop)로 계산해 x에 저장
• 단항 연산: x=uop y, 변수 y에 단항 연산자 uop 적용해 결과 x에 저장
• 변수 복사 및 상수 할당: x=y, x=n, x에 변수 y의 값 또는 상수 n 복사
• 점프: goto L
• 조건부 점프: if x goto L, if False x goto L
• 배열 접근: x=y[i], x[i]=y
• 입출력: read x, write x, 사용자 입력 값을 x에 저장하거나, x의 값을 출력

• 메모리 상태 = 주소(특정 메모리 위치)와 값의 매핑
• 주소: 일반 변수 이름+메모리 주소x주소에서 상대적 위치
• 값: 정수형 값+배열이나 동적 메모리의 시작 주소x해당 메모리 블록의 크기
• 메모리 주소
• 오프셋: 메모리 주소에서 상대적인 위치
• 크기: 메모리 블록의 크기

• skip: 메모리 상태 M은 변하지 않음
• alloc
  • n 크기의 메모리 블록이 아직 할당되지 않은 경우에만 수행 가능.
  • 새로운 주소 l에 크기 s의 블록 할당, 블록 초기값은 모두 0으로 설정. x는 블록의 시작 주소와 크기 가리킴
• 산술 및 논리 연산
  • bop: 이항연산, y와 z의 값을 계산해 x에 저장. (덧셈, 곱셈, 크기 비교 등)
  • uop: 단항 연산, 음수 변환, 논리 부정 등
• 변수 복사 및 상수 할당: y의 값을 x에 복사하거나 상수 n을 x에 저장
• 점프 명령: 무조건 점프 - 지정된 라벨 L로 이동, 조건부 점프 - x가 참이면 L로 점프, 거짓이면 다음 명령으로 진행
• 배열 접근:
  • 읽기- y의 i번째 요소를 읽어 x에 저장. i는 유효 범위 내에 있어야 함
  • 쓰기-x[i] 위치에 y값 저장, i가 유효한 범위 내에 있어야 함.
• 입출력:
  • 읽기: 사용자로부터 입력값을 읽어 x에 저장. 출력: x의 값을 출력

• 첫 번째 명령 설정: 프로그램의 첫 번째 명령어를 instr로 설정. 프로그램은 항상 첫 번째 명령어부터 실행 시작
• 초기 메모리 상태 설정: 초기 메모리 상태 M을 빈 매핑으로 설정. M=[]은 메모리 공간 초기화. 변수에 아무 값도 할당x
• 반복수행
  • 현재 명령어 instr이 HALT라면 프로그램 실행 종료
  • 메모리 상태 업데이트, 현재 명령어 instr에 따라 메모리 상태 M' 계산. 메모리 상태 업데이트
  • 다음 실행할 명령어 결정. goto L, if x goto L, if False x goto L. L로 점프.
  • 그 외의 경우: 프로그램에서 instr 바로 뒤에 있는 명령어로 이동

• 상수 변환: 상수 n을 t라는 새로운 변수에 할당. t는 n의 값 가짐
• 변수 변환: x의 값을 t에 복사. t는 x의 값 가짐.
• 배열 접근 x[e]: e를 t1에 계산, 해당 명령어를 code로 기록. t2에 x[t1] 값을 저장하는 명령어 추가. t2는 x[e]값 가짐
• 덧셈: e1을 t1에 e2를 t2에 계산. t1+t2 결과를 t3에 저장. t3은 e1+e2의 값을 가짐.
• 부호 반전: e를 t1에 계산. -t1의 결과를 t2에 저장. t2는 -e의 값을 가짐.

• 상수 2가 변환되어 임시 변수 t에 저장
• 변수 x의 값이 임시변수 t에 복사
• 상수 1을 t1에 저장. x[t1]의 값을 계산해 t2에 저장. t2는 x[1]의 값 가짐
• 상수 2를 t1에 저장. 상수 3을 t2에 저장. t1과 t2의 합을 t3에 저장.
• 상수 5를 t1에 저장. -t1의 값을 t2에 저장. t2는 -5 값 가짐.
• 변수 x를 t1에 저장. 상수 1을 t2에 저장. t1+t2를 계산해 t3에 저장. 상수 2를 t4에 저장. y[t4] 계산해 t5에 저장. t3+t5를 계산해 t6에 저장.

• 대입 연산 x=e
  • 식 e를 trans_e를 사용해 변환. trans_e는 (t1,code1)을 반환
  • code1은 e를 계산하는 명령어 목록
  • t1에 저장된 결과를 변수 x에 대입하는 명령어 추가
• 배열 대입 연산 x[e1]=e2
  • e1과 e2를 각각 trans_e를 사용해 변환
  • t1은 배열 인덱스 e1의 결과, t2는 대입할 값 e2의 결과
  • [x[t1]]=t2]는 x[t1] 위치에 t2 값을 저장하는 명령어
• 입력 명령: read x 명령은 값을 읽어 x에 저장하는 단일 명령어로 변환
• 출력 명령:
  • e를 trans_e를 사용해 변환
  • code1은 e를 계산하는 명령어 목록, t1은 계산 결과
  • [write t1] 명령어는 t1의 값을 출력

trans_s(if e stmt1 stmt2) =
  (* e를 표현식으로 변환하여 결과를 얻는다. *)
  let (t1, code1) = trans_e(e) (* t1: e의 결과를 저장할 임시 변수, code1: e를 계산하는 명령어 *)
  
  (* stmt1과 stmt2를 각각 변환하여 명령어 목록을 얻는다. *)
  let code_t = trans_s(stmt1) (* code_t: stmt1의 변환된 명령어 *)
  let code_f = trans_s(stmt2) (* code_f: stmt2의 변환된 명령어 *)

  in
    (* e를 평가하는 코드 추가 *)
    code1 @

    (* 조건 결과에 따라 분기 *)
    [if t1 goto lt] @  (* t1이 참이면 lt로 이동 *)
    [goto lf] @        (* t1이 거짓이면 lf로 이동 *)

    (* stmt1을 실행하기 전 레이블 추가 *)
    [(lt, skip)] @     (* lt: stmt1의 시작 지점 *)
    code_t @           (* stmt1의 명령어 추가 *)

    (* stmt1 실행 후 조건문 끝으로 이동 *)
    [goto lx] @        (* 조건문 종료 후 lx로 이동 *)

    (* stmt2를 실행하기 전 레이블 추가 *)
    [(lf, skip)] @     (* lf: stmt2의 시작 지점 *)
    code_f @           (* stmt2의 명령어 추가 *)

    (* stmt2 실행 후 조건문 끝으로 이동 *)
    [goto lx] @        (* 조건문 종료 후 lx로 이동 *)

    (* 조건문 종료 지점 레이블 추가 *)
    [(lx, skip)]       (* lx: 조건문 끝 *)

 

trans_s(while e stmt) =
  (* 표현식 e를 변환하여 결과를 얻음 *)
  let (t1, code1) = trans_e(e)  (* t1: e의 결과를 저장하는 임시 변수, code1: e를 평가하는 명령어 *)

  (* 본문 stmt를 변환하여 명령어 시퀀스를 얻음 *)
  let code_b = trans_s(stmt)  (* code_b: stmt의 변환된 명령어 *)

  in
    (* 루프 시작 지점 레이블 추가 *)
    [(le, skip)] @           (* le: while 루프의 조건을 평가하는 시작 지점 *)
    code1 @                  (* 조건 e를 평가하는 명령어 추가 *)
    [ifFalse t1 lx] @        (* 조건이 거짓이면 lx로 이동하여 루프를 종료 *)
    code_b @                 (* 루프 본문 실행 *)
    [goto le] @              (* 본문 실행 후 다시 조건으로 돌아감 *)
    [(lx, skip)]             (* lx: 루프의 끝 지점 레이블 *)

trans_s(do stmt while e) =
  (* do-while 루프는 stmt를 먼저 실행한 후, while 루프의 명령어를 추가 *)
  trans_s(stmt) @ trans_s(while e stmt)

 

(* Declarations *)
trans_d(int x) = 
  [x = 0]  (* 변수 x를 선언하고 초기값 0을 할당 *)

trans_d(int[n] x) = 
  [x = alloc(n)]  (* 크기 n의 배열을 위해 메모리를 할당하고 x에 그 메모리 위치를 저장 *)

(* Blocks *)
trans_b(d1, ..., dn, s1, ..., sm) = 
  trans_d(d1) @ ... @ trans_d(dn)  (* 모든 선언문 d1, ..., dn 변환 *)
  @ trans_s(s1) @ ... @ trans_s(sm)  (* 모든 명령문 s1, ..., sm 변환 *)

 

Examples:
1. x = 1 + 2 
   Translation steps:
   t1 = 1;             (* 임시 변수 t1에 값 1 저장 *)
   t2 = 2;             (* 임시 변수 t2에 값 2 저장 *)
   x = t1 + t2;        (* t1 + t2 계산 후 결과를 x에 저장 *)

2. x[1] = 2
   Translation steps:
   t1 = 1;             (* 임시 변수 t1에 인덱스 값 1 저장 *)
   t2 = 2;             (* 임시 변수 t2에 값 2 저장 *)
   x[t1] = t2;         (* t2에 저장된 값을 x[t1]에 저장 *)

3. if (1) x = 1; else x = 2;
   Translation steps:
   t1 = 1;             (* 조건식 1을 평가하고 t1에 저장 *)
   if t1 goto l_true;  (* t1(조건식)이 참이면 l_true로 이동 *)
   goto l_false;       (* 그렇지 않으면 l_false로 이동 *)
   (l_true: skip);     (* 참 분기 시작 레이블 *)
   t2 = 1;             (* 임시 변수 t2에 값 1 저장 *)
   x = t2;             (* t2의 값을 x에 저장 *)
   goto l_exit;        (* 참 분기 실행 후 종료 지점으로 이동 *)
   (l_false: skip);    (* 거짓 분기 시작 레이블 *)
   t3 = 2;             (* 임시 변수 t3에 값 2 저장 *)
   x = t3;             (* t3의 값을 x에 저장 *)
   (l_exit: skip);     (* 종료 레이블 *)

4. while (x < 10) x++;
   Translation steps:
   (l_begin: skip);    (* 반복문 시작 레이블 *)
   t1 = x;             (* x의 값을 t1에 로드 *)
   t2 = 10;            (* 임시 변수 t2에 값 10 저장 *)
   t3 = t1 < t2;       (* 조건식 x < 10 평가 *)
   ifFalse t3 goto l_exit; (* 조건이 거짓이면 l_exit로 이동 *)
   t4 = x;             (* x의 값을 t4에 로드 *)
   t5 = t4 + 1;        (* t4를 1 증가 *)
   x = t5;             (* 증가된 값을 x에 저장 *)
   goto l_begin;       (* 반복문 시작으로 이동 *)
   (l_exit: skip);     (* 종료 레이블 *)