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

Од Википедија, слободна енциклопедија

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

V → w

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

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

{an bn  cn :n ≥ 0 }

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

Содржина 1 Формална дефиниција 2 Примери 3 Деривации и синтаксни дрва 4 Референци

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

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

   Vt  е конечно множество од терминали 
       Vn е конечно множество од не- терминали 
        P е конечно множество од продукциски правила
        S е елемент одf 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. Retrieved on 2006-08-24.

Теорија на автомати: формални јазици и формални граматики
Хиерархија на Чомски	Граматики	Јазици	автомати
Тип-0	Нерестриктирани	Рекурзивно преброиви	Тјурингова машина
n/a	(нема вообичаено име)	Рекурзивни	Одлучувач
Тип-1	Контексно осетливи	Контексно осетливи	Линеарни
n/a	Индексирани	Индексирани	Nested stack
Тип-2	Контексно слободни	Контексно слободни	Недетерминистички Pushdown
n/a	Детерминистички контексно слободни	Детерминистички контексно слободни	Детерминистички Pushdown
Тип-3	Регуларни	Регуларни	Конечен
Секоја категорија на јазици или граматики е соодветно подмножество на категоријата над неа.