한 걸음

비단말 하나를 우변으로 바꿉니다

지금 가진 기호들에서 비단말 하나를 골라, 그 이름이 좌변인 규칙의 우변으로 바꿔 씁니다. 규칙을 한 번 쓴 것입니다. 시작 기호에서 출발해 이 일을 되풀이하는 것이 유도(derivation)입니다.

2편의 예제 문법 여섯 줄에서 가져온 규칙입니다.

처음부터 끝까지

여덟 번 바꾸면 문장이 됩니다

시작 기호 <program>에서 출발합니다. 걸음마다 가장 왼쪽 비단말을 규칙 하나로 바꿉니다. 여덟 번 바꾸자 비단말이 모두 사라지고 a = b + const 가 남았습니다.

이 강의가 따르는 교재의 유도 예입니다. 대안이 여럿인 규칙에서는 만들려는 문장에 맞는 쪽을 골랐습니다.

이름 붙이기

단말만 남으면 문장입니다

유도하는 동안 나오는 줄 하나하나를 문장 형태(sentential form)라고 합니다. 그 가운데 비단말이 하나도 없이 단말 기호만 남은 것이 문장입니다. 1편에서 말한 '그 언어의 문장'은 이렇게 유도해 낼 수 있는 문자열입니다.

바꾸는 순서

어느 것부터 바꿔도 됩니다

비단말이 둘 이상이면 어느 것부터 바꿀지 고를 수 있습니다. 늘 가장 왼쪽부터 바꾸면 레프트모스트 유도(leftmost derivation), 가장 오른쪽부터 바꾸면 라이트모스트 유도(rightmost derivation)입니다. 섞어도 됩니다.

앞 장의 유도는 레프트모스트 유도였습니다. 쓰는 규칙이 같으면 순서가 달라도 같은 문장에 이릅니다.

유도되지 않으면

만들 수 없으면 문장이 아닙니다

a = b + 는 이 문법으로 만들 수 없습니다. + 뒤의 <term>은 변수나 const로만 바뀌고, 지우는 규칙은 없기 때문입니다. 어떤 유도로도 나오지 않는 문자열은 그 언어의 문장이 아닙니다. 구문 오류입니다.

아래 문자열은 예시입니다.