Формальний опис вхідної мови програмування
Одною з перших задач, що виникають при побудові компілятора, є визначення вхідної мови програмування. Для цього використовують різні способи формального опису, серед яких ми розглянемо розширену нотацію Бекуса-Наура (Backus/Naur Form - BNF).
Деталізований опис вхідної мови
два типи даних: цілий (int) та логічний (boolean);
змінні довільної довжини;
символи групування арифметичних операцій: “(”, “)”;
логічні операції над цілими і логічними: (,&),(~),>=;
оператор присвоєння: “:=” ;
оператори блоку: “{”, “}”;
оператори виводу (in) і виводу (out);
оператор циклу ( repeat-until ).
1.2. Перелік термінальних символів та ключових слів
Визначимо окремі термінальні символи та нерозривні набори термінальних символів (ключові слова):
pochatok
kinez.
;
,
=
:=
#
&
~
>=
(
)
boolean
true
false
int
k1
k2
k3
repeat
until
in
out

До термінальних символів віднесемо також усі цифри (0-9), латинські букви (a-z, A-Z) та символ пробілу (“ ”).
Всього: 23 + 10 + 52 + 1 = 86 термінальних виразів. Це “цеглинки”, з яких має будуватися текст будь-якої вхідної програми.
Формальний опис вхідної мови в термінах BNF
Правила написання правил у розширеній нотації Бекуса-Наура:
нетермінальні вирази записуються у кутових дужках: “<”, “>” ;
термінальні вирази записуються жирним шрифтом або у подвійних лапках;
усі нетермінальні вирази мають бути “розкриті” за допомогою термінальних;
сивол “::=” відділяє праву частину правила від лівої;
символ “|” розділяє альтернативи;
сиволи “[”, “]” означають необов’язковість (вираз в дужках може бути відсутнім);
сиволи “{”, “}” означають повторення.

Формальний опис заданої вхідної мови в термінах BNF:
<program>
::= pochatok <block> kinez.

<block>
::= { < statement > | [{<statement >}] }

<statement>
::= <declaration> | <operator>




<declaration>
::= <type> <ident>{,[<ident>]}; | <const_ident> = <int_const> | <bool_const>;

<operator>
::= <bind> | <in> | <out> | <repeat-until>




<type>
::= int | boolean

<ident>
::= <letter> {[<letter>] | [number]}

<const_ident>
::= k1 | k2 | k3

<int_const>
::= [“-“] < number > [{<number >}]

<bool_const>
::= true | false

<bind>
::= <ident> := <expression> | <invert>;

<in>
::= in <ident>;

<out>
::= out <ident>;

<repeat-until>
::= repeat <block> until <expression>;




<letter>
::=a|b|c|d|e|f|g|h|i|j|k|l|n|m|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|N|M|O|P|Q|R|S|T|U|V|W|X|Y|Z

<number>
::= 0|1|2|3|4|5|6|7|8|9

<expression>
::= <operand> [{<operation> <operand>}]

<invert>
::= ~ <ident>

<operand>
::= ( <expression> ) | <ident> | <int_const> | <bool_const>

<operation>
::= # | & | >=

Формальний опис складено за допомогою 20-ти нетермінальних виразів.
2. Формальний опис вхідної мови програмування
<program>
::= <statment>

<statement>
::= “{“{[<declaration>] }|{[ <operator>]}”}”

<declaration>
::= <type> <ident>{“,”[<ident>]};

<operator>
::= <bind> | <if-else> | <do-while>|<print>

<block>
::=”{“{[{[<operator>]}|{[<bind>]}]}”}”|<operator>”;”|<bind>”;”

<bind>
::= <ident> = <expression>;

<if-else>
::= if “(“<bool_expression>”)” <block> [else <block>].

<while>
::= do<block>while”(“ <bool_expression>”)”;

<type>
::= boolean | int|word

<ident>
::= <letter> [{<letter>}]|[{number}]

<int_const>
::= [“-“]< number > [{<number >}]

<bool_const>
::= true | false

<letter>
a|b|c|d|e|f|g|h|i|j|k|l|n|m|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|N|M|O|P|Q|R|S|T|U|V|W|X|Y|Z

<number>
::= 0|1|2|3|4|5|6|7|8|9

<expression>
::= <num_expression> | <bool_expression>

<num_expression>
::= <num_operand> [{<num_operation> <num_operand>}]

<bool_expression>
::= ( <num_operand> <bool_operation> <num_operand> ) | <ident> | <bool_const>

<num_operand>
::= ( <num_expression> ) | <ident> | <int_const>.

<num_operation>
::= *| / | + | - |^

<bool_operation>
::= < | >| == |!=|!