NandToTetris : 컴파일러 2: 코드 생성 (밑바닥부터 만드는 컴퓨팅 시스템)

컴파일러

고수준 프로그램을 vm코드로 변경해주는 일종의 번역기입니다.

고수준 언어는 객체와 배열등 다양한 추상적 개념들이 있지만 컴파일러의 vm코드에서는 스택과 가상 세그먼트만 사용 가능합니다.

잭 컴파일러는 jack 코드를 vm 코드로 변환합니다.

 

각각의 파일들은 각각의 vm코드로 변환되며 (filename.jack -> fileName.vm)

서브루틴(생성자, 메서드 등)들은 fileName.subName으로 변환됩니다.

 

앞장에서 다뤘던 요소 Tokenizer를 포함하여 총 5개의 모듈이 만들어져야 합니다.

 

1. JackCompiler

입력된 jack 파일을 vm파일로 변환하는 핵심 모듈 , JackToknizer를 호출해여 입력을 전달하고 vm파일을 반환합니다.

이후 SymbolTable, VMWriter를 이용해 최종 vm파일을 만들고 반환합니다.

 

2. SymbolTable

jack파일에는 여러 종류의 변수들과 scope가 존재하는데 클래스가 컴파일될때 클래스레벨 변수와 서브루틴 레벨 변수를 나누어 테이블을 생성하고 각 변수에 실행 인덱스를 제공합니다.

 

3. VMWriter

vm코드를 생성하고 출력 vm파일에 보냅니다. 

 

4. ComplitaionEngine

Tokenizer로 부터 부터 입력을 받고 VMWriter를 통해 출력을 작성합니다.

code generator

앞서 구문 분석기를 알아보았고 이제는 실행 가능한 vm코드를 만드는 코드 생성기 code generator입니다.

code generator를 구현하기 위해서는 파서 parsor 의 기능이 일부 필요합니다.

Jack프로그램은 여러 클래스로 이루어져있고 각 클래스 파일들은 개별적으로 컴파일됩니다.

그리고 클래스에서는 class-level code와 subroutine-level code 2가지로 나누어서 컴파일됩니다.

그리고 각 subroutine들을 하나씩 컴파일합니다.

 

서브 루틴을 컴파일할때는 아래 그림처럼 서브 루틴 내에 존재하는 변수, 표현식, if, while, 객체, 배열들이 모두 컴파일되어야합니다.

변수 처리

앞서 언급한 것 처럼, 변수 또한 class-level과 subroutine-level 두가지 관점에서 존재하며

각 변수들은 식별자와 타입 (int, char 등), 종류 (locak, static), 범위 (scope)를 가집니다. 

(핵 플랫폼에서는 class scope와 subroutine scope 2개만 존재!)

 

 

Symbol Table

변수, 상수, 서브루틴, 클래스 등 프로그램에서 사용되는 식별자(identifier)에 대한 정보를 관리하는 자료구조이며 해시 테이블 추상화로 구성됩니다. 

클래스 마다 class-level, subroutine-level의 식별자들이 각각 다른 symbol table에 존재합니다.

클래스는 컴파일 될 때 마다 새롭게 symbol 테이블을 가지게됩니다.

subroutine symbol 테이블의 첫번째 로우(this)의 type은 항상 해당 클래스를 가지며 argument 0으로 정의됩니다.

 

만약 x + 17이라는 명령이 있다면 먼저 x가 subroutine수준의 변수인지 확인하고, 이 작업이 실패하면(subroutine 수준이 아니면)

컴파일러는 x가 정적변수나 필드변수인지 확인합니다.

 

컴파일러는 symbol table들을 LinkedList로 연결하여 사용하고있기에 현재 범위와 관련된 테이블에서 값을 찾고 관련 테이블에서 그 값을 찾지 못하면 리스트의 다음 테이블에서 찾는 방식으로 찾아나갑니다. 

만약 어느 테이블에도 없으면 undefined 에러를 발생시킵니다.

Jack 문자열 컴파일

일반적을 객체지향 언어들은 Stringd이라는 클래스 인스턴스로 문자열을 처리합니다.

