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

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

اهمیت این الگوریتم از لحاظ پیچیدگی محاسباتی آن است که $\Theta (n^{3}\cdot |G|)$ است. این الگوریتم از برنامه‌نویسی پویا به این شکل استفاده می‌کند که ابتدا برای هر حرفِ یک جمله ورودی، تمام متغیرهایی که منجر به تولید آن حرف می‌شوند را در مجموعه ای مجّزا قرار می‌دهد. بعد همین کار را برای زیرجمله‌های دوحرفی تکرار می‌کند و بعد زیرجمله‌های سه حرفی تا به کل جمله برسد. در نهایت اگر متغیر ابتدایی را در مجموعه متغیرهای جمله پایانی یافت نتیجه می‌گیرد که جمله توسط گرامر تولید شده‌است.

let the input be a string S consisting of n characters: a_۱... a_n.
let the grammar contain r nonterminal symbols R_۱... R_r.
This grammar contains the subset R_s 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 R_j -> a_i
    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 R_A -> R_B R_C
        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 R_s) then
  S is member of language
else
  S is not member of language

منابع

جان کوک and Jacob T. Schwartz (1970). Programming languages and their compilers: Preliminary notes. Technical report, موسسه ریاضی کورانت, دانشگاه نیویورک.
T. Kasami (1965). An efficient recognition and syntax-analysis algorithm for context-free languages. Scientific report AFCRL-65-758, Air Force Cambridge Research Lab, بدفورد، ماساچوست.
Daniel H. Younger (1967). Recognition and parsing of context-free languages in time n^۳. Information and Control 10(2): 189–208.
Knuth, Donald E. (November 14, 1997), The Art of Computer Programming Volume 2: Seminumerical Algorithms (3rd ed.), Addison-Wesley Professional, p. 501, ISBN 978-0-201-89684-8
Lange, Martin; Leiß, Hans (2009), "To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm", Informatica Didactica, pdf, 8, archived from the original on 29 November 2014, retrieved 24 March 2013 {{citation}}: External link in |place= (help)نگهداری CS1: موقعیت (link)
Sipser, Michael (1997), Introduction to the Theory of Computation (1st ed.), IPS, p. 99, ISBN 0-534-94728-X
Lee, Lillian (2002), "Fast context-free grammar parsing requires fast Boolean matrix multiplication", Journal of the ACM, 49 (1): 1–15, doi:10٫1145/505241٫505242. {{citation}}: Check |doi= value (help)
Valiant, Leslie G. (1975), "General context-free recognition in less than cubic time", Journal of Computer and System Sciences, 10 (2): 308–314

پیوند به بیرون

الگوریتم CYK به جاوااسکریپت