Crafting Interpreters - 13. Inheritance 를 읽고

http://craftinginterpreters.com/inheritance.html

- Superclass and Subclass
기존의 class에 상속을 위한 super class 관계 더하기
method를 찾을 때 현재 class에 없으면 super class에서 찾는다.

- super keyword
superclass에 있는 함수를 사용하려면? super.method()로 호출한다. 이 경우 어떤 superclass의 함수를 사용해야 할까? => super.method()를 실제로 부르는 함수의 superclass를 호출해야 한다.
이전에 어떤 environment에서의 값을 사용해야 하는지를 알기 위해 사용했던 방법이 무었이었지? superclass를 찾는 경우에도 마찬가지로 Resolver를 통해 필요한 위치를 기억해 놓도록 한 후, 나중에 함수가 실행 될 때 environment에 이 super를 넣어준다.

Crafting Interpreters - 12. Classes 를 읽고

 http://craftinginterpreters.com/classes.html

기존에 되어 있는 것에서 class를 추가만 하면 된다.
가장 먼저 class 선언 부분을 LoxClass를 통해 추가하고 instance를 생성하는 부분은 LoxInstance를 통해 생성한다.

- Instance의 property 찾기(get)
someObject.someProperty의 형태이므로 someObject를 찾고 여기의 someProperty를 찾는다.

- Instance의 property에 값 설정(set)
someObject.someProperty = value 의 형태이므로 위 get에서 한대로 someObject의 someProperty를 찾고 여기에 value를 설정한다.

- Instance에서 method 찾기
LoxClass에 method들을 저장해 놓고, LoxInstance에서 someObject.some 으로 찾을 때 get 함수에서 먼저 property가 있는지 확인해보고 없으면 method가 있는지 확인해 본다.
property는 LoxInstance에 저장되어 있고 method는 LoxClass에 저장되어 있다.

- This
Resolver에서 this를 찾을 위치를 저장해 놓는다.
LoxInstance에서 method를 찾아서 실행할 때 environment에 this도 있어야 하므로 새로운 LoxFunction을 만들면서 여기에 this를 포함하고 있는 environment를 넘겨준다.

- Constructor
init 함수를 constructor로 사용하자. Class에 선언된 함수중 init 함수가 있으면 이를 constructor로 사용한다. init 함수의 경우에는 return이 this가 되도록 한다.

Crafting Interpreters - 11. Resolving and Binding 을 읽고

http://craftinginterpreters.com/resolving-and-binding.html

지금까지의 내용을 가지고 다음의 코드가 어떤 결과를 표시할 지 생각해보자.

var a = "global";
{
  fun showA() {
    print a;
  }

  showA();
  var a = "block";
  showA();
}

결과는 다음과 같다.

global
block

뭐가 문제일까?

앞장에서 함수에 Environment를 적용할 때 함수가 실행될 때마다 Environment를 새로 생성했다. 그리고, 함수안에서 사용하는 변수의 값을 찾을 때 현재 Environment로부터 부모 Environment로 점차로 찾아가는 형태로 구현을 했다.

여기의 어떤 점이 문제였을까?

위의 코드에서 showA()를 선언했을 때의 Environment를 살펴보자.

global environment(a="global") <- block environment() <- showA environment()

따라서, 처음 showA(); 를 호출할 때는 global environment의 a가 찾아진다. 그런데 두번째 a인 var a = "block"; 가 실행되면서 block environment에 a="block" 가 추가된다. 이 다음에 showA() 를 호출하면 앞에서처럼 점진적으로 Environment를 찾아갈 텐데 block environment에 a가 추가되었기 때문에 여기의 a를 찾게 되고 이 a 의 값이 출력되게 된다.

위의 문제를 해결하려면?
아래와 같은 코드가 있을 때 1과 2에서의 scope가 실제로는 같지 않아야 함을 의미한다.

{
  var a;
  // 1.
  var b;
  // 2.
}

그렇다면, 이 문제를 어떻게 해결할 수 있을까?

첫번째로는 변수 선언이나 함수 선언의 경우마다 새로운 scope를 생성하는 것이다.(이전에는 기존의 Environment에 새로운 선언을 바로 추가했다.)

두번째로는 Semantic Analysis를 사용하는 것이다.

이 방법은 block과 function의 경우 새로운 scope를 생성하고, variable이나 assignment가 있는 경우 어떤 scope에 있는 값이 사용되어야 하는지를 미리 설정해 놓고 나중에 이 값을 사용한다.

우리는 두번째 방법으로 구현을 변경해 볼 것이다.
-> parser를 통해 나온 결과를 바로 interpreter에 보내지 않고 이 사이에 Resolver를 통해 Semantic Analysis를 한 후 interpreter에서 변수를 사용할 때 이 정보를 사용한다.

Crafting Interpreters - 10. Functions 를 읽고

http://craftinginterpreters.com/functions.html