문자열 상수가 나올 때 마다 컴파일러는 String 생성자를 호출해서 새로운 String 객체를 생성하고 반환하는 코드를 생성합니다.

이 초기화는 문자열 상수마다 String메서드의 appendChar를 연달아서 호출하는 방식으로 이루어집니다.

 

현대의 언어 (Java, Python)은 gc를 제공하여 사용하지 않는 클래스들을 처리하고, 객체의 효율적 활용을 위해 다양한 최적화와 특화된 문자열 클래스를 제공합니다.

잭 OS는 하나의 String 클래스만 지원하며, 최적화는 지원하지 않는다고 합니다.

Jack 표현식 컴파일

잭은 중위표기법을 사용해서 표현식을 작성합니다.  {a * (b + c)}

반면 우리가 컴파일할 목적 언어는 후위표기법 입니다. {a b c + *}

 

vm머신은 스택기반이기에 중위표현식을 직접 처리 할 수 없습니다.

그래서 후위표현식으로 변환 후 스택 연산을 이용해 vm코드로 변경하는 작업이 필요합니다.

위에 그림에서 나와있듯이 parse tree를 통해 표현식들을 변환합니다.

표현식은 컴파일은 compileExpression 루틴에서 처리됩니다.

codewrite 알고리즘

codewrite알고리즘은 전달받은 표현식을 vm명령으로 변경합니다.

들어온 값이 상수라면 push c 상수를 push하는 명령어를 만듭니다.

 

아래 예시와 같이 x + g(2,y -5, -z)같은 표현식이 들어오면

x에 대한 코드를 먼저 생성하고 g에 대한 코드를 모두 생성하고 op를 생성합니다.

전체 Jack 표현식

Jack언어의 표현식 문법입니다.

Jack 명령문 컴파일 (let, do, return)

return 명령문은 compileExpression 루틴을 호출해서, 표현식의 값을 계산하여 스택에 넣는 vm코드를 생성합니다.

이후 return vm명령을 생성합니다.

 

let 명령문 (let varName = expression)은 varName을 기억하는것 부터 시작합니다.

이후 compileExpression을 호출하여 표현식의 값을 스택에 넣고 마지막으로 pop varName vm명령을 생성합니다.

여기서 varName은 실제로 symbol 테이블에서 varName에 매핑됩니다. (local 3, static 1 등)

 

do 명령문 (do className functionName(exp1, exp2, ..., expn))은 서브루틴의 반환값은 무시하고 서브루틴의 기능만을 호출하기 위한 명령문입니다.

compileExpression를 호출하고 pop temp 0 명령으로 최상위 스택 항목을 제거하면 됩니다. 

Jack 명령문 컴파일 (while, if)

while, if문들은 vm언어의 goto, if-goto, label로 변형되어야합니다.

if, while문의 경우에는 항상 expression의 true, false를 통해 실행할 코드가 변경됩니다.

 

if 문은 먼저 expression의 값을 계산하고 그 결과에 대해 부정합니다.

만약 부정한값이 참이면 L1으로 이동하고 거짓이면 L2로 이동합니다.

while문은 label (L1)을 만들고 expression을 계산하는 코드를 생성합니다. 

그리고 계산된 expression을 부정합니다. 값이 참이면 label L2로 가서 빠져나갑니다.

Jack 객체 컴파일

객체 지향 언어들은 객체 object라는 집합적인 추상 개념을 다룰 수 있는 수단을 제공합니다.

객체들은 static, field, local, argument로 참조되는 메모리 블록으로 구현되며,

객체 변수 또는 포인터라고 하는 참조 변수들은 메모리 블록의 시작 주소를 담고있습니다.

잭은 heap을 통해 객체를 구현합니다.

 

p객체의 foo메소드가 있다고 생각해봅시다.

p.foo()와 같은 호출이 호출되면 (피호출) foo안의 코드들은 this위에서 동작해야합니다.

즉 메서드가 실행될 때, 해당 메서드가 호출된 객체의 필드(인스턴스 변수)를 변경할 수 있도록 this를 올바르게 설정해야합니다.

