Разлика помеѓу преработките на „Контексно слободна граматика“

с
Јазична исправка, replaced: Retrieved on → Посетено на
с
с (Јазична исправка, replaced: Retrieved on → Посетено на)
 
Во лингвистиката и информатиката '''контексно-слободна граматика''' ([[англиски јазик|англиски]]: ''Context-free grammar'', ''CFG'') е формална граматика каде што секое продукциско правило ја има формата
 
:V → w
 
каде V е нетерминален симбол и w е [[низа (информатика)|низа]] составена од терминали и/или не-теминали. Поимот " контексно-слободна" го објаснува фактот дека не-терминално V секогаш може да биде заменето со w, без разлика каде и да се појавува. Формален јазик е контексно слободен ако постои контексно-слободна граматика која го создава.
Контексно слободните граматики се доволно моќни за да креираат синтакса на повеќето програмски јазици; всушност, синтаксата на повеќе програмски јазици е изградена врз основа на контексно-слободна граматика. Од друга страна пак, контексно-слободните граматики се доволно едноставни за да дозволат конструкција на ефикасни [[расчленување (информатика)|расчленувачки]] алгоритми кои за даден стринг, одлучуваат дали и како ќе бидат созадени од граматиката.
 
Не сите јазици се контексно-слободни. Добро познат пример е бројач
{a<sup>n</sup> b<sup>n</sup> c<sup>n</sup> :n ≥ 0 }
множество од стрингови што содржи број на а буквата, да има исто толку и b букви, а исто толку и c букви.
 
 
== Формална дефиниција ==
Елементите од P се од форма [[Податотека:KSG1.jpg]]
Јазик L е контексно-слободен јазик (CFL) ако неговата граматика е контексно-слободна граматика. Попрецизно ,тоа е јазик чии зборови, реченици и фрази се создадени од симболи и зборовиод контексно-слободна граматика.
 
 
== Примери ==
Ова е контексно-слободна граматика за синтаксички точен алгебарски израз со промениливи x, y и z:
 
S → x | y | z | S + S | S - S | S * S | S/S | (S)
 
Оваа граматика, за пример, создава стринг
 
Контексно-слободна граматика за јазикот што го содржи сите стрингови составени од {a,b} кои содржат различен број на a и b.
S → U | V
 
U → TaU | TaT
 
V → TbV | TbT
 
T → aTbT | bTaT | ε
 
Тука, T може да создава стрингови кои ќе имаат ист број на a и b, U создава стрингови со повеќе e а од b и V создава стрингови со помалку а од b.
 
 
 
'''Пример 4'''
Друг пример за контексно-слободна граматика е {b<sup>n</sup> a<sup>m</sup> b<sup>2n</sup> :n ≥ 0 ,m ≥ 0} . Ова не е регуларен израз, но е контексно-слободен и може да биде созадден од следнава контексно-слободна граматика:
 
S → bSbb | A
 
A → aA | ε
 
A → aA | ε
 
== Деривации и синтаксни дрва ==
Има два начина за да опишеме како даден стринг може да резултира од стартниот симбол на една граматика. Наједноставен начин е со правење листа од следните стрингови од симболи, почнувајќи од стартниот симбол и завршувајќи со стринг, според назначените правила. Ако работиме според "секогаш прво заменувај го најлевиот не-терминал" тогаш за контексно-слободна граматика листата со назначените граматички правила самата по себе е доволна. Тоа се нарекува најлева деривација на стринг. За пример, ја земаме следнава граматика:
 
(1) S → S + S
 
(2) S → 1
 
(3) S → a
 
Стрингот "1 + 1 + a" тогаш лева деривација на стрингот е листата [ (1), (1), (2), (2), (3) ]. Аналогно,најдесната деривација е дефинирана како листата што ја добиваме ако секогаш го заменуваме најдесниот нетерминал прво. Во овој случај тоа е листата [ (1), (3), (1), (2), (2)].
Исто така под деривација се подразбира хиерархиска подреденост на даден стринг. На пример стрингот "1 + 1 + a” според најлева деривација ќе биде:
 
S→S+S (1)
 
S→S+S+S (1)
 
S→SS→1+S+S (12)
 
S→1+S1+S (2)
 
S→1+1+Sa (23)
 
{ { { 1 }S + { 1 }S }S + { a }S }S
S→1+1+a (3)
 
{ { { 1 }S + { 1 }S }S + { a }S }S
 
Каде { ... }S е подстринг кој припаѓа на S. Оваа хиерархија може да биде претставена и со дрво:
Ова дрво е наречено постоечко синтаксно дрво на стрингот. Во овој случај налевата и најдесната деривација го дефинираат истото дрво, но тука може да се изведе уште една најлева деривација за конкретниот стринг.
 
S→ S + S (1)
 
S→ 1 + S (2)
 
S→ 1 + S + S (1)
 
S→ 1 + 1 + S (2)
 
S→ 1 + 1 + a (3)
 
И тоа го претставува следново синтаксно дрво:
 
 
 
 
 
S
| |
'1' 'a'
 
 
Ако за одредени стрингови постои повеќе од едно расчленувачко дрво тогаш граматиката се нарекува ambiguous grammar. Таквите граматики најчесто тешко се расчленуваат затоа што расчленувачот не може секогаш да одлучи кое граматичко правило да го употреби.
 
 
== Наводи ==
* Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 2.1: Context-Free Grammars, pp.&nbsp;91–101. Section 4.1.2: Decidable problems concerning context-free languages, pp.&nbsp;156–159. Section 5.1.1: Reductions via computation histories: pp.&nbsp;176–183.
* ^ L, BalaSundaraRaman; Ishwar.S, Sanjeeth Kumar Ravindranath (2003-08-22). "Context Free Grammar for Natural Language Constructs - An implementation for Venpa Class of Tamil Poetry". Proceedings of Tamil Internet, Chennai, 2003, 128-136, International Forum for Information Technology in Internet. RetrievedПосетено onна 2006-08-24.
 
{{Formal languages and grammars}}