Written by JS970
on March 30, 2023

프로그래밍언어론 2023-03-30 수업정리

Flow

3.28 수업정리에서 이어짐

Grammar : (N, T, P, S)
- N : non-terminal set
- T : terminal set
- P : production rules
- S : start symbols
- 다음 수식에서 N과 (N, T)의 합집합에 대한 kleene closure가 times되었다. -> CFG$$P \subseteq N \times (N \cup T)^* $$
문법을 표현하는 방법으로는 CFG로 표기하는 방법과 BNF로 표기하는 방법이 있다.
아래에서 CFG와 BNF로 표기된 문법은 동치이다.
- CFG$$P = {A->a,\ A->aAa},\ N = {A},\ T = {a},\ S = A$$
- BNF
```
<A> ::= a <A> a
	| a
	;
```
위의 예시에서 확인할 수 있둣이, BNF는 ::=(assignment), <변수>, '상수' 와 같은 meta-symbol을 사용한다.
문법에 따라 derivation하는 것을 tree형태로 나타낸 것이 parse tree이다.
parse tree는 아래와 같이 분류할 수 있다.
- AST : Abstract Statement Tree, 추상구문트리
- CST : Concrete Statement Tree

LISP이 Scheme, Common LISP으로 발전했다. Common LISP은 CLOS로 발전했고, Scheme과 CLOS의 variant라고 할 수 있는 Clojure가 탄생했다.

LISP과 마찬가지로 계산보다는 기호처리가 중심이다 -> 인공지능 분야에서 활약
전통적인 함수형 언어이며, 재귀적 함수호출이 중심이 되는 언어이다.
- function call 이 recursive하게 일어난다.
LISP과는 다른 특징으로는 아래와 같은 특징이 있다.
- 배치 영역 규칙, lexical scoping(static scpoing과 유사하다.)
- 꼬리 호출 최적화(tail-call optimization)
- 일등급 컨틴뉴에이션(first-class continuation) - 꼬리함수?
장점 : 간단한 구문
단점 : 너무 간단한 구문

S-Expression : 리스트와 아톰으로 구성된다.
- 아톰 : symbols, literals
- 리스트 : Scheme의 유일한 자료 구조이다. 아톰을 원소로 가진다.
S-Expression : (f a1 a2)의 의미는 a1, a2의 값을 구한 후 여기에 함수 f를 적용하겠다는 의미이다.
- 이를 Eval-Apply Model이라고 한다.
특수 구문
- (quote ...) : ...을 있는 그대로 취급하라
- (cond ...) : 조건에 따라 값을 계산하라
- (let ... expr) : 바인딩이 있는 상태에서 expr을 계산하라
- (define name expr) : name을 expr로 정의하라
- (lambda (x y ...) expr) : x y ... 을 인수로 받아서 expr을 반환하는 함수
- (if c x y) : c가 참이면 x, 거짓이면 y를 실행한다.

(define factorial
	(lambda (x)
	  (if (= x 0) (+ x 1) (* x (factorial (- x 1))))))
(write (factorial (read)))

실행
구현 설명
- x가 0값을 가질 때는 x+1 즉, 1을 반환한다.
- 이외의 경우에는 factorial(x-1)에 x를 곱한 값을 반환한다.
- write을 통해 입력을 받는다.
- 입력 받은 값(read)를 factorial함수의 연산을 거쳐 출력한다.

Top