함수에서의 return을 위해 exception을 사용한다.
함수 시작시 Environment를 새로 할당하여 시작한다.
함수가 선언되는 시점의 Environment를 저장하고 있다가 함수 시작시 새로 할당되는 Environment의 parent로 설정해준다.

Crafting Interpreters - 9. Control Flow 를 읽고

http://craftinginterpreters.com/control-flow.html

Turing Machines

if, logical operator(and와 or), while, for 를 추가

for 문 같은 경우 while 문으로 쉽게 변경이 가능하다. 따라서, 내부적으로는 for 를 while 로 변환해서 사용할 수 있다. 이러한 것을 syntactic sugar 라고 한다.

Crafting Interpreters - 8. Statements and State 를 읽고

http://craftinginterpreters.com/statements-and-state.html

Statement는 값을 내는 것이 아닌 다른 무언가(side effect - output을 내거나 state를 변경하거나 하는 것)를 하는 것이다.

변수 선언을 하면 어딘가에 저장이 되어 있어야 나중에 이 변수의 값을 사용할 수 있습니다. 이를 위해 Environment라고 하는 것이 필요하게 됩니다.
Environment는 HashMap으로 (변수 이름, 값)을 내부에 저장하고 있습니다. 현재로서는 값을 저장할때는 define, 값을 꺼내올때는 get, 값을 재할당할때는 assign정도의 함수만 가지고 있으면 되겠습니다.

변수가 선언되고 사용되는 위치에 따라 scope가 지정됩니다. 이것은 block({})으로 지정합니다.  scope에는 lexical scope과 dynamic scope이 있는데 우리는 lexical scope를 사용합니다.
가장 상위를 global scope라고 하고 이후의 코드에서 별도의 scope를 가지고 싶으면 block을 사용합니다. 이러한 경우 block 내부의 변수가 외부의 변수를 가릴 수도 있고 값을 변경할 수도 있습니다. 이에 대한 처리를 위해 Environment에 parent Environment를 추가합니다. 어떤 값을 찾을 때 자기 자신이 가지고 있지 않으면 바로 에러를 발생시키지 않고 parent Environment에게 위임하는 거지요. parent에게서 변수가 찾아지면 그 값을 사용하면 되고 여전히 찾아지지 않으면 그의 parent에게 위임합니다. 이렇게 global environment까지 찾아 보게 합니다.

Crafting Interpreters - 7. Evaluating Expressions 를 읽고

http://craftinginterpreters.com/evaluating-expressions.html

앞장에서 파서를 만들어 봤다. 이번 장에서는 expression의 값을 구해보자.

Lox는 dynamically typed language이므로 런타임에 타입을 체크한다. 그러면 타입은 어떻게 알 수 있을까? JVM에서 Lox를 구현하고 있으므로 JVM의 도움으로 쉽게 체크할 수 있다.(자바는 instanceOf로 코틀린은 is로 타입을 확인한다.)

또한 Lox에서 사용하는 primitive type들은 자바에서의 타입과 쉽게 매치할 수 있다.

Lox type	Java representation
nil	null
Boolean	Boolean
number	Double
string	String

나중에 함수, 클래스, 인스턴스 등을 추가하면 좀 더 복잡해질 것이다.

런타임에 에러가 발생하면 어떻게 할까?(자바라면 ClassCastException을 던지고 stack trace를 보게 될 것이다.) 에러가 발생하면 에러의 위치(line number)와 에러 메시지를 화면에 보여주자.

Crafting Interpreters - 6. Parsing Expressions 를 읽고

http://craftinginterpreters.com/parsing-expressions.html

앞장에서 문법을 어떻게 표현할 것인지를 살펴보고 간단한 문법을 Context-free grammar로 표시해 봤습니다.

이러한 문법 표현에서 모호함(ambiguity)이 있을 수 있습니다. 예를 들면, 1 + 2 * 3 의 경우 결과가 어떻게 나와야 할까요? 앞에서 부터 계산을 하면 결과는 9가 될 것이고, 곱하기를 먼저 한다면(우리가 수학에서 배웠듯이) 결과가 7이 될 겁니다.

이러한 모호함을 우선 순위(precedence)와 결합 법칙(associativity)을 정해서 해결할 수 있습니다.(또는 먼저 계산되어야 하는 값에 괄호를 사용할 수도 있을 겁니다.)

