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

الگوریتم سی وای کا   در علوم رایانه یک الگوریتم برنامه‌ریزی پویا برای به‌دست آوردن تجزیه گرامری جملات با استفاده از گرامر مستقل از متن است.

اهمیت این الگوریتم از لحاظ پیچیدگی محاسباتی آن است که  است. این الگوریتم از برنامه‌نویسی پویا به این شکل استفاده می‌کند که ابتدا برای هر حرفِ یک جمله ورودی، تمام متغیرهایی که منجر به تولید آن حرف می‌شوند را در مجموعه ای مجّزا قرار می‌دهد. بعد همین کار را برای زیرجمله‌های دوحرفی تکرار می‌کند و بعد زیرجمله‌های سه حرفی تا به کل جمله برسد. در نهایت اگر متغیر ابتدایی را در مجموعه متغیرهای جمله پایانی یافت نتیجه می‌گیرد که جمله توسط گرامر تولید شده‌است. 

 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

 منابع 

 جان کوک 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.






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

رده:الگوریتم‌های تجزیه