1. Syntax & Semantics
🌱 프로그래밍 언어는 syntax와 semantics로 나뉘어져 있다.
Syntax : 프로그램의 문법적인 구조
Semantics : 문법적으로 옳은 프로그램의 '의미'
첫 번째 예시를 보면, 두 statement는 syntatically 다르다. 왼쪽은 x, y를 오른쪽은 a, b를 사용했기 때문이다.
그러나 두 statement는 semantically 의미적으로 동일하다.
두 번째 예시를 보면, 두 statement는 syntatically 다르다. 오른쪽에는 없는 statement가 왼쪽에만 있기 때문이다.
왼쪽과 오른쪽은 동일한 일을 한다. y:=x는 어떠한 일도 하지 않기 때문에, 두 statement는 동일한 결과를 낳기 때문에 semantically 동일하다.
2. 프로그래밍 언어 디자인
새로운 프로그래밍언어 AE(Arithmetic Expression)를 디자인해 보자!
프로그래밍 언어를 디자인하기 위해 다음과 같은 단계를 거쳐야 한다.
step1. Syntax를 정의해야 한다.
1) Concrete Syntax
2) Abstract Syntaxstep2. Semantic를 정의해야 한다.
1) English Specification으로 정의 (자연어로 정의)
2) Reference Implementation으로 정의
3) Formal Language로 정의
🌱 새로운 프로그래밍 언어 AE는 두 정수 간의 덧셈과 뺄셈만을 수행하는 언어다.
아래는 우리가 만들 AE 언어의 Valid한 Syntax들이다!
3. AE의 Concrete Syntax 정의하기
1) Numbers의 syntax
number은 nat이거나 -nat이어야 한다.
nat은 digit이거나 digit nat이어야 한다.
digit은 0이거나 1이거나 .. 9여야 한다.
🌱 Number는 정수를 나타내는 string의 집합이다.
digit = { “0”, “1”, “2”, “3”, “4”, “5”, “6”, “7”, “8”, “9” }
➡ digit = single-digit number을 나타내는 string의 집합
nat = digit ⋃ { “00”, “01”, “02”, ..., “99”, “000”, “001”, “002”, ...}
➡ nat = digit이거나, nat이 뒤에 오는 digit의 집합
➡ nat = 0 혹은 양의 정수를 나타내는 string의 집합
number = nat ⋃ { “-0”, “-1”, “-2”, ..., “-9”, “-10”, “-11”, “-12”, ..., “-99”,...}
➡ number = nat이거나, -이 붙은 nat
➡ 정수를 나타내는 string의 집합 (0, 양의 정수, 음의 정수)
2) Expression의 Syntax
🌱 expression은 정수 간의 expression을 나타내는 string의 집합이다.
expr = number U { "0+0", ..., "13 + 214", ..., "(2-6)", ...}
+ : addition
- : subtraction
() : precedence
4. AE의 Abstract Syntax 정의하기
Abstract Syntax는 Program이 아니라 Compiler 에 의해 사용된다.
언어가 어떻게 보이는지에 대해 다루는 것이지만,
concrete syntax는 프로그래머에 의해 이용된다면 (프로그래머가 참고하여 코딩)
abstract syntax는 compiler에 의해 이용된다.
📌 Concrete Syntax
3 + 4 (infix)
3 4 + (postfix)
+ 3 4 (prefix)
이 3개의 syntax는 모두 동일한 일을 한다. 3과 4를 더하는 것!
즉 같은 일을 하더라도 다르게 표현될 수 있다. 다른 점은 +의 위치일 뿐이다. (전혀 중요하지 않음)
이 3가지 예시처럼 cocnrete syntax는 필요하지 않은 정보(디테일)도 포함한다.
📌 Abstract Syntax
(add (num 3)(num4))
conrcrete syntax의 불필요한 syntax는 모두 제거한다. +의 위치는 필요없는 정보이므로 제거한다.
이 syntax는 +의 위치를 신경쓰지 않으므로 더욱 더 간단하다.
4가지 언어가 모두 동일한 함수를 만들고 있지만, 각기 다른 모습을 가지고 있다.
python은 def, javascript는 function, racket은 define으로 함수 정의를 시작하고
python은 add(x,y)이지만 racket은 (add x,y)구조이다. 이처럼 디테일이 모두 다른데,
이는 모두 concrete syntax가 불필요한 디테일을 포함하고 있다는 것을 보여준다.
🔔 Concrete Syntax -> Abstract Syntax
따라서 이 concrete syntax를 abstract syntax로 바꿔보자!
어떻게? -> 불필요한 정보(def, function, let, 등) 를 제거함으로써!
Abstract Syntax는 tree로 나타낼 수 있다.
fundef 노드는 function name(add)와 파라미터(var), 그리고 body(Add)를 가진다.
body에는 두 개의 파라미터(x, y)가 있다.
Var을 없애서 더 간단하게 나타낸다면 위와 같다.
Abstract Syntax와 Concrete Syntax를 비교해보면, Abstract Syntax에는 괄호, def 키워드, semicolon 등 불필요한 디테일이 없다.
4가지 언어의 함수 모두 이와 같이 나타낼 수 있다.
5. 실습 : AE 언어를 위한 Abstract Syntax 만들어 보기
우리가 정의한 언어 Arithmetic Expression을 위한 Abstract Syntax를 만들어 보자 !
Abstract Syntax는 tree 구조로 표현될 수 있다.
Abstract Syntax는 프로그램을 나타내는 모든 트리의 집합이다.
AE Expression의 Abstract Syntax는 집합 E로 나타낼 수 있다.즉, E는 Set of Abstract Syntax이다.
1) Number에 대한 Abstract Syntax
Num Node에는 n이 있다. Num은 AE의 정수를 나타내는 노드이다. n은 정수의 집합인 Z에 속한다.
2) Addition에 대한 Abstract Syntax
ADD는 AE의 덧셈을 나타내는 노드이다.
두 개의 Child Node e1, e2를 가진다. 두 노드 모두 E( Set of Abstract Syntax) 의 element이다.
3) Subtraction에 대한 Abstract Syntax
SUB는 AE의 뺄셈을 나타내는 노드이다.
두 개의 Child Node e1, e2를 가진다. 두 노드 모두 E( Set of Abstract Syntax) 의 element이다.
4) 정의한 Abstract Syntax를 이용해서, 프로그램을 AST로 표현하기
프로그램 코드 "5 - 1 + 3" 는 이와 같이 표현될 수 있다.
우리는 Concrete Syntax에 포함되어 있던 괄호를 불필요한 디테일이기 때문에 Abstract Syntax에는 포함하지 않았다.
우리는 괄호 없이 Abstract Syntax로 우선순위를 표현할 수 있다. (5-1)+3은 위와 같이, 5-(1+3)은 아래와 같이 우선순위를 표현할 수 있다.
5) Abstract Syntax를 Ocaml로 나타내기
type expr =
| Num of int
| Add of expr * expr
| Sub of expr * expr Abstract Syntax를 정의하기 위해, Variant type을 사용한다. Num, Add, Sub은 Ocaml 문법의 Constructor로 만든 것이다. Num 노드는 int가 될 수 있고, Add 노드와 Sub 노드는 각각 두 개의 expr을 받게 된다.
Abstract Syntax는 Tree로 나타낼 수 있다고 했는데, 이 외에 다음과 같이 표현할 수도 있다.
Add(Sub(Num 5, Num 1), Num 3)
Sub(Add(Num 1, Num 3), Sub(Num 2, Num 9))
이 두 표현은 트리와 똑같은 Abstract Syntax이다.
6) Abstract Syntax의 단순한 표현
Abstract Syntax 트리를 계속 그리는 것은 귀찮으므로 아래와 같이 Simple Description을 이용할 수 있다.
즉, 각각의 Abstract Syntax 트리는 위에 있는 Abstract Syntax 표현인 n, e1 + e2, e1 - e2와 동일하다.
❗❗ 주의사항 ❗❗
Abstract Syntax 의 + sign과 - sign은 arithmetic operator가 아니다.
+와-는 Integer domain에서의 연산자다.
Abstract Syntax에서+와-는 E domain에서의 연산자다. 즉, 그저 ADD와 SUB 노드일 뿐이다.
따라서 우리는 Integer Domain의 연산자와 구분하기 위해 Integer Domain의 연산자는-z,+z라고 표현할 것이다.
7) Abstract Syntax 를 BNF Form으로 타내기
Abstract Syntax를 BNF form으로 나타낼 수 있다.
8) AE 언어에 대한 Parser : Convert AE program to AST
parser는 "1+", "2*4", "0++3"과 같은 프로그램을 reject한다.
syntax에 맞지 않기 때문이다.
따라서 프로그램은 syntax에 맞아야 하고, parser는 맞다면 위와 같이 AST를 generate한다.
