[CS 기본 개념] 전공면접 준비자료 #1 Programming Language

😄 제가 대학원 준비과정에서 정리했던 컴퓨터공학과 기본 과목을 공유합니다!
📬 댓글로 이메일 남겨주시면 한글 파일 보내드리겠습니다!

📚 Programming Language

1. Chomsky hierarchy

생성 규칙의 제약에 따라 나눈 계층

1. Type - 0
무제약 문법 (UG, Unrestricted Grammar)
생성 규칙에 제약 없음
튜링 머신으로 인식

2. Type - 1
문맥 의존 문법 (CSG, Context-Sensitive Grammar)
선형 구속 오토마타에 의해 인식
Production rule : 하나의 non-T만 T를 생성

3. Type - 2
문맥 자유 문법(CFG, Context-Free Grammar)
푸시다운 오토마타에 의해 인식 (PDA)
Production rule : 왼편에 하나의 non-T만 사용해서 생성

4. Type - 3
정규 문법(Regular Grammar)
(좌선형 문법) 형태를 가짐
유한 상태 오토마타에 의해 인식 (FA)

---

2. Imperative / Declarative

1. Imperative (명령형)
how의 관점으로 상태와 제어흐름이 존재

2. Declarative (선언형)
what의 관점으로 상태와 제어흐름이 없음
약속된 정의만 사용해서 작성

---

3. Compilation / Interpretation

1) Compilation

PL program -> machine code program
다양한 검증과정 적용 가능
최적화 기법 적용 가능

• Static-typed language
  컴파일 시점에 모든 변수 타입 결정
  (OCaml, C++ = type inference 제공)

2) Interpretation

PL program -> 실행 결과
구문구조가 단순하고 실행이 simple

• Dynamic typed language
  런타임 시점에 모든 변수 타입 결정
  (Python, Script 언어)

---

4. Program 실행 과정

1. Front-end
program -> Lexer / Parser -> AST

2. Back-end
Compiler || Interpreter

---

5. Parser / Lexer

1. Parser (syntax analyzer)
regular expression 활용

2. Lexer (lexical analyzer)
CFG || CSG 활용

---

6. Syntactic sugar

Concrete syntax만 확장해 언어 표현력 확장

---

7. Occurrence of identifier

1. Binding Occurrence
변수 정의

2. Bound Occurrence
정의된 변수 사용

3. Free Identifier
정의되지 않은 변수 접근
Scope
Binding Occurrence가 bound 될 수 있는 범위

• Lexical scope
  Binding occurrence의 scope이 컴파일 시점에 정의
• Dynamic scope
  Binding occurrence의 scope이 런타임 시점에 정의

---

8. High-order / First-order

1. High-order function
다른 함수를 인자로 받거나 함수를 반환하는 함수
2. First-order function
다른 함수를 인자로 받거나 함수를 반환하지 못하는 함수
3. First-class function
함수와 변수를 별도로 구분하지 않고 동일하게 사용

---

9. Eager evaluation / Lazy evaluation

1. Eager evaluation (Called by value)
인자를 먼저 계산하고 함수를 호출하는 방식
2. Lazy evaluation (Called by name)
표현식을 바로 계산하지 않고 필요할 때 계산하는 방식