الگوریتم سی وای کا

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

الگوریتم سی وای کا (به انگلیسی: Cocke–Younger–Kasami (CYK) algorithm) در علوم رایانه یک الگوریتم برنامه‌ریزی پویا برای بدست آوردن تجزیه گرامری جملات با استفاده از گرامر مستقل از متن است.

اهمیت این الگوریتم از لحاظ پیچیدگی محاسباتی آن است که \Theta(n^3 \cdot |G|) است.

شبه کد[ویرایش]

let the input be a string S consisting of n characters: a۱... an.
let the grammar contain r nonterminal symbols R۱... 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
  S is member of language
else
  S is not member of language

منابع[ویرایش]

پیوند به بیرون[ویرایش]