Паскаль: мова та метамова, Детальна інформація

на правило N ::= X [ Z ] Y також утворюється еквівалентна БНФ. Наприклад, замість правил

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

можна вжити правило

<вираз> ::= <первинне> [ ('+'| '-') <первинне> ]

або замість правил

<оператори-розгалуження> ::=

if <умова> then <оператор> else <оператор> |

if <умова> then <оператор>

– правило

<оператори-розгалуження> ::=

if <умова> then <оператор> [ else <оператор> ]

Іноді буває зручно позбутися якогось поняття, замінивши його нетермінал відповідним метавиразом, наприклад, замість нетермінала <первинне> з прикладу 10.2 записати метавиразом <стала> | <ім'я> або навіть '1' | '2' | 'x' | 'y' | 'z'. Таким чином, сукупність БНФ із прикладу 10.2 еквівалентна сукупності

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

<ім'я> ':=' ('1' | '2' | <ім'я>) [ ('+'| '-') ('1' | '2' | <ім'я>) ]

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

Зміст метасимволів "{", "}" означимо за допомогою такого прикладу.

Приклад 3. Ім'я, або ідентифікатор, у мовах програмування – це послідовність букв і цифр, що починається з букви. Нехай буквами є лише A, B, C, цифрами – 0 і 1. Ідентифікаторами в цьому алфавіті є, наприклад, A, B1, BC, C1CAAB0 тощо. Означимо сукупність БНФ, що задає їх синтаксис.

Розглядаючи поняття "ідентифікатор", можна ввести поняття "послідовність букв і цифр, можливо, порожня". Позначимо ці два поняття відповідно нетерміналами <Ід> і <ПБЦ>. Введемо також поняття "буква" й "цифра" (нетермінали <Б> і <Ц>). Послідовність букв і цифр або порожня, або починається буквою або цифрою, за якою записано послідовність букв і цифр. Іншими словами,

<Ід> ::= <Б><ПБЦ>

<Б> ::= 'A' | 'B' | 'C'

<Ц> ::= '0' | '1'

<ПБЦ> ::= <> | (<Б> | <Ц>) <ПБЦ>.

Узагальнимо букви й цифри поняттям "символ", додавши правило <символ> ::= <Б> | <Ц>. Тоді <ПБЦ> можна задати двома правилами:

<ПБЦ> ::= <> | <символ> <ПБЦ>.

За допомогою цих правил із нетермінала <ПБЦ> виводяться всі можливі послідовності символів:

<>, <символ>, <символ><символ>, … ,

і тільки вони. Позначимо множину послідовностей, складених із <символ>, метавиразом {<символ>} із новими метасимволами "{", "}". Вважатимемо, що всі послідовності символів вивідні з цього метавиразу. Отже, правило

<ПБЦ> ::= {<символ>}

за нашим означенням є еквівалентним правилам

<ПБЦ> ::= <> | <символ> <ПБЦ>.