Drvo izvođenja

Jezici, kako oni prirodni (engleski, francuski, srpski, ...), tako i veštački (npr. programski jezici) se formalno mogu opisati na različite načine. Način na koji opisujemo jezik zavisi pre svega od karakteristika samog jezika, kao i od namene tj. razloga zbog koga to činimo.

Jedan od dobrih načina je opis jezika gramatikom. Ovo je pristup koji se primenjuje na prirodne jezike. Pod gramatikom nekog jezika smatramo uređenu četvorku :

• azbuke(nad kojom definišemo gramatiku),
• skupa nezavršnih simbola,
• skupa pravila gramatike
• i početnog simbola.

Primer: Srpski jezik možemo posmatrati kroz pravila kojima je zadat npr. leksička i morfološka pravila koja određuju konstrukciju samih reči, dalje sintaksička pravila, koja se bave konstrukcijom rečenice, semantička pravila... Sva ova pravila čine gramatiku srpskog jezika.

U računarstvu, prilikom analize programskih jezika, postoji više različitih pristupa jeziku, naravno zavisno od potrebe i karakteristika samog jezika. Konkretno, za sintaksičku analizu jednog programskog jezika, je dovoljno posmatrati kontekstno slobodne jezike, jer oni uglavnom pokrivaju konstrukcije koje se javljaju. Dobra karakterizacija kontekstno slobodnih jezika je preko kontekstno slobodnih gramatika.

Kontekstno slobodne gramatike su gramatike kod kojih su sva pravila oblika A→α gde je A nezavršni simbol, a α niska sastavljena od završnih i nezavršnih simbola.

Drvo izvođenja

Reč w pripada jeziku J generisanom kontekstno slobodnom gramatikom ukoliko se može opisati način na koji se ona u datoj gramatici izvodi iz početnog simbola. Drvo izvođenja(engl. parse tree) je jedan način na koji se može prikazati izvođenje niske. Drvo izvođenja zovemo još i apstraktno sintaksičko drvo.

Primer: Neka je Ana uči. jedna niska u srpskom jeziku. Ona zadovoljava pravila da se rečenica završava tačkom i sadrži subjekat i predikat. Dalje, Ana zadovoljava pravilo da je subjekat imenica, a uči zadovoljava pravilo da je predikat glagol. Izvođenje možemo prikazati na sledeći način:

• rečenica→subjekat predikat intrpunkcijski_znak
• subjekat→imenica
• predikat→glagol interpunkcijski znak→.

U ovom primeru rečenica, subjekat, predikat, imenica, glagol su nezavršni simboli, a Ana, . i uči završni simboli gramatike.

Opis drveta

Drvo izvođenja za KSG G i datu nisku je uređeno drvo koje u korenu ima početni simbol gramatike. Čvorovi drveta se mogu podeliti na unutrašnje čvorove i listove. Unutrašnji čvorovi mogu biti samo nezavršni simboli gramatike, dok su listovi simboli azbuke nad kojom je definisana gramatika. Važi sledeće pravilo: Ukoliko je A unutrašnji čvor drveta, a X₁,X₂,....,X_n njegovi neposredni potomci, onda data gramatika sadrži pravilo oblika

A→X₁X₂....X_n

Ukoliko postoji pravilo

A→ ε

tada čvor A može da ima samo jednog potomka obeleženog sa ε.

---

Reč kojoj je pridruženo drvo izvođenja se dobija dopisivanjem listova tog drveta redom sleva udesno. Svakom izvođenju jedne niske se pridružuje jedno drvo izvođenja u datoj gramatici. Ipak, dva izvođenja jedne niske mogu imati isto drvo izvođenja. Takva dva izvođenja se razlikuju u redosledu primene pravila i za njih kažemo da su ekvivalentna.

Ukoliko u datoj gramatici svaka reč ima jedinstveno drvo izvođenja, gramatika je jednoznačna. U suprotnom ona je višeznačna.

Primer(nastavak):

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

Reference

• Vitas, Duško M., „Prevodioci i interpretatori (Uvod u teoriju i metode kompilacije programskih jezika )“, Matematički fakultet, Beograd 2006.

Vidi još

• Parsiranje
• Parser