토큰을 분석(parsing)하는 방법에는 여러가지 방법이 있는데 여기서는 Recursive descent parsing을 살펴볼 겁니다. 파서를 만드는 가장 간단한 방법이지만 그렇다고 만만하게 볼 파서는 아닙니다. 실제로 GCC나 V8(JavaScript)이나 Roslyn(C#)등에서 사용되고 있거든요.

토큰을 분석하다 에러를 만나면 어떻게 하는 것이 좋을까요? 처음으로 만나는 에러에서 멈추고 그 부분을 표시해주는게 좋을까요? 이게 가장 간단한 방법이기도 하지요. 하지만, 사용자한테는 매번 에러가 나타날 때마다 바로바로 표시해 주는 것보다는 전체에서 발생할 수 있는 에러를 한번에 표시해주는게 좋을겁니다. 이걸 error recovery라고 부릅니다.

에러가 발생해도 계속 진행하면서 이후의 에러도 확인하려면 어떻게 해야 할까요? 에러가 발생한 지점부터 특정 지점까지는 무시했다가 그 다음부터 토큰 분석을 다시 시작해야 할겁니다. 안그러면 엄청나게 쓸데없는 에러가 표시되겠지요. 에러가 발생하면 파서는 바로 panic mode로 들어가고 다시 정상적으로 파싱을 시작할 수 있는 지점을 만나면 panic mode를 벗어나게 됩니다. 이러한 과정을 synchronizaion이라고 합니다.

Crafting Interpreters - 5. Representing Code 를 읽고

http://craftinginterpreters.com/representing-code.html

앞장에서 살펴본 내용은 단순한 토큰의 나열이었죠.

예를 들어 1 + 2 * 3 - 4 가 있다고 하면 1, +, 2, *, 3, -, 4 이렇게 개별 토큰의 나열을 만드는 것을 해봤습니다. 근데 이것만으로는 아무 의미가 없습니다. 계산을 한다고 할 때 앞에서 부터 계산을 하는데 중간에 곱하기가 있으면 곱하기를 먼저 한다던지 하는 어떤 법칙이 필요하죠. 이걸 표현할 필요가 있습니다. => 문법

문법을 Context-Free Grammar로 표현할 수 있고 이 문법을 통해 어떤 형태가 옳은지를 표현할 수 있습니다. 이에 맞지 않으면 틀린 표현이 되는 것이겠지요.

아래와 같이 문법에 맞는 rule들을 표시하는데 각각의 rule은 head와 body로 표시합니다.

A -> a
B -> b
(A는 a로 변환할 수 있고, B는 b로 변환할 수 있다는 의미입니다.)

컴퓨터 과학에서는 이것을 아래와 같이 Backus-Naur form의 형태로 많이 사용합니다.

expression → literal
           | unary
           | binary
           | grouping ;

literal    → NUMBER | STRING | "true" | "false" | "nil" ;
grouping   → "(" expression ")" ;
unary      → ( "-" | "!" ) expression ;
binary     → expression operator expression ;
operator   → "==" | "!=" | "<" | "<=" | ">" | ">=" 

| "+" | "-" | "*" | "/" ;

오른쪽에 있는 값들 중 "true"나 "==" 등은 더이상 쪼개 질 수 없기 때문에 terminal이라 부르고, expression이나 operator등은 다른 rule로 더 쪼개질 수 있기 때문에 nonterminal이라 부릅니다.

이 문법에 대한 data structure는 tree로 표현할 수 있습니다. 이것을 syntax tree라고 합니다.
(이처럼 보통 트리를 많이 사용합니다. 하지만, 다르게 표현할 수도 있는데요. 예를 들면, 바이트코드로 표현하는 방법이 있습니다.)

트리를 순회하면서 작업을 하려면 어떻게 하는게 좋을까요? 이와 관련하여 Expression problem이라는 것이 있습니다.
(이와 관련한 내용은 다음의 링크를 참고: http://www.haruair.com/blog/3338)

syntax tree를 보기 좋게 표현할 수 있으면 좋겠죠?
트리를 텍스트로 바꾸어 보기 좋게 표현해 주는 것을 pretty printer라고 부릅니다.
(이와 관련한 내용은 다음의 링크를 참고: https://jooyunghan.gitbooks.io/a-prettier-printer-kr/content/chapter1.html#sec1)

Crafting Interpreters - 4. Scanning 을 읽고

http://craftinginterpreters.com/scanning.html

인터프리터의 간단한 동작 단계는 scanning -> parsing -> evaluating code 로 말 할 수 있습니다. 4장에서는 이중 scanning에 대해 설명합니다.

다음과 같은 코드가 있다고 하면,

var language = "lox";

이 코드는 다음의 5개의 토큰으로 분할됩니다.

var, language, =, "lox", ;

이러한 개별 토큰들의 타입을 TokenType으로 분류합니다. 분류된 토큰들은 이후에 parsing 단계에서 사용되어야 하는데 그 때 필요한 정보들을 저장하고 있어야 하겠죠.

그래서,  Token class를 만듭니다. 이 class는 다음의 정보들을 저장하고 있습니다.

type: 토큰의 타입(TokenType)
lexeme: 토큰 string
literal: 토큰의 값
line: 토큰이 있는 소스의 라인값으로 에러 표시에 사용합니다.

lexeme과 literal의 차이에 대한 예

"lox"의 경우 lexeme은 "lox"이고, literal은 "를 제외한 lox 이다.
1234 의 경우 lexeme은 1234이고, literal은 double값인 1234.0이다.

토큰을 나눌 때 주의사항

orchid의 경우 or과 chid로 분리할 것인가 orchid로 분리할 것인가: 긴 토큰으로 분리하는 형태로 한다. - maximal munch