LL 문법: 하향식 파서가 받는 문법
규칙대로 함수를 짰는데 끝나지 않는다면?
조건 ① 좌측 재귀
자기로 시작하는 규칙
하향식 파서가 받는 문법을 LL 문법이라고 합니다. 첫째 조건은 우변이 좌변과 같은 비단말로 시작하는 좌측 재귀(left recursion)가 없어야 한다는 것입니다. 함수로 옮기면 토큰을 읽지 않은 채 자기를 또 부르고, 끝나지 않습니다.
LL은 입력을 왼쪽에서 오른쪽으로 읽고(L), 레프트모스트 유도를 한다(L)는 뜻입니다. 다른 비단말을 거쳐 돌아오는 간접 좌측 재귀도 안 됩니다.
고치는 법
되풀이를 뒤로 보냅니다
한 규칙 안에서 바로 생기는 좌측 재귀는 규칙을 바꿔 써서 없앨 수 있습니다. 자기로 시작하지 않는 쪽을 앞에 두고, 되풀이되는 쪽은 새 비단말을 만들어 뒤로 보냅니다. 만들어 내는 문장은 그대로입니다.
ε(엡실론)은 아무것도 없다는 뜻입니다. 교재의 일반 꼴 A → Aα | β 를 A → βA′, A′ → αA′ | ε 로 바꾸는 방법을 식의 규칙에 맞춰 본 예시입니다.
바꾸고 나면
이제는 읽고 나서 부릅니다
바꾼 규칙을 함수로 옮기면 먼저 토큰을 읽고 나서 자기를 부릅니다. 부를 때마다 남은 입력이 줄어들고, 더 읽을 것이 없으면 ε 쪽을 골라 끝납니다.
입력 id + id + id 는 예시입니다.
조건 ② 쌍별 서로소
첫 토큰이 겹치면 고를 수 없습니다
하향식 파서는 미리보기 토큰 하나로 우변을 고릅니다. 두 우변이 같은 토큰으로 시작하면 고를 수 없습니다. 한 비단말의 우변들은 시작할 수 있는 첫 토큰이 서로 겹치지 않아야 합니다. 이 조건이 쌍별 서로소(pairwise disjointness)입니다.
교재의 규칙입니다. identifier는 식별자 토큰이고, x와 x[3]은 예시입니다.
검사하는 법
FIRST 집합을 견줍니다
우변이 시작할 수 있는 첫 단말을 모은 것이 FIRST 집합입니다. 한 비단말의 우변을 둘씩 짝지어, FIRST 집합에 같은 단말이 하나도 없으면 통과입니다.
교재의 예입니다. 기호로는 FIRST(αi) ∩ FIRST(αj) = ∅, 곧 두 집합에 겹치는 것이 없다고 적습니다.
고치는 법
함께 시작하는 부분을 묶어 냅니다
두 우변이 함께 시작하는 부분을 앞으로 묶어 내고, 갈라지는 뒷부분을 새 비단말로 만듭니다. 이것이 좌측 인수분해(left factoring)입니다. 이제 identifier를 읽은 다음에 고르면 됩니다.
EBNF로는 <variable> → identifier [ [<expression>] ] 로 적습니다. 바깥 대괄호는 있어도 되고 없어도 된다는 표기입니다.
다음 편