Мова та метамова, Детальна інформація
Мова та метамова
А тепер почнемо уточнювати, яким саме чином сукупність БНФ задає синтаксис виразів мови.
Приклад 1. Розглянемо мову, виразами в якій є речення, що складаються з підмета й присудка. Підмет, крім того, може мати означення (а може і не мати). Цим означенням може бути одне зі слів – злющий або великий, підметом – комар або слон, присудком – дзижчить або тупотить. Побудуємо сукупність БНФ, що задають синтаксис речень.
Спочатку введемо додаткові позначення. Якщо структура представників якогось поняття задається кількома БНФ, то об'єднаємо їх, записавши альтернативні праві частини в однім правилі й відокремивши символом "|". Цей символ позначає слово "або"; він також є метасимволом.
З цими позначеннями очевидні такі БНФ:
<означення> ::= великий | злющий
<підмет> ::= комар | слон
<присудок> ::= дзижчить | тупотить
Підмет у реченні може бути як із означенням, так і без нього. Введемо поняття <група підмета> і БНФ
<група підмета> ::= <означення> <підмет> | <підмет>
Тоді структура речення задається такою БНФ:
<речення> ::= <група підмета> <присудок>\xF0E7
Серед понять мови виділяється головне; воно позначається спеціальним початковим нетерміналом. Очевидно, що в нашій мові, наприклад, головним поняттям є речення, а в мові Паскаль – програма.
Означимо тепер такі поняття, як послідовність терміналів, вивідна з початкового нетермінала, і формальна мова, задана сукупністю БНФ.
Якщо замінити початковий нетермінал (позначимо його S) на праву частину правила, у якому S ліворуч, то одержимо послідовність символів (терміналів і нетерміналів), що називається вивідною з S. У прикладі 10.1 такою є
<група підмета> <присудок>
Якщо у вивідної з S послідовності замінити якийсь нетермінал на відповідну йому праву частину, то одержимо послідовність, що теж називається вивідною з S, тощо. Наприклад,
<означення> <підмет><присудок>,
<означення> <підмет> тупотить,
злющий <підмет> тупотить,
злющий комар тупотить
(тут кожна послідовність символів утворювалася з попередньої заміною одного з нетерміналів на праву частину правила).
Вивідні з S послідовності, що складаються лише з терміналів, називаються вивідними виразами. Саме вони є представниками головного поняття мови. Наприклад, послідовність злющий комар тупотить є вивідним виразом і представником головного поняття – речення.
Нарешті, формальна мова, задана сукупністю БНФ – це множина вивідних виразів.
У прикладі 1 формальна мова утворена всіма можливими реченнями. Зауважимо, що всього їх 12: 8 із означеннями і 4 без них.
а те, що сам по собі <присудок> із початкового нетермінала не виводиться.
Будемо вважати також, що будь-яка з альтернатив метавиразу виводиться з нього. Наприклад, із метавиразу
<група підмета> ::= <означення> <підмет> | <підмет>
виводяться і <означення> <підмет>, і <підмет>.
Приклад 2. Розглянемо оператори присвоювання змінним, іменами яких можуть бути лише x, y, z, а вирази у правій частині можуть бути або сталими 1 і 2, або іменами x, y, z, або сумою чи різницею цих сталих і змінних. Головним тут, очевидно, є поняття <оператор присвоювання>:
<оператор присвоювання> ::= <ім'я> ':=' <вираз>
Приклад 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
© Referats, Inc · All rights reserved 2021