Кук-Јангер-Касами алгоритам — разлика између измена
Садржај обрисан Садржај додат
м Бот Додаје: vi:Thuật toán CYK |
Нема описа измене |
||
Ред 1:
'''Кук-Јангер-Касами алгоритам''' (''-{
:<math>w \in A ?</math>
Овај алгоритам спада у методе синтаксичке анализе које омогућавају анализирање било које [[контекстно слободна граматика|контекстно слободне граматике]]. У основи, овом методом се, почетно од стартног симбола граматике, анализирају сва могућа извођења, док се не утврди да ли реч припада језику или не. Уколико се утврди да припада језику, овај алгоритам нам омогућава и увид у начин на који је реч изведена.
Стандардни алгаритам анализира КС граматике које су дате у нормалној форми Чомског. Ипак, како се свака контекстно слободна граматика може превести у овај облик, метода је применљива на све КСГ.
Постоје и проширења алгоритма којима се могу анализирати граматике које нису у нормалној форми Чомског.
CYK алгоритам спада у ефикасније алгоритме синтаксичке анализе који имају широку применљивост.
Сложеност алгоритма је полиномска и спада у класу ''-{O(n<sup>3</sup>)}-'', где је n дужина анализиране ниске. Наравно, постоје и методе линеарне сложености, али су оне применљиве само на неке поткласе КСГ.
== Алгоритам ==
Имплементација динамичким програмирањем:
<code>
for i := 1 to n do T[i,1] := {A iz V : A → x<sub>i</sub> iz P}
for j := 2 to n do
Линија 18 ⟶ 23:
return S iz T[1,n]
</code>
Могуће је алгоритам проширити тако да анализира и тежинске и стохастичке контекстно слободне граматике.
== Референце ==
* ''Скрипта за предмет „Информатика 3“, УНИ Карлсруе, Петер Сандерс''
* ''Витас, Душко М., „Преводиоци и интерпретатори (Увод у теорију и методе компилације програмских језика )“, Математички факултет,Београд 2006.''
[[Категорија:Алгоритми]]
===Погледајте===
[[Earley algorithm]]
[[af:CYK-algoritme]]
[[cs:Algoritmus Cocke-Younger-Kasami]]
| |||