Мова та метамова

<оператор присвоювання> ::= <ім'я> ':=' <вираз>

Вираз складається зі сталих і імен. Узагальнимо їх поняттям <первинне>, і запишемо БНФ виразів і первинних:

<вираз> ::= <первинне> | <первинне> '+' <первинне> |

<первинне> '-' <первинне>

<первинне> ::= <стала> | <ім'я>

БНФ сталих і імен очевидні:

<стала> ::= '1' | '2'

<ім'я> ::= 'x' | 'y' | 'z'

Записана сукупність БНФ задає синтаксис операторів присвоювання, а також виразів, сталих і імен. Крім того, задано множини конкретних імен, сталих, виразів і операторів присвоювання.Підіб'ємо підсумок. БНФ – це вираз у алфавіті, що складається з терміналів, нетерміналів і спеціальних метасимволів. БНФ мають цілком визначений синтаксис (нетермінал, потім знак '::=' і метавираз). Їхньою семантикою є задання структури і множин представників понять, позначених нетерміналами. Таким чином, ми маємо мову БНФ. Вона призначена для описання інших мов і називається метамовою.

Існують різні метамови; деякі з них задаються строго й точно засобами логіки і математики і тому називаються формальними. Мова БНФ, описана тут неформально, насправді є окремим випадком формальної метамови – мови формальних граматик.

Мова БНФ була створена спеціально для описання синтаксису виразів мов програмування. З цією метою її використовуємо й ми.

3. Розширені БНФ

Доповнимо мову БНФ кількома зручними конструкціями. Тут нам знадобиться ще одне поняття – еквівалентність БНФ. Дві сукупності БНФ називаються еквівалентними, якщо задають ту саму формальну мову.

Для запису еквівалентних БНФ у більш короткому і наочному вигляді алфавіт метасимволів розширюється символами "(", ")", "[", "]", "{", "}". Метавирази з такими символами називаються розширеними, а БНФ – розширеними БНФ, або скорочено РБНФ. Розглянемо побудову РБНФ.

Нехай букви X, Y, Z, … , T позначають довільні метавирази (можливо, порожні), N – нетермінал.

Заміною кількох правил вигляду

N ::= X Z Y

…

N ::= X T Y

у деякій сукупності БНФ на правило вигляду

N ::= X ( Z | … | T ) Y

утворюється сукупність БНФ, еквівалентна початковій. Метасимволи "(" та ")" тут просто відокремлюють частину метавиразу з альтернативами Z, … , T від інших частин. Наприклад, правила