착안

번호 하나로 기억합니다

LR 파서는 시프트-리듀스를 체계적으로 구현한 파서입니다. 넣을지 줄일지는 지금까지의 파싱 이력으로 정할 수 있습니다. 크누스(Knuth)는 나올 수 있는 상황이 유한하고 많지 않다는 데 착안했습니다. 상황마다 번호를 붙인 것이 파서 상태(parser state)이고, 스택에 함께 넣어 둡니다.

LR은 입력을 왼쪽에서 오른쪽으로 읽고(L), 라이트모스트 유도를 거꾸로 밟는다(R)는 뜻입니다.

생김새

보는 것은 둘뿐입니다

LR 파서는 파스 스택, 남은 입력, 파서 코드, 그리고 파싱 테이블(parsing table)이라는 표로 이루어집니다. 스택에는 기호와 상태가 번갈아 들어갑니다. 파서는 스택 맨 위의 상태와 다음 토큰, 이 둘만 보고 표에서 할 일을 찾습니다.

처음에는 스택에 상태 0만 있습니다.

표의 두 부분

할 일의 표와 갈 상태의 표

표는 두 부분입니다. ACTION 테이블은 지금 상태와 다음 토큰을 보고 할 일을 정합니다. 시프트, 리듀스, 수락, 오류 가운데 하나입니다. GOTO 테이블은 리듀스한 뒤 스택에 놓을 상태를 정합니다.

교재의 표에서 몇 줄만 옮겼고 괄호 칸은 뺐습니다. 규칙 번호는 1 E → E + T, 2 E → T, 3 T → T * F, 4 T → F, 5 F → ( E ), 6 F → id 입니다.

한 걸음: 시프트

0행 id열은 S5

첫 걸음입니다. 스택에는 상태 0만 있고 다음 토큰은 id입니다. 표의 0행 id열은 S5입니다. S는 시프트, 5는 새 상태입니다. id와 상태 5를 차례로 스택에 넣습니다.

한 걸음: 리듀스

5행 +열은 R6

다음 걸음입니다. 맨 위 상태 5, 다음 토큰 + 의 칸은 R6, 곧 6번 규칙 F → id 로 리듀스하라는 뜻입니다. 핸들 id와 그 상태를 빼고 좌변 F를 넣습니다. 그 위에 놓을 상태는 GOTO 테이블에서, 드러난 상태 0의 행과 F의 열로 찾습니다.

끝까지

끝은 수락 아니면 오류

같은 식으로 표를 찾고 넣거나 줄이기를 되풀이합니다. 표의 칸이 수락(accept)이면 오류 없이 파싱이 끝난 것입니다. 찾은 칸이 비어 있으면 오류(error)이고, 파서는 오류 처리 루틴을 부릅니다.