Мова та метамова, Детальна інформація

Мова та метамова
Тип документу: Реферат
Сторінок: 6
Предмет: Комп`ютерні науки
Автор: Олексій
Розмір: 13.9
Скачувань: 981
А тепер почнемо уточнювати, яким саме чином сукупність БНФ задає синтаксис виразів мови.

Приклад 1. Розглянемо мову, виразами в якій є речення, що складаються з підмета й присудка. Підмет, крім того, може мати означення (а може і не мати). Цим означенням може бути одне зі слів – злющий або великий, підметом – комар або слон, присудком – дзижчить або тупотить. Побудуємо сукупність БНФ, що задають синтаксис речень.

Спочатку введемо додаткові позначення. Якщо структура представників якогось поняття задається кількома БНФ, то об'єднаємо їх, записавши альтернативні праві частини в однім правилі й відокремивши символом "|". Цей символ позначає слово "або"; він також є метасимволом.

З цими позначеннями очевидні такі БНФ:

<означення> ::= великий | злющий

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

а те, що сам по собі <присудок> із початкового нетермінала не виводиться.

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

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

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

Приклад 2. Розглянемо оператори присвоювання змінним, іменами яких можуть бути лише x, y, z, а вирази у правій частині можуть бути або сталими 1 і 2, або іменами x, y, z, або сумою чи різницею цих сталих і змінних. Головним тут, очевидно, є поняття <оператор присвоювання>:

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

The online video editor trusted by teams to make professional video in minutes