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)