컴파일러란

컴파일러

• 언어를 번역하는 프로그램
• Source Program을 Target Program로 번역
• 고급언어로 작성한 프로그램을 각각의 기계에서 효율적으로 실행하기 위해 필요

번역 과정

• Lexical analysis: 소스 프로그램을 읽음, 토큰
• Syntax analysis: 스캐너에서 읽은 토큰을 구문 분석을 통해 언어에 속하는 지 파악
• Semantic analysis: 의미상 맞지 않는 경우 파악
• Source code optimizer: 최적화가 되면 빨리지고 좋지만 컴파일이 느려짐
• Intermediate representaion: 번역되기 좋은 형태, three address code
• Code generator & target code optimization

오토마타

• abstract computing devices
• 단수형은 automaton

오토마타는 언어를 인식
문법은 언어를 생성

형식 언어

• 알파벳: 유한하고 비어있지 않은 문자의 집합
• 스트링: 유한한 sequence of symbols(문자의 시퀀스)
• $\sum^*$: 0번 이상 반복
• $\sum^+$: 1번이상 반복
• 언어는 $\sum^*$의 부분 집합

문법

• 언어를 규칙들로 명세한 것
• 규칙과 절차의 집합
• $G=(V_N,V_T,P,S)$
• $V_N$: set of non-terminal symbols(finite set)
• $V_T$: set of terminal symbols(finite set)
• $P$: productions(finite set)
• $S$: start symbol
• 프로덕션만 알면 문법을 파악할 수 있다.

Derivatoin

• Production을 적용해 다른 문자열로 바꾸는 것($⇒$)

촘스키 계층 구조

• 0 Unrestricted Grammar

  • $\alpha \rightarrow \beta$
  • Turing machine

• 1 Context-Sensitive Grammar

  • $\alpha \rightarrow \beta$
  • $|\alpha| \leq |\beta|, \alpha \in V^+, \beta \in V^*$
  • Linear bounded automata

• 2 Context-Free Grammar

  • $\alpha \rightarrow \beta$
  • $\alpha \in V_N, \,\beta \in V^*$
  • Pushdown automata

• 3 Regular Grammar

  • $\alpha \rightarrow t\beta | t$ (right linear)
  • $\alpha \rightarrow \beta t | t$ (left linear)
  • $\alpha, \beta \in V_N, \, t \in V^*_T$
  • Finite automata

Regular expressions

• 언어를 서술하는 대수적인 방법
• e가 정규 표현 일 때
  • L(e)는 이것을 정의하는 언어

기본
1. 심볼 a가 있을 때, $L(a)=\{a\}$
2. $\epsilon$ 이 정규 표현일 때 $L(\epsilon)=\{\epsilon\}$
3. 공집합이 정규표현일 때, 언어는 공집합

응용

1. $L(r+s)=L(r) \cup L(s)$
2. $L(rs)=L(r)L(s)$ //Concatenation
3. $L(r^*)=(L(r))^*$