파서의 목표

파서가 할 일은 둘입니다

구문 분석기를 파서라고 했습니다. 파서가 하는 일이 파싱(parsing)입니다. 목표는 둘입니다. 구문 오류를 모두 찾아 알맞게 알려 주고 빨리 다음으로 넘어가는 것, 그리고 파스 트리를 만드는 것입니다.

왼쪽은 47을 빼서 만든 틀린 예시입니다. 나무는 간단히 그렸습니다.

2강 되짚기

규칙으로 바꿔 써 가는 것이 유도

규칙의 왼쪽이 좌변, 오른쪽이 우변입니다. 꺾쇠로 싼 이름은 더 풀어 쓰는 비단말(nonterminal), id와 + 는 더 풀지 않는 단말(terminal), 곧 토큰입니다. 좌변을 우변으로 바꿔 써 가는 것이 유도(derivation)입니다.

줄여 만든 예시 문법입니다. id는 식별자 토큰이어서 sum + total 은 파서에게 id + id 로 보입니다.

하향식

뿌리에서 잎으로

하향식 파서(top-down parser)는 뿌리(루트)에서 출발해 아래로 내려가며 트리를 만듭니다. 뿌리는 유도가 출발하는 비단말, 곧 시작 기호입니다. 늘 가장 왼쪽 비단말부터 풉니다. 이 순서의 유도를 레프트모스트 유도(leftmost derivation)라고 합니다.

상향식

잎에서 뿌리로

상향식 파서(bottom-up parser)는 잎, 곧 토큰에서 출발해 위로 올라갑니다. 어떤 규칙의 우변과 같은 부분을 찾아 좌변으로 바꿉니다. 지나온 줄을 거꾸로 읽으면, 늘 가장 오른쪽 비단말을 푸는 라이트모스트 유도(rightmost derivation)가 됩니다.

미리보기

토큰은 하나만 미리 봅니다

쓸모 있는 파서는 입력을 앞에서부터 읽으며, 다음 토큰 하나만 미리 보고 어느 규칙을 쓸지 정합니다. 이 토큰을 미리보기 토큰(lookahead)이라고 합니다. 하향식이든 상향식이든 같습니다.

파싱에 드는 시간

문법을 가려 받아야 빠릅니다

비모호한 문법이면 무엇이든 받는 파서는 입력 길이의 세제곱에 비례하는 시간이 듭니다. 그래서 컴파일러는 일부 문법만 받는 대신, 길이에 비례하는 시간에 끝나는 파서를 씁니다.

비모호한 문법은 문장마다 파스 트리가 하나뿐인 문법입니다(2강). 아래의 수는 100의 세제곱과 100을 견준 예시입니다.