Представлення оператора Паскаля While за допомогою КС-граматики

Специфіка формально лінгвістичного підходу до опису безлічі ланцюжків починає проявлятися при розгляді вужчих класів граматик. Загальноприйнятою класифікацією граматик і породжуваних ними мов є ієрархія Хомского, що містить чотири типи граматик. Однією з них є КС - граматика.

КС - мови є найбільш вивченими класом. Це пояснюється тим, що з одного боку КС-граматики виявилися дуже відповідним апаратом для опису будови природних мов і особливо мов програмування. З іншого боку, завдяки відносній простоті і змістовності структури КС-мов і наявності зручних засобів її опису дослідження їх представляє значний практичний інтерес.

Поява поняття КС-граматики практично співпала з розробкою мета мови Бекуса (чи нормальної форми Бекуса), яка була уперше використана при описі мови програмування АДГОЛ, - 60 і швидко став загальноприйнятим засобом формального опису мов програмування. Описом мови за допомогою нормальних форм Бекуса є сукупність так званих "металінгвістичних формул" - виразів виду Х::=Y1|Y2|.. |Yn, де Х - деякий текст ув'язнений в кутові дужки і званий металінгвістичною змінною, а Y1, .., Yn - послідовність металінгвістичних змінних і основних символів мови (букв, цифр, роздільників, неділимих слів типу "begin" і тому подібне). Знак ::= називається металінгвістичною зв'язкою і читається як "є" або "це". Знак |- це металінгвістична зв'язка "або". Металінгвістична змінна є ім'ям конструкції мови.

Металінгвістична формула в цілому - це опис різних синтаксичних варіантів побудови конструкцій Х, що стоїть в лівій частині, через інші конструкції і символи мови, вказані в правій частині. Перерахування варіантів представлення виробляється з використанням зв'язки "або".

 

Розглянемо як приклад для КС-граматики оператор Паскаля While.

 

У – умова

ЗМ – змінна

Д - дія

СС – службовий знак

Б – буква

Ц – цифра

БЦ – БЦ - ланцюг

Ч – число

ОП – оператор

КС – ключове слово

 

<КС1><УМ><КС2><Д>

 

<КС1> While

< КС2> Do

<У> <ЗМ> <СС> <ЗМ>

<У> <_ЗМ> <СС> <Ч>

<ЗМ> <Б>

<ЗМ> <Б> <БЦ>

<Б> <А>

<Б> <а>

<Б> <B>

.

.

.

<Б> <Z>

<Б> <z>

<БЦ> <Б> <БЦ>

<БЦ> <Ц> <БЦ>

<Ц> <1>

<Ц> <2>

<Ц> <3>

<Ц> <4>

<Ц> <5>

<Ц> <6>

<Ц> <7>

<Ц> <8>

<Ц> <9>

<Ц> <0>

<СС> << >

<СС> < >>

<СС> < = >

<СС> <<= >

<СС> <>= >

<Ч> <Ц>

<Ч> <Ц> <Ч>

<Д> <begin> <ОП> <end>

<ОП> <ЗМ><ЗМ>

<ОП> <ЗМ><Ч>