[Computer] 컴파일러

컴파일러라 함은
고급언어로 된 소스코드를 기계어로 번역해 주는 번역기의 일종이다.

논리적 구조로는
소스프로그램->어휘분석기->토큰->구문분석기->구문분석정보(파스트리or추상구문트리)->중간코드생성기->중간코드->코드최적화->목적코드생성기->목적코드

어휘분석을 위해 정규문법을 사용하고
구문분석을 위해 Context-free문법을 사용한다.

정규문법을 인식하는 FA(Finite Automata)가 있고, DFA와 NFA가 있다.
Context-free문법을 인식하는 PDA(Push Down Automata)가 있고 FA와는 다르게 스택을 사용한다.

구문분석을 하는 방법으로 Top-down 방식과 Bottom-up 방식이 있다.

결정적으로 구문 분석을 하기 위해서는 First 와 Follow의 개념을 사용한다.

Top-down방식은 시작 심벌에서 스트링으로 트리를 작성하며
이때에는 결정적 구문 분석을 위해 left-recursion을 제거하고 left-factoring해야 한다.
또한 LL조건을 만족해야 한다.
Strong LL조건을 사용하는 Recursive-descent파서와 LL조건을 사용하는 Predictive파서가 있다.

Bottom-up방식은 스트링으로 부터 시작 심벌로 서브트리를 연속적으로 만들며
이때에는 결정적 구문 분석을 위해 LR조건을 사용한다.
LR조건을 사용하는 파싱 테이블로 SLR(simple LR), CLR(Canonical LR), LALR(Lookahead LR)이 있다.

어휘분석기를 자동적으로 생성해 주는 LEX가 있고, 구분분석기를 자동적으로 생성해 주는 YACC가 있다.

전체적인 흐름은 이와 같다.

1학년때는 단순히 컴파일 되는 과정을 배웠고 2학년때 계산이론을 통해 FA나 PDA등과 타입3~타입0까지 배우면서 도대체 어떻게 사용되는지 잘 이해가 안됐는데, 지금은 좀 더 구체적으로 이해가 되었다. 어휘분석기를 직접 C언어로 간단하게 만들어 보면서 문법을 정의하는 것 자체도 어렵구나 하는 생각을 했다.

그리고 컴퓨터에 수학적 내용을 적용해서 증명하고 성능을 향상시키는 방법을 실제로 봄으로써 컴퓨터에 역시 수학은 중요하구나 하는 생각도 들었다.