갱스터의 블로그

Memory Organization (Stack) Run-Time Stack run-time stack이란 call stack이라고도 불리며, 한 함수를 call 할 때마다 생성되는 프레임이나 activation record이 구성하는 스택을 말한다. Activation record 함수를 수행하기 위한 execution environment으로 스택의 한 칸을 의미한다. Activation record에는 로컬 변수와 인자, 리턴값, 기타 임시 저장소(3-addr code에서 사용)를 의미하고, 재귀문일 때에도 각 call마다 하나씩 스택에 Activation record를 넣는다. run-time stack의 연산은 아래와 같다. - f 가 호출되면 f의 frame을 stack에 push (호출) -..

2 Classes of Storage in Process 우리가 사용할 수 있는 저장소는 두 가지가 있다. Registers 빠른 접근 일반 프로그래머에게는 보이지 않음 간접 접근이 불가능하다. 즉, 주소를 얻을 수 없다. Memory 상대적으로 접근이 느리지만, 간접접근 즉 주소를 얻을 수 있다. 위와 같은 특성으로 인해 변수 저장을 register를 이용할 것인지, memory를 이용할 것인지 결정하는데, 이는 HIR을 LIR로 변환하는 단계에서 주로 결정된다. Storage Class Selection 저장소에 저장하는 방법은 두 가지 방법이 존재한다. All memory approach 이 방법은 일단 모든 변수를 memory에 저장한 후 해당 변수 중 가능한 것을 register에 저장하도록 조..

Statement Expressions 우리는 앞서 t = [[a + b]]와 같이 임시 변수에 결과값을 넣는 경우 expression, v = a+b와 같이 명령만 실행하는 경우 statement라고 명명했다. 이때 statement는 결과값이 없는데, statement가 결과값을 갖도록 확장할 수 있다. 결과값을 가질 수 있는 경우는 아래와 같다. - Block statements - If-then-else - Assignment statements 위와 같이 statement가 결과값을 갖게 하면 융통성이 생기게 된다. 3-주소 Translation 규칙: Statement Expression 위 예제에서 e값을 받아 t1에 넣고, e가 거짓인 경우 분기한 후 s를 실행한다. 이때 statement..

3-주소 Translation 규칙: Statement Seq. 여러 문장들이 단순하게 연속해서 존재할 때, 각각에 대해 번역한 후 연결해주면 된다. 이때 위 식에서는 결과값을 t에 대입하지 않는데, statement는 결과값이 없으므로 결과값을 받을 t가 필요없다. 이러한 statement의 경우 단순히 연결만 하면 된다. 즉, t = [[e]]와 같이 결과값이 있는 경우를 expression, 결과값이 없고 단순히 연결하는 경우는 statement라고 한다. 3-주소 Translation 규칙: Assignment 위 경우는 단순히 expre의 결과를 할당하는 경우이다. OP처럼 v(변수 이름)와 '='은 HIR과 LIR이 모두 사용하기 때문에 [[ ]]에서 그대로 빠져나갈 수 있다. 다만, e는 H..

HIR to LIR HIR는 상위 언어, 혹은 AST 등으로 생각할 수 있는데, 이러한 HIR을 LIR 즉, 3-addr code와 같은 형태로 바꿀 때 nested 구조(while, if, etc)로 인해 필연적으로 한 줄의 HIR코드는 여러 줄의 LIR 코드로 바뀐다. 여러 줄로 바뀌는 과정에서 임시 변수를 정의하고 임시 변수를 가져다 쓰는 형태로 바뀐다. 이때, 여러 줄로 바뀌는 규칙이 존재한다. Notation [[ e ]] HIR e에 대한 LIR expression. 즉, e는 하이레벨 코드가 하나 이상 섞인 HIR이며, [[]]에 들어가게 되면 LIR expr로 나오게 된다. 주로 sequence of LIR instruction이다. t = [[ e ]] e가 표현식일 때, 결과 값을 t에..

