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

Од Википедија — слободната енциклопедија
[непроверена преработка][непроверена преработка]
Избришана содржина Додадена содржина
Нема опис на уредувањето
Нема опис на уредувањето
Ред 6: Ред 6:
Контексно-слободните граматики се доволно моќни за да креираат синтакса на повеќето програмски јазици; всушност, синтаксата на повеќе програмски јазици е изградена врз основа на контексно-слободна граматика. Од друга страна пак, контексно-слободните граматики се доволно едноставни за да дозволат конструкција на ефикасни парсирачки алгоритми кои за даден стринг, одлучуваат дали и како ќе бидат созадени од граматиката.
Контексно-слободните граматики се доволно моќни за да креираат синтакса на повеќето програмски јазици; всушност, синтаксата на повеќе програмски јазици е изградена врз основа на контексно-слободна граматика. Од друга страна пак, контексно-слободните граматики се доволно едноставни за да дозволат конструкција на ефикасни парсирачки алгоритми кои за даден стринг, одлучуваат дали и како ќе бидат созадени од граматиката.


Не сите јазици се контексно-слобони — добро познат пример со бројач е {a<sup>n</sup> b<sup>n</sup> c<sup>n</sup> :n &ge; 0 }, множество од стрингови што содржи број на а буквата, да има исто толку и b букви ,а исто толку и c букви.
Не сите јазици се контексно-слободни.Добро познат пример е бројач {a<sup>n</sup> b<sup>n</sup> c<sup>n</sup> :n &ge; 0 }, множество од стрингови што содржи број на а буквата, да има исто толку и b букви ,а исто толку и c букви.





Преработка од 20:18, 27 февруари 2007

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

V → w

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

Не сите јазици се контексно-слободни.Добро познат пример е бројач {an bn cn :n ≥ 0 }, множество од стрингови што содржи број на а буквата, да има исто толку и b букви ,а исто толку и c букви.


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

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

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

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


Примери

Пример 1

Контексно-слободна граматика е дадена со: S → aSb | ε каде | се користи за да одвои повеќе избори од истиот не-терминал, и ε е за празен стринг. Граматиката го создава јазикот е {an bn :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

Друг пример за контексно-слободна граматика е {bn am b2n :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. Таквите граматики најчесто тешко се парсираат затоа што парсерот не може секогаш да одлучи кое граматичко правило да го употреби.