Контексно слободна граматика

Во лингвистиката и информатиката контексно-слободна граматика (англиски: Context-free grammar, CFG) е формална граматика каде што секое продукциско правило ја има формата

V → w

каде V е нетерминален симбол и w е низа составена од терминали и/или не-теминали. Поимот " контексно-слободна" го објаснува фактот дека не-терминално V секогаш може да биде заменето со w, без разлика каде и да се појавува. Формален јазик е контексно слободен ако постои контексно-слободна граматика која го создава. Контексно слободните граматики се доволно моќни за да создаваат синтакса на повеќето програмски јазици; всушност, синтаксата на повеќе програмски јазици е изградена врз основа на контексно-слободна граматика. Од друга страна пак, контексно-слободните граматики се доволно едноставни за да дозволат конструкција на ефикасни расчленувачки алгоритми кои за даден стринг, одлучуваат дали и како ќе бидат созадени од граматиката.

Не сите јазици се контексно-слободни. Добро познат пример е бројач

{an bn  cn :n ≥ 0 }

множество од стрингови што содржи број на а буквата, да има исто толку и b букви, а исто толку и c букви.

Формална дефиниција

Како и секоја формална граматика, контексно-слободна граматика G може да биде дефинирана како 4-ворка: G = (Vt,Vn,P,S) каде

	Vt  е конечно множество од терминали 
       Vn е конечно множество од не- терминали 
	P е конечно множество од продукциски правила
	S е елемент од Vn, единствениот почетен не-терминал. 
	Елементите од P се од форма   

Јазик L е контексно-слободен јазик (CFL) ако неговата граматика е контексно-слободна граматика. Попрецизно ,тоа е јазик чии зборови, реченици и фрази се создадени од симболи и зборовиод контексно-слободна граматика.

Примери

Пример 1

Контексно-слободна граматика е дадена со: S → aSb | ε каде | се користи за да одвои повеќе избори од истиот не-терминал, и ε е за празен стринг. Граматиката го создава јазикот е {aⁿ bⁿ :n ≥ 0 }, кој не е регуларен.

Пример 2

Ова е контексно-слободна граматика за синтаксички точен алгебарски израз со промениливи x, y и z:

S → x | y | z | S + S | S - S | S * S | S/S | (S)

Оваа граматика, за пример, создава стринг

"( x + y ) * x - z * y / ( x + x )".

Оваа граматика не е конкретна, односно од неа може да се создадат повеќе различни дрва и на тој начин нема да се добие точен израз.

Пример 3

Контексно-слободна граматика за јазикот што го содржи сите стрингови составени од {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ⁿ a^m b²ⁿ :n ≥ 0 ,m ≥ 0} . Ова не е регуларен израз, но е контексно-слободен и може да биде созадден од следнава контексно-слободна граматика:

S → bSbb | A

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→1+S+S (2)

S→1+1+S (2)

S→1+1+a (3)

{ { { 1 }S + { 1 }S }S + { a }S }S

Каде { ... }S е подстринг кој припаѓа на S. Оваа хиерархија може да биде претставена и со дрво:

          S
         /|\
        / | \
       /  |  \
      S  '+'  S
     /|\      |
    / | \     |
   S '+' S   'a'
   |     |
  '1'   '1'

Ова дрво е наречено постоечко синтаксно дрво на стрингот. Во овој случај налевата и најдесната деривација го дефинираат истото дрво, но тука може да се изведе уште една најлева деривација за конкретниот стринг.

S→ S + S (1)

S→ 1 + S (2)

S→ 1 + S + S (1)

S→ 1 + 1 + S (2)

S→ 1 + 1 + a (3)

И тоа го претставува следново синтаксно дрво:

          S 
         /|\
        / | \
       /  |  \
      S  '+'  S
      |      /|\
      |     / | \
     '1'   S '+' 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. 91–101. Section 4.1.2: Decidable problems concerning context-free languages, pp. 156–159. Section 5.1.1: Reductions via computation histories: pp. 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. Посетено на 2006-08-24.