CYK 알고리즘

CYK 알고리즘(Cocke-Younger-Kasami 알고리즘, CYK Algorithm) 또는 CKY 알고리즘은 특정한 문자열에 대해, 그 문자열이 특정한 문맥 자유 문법에 속하는지를 판단하고, 또한 어떠한 방식으로 생성되는지를 판단하는 파싱 알고리즘이다. 이 알고리즘은 동적 계획법을 사용하며, 상향식 파싱 구조를 가지고 있다.

기본적으로 CYK 알고리즘에서는 촘스키 정규 형식으로 표현된 문맥 자유 문법을 사용하지만, 모든 문맥 자유 문법은 촘스키 정규 형식으로 변환이 가능하기 때문에 CYK 알고리즘을 사용할 수 있다.

문자열의 길이가 $n$일 때, CYK 알고리즘은 Θ(n³)의 시간 복잡도를 가진다. 이것은 현재 모든 문맥 자유 문법을 파싱할 수 있는 가장 효율적인 알고리즘이다. (CYK 알고리즘보다 효율적으로 동작하는 몇몇 알고리즘이 있지만, 그 알고리즘은 특정한 문법의 경우에만 사용이 가능하다.)

알고리즘

membership 문제를 푸는 CYK 알고리즘은 아래와 같다:

Let the input string consist of n letters, a1 ... an.
Let the grammar contain r terminal and nonterminal symbols R1 ... Rr.
This grammar contains the subset Rs which is the set of start symbols.
Let P[n,n,r] be an array of booleans. Initialize all elements of P to false.
For each i = 1 to n
  For each unit production Rj -> ai, set P[i,1,j] = true.
For each i = 2 to n -- Length of span
  For each j = 1 to n-i+1 -- Start of span
    For each k = 1 to i-1 -- Partition of span
      For each production RA -> RB RC
        If P[j,k,B] and P[j+k,i-k,C] then set P[j,i,A] = true
If any of P[1,n,x] is true (x is iterated over the set s, where s are all the indices for Rs)
  Then string is member of language
  Else string is not member of language

예

예시 문법은 다음과 같다.

$\begin{array}{cc}\mathrm{S}& ⟶\mathrm{N}\mathrm{P}\mathrm{V}\mathrm{P}\\ \mathrm{V}\mathrm{P}& ⟶\mathrm{V}\mathrm{P}\mathrm{P}\mathrm{P}\\ \mathrm{V}\mathrm{P}& ⟶\mathrm{V}\mathrm{N}\mathrm{P}\\ \mathrm{V}\mathrm{P}& ⟶\mathrm{e}\mathrm{a}\mathrm{t}\mathrm{s}\\ \mathrm{P}\mathrm{P}& ⟶\mathrm{P}\mathrm{N}\mathrm{P}\\ \mathrm{N}\mathrm{P}& ⟶\mathrm{D}\mathrm{e}\mathrm{t}\mathrm{N}\\ \mathrm{N}\mathrm{P}& ⟶\mathrm{s}\mathrm{h}\mathrm{e}\\ \mathrm{V}& ⟶\mathrm{e}\mathrm{a}\mathrm{t}\mathrm{s}\\ \mathrm{P}& ⟶\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{h}\\ \mathrm{N}& ⟶\mathrm{f}\mathrm{i}\mathrm{s}\mathrm{h}\\ \mathrm{N}& ⟶\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{k}\\ \mathrm{D}\mathrm{e}\mathrm{t}& ⟶\mathrm{a}\end{array}$

참고 문헌

• John Cocke and Jacob T. Schwartz (1970). Programming languages and their compilers: Preliminary notes. Technical report, Courant Institute of Mathematical Sciences, New York University.
• T. Kasami (1965). An efficient recognition and syntax-analysis algorithm for context-free languages. Scientific report AFCRL-65-758, Air Force Cambridge Research Lab, Bedford, MA.
• Daniel H. Younger (1967). Recognition and parsing of context-free languages in time n³. Information and Control 10(2): 189–208.