From Wikipedia, the free encyclopedia
Кук-Јангер-Касами алгоритам () је алгоритам који служи за одређивање припадности неке речи контекстно слободном језику A (тип 2 у класификацији Чомског), тј:
![]() | Овај чланак садржи списак литературе, сродне писане изворе или спољашње везе, али његови извори остају нејасни, јер нису унети у сам текст. |
Овај алгоритам спада у методе синтаксичке анализе које омогућавају анализирање било које контекстно слободне граматике. У основи, овом методом се, почетно од стартног симбола граматике, анализирају сва могућа извођења, док се не утврди да ли реч припада језику или не. Уколико се утврди да припада језику, овај алгоритам омогућава и увид у начин на који је реч изведена. Стандардни алгоритам анализира КС граматике које су дате у нормалној форми Чомског. Ипак, како се свака контекстно слободна граматика може превести у овај облик, метода је применљива на све КСГ. Постоје и проширења алгоритма којима се могу анализирати граматике које нису у нормалној форми Чомског.
алгоритам спада у ефикасније алгоритме синтаксичке анализе који имају широку применљивост. Сложеност алгоритма је полиномска и спада у класу (због три угнежђене петље), где је дужина анализиране ниске. Наравно, постоје и методе линеарне сложености, али су оне применљиве само на неке поткласе КСГ. Алгоритам припада парадигми динамичког програмирања.
Имплементација динамичким програмирањем:
Улаз: карактери а1.... аn од којих се састоји задата ниска, симболи задате
граматике: терминала и нетерминали ... , где је 1 почетни симбол
Излаз: одговор да ли ниска припада језику граматике
{ локалне варијабле:
(бројачке променљиве)
матрица логичких вредности (на почетку сваки елемент матрице има вредност 0)
(током рада алгритма ће постати 1 ако подниска улазне ниске од позиције
на дужини може да се генерише из r)
(узећемо да је први елемент , а не )
за свако правило граматике поставити ;
(скенира се улазна ниска, а за свако )
(прегледа се префикс ниске дужине )
(извођење из правила граматике)
за свако правило
(тј. ако је правило такво да се из може генерисати
подниска дужине почев од позиције , и из се може генерисати
подниска дужине почев од позиције , онда се из може
генерисати подниска дужине почев од позиције , тј. )
'ниска је члан језика'
'ниска није члан језика'
}
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.