각각의 예를 분류하면 아래와 같다. - 3-addr code: GCC GIMPLE, LLVM - Stack machine code: JVM byte code, MSIL - Tree code: GCC RTL 가상 기계 코드 (Bytecode, MSIL) 컴파일러는 전반부와 후반부로 나뉘는데, 전반부가 끝나면 IR이 등장하고, IR은 후반부를 거쳐서 target machine code로 변환된다. 전반부는 주로 High-level 언어만 관련이 있고, 후반부는 주로 머신코드와 관계가 되어있으므로 IR을 잘 정의 해야 한다. 전반부와 후반부로 나눠놓고, 후반부를 interpreter로 만드는 경우가 있다. 후반부를 interpreter로 만들면 후반부 자체가 가짜 기계가 되고, 중간코드는 interpreter..

각각의 예를 분류하면 아래와 같다. - 3-addr code: GCC GIMPLE, LLVM - Stack machine code: JVM byte code, MSIL - Tree code: GCC RTL 예1) GCC의 GIMPLE GCC는 c 언어의 컴파일러로 최소 3개의 중간 코드가 존재한다. 중간 코드로는 GENERIC, GIMPLE, RTL이 있다. 이러한 GCC 컴파일러는 c언어 뿐만 아니라, c++, Objective C, Ada까지 입력으로 받을 수 있으며, target 코드의 종류도 여러 가지이다. GCC는 사실 컴파일러라기 보다 Compiler Generation Framework이라고 부르는 것이 더 정확하며, GCC에서 c 컴파일러를 찾기 위해서는 폴더를 타고 들어가야 한다. GEN..

Intermediate Representation(IR) IR은 위 사진에서의 단계 중 중간 코드를 의미한다. 전체적인 컴파일 과정은 High-level 언어에서 Low-level 언어로 만들어주는 과정인데, 이 과정에서 High-level 언어보다는 low하고, Low-level 언어보다 high한 언어로 만들어주는 단계를 거치게 된다. 이러한 IR은 언어와 기계에 독립적이며 컴파일러 내부적으로 사용하는 경우가 가장 많다. IR은 instruction list의 형태와 같은데, 기계어 코드와 같은 list 형태가 가장 많다. 또한 tree 형태로도 존재한다. 이러한 instruction(node)의 종류가 적을 수록 최적화나 번역에 좋다. Java, C, C++과 같은 High-level 언어를 받아서..

Parse Tree 파스트리는 유도 과정을 트리로 나타낸 것이다. leaf node는 terminal, 중간 노드는 non-terminal을 의미하고, 좌측유도인지, 우측유도인지는 표현이 되지 않는다. 위의 파스트리는 유도를 나타내기 위한 불필요한 부분이 존재한다. 트리 자체로 우선 순위를 나타낼 수 있으므로 괄호 또한 불필요하다. AST(Abstract Syntax Tree) 이때, 위의 파스트리에서 불필요한 부분을 모두 삭제한 것을 AST라고 한다. 다양한 언어로 위와 같은 AST 형태를 나타낼 수 있다. 위는 자바 코드로 작성한 AST 자료구조이다. Add와 Num 모두 Expr 클래스를 상속하고 있으므로 인자를 받을 때 Num인지, Add인지 구분할 필요가 없다. 그러나 각 클래스에 따라 자식으로..

Semantic Analysis 우리는 지금까지 어휘 분석과 구문 분석의 방법에 대해 학습했다. 이제 그 다음 단계인 의미 분석에 대해 학습해야 하는데, 구문 분석한 결과인 parsing tree를 통해 바로 의미를 분석하는 것일까? 사실 파싱 트리를 통해 바로 의미 분석을 해도 되고, 여러 가지 처리 후 의미 분석 단계로 넘어갈 수 있다. 구문 분석에서 의미 분석 단계로 넘어갈 때 필요한 두 가지 도구를 소개하겠다. Syntax-Directed Definition/Translation(SDD/SDT) Abstract Syntax Tree(AST) 이번 포스트에서는 SDD만 설명하고 마치도록 하고, 이어지는 포스트에서 AST에 대해 설명하겠다. Syntax-Directed Definition(SDD) S..