Завршни и незавршни симболи

У теорији формалних језика се под завршним симболима (енгл. terminal symbols) граматике се подразумевају слова азбуке над којом је конструисана граматика. Свака реч језика је пре свега ниска завршних симбола граматике, који су поређани по неком редоследу зависно од правила граматике. У контекстно слободним граматикама завршни симболи могу учествовати само са десне стране правила. У дрвету извођења произвољне ниске у некој граматици, завршни симболи се могу наћи само као листови тог дрвета.

Скуп незавршних симбола (енгл. nonterminals, нетерминални, помоћни симболи) је скуп симбола помоћу којих се конструишу правила извођења у формалној граматици. Процес извођења ниске у некој граматици се састоји у узастопном примењивању правила граматике. Притом, незавршни симболи се замењују завршним симболима, другим незавршним симболима или њиховом комбинацијом. Почетни симбол граматике је такође незавршни.

Незавршни симболи граматике не могу бити листови дрвета извођења, јер се, у супротном, дописивањем листова добија реч из језика која садржи незавршни симбол. То је немогуће, јер се при одређивању скупа помоћних симбола за неку граматику захтева да он буде дисјунктан са азбуком тј. скупом завршних симбола.

Завршни симболи се обично обележавају малим словима абецеде: a,b,c,d......

Незавршни симболи се обично обележавају великим словима абецеде: A,B,C,D......

Речи једног језика или њихове префиксе, суфиксе и инфиксе се означавају: u,w,v,y,x....

Ниске које се добијају у процесу извођења, а које садрже и незавршне симболе обележавају се са: α,β,γ,δ...

Пример:

Нека је граматика G=(Σ,N,P,E) аритметичких израза, и важи:
Σ={broj} је азбука, broj је завршни симбол
N={E,T,F} је скуп незавршних симбола
E је почетни(стартни) симбол
P је скуп правила:
      T
      F
      broj
тада је израз broj+broj*broj изведен у датој граматици на следећи начин:
E⇒E+T⇒T+T⇒F+T⇒broj+T⇒broj+T*F⇒broj+F*F⇒broj+broj*F⇒broj+broj*broj

За извођење из претходног примера добија се следеће дрво:

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

Литература

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