Дрво извођења

Језици, како они природни (енглески, француски, српски, ...), тако и вештачки (нпр. програмски језици) се формално могу описати на различите начине. Начин на који описујемо језик зависи пре свега од карактеристика самог језика, као и од намене тј. разлога због кога то чинимо.

Један од добрих начина је опис језика граматиком. Ово је приступ који се примењује на природне језике. Под граматиком неког језика сматрамо уређену четворку :

• азбуке(над којом дефинишемо граматику),
• скупа незавршних симбола,
• скупа правила граматике
• и почетног симбола.

Пример: Српски језик можемо посматрати кроз правила којима је задат нпр. лексичка и морфолошка правила која одређују конструкцију самих речи, даље синтаксичка правила, која се баве конструкцијом реченице, семантичка правила... Сва ова правила чине граматику српског језика.

У рачунарству, приликом анализе програмских језика, постоји више различитих приступа језику, наравно зависно од потребе и карактеристика самог језика. Конкретно, за синтаксичку анализу једног програмског језика, је довољно посматрати контекстно слободне језике, јер они углавном покривају конструкције које се јављају. Добра карактеризација контекстно слободних језика је преко контекстно слободних граматика.

Контекстно слободне граматике су граматике код којих су сва правила облика А→α где је А незавршни симбол, а α ниска састављена од завршних и незавршних симбола.

Дрво извођења

Реч w припада језику Ј генерисаном контекстно слободном граматиком уколико се може описати начин на који се она у датој граматици изводи из почетног симбола. Дрво извођења(енгл. parse tree) је један начин на који се може приказати извођење ниске. Дрво извођења зовемо још и апстрактно синтаксичко дрво.

Пример: Нека је Ана учи. једна ниска у српском језику. Она задовољава правила да се реченица завршава тачком и садржи субјекат и предикат. Даље, Ана задовољава правило да је субјекат именица, а учи задовољава правило да је предикат глагол. Извођење можемо приказати на следећи начин:

• реченица→субјекат предикат интрпункцијски_знак
• субјекат→именица
• предикат→глагол интерпункцијски знак→.

У овом примеру реченица, субјекат, предикат, именица, глагол су незавршни симболи, а Ана, . и учи завршни симболи граматике.

Опис дрвета

Дрво извођења за КСГ G и дату ниску је уређено дрво које у корену има почетни симбол граматике. Чворови дрвета се могу поделити на унутрашње чворове и листове. Унутрашњи чворови могу бити само незавршни симболи граматике, док су листови симболи азбуке над којом је дефинисана граматика. Важи следеће правило: Уколико је А унутрашњи чвор дрвета, а X₁,X₂,....,X_n његови непосредни потомци, онда дата граматика садржи правило облика

A→X₁X₂....X_n

Уколико постоји правило

A→ ε

тада чвор А може да има само једног потомка обележеног са ε.

---

Реч којој је придружено дрво извођења се добија дописивањем листова тог дрвета редом слева удесно. Сваком извођењу једне ниске се придружује једно дрво извођења у датој граматици. Ипак, два извођења једне ниске могу имати исто дрво извођења. Таква два извођења се разликују у редоследу примене правила и за њих кажемо да су еквивалентна.

Уколико у датој граматици свака реч има јединствено дрво извођења, граматика је једнозначна. У супротном она је вишезначна.

Пример(наставак):

дрво за наведену реченицу би изгледало овако:
           __реченица__
          |     |      |
   субјекат предикат интерпункцијски знак
    |           |                     |
   именица    глагол                  .
    |           |
    Ана        учи

Референце

• Витас, Душко М., „Преводиоци и интерпретатори (Увод у теорију и методе компилације програмских језика )“, Математички факултет, Београд 2006.

Види још

• Парсирање
• Парсер