줄이기

우변을 찾아 좌변으로 바꿉니다

상향식 파싱은 토큰 줄에서 어떤 규칙의 우변과 같은 부분을 찾아, 그 규칙의 좌변으로 바꿉니다. 이 바꾸기가 리듀스(reduce), 곧 줄이기입니다. 되풀이해서 문법의 시작 기호 E 하나만 남으면 문법에 맞는 입력입니다.

5편처럼 식, 항, 팩터 세 층으로 된 교재의 문법입니다. E → E + T 처럼 좌측 재귀가 있지만 상향식 파서에서는 문제가 되지 않습니다.

핸들

아무 데나 줄이면 막힙니다

E + T * id 에는 우변과 같은 부분이 E + T, T, id 셋입니다. 줄여서 시작 기호까지 갈 수 있는 것은 id뿐입니다. 지금 줄여야 하는 이 부분이 핸들(handle)이고, 핸들 찾기가 상향식 파싱의 핵심입니다.

교재의 예입니다. 이 문법에서 * 는 T 뒤에만 옵니다(T → T * F).

동작 둘

스택에 넣고, 맨 위를 줄입니다

상향식 파서는 기호를 쌓아 두는 파스 스택(parse stack)을 씁니다. 동작은 둘입니다. 시프트(shift)는 다음 토큰을 스택 맨 위로 옮기고, 리듀스는 스택 맨 위에 생긴 핸들을 좌변으로 바꿉니다. 이것이 시프트-리듀스 알고리즘입니다.

끝까지

줄일 때마다 트리가 위로 자랍니다

id + id * id 를 끝까지 따라갑니다. 줄일 때마다 트리의 마디가 하나씩, 아래에서 위로 생깁니다. 스택에 시작 기호 E만 남고 입력이 비면 끝입니다.

곱셈을 먼저 묶어야 해서, 스택이 E + T 여도 다음 토큰이 * 이면 줄이지 않고 넣습니다. 이 판단은 다음 편에서 봅니다.

4편에서 한 말

거꾸로 읽으면 유도입니다

파서가 지나온 줄을 아래에서 위로 읽으면, E에서 시작해 늘 가장 오른쪽 비단말을 풀어 가는 유도가 됩니다. 4편에서 말한 대로, 상향식 파싱은 라이트모스트 유도를 거꾸로 밟습니다.