CYK 구문분석 계산기

촘스키 정규형(CNF)으로 적힌 문맥자유문법이 주어진 문자열을 만들 수 있는지 O(n³·|문법|)에 판정합니다. 문자열의 모든 부분문자열마다 "어떤 비단말이 이것을 만들 수 있는가"를 짧은 것부터 긴 것 순으로 채워 올라가는 구간 DP입니다.

모든 생성규칙이 A→BC(비단말 둘)이거나 A→a(단말 하나)인 모양으로 고정되어 있어야, 부분문자열을 정확히 두 조각으로 나눠 왼쪽·오른쪽 각각의 답을 재사용하는 구간 DP가 성립하기 때문입니다. 임의의 문맥자유문법은 CNF로 바꿀 수 있다고 알려져 있지만, 그 변환(단위 규칙·엡실론 규칙 제거 등) 자체는 이 계산기가 하지 않습니다 — 문법을 처음부터 CNF로 입력해야 합니다.

길이 1(글자 하나)인 부분문자열부터 시작해, A→(그 글자) 규칙이 있는 비단말들을 채웁니다. 길이 l인 부분문자열은 두 조각(길이 k와 l−k)으로 나누는 모든 방법을 시도해, 왼쪽 조각에 B가 있고 오른쪽 조각에 C가 있는데 A→BC 규칙이 있으면 A를 그 칸에 넣습니다. 표의 꼭짓점(전체 문자열)에 시작 기호가 있으면 문법이 그 문자열을 만들 수 있다는 뜻입니다.

네, 같은 문자열을 만드는 방법이 여러 가지면 그 문법은 "모호(ambiguous)"합니다. 이 계산기는 받아들이는지 여부와 함께 그 중 하나의 파스 트리만 복원해 보여 줍니다.

CYK(상향식 구간 DP)와는 완전히 다른 방향에서 같은 정의를 계산하는 하향식 메모이제이션 판정기를 따로 만들어, 여러 문법과 길이 1~8의 모든 문자열에서 두 결과가 항상 같은지 대조했습니다. 파스 트리는 잎을 순서대로 이으면 원래 문자열이 그대로 나오는지도 확인했습니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이뤄지고 입력값은 이 기기에만 남습니다.