규칙 한 번, 가지 한 번

좌변은 부모, 우변은 자식

규칙을 한 번 쓰는 것을 나무로 그리면, 좌변의 비단말이 부모가 되고 우변의 기호들이 그 아래 자식으로 달립니다. 유도에서는 줄이 하나 늘고, 나무에서는 가지가 한 번 뻗습니다.

나무가 자랍니다

유도 전체가 파스 트리 하나

3편의 유도를 나무로 옮겼습니다. 규칙을 쓸 때마다 가지가 뻗습니다. 이렇게 유도를 나무 구조로 나타낸 것이 파스 트리(parse tree)입니다.

1강 8편에서 구문 분석이 만든다고 한 나무입니다. 그때는 비단말을 빼고 간단히 그렸습니다.

나무의 세 부분

잎만 읽으면 문장입니다

맨 위 루트는 시작 기호입니다. 가지가 갈라지는 내부 노드는 모두 비단말이고, 더 뻗지 않는 끝인 잎 노드는 모두 단말입니다. 잎을 왼쪽부터 차례로 읽으면 유도한 문장이 됩니다.

노드(node)는 나무의 마디 하나를 가리킵니다.

나무가 알려 주는 것

나뭇가지 하나 아래는 한 덩어리

b + const 는 <expr>라는 나뭇가지 하나 아래에 모여 있습니다. 식 하나라는 뜻입니다. 그 식 전체가 = 의 오른쪽에 옵니다. 컴파일러(코드를 기계어로 번역하는 프로그램)는 파스 트리의 이 묶음대로 뜻을 정합니다.

<stmt> 아래만 그렸습니다.