말이 조금 어려운데, 예를들어 Jack 컴파일러가 피호출되는 p.foo();를 VM 코드로 변환할 때,
아래와 같이 this 세그먼트가 p 객체의 필드와 연결되도록 설정하는 과정이 필요합니다.

배열 또한 Array 클래스의 인스턴스로 구현되어 있기에 배열을 사용할때도 객체의 방법과 유사하게 동작합니다.

push argument 0   // p 객체의 주소 (현재 메서드가 실행되는 객체) 
                  // 메서드는 항상 첫 번째 인자로 자신을 호출한 객체의 주소를 받음
pop pointer 0     // this = p; 객체의 주소 저장

Jack 생성자 컴파일

생성자 관점에서의 호출 컴파일과 피호출자 관점에서의 컴파일 두가지가 존재합니다.

생성자 호출 컴파일 (caller)

객체 생성은 크게 2가지 단계로 나뉩니다.

1. var Point p와 같이 클래스 타입 변수가 선언될 때

2. let p = Point.new(2,3)과 같이 클래스 생성자를 호출해서 그 객체가 인스턴스로서 생성 될 때

 

먼저 인스턴트 생성 명령문을 let p = Point.new(2,3)이 실행되면

생성자가 Point인스턴스를 나타내는 크기만큼 메모리를 할당하고 그 값을 초기화해야하고,

p가 이 블록의 시작 주소를 참조하도록 합니다.

 

위 그림에서 2개의 객체가 생성되었는데, 생성자는 각각 두 객체의 메모리를 할당합니다.

이렇게 컴파일이 되면 symbol 테이블이 업데이트되고 저수준 코드가 생성되지만, 그 이후에는 어떠한 동작도 하지않습니다.

객체는 런타임, 즉 컴파일된 코드가 실행될 때 생성되고 변수에 바인딩됩니다.

생성자 호출 컴파일 (callee)

이제 생성자가 실행될 때 생성자의 관점 (피호출자)에서도 알아보겠습니다.

생성자는 argument와 local변수 그리고 명령문을 사용 할 수 있는 서브루틴이며 컴파일러도 생성자를 서브루틴으로 취급합니다.

새 객체를 생성하려면 먼저 객체의 크기만큼 RAM에 공간을 할당해야합니다.

컴파일러는 Memory.alloc(size)라는 os함수를 실행하여 객체가 필요한만큼의 공간크기를 지정하고 그 주소를 반환합니다.

 

Memory.alloc(size)을 호출하기 전 컴파일러는 필요한 메모리 블록의 크기를 계산합니다.

예를 들어 Point객체에 int x, y가 있다면 push constant 2, call Memory.alloc 명령을 생성해서 Memory.alloc(2)함수를 실행합니다.

alloc은 크기가 2인 사용 가능한 메모리 블록을 찾고 그 시작 주소를 stack에 push합니다.

그 후 pop point 0명령을 실행하여 this를 alloc이 반환한 주소로 설정합니다.

 

위 그림의 코드를 보면 이렇게 this가 처리된 후 let x = ax;라는 명령이 실행됩니다.

컴파일러는 x가 어떤 변수인지 세그먼트 확인을 위해 symbol 테이블을 참조합니다. (x는 this 0, ax는 argument 0입니다.)

그 후 compileLet 루틴이 push argument 0, pop this 0명령을 생성합니다.

 

그리고 잭의 모든 생성자는 return this로 끝나야 합니다.

그렇기에 컴파일러는 생성자 컴파일의 마지막에 push pointer 0, return을 붙이게 됩니다.

Jack 메소드 컴파일

각 클래스들은 별도의 컴파일 단위입니다.

일반적으로 객체지향 언어에서 코드를 작성하다보면 클래스에서 다른 클래스의 메소드를 호출하게 되는데

클래스의 메소드는 호출되는 클래스 (callee)에 의해 캡슐화 되어있습니다.

하지만 vm언어에는 객체나 메서드에 대한 개념이 없기에 객체지향이 아닌 절차지향 언어처럼 처리합니다.

 

잭 언어는 두 종류의 메소드 호출을 지원합니다.

• varName.methodName(exp1, ..., expn) : varName이 참조하는 객체에 메소드 적용 (caller)
• methodName(exp1, ..., expn) : 현재 객체에 객체에 메소드 적용 (callee)

 

varName.methodName(exp1, ..., expn) caller시점

먼저 메소드 호출 varName.methodName(exp1, ..., expn) 컴파일되면

기본 주소 push varName 명령을 시작하여 모든 argument와 기본주소(p1)를 stack에 push합니다.

이후 compileExpresion을 n번 호출합니다.

마지막으로 call className.methodName n+1을 실행합니다. (만약 argument가 없다면 n+1이 아닌 1)

 

methodName(exp1, ..., expn) (callee)

methodName(exp1, ..., expn) 처럼 현재 객체에서 실행되는 메소드도 존재합니다.

이미 this 세그먼트가 설정되어 있기 때문에, 이 경우에는 this가 없이, 필요한 인자를 바로 사용할 수 있습니다.

즉 argument만 스택에 push하고 필요햔 명령어를 실행하면 됩니다.

 

마지막으로 void메소드는 고수준언어 시점에서는 값을 반환하지 않지만 잭 컴파일러에서는 반드시 값을 반환해야합니다.

그러므로 컴파일러에서는 void메소드의 마지막에 push constant 0, return 명령을 실행합니다.

이후 caller코드는 pop temp 0를 실행하여 스택에서 불필요한 값을 제거합니다.

Jack 배열 컴파일

고수준언어에서 var Array arr가 선언되면 컴파일러는 이 배열을 local 0로 초기화합니다.

이후 Array 클래스의 서브루틴을 호출해서 배열에 해당하는 공간을 heap에 할당합니다.

새로 할당된 heap주소는 local 0에 저장됩니다.

symbol테이블에는 local, 0, Array, arr 이 4개의 컬럼을 첫 로우에 추가합니다.

 

위 그림의 vm 코드를 보면 push local 0으로 배열의 주소를 초기화하고

배열의 크기인 constant 2도 push 후 add합니다. 이 결과로 대상 주소가 스택에 push됩니다.

다음으로 pop point 1로 주소를 that 세그먼트에 추가합니다.

that에 arr의 주소가 들어갔기에 이제 배열을 조작할 수 있습니다.

 

위 그림의 코드에는 없지만 push 17, pop that 0 명령을 사용해서 배열에 값 17을 추가합니다.

(배열에 다른 인덱스에 값을 넣을때는 offset을 추가해서 사용합니다.

이후 push that 0, pop local 1과 같은 명령을 통해 배열에 값을 참조 할 수 있습니다.

 

하지만 위와같은 방식에 하나의 문제가 있습니다.

바로 let a = b[j]같은 명령에는 동작하지만 let a[i] = b[j]처럼 할당 명령 왼편에도 인덱스가 있는 경우에는 실패합니다.

그래서 위와같은 let arr[expression1] = expression2 에서도 제대로 동작하기 위한 전략이 조금 필요합니다.

 

아래 그림은 let arr[expression1] = expression2와 같은 코드가 동작하기 위한 vm코드입니다.

 

let arr[expression1] = expression2 을 위한 전략

먼저 state1 까지 코드가 실행되면 a[i], b[j]의 RAM주소가 stack에 들어갑니다.

이후 stack의 b[j]의 기본주소를 pop하여 pointer 1에 넣습니다.

that 0가 b[j]와 정렬되었기에 b[j]에서 찾은 값을 temp 0에 넣습니다.

 

pop pointer 1을 실행해서 a[i]주소도 정렬하고 stack을 비웁니다.

이러한 방법으로 a[i] = b[j]를 가능하게 만들 수 있습니다.

 

---

어느 순간부터 바쁘다는 핑계로 과제를 안하고있는데, 이제 마지막장 운영체제만 남았으니 일단 마저 내용만 다 정리한다음 나중에 다시 보면서 과제를 진행해야겠다..ㅠㅠ