ПАСКАЛЬ: МОВА ТА МЕТАМОВА

<підмет> ::= комар | слон

<присудок> ::= дзижчить | тупотить

Підмет у реченні може бути як із означенням, так і без нього. Введемо поняття <група підмета> і БНФ

<група підмета> ::= <означення> <підмет> | <підмет>

Тоді структура речення задається такою БНФ:

<речення> ::= <група підмета> <присудок>

Серед понять мови виділяється головне; воно позначається спеціальним початковим нетерміналом. Очевидно, що в нашій мові, наприклад, головним поняттям є речення, а в мові Паскаль – програма.

Означимо тепер такі поняття, як послідовність терміналів, вивідна з початкового нетермінала, і формальна мова, задана сукупністю БНФ.

Якщо замінити початковий нетермінал (позначимо його S) на праву частину правила, у якому S ліворуч, то одержимо послідовність символів (терміналів і нетерміналів), що називається вивідною з S. У прикладі 10.1 такою є

<група підмета> <присудок>

Якщо у вивідної з S послідовності замінити якийсь нетермінал на відповідну йому праву частину, то одержимо послідовність, що теж називається вивідною з S, тощо. Наприклад,

<означення> <підмет><присудок>,

<означення> <підмет> тупотить,

злющий <підмет> тупотить,

злющий комар тупотить

(тут кожна послідовність символів утворювалася з попередньої заміною одного з нетерміналів на праву частину правила).

Вивідні з S послідовності, що складаються лише з терміналів, називаються вивідними виразами. Саме вони є представниками головного поняття мови. Наприклад, послідовність злющий комар тупотить є вивідним виразом і представником головного поняття – речення.

Нарешті, формальна мова, задана сукупністю БНФ – це множина вивідних виразів.

У прикладі 10.1 формальна мова утворена всіма можливими реченнями. Зауважимо, що всього їх 12: 8 із означеннями і 4 без них.

Крім поняття виводимості з початкового нетермінала, використовується також поняття виводимості з довільної послідовності терміналів і нетерміналів незалежно від того, чи виводиться сама ця послідовність із S, чи ні. Так, із <присудок> у прикладі 10.1 виводяться дзижчить і тупотить, незважаючи на те, що сам по собі <присудок> із початкового нетермінала не виводиться.

Будемо вважати також, що будь-яка з альтернатив метавиразу виводиться з нього. Наприклад, із метавиразу

<група підмета> ::= <означення> <підмет> | <підмет>