Završni i nezavršni simboli

U teoriji formalnih jezika se pod završnim simbolima (engl. terminal symbols) gramatike se podrazumevaju slova azbuke nad kojom je konstruisana gramatika. Svaka reč jezika je pre svega niska završnih simbola gramatike, koji su poređani po nekom redosledu zavisno od pravila gramatike. U kontekstno slobodnim gramatikama završni simboli mogu učestvovati samo sa desne strane pravila. U drvetu izvođenja proizvoljne niske u nekoj gramatici, završni simboli se mogu naći samo kao listovi tog drveta.

Skup nezavršnih simbola (engl. nonterminals, neterminalni, pomoćni simboli) je skup simbola pomoću kojih se konstruišu pravila izvođenja u formalnoj gramatici. Proces izvođenja niske u nekoj gramatici se sastoji u uzastopnom primenjivanju pravila gramatike. Pritom, nezavršni simboli se zamenjuju završnim simbolima, drugim nezavršnim simbolima ili njihovom kombinacijom. Početni simbol gramatike je takođe nezavršni.

Nezavršni simboli gramatike ne mogu biti listovi drveta izvođenja, jer se, u suprotnom, dopisivanjem listova dobija reč iz jezika koja sadrži nezavršni simbol. To je nemoguće, jer se pri određivanju skupa pomoćnih simbola za neku gramatiku zahteva da on bude disjunktan sa azbukom tj. skupom završnih simbola.

Završni simboli se obično obeležavaju malim slovima abecede: a,b,c,d......

Nezavršni simboli se obično obeležavaju velikim slovima abecede: A,B,C,D......

Reči jednog jezika ili njihove prefikse, sufikse i infikse se označavaju: u,w,v,y,x....

Niske koje se dobijaju u procesu izvođenja, a koje sadrže i nezavršne simbole obeležavaju se sa: α,β,γ,δ...

Primer:

Neka je gramatika G=(Σ,N,P,E) aritmetičkih izraza, i važi:
Σ={broj} je azbuka, broj je završni simbol
N={E,T,F} je skup nezavršnih simbola
E je početni(startni) simbol
P je skup pravila:
      T
      F
      broj
tada je izraz broj+broj*broj izveden u datoj gramatici na sledeći način:
E⇒E+T⇒T+T⇒F+T⇒broj+T⇒broj+T*F⇒broj+F*F⇒broj+broj*F⇒broj+broj*broj

Za izvođenje iz prethodnog primera dobija se sledeće drvo:

                     ____Е____
                    |    |    |
                    Е    +    Т
                    |       __|__
                    Т      |  |  |
                          Т  *  F
                    F      |     |
                    |      F    broj
                   
                          broj

Literatura

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