[컴파일러개론] 기말고사 정리

9주차

SDD(Syntax Directed Definition)

파싱 단계에서 의미있는 일을 할 수 있도록 semantic action을 적어놓음

파서 생성기(yacc)에서 주로 사용

lhs에 메모리가 있어 결과를 저장한다.

$$, $1, $2, ... 이름은 rule local

Listener style in Antlr(LL파서)

Type Declaration

 

속성의 종류

synthesized attr

- bottom up으로만 이루어진

- children에 의해 계산

inherited attr

- parent, sibling에 의해 계산

 

AST(Abstract Syntax Tree)

파스트리에서불필요한 정보를 제거한형태

AST 만들기

1. 파싱단계에서 만들기

- LL : 유도할때

- LR : reduce할 때

2. 만들어진 파스트리를 순회하면서 만들기

- SDD를 사용해서 만들기

 

 

On-the-fly evaluation방법

AST node 방문 순서대로 그냥 따라 evaluation

 

S-attributed SDD : synthesized attr.만 가지고 있는

L-attributed SDD : synthesized attr. + 값이왼쪽에서 오른쪽으로 흘러 계산이 이루어지는 경우    

 

10주차

IR(중간언어)

HIR 

AST로부터 번역이 용이

INPUT 언어의 모든 표현력을 그대로 유지(최적화) 

LIR

단순한 instruction으로 구성

Machine의 구조를 어느 정도 표현하게 됨

 

LIR 종류

- N-tuple표기법

- Stack machine code

- Tree 표현

 

a = [b] : load instruction

[a] = b : store instruction

a = addr b : symbolic address

cjump a L : conditional jump

 

3주소 코드

임시변수 : 새 location, 중간값 저장을 위해 사용

 

3주소 코드

1. GCC GIMPLE

GENERIC : 트리 형태 HIR

GIMPLE : 3주소 코드

RTL : 트리 형태 LIR

 

2. LLVM BIT 코드

인터페이스가 깔끔하다. 다양한 plugin 최적화 기능

Stack Machine Code

MSIL(가상 기계 코드)

이식성, 호환성이 목적

 

JVM Bytecode

global 변수는 constant pool에

CIL CODE

 

Tree구조 코드

기계어 코드를 만들 때 좋음

메모리 로드 등이 명시적으로 표현됨

code generation 과정에서 어떻게 묶느냐에 따라 명령어가 다르다.

 

 

11주차

to 3-addr code(고급언어를 3-addr code로 바꾸는과정)

3-addr code(quadruple)

 

HIR to LIR

1줄 => 여러줄(nesting 구조때문)

[[e]] : HIR e에대한 LIR expression

   

중요

 

Statements

IF

WHILE

SWITCH

switch는 lookup 테이블로도구현 가능

but 보안면에서 좋지않음

가시성이 떨어져 최적화가 잘 안됨

 

storage management

registers : 빠른접근, 간접 접근 불가 

memory : 상대적으로 느린 접근, 간접 접근 가능

 

all memory approach

모든 변수를 일단 memory로 하고 이 중 가능한  것은 register로 조정

 

원칙이 있으면 좋겠다.

=> standard approach

globals / statics : memory

주소 필요한 변수, struct, arrays => memory

아니면 virtual register

 

memory의 4대 영역

code space : 명령을 저장하는 공간

static(or global) : 프로그램과 life time을 함께하는 변수들 집합

stack : local 변수들

heap : malloc, new에 의해 동적으로 할당되는 공간

변수 바인딩

environment: <변수, storage location>

state : <변수, 값>

 

바인딩: 어떤 environment에서 변수 이름 N이 storage location S에 지정되면 N이 S에 바인딩 된다고 함

 

Static allocation

global변수, constants, static변수들

프로그램 전체 수행 동안 안변하는 location으로 바인딩 하는 것

 

Heap allocation

연속적인 global 영역의 일부를 OS로부터 받은 것

프로그램 수행 중 요청과 반환(deallocate, free)도 해야함

 

runtime stack

한 함수 call마다 하나씩 두는 frame들(activation record)이 구성하는 stack

 

activation record : 해당 함수 수행을 위한 execution environment

local변수, 인자, 리턴값, 기타 임시 storage들이 들어감

 

entry의 크기가 가변적이기 때문에 포인터 2개로 표현한다.

SP : Stack pointer, frame top을 가리킴

FP : Frame pointer, frame base를 가리킴

 

=> 2개의 포인터를 이용함으로써

small offset 유지 -> instruction도 짧아짐

함수 호출 전

actual parameters, 리턴 주소를 스택에 저장하는 코드 생성

callee로 jump하는 코드 생성

 

함수 진입직전(prolog)

FP를 push하고, old SP를 new FP로 놓고,

local 변수를 스택에 push하는 코드를 생성

 

return문에서(Epilog)

pop하고

리턴값을 적절한 장소에 저장하고

old SP, FP를 restore하고

리턴주소를 pop하여 그리로 jump하는 코드를 생성

 

함수 호출이 끝난 후

리턴 값을 사용하는 코드를 생성

 

dynamic link : old FP의 위치를 현 frame에서 보관(수행 관련)

static link : nested function일 경우, outer function의 frame 위치를 현 frame에서 보관

 

+는 실인자, -는 local변수