누구나 거치는 일

어떤 구현이든 소스를 먼저 분석합니다

1강에서 본 구현 방법은 셋이었습니다. 미리 통째로 번역하는 컴파일, 번역 없이 한 문장씩 실행하는 순수 인터프리트, 중간 언어까지만 번역하는 하이브리드입니다. 어느 방법이든 소스 프로그램을 먼저 분석해야 합니다. 그 분석이 어휘 분석과 구문 분석입니다.

두 부분

끊는 쪽과 구조를 찾는 쪽

글자를 어휘 단위, 곧 뜻이 있는 가장 작은 조각으로 끊는 쪽이 어휘 분석기(lexical analyzer), 그 조각들의 구조를 찾는 쪽이 구문 분석기(syntax analyzer)입니다. 구문 분석기는 파서(parser)라고도 부릅니다.

나무는 간단히 그린 것입니다. 괄호는 + 를 먼저 묶으라는 표시여서, 나무에서는 + 가 / 아래에 달린 모양으로 나타납니다.

바탕은 문법

구문 분석은 문법 규칙을 따라갑니다

2강에서 본 BNF는 문법을 규칙으로 적는 표기법입니다. 구문 분석은 대부분 BNF로 적은 문법을 바탕으로 합니다. 그렇게 하면 좋은 점이 셋입니다.

나누는 이유

왜 한꺼번에 하지 않을까요

글자를 끊는 일은 구조를 찾는 일보다 쉬워서 더 간단한 방법으로 할 수 있습니다. 따로 떼어 두면 파서가 단순해지고, 어휘 분석기만 골라 빠르게 다듬을 수 있습니다.

이식성은 다른 환경으로 옮기기 쉬운 정도입니다(1강). 어휘 분석기의 일부는 환경에 따라 달라질 수 있지만 파서는 그대로 옮길 수 있습니다.

필요한 기억

파서에게는 스택이 더 필요합니다

어휘 분석기는 글자를 읽으며 상태 사이를 옮겨 다니면 됩니다. 파서는 괄호처럼 겹겹이 들어가는 구조를 다뤄야 해서, 몇 겹 안인지 쌓아 두는 스택(stack)이 더 필요합니다.

스택은 나중에 넣은 것을 먼저 꺼내는 구조입니다. 왼쪽을 유한 오토마톤(finite automaton), 오른쪽을 푸시다운 오토마톤(push-down automaton)이라고 합니다. 입력은 예시입니다.