Gramatyki Formalne cz I 2

Przykład — budoyya gramatyki z 3 zmiennych i 2 działań (mnożenia i dodawania). Można rozwinąć na więcej zmiennych i działań. Elementy gramatyki, której aksjomatem jest wyrażenie (symbol nieterminalny): wyrażenie = wyrażenie "+!' składnik

wyrażenie = składnik    \

składnik = składnik -^5«    ^Symb°'^{e termina}'^ne

symbole terminalne

składnik = czynnik czynnik = "("wyrażenie")"

czynnik = "x" •• ...

czynnik = "x"    '^> symbole terminalne

czynnik = "y" czynnik = "z"

Powyższa gramatyka została zapisana wtzw. notacji BNF (Bachus — Naur Formatism — nazwiska inyyestorów) sformułowanej przez F. Backusa i P. Naura przy definiowaniu języka Algol. Obecnie stosuje się EBNF — poszerzony formalizm Bachusa — Haura.

wyrażenie = wyrażenie + składnik = wyrażenie + składnik * czynnik = wyrażenie + składnik * (wyrażenie! = wyrażenie + składnik * (wyrażenie + składnik) = podst. za wyrażenie dwukrotnie składnik i czterokrotnie za składnik czynnik = x + y * (2 + x)

Każde poprawnie algebraicznie wyrażenie zawierające wymienione wyżej symbole terminalne będzie akceptowane przez naszą gramatykę. Nie będą akceptowane wyrażenia niepoprawne algebraicznie: x + * y

)2 + y(

xy +2 2 + itp.

Metody zapisu gramatyk formalnych są doskonalone. Na przykład wprowadza się symbol Ś dla rozdzielenia występujących w tej samej linii zapisów różnych następników tego samego symbolu nieterminalnego: czynnik = "("wyrażenie")" .

czynnik = "X" ———czynnik = "("wyrażenie")" | X | Y | Z czynnik = "Y" czynnik = "Z"

Wprowadza sie też nawiasy "{""}" dla wielokrotnie powtarzanego fragmentu definicji rekurencyjnych:

wyrażenie = wyrażenie "+" składnik wyrażenie = składnik

wyrażenie = składnik {"+" składnik}

składnik = składni.....czynnik

składnik = czynnik ------

składnik = czynnik {czynnik}