4.2. Контекстно-вільні граматики

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

Якщо S₁ й S₂ є інструкціями, а Е — виразом, то

if E then S₁ else S₂ (4.1)

є інструкцією.

Цей тип умовних інструкцій не може бути визначений з використанням регулярних виразів. У главі 2 "Лексичний аналіз", ми бачили, що регулярні вирази можуть визначати лексичну структуру токенів. Однак, використовуючи для позначення класу інструкцій синтаксичну змінну stmt, а для класу виразів — ехрr, можемо легко представити інструкцію (4.1) за допомогою продукції граматики

stmt := if expr then stmt else stmt (4.2)

У цьому розділі розглянемо визначення контекстно-вільної граматики й познайомимося з термінологією, використовуваної при описі процесу синтаксичного розбору. З п. 4.1 ми знаємо, що контекстно-вільна граматика (або, для стислості, просто граматика) складається з терміналів, нетерміналів, стартового символу й продукцій.

1. Термінали являють собою базові символи, з яких формуються рядки. Слово "токен" є синонімом слова "термінал", коли ми говоримо про грам­атики мов програмування. В (4.2) кожне із ключових слів if, then, else є терміналом.

2. Нетермінали являють собою синтаксичні змінні, які визначають множини рядків. В (4.2) stmt й expr є нетерміналами. Нетермінали визначають множини рядків, які допомагають у визначенні мови, породжуваною граматикою. Крім того, вони накладають на мову ієрархічну структуру, що полегшує синтаксичний аналіз і трансляцію.

3. Один з нетерміналів граматики вважається стартовим символом, і множина рядків, які він визначає, є мовою, обумовленою граматикою.

4. Продукції граматики визначають спосіб, яким термінали й нетермінали можуть поєднуватися для створення рядків. Кожна продукція складається з нетермінала, за яким слідує три символи ::=, і рядок нетерміналів та/або терміналів.

Приклад 4.3. Граматика з наступними продукціями визначає прості арифметичні вирази:

expr ::= expr op expr

expr ::= (expr)

expr ::= - expr

expr ::= id

op ::= +

op ::= -

op ::= *

op ::= /

У цій граматиці термінальними символами є: id, ‘+’, ‘-‘, ‘*’, ‘/’, ‘(‘, ‘)’, а нетермінальними символами граматики: expr й op. Стартовим символами граматики є expr.

Угоди по позначеннях

Для того щоб уникнути постійного згадування "це — термінал", "це — нетермінал" і т.п., в подальшому будемо використати наступні угоди щодо позначень.

1. Терміналами є символи:

• малі літери з початку алфавіту, такі як а, b, c;

• символи операторів, такі як +,- і т.п.;

• символи пунктуації, такі як коми, дужки й т.п.;

• цифри 0, 1, ...., 9;

• рядки, виділені жирним шрифтом, такі як id або if.

2. Ці символи є нетерміналами:

• прописні букви з початку алфавіту, такі як А, В, C;

• буква S, що звичайно означає стартовий символ;

• імена з малих літер, виділені курсивом, такі як stmt або expr.

3. Прописні букви з кінця алфавіту, такі як X, Y, Z, представляють граматичні символи, тобто або термінали, або нетермінали.

4. Малі літери з кінця алфавіту, такі як u, v, ..., z, позначають рядки термі­налів.

5. Малі грецькі букви, такі як α, β, γ представляють рядки граматичних символів. Таким чином, у загальному виді продукція може бути записана як А ::= α, у якій одиночний нетермінал А розташовується ліворуч від сполучення символів ‘::=’ (у лівій частині продукції), а рядок граматичних символів α у правій частині продукції.

6. Якщо А ::= α₁, A ::= α₂, ..., A ::= α_k являють собою продукції з А в лівій частини (ми називаємо їх А-продукціями), то можемо записати

А ::= α₁|α₂|...|α_k. Ми називаємо α₁, α₂, ..., α_k альтернативами А.

7. Якщо інше не зазначено явно, ліва частина першої продукції є стартовим символом.

Приклад 4.4. Використовуючи наведені угоди, можна записати граматику із приклада 4.2 як

Е ::= ЕАЕ|(Е)|-Е|id

А ::= + | - | * | /

З наших угод слідує, що Е и А — нетермінали, причому Е є старто­вим символом. Інші символи являють собою термінали.

Породження

Існує кілька способів розглядати процес визначення мови граматикою. Раніше ми бачили його як процес побудови дерев розбору. Однак є й інший корисний спосіб, що дає точний опис спадної побудови дерева розбору. Основна ідея полягає в тому, що продукція розглядається як правило, що переписує нетермінал з лівої частини і заміщує його рядком із правої частини продукції.

Розглянемо, наприклад, наступну граматику арифметичних виразів із нетерміналом Е, що представляє вираз.

Е ::= Е + Е | Е* Е | (Е) | -Е | id (4.3)

Продукція Е ::= -Е означає, що вираз, якому передує знак мінуса, також є виразом. Ця продукція може використатися для породження (derivation) більш складних виразів із простих, дозволяючи нам заміняти будь-який екземпляр Е на -Е. У найпростішому випадку ми можемо замістити одне Е на -Е и описати це як Е → -Е, що можна прочитати як "Е породжує -Е", або "з Е виводиться -Е", Продукція Е ::= (Е) говорить, що ми можемо також замінити один екземпляр Е в будь-якому рядку граматики на (Е), наприклад Е*Е → (Е)*Е або Е*Е → Е *( Е).

Ми можемо взяти нетермінал Е и неодноразово застосовувати продукції в довільному порядку для одержання послідовності заміщень, наприклад, Е→ -Е → -(Е) → -(id). Таку послідовність замін назвемо висновком (derivation), або породженням -(id) з Е. Такий висновок є доказом того, що одним із прикладів виразу Е є рядок -(id).

Більш абстрактно, ми говоримо, що αAβ → αγβ, якщо А ::= γ є продукцією, а α і β являють собою довільні рядки граматичних символів. Якщо α₁ → α₂ → ... → α_n, говоримо, що α₁ породжує α_n. Символ → означає "породжує за один крок". Часто ми говоримо "породжує за нуль або більше кроків" і позначаємо це символом →^* . Таким чином,

1. α →^* α для будь-якого рядка α,

2. якщо α →^* β и β→^* γ , то α →^* γ .

Аналогічно символ →⁺ використається для позначення "породжує за один або більше кроків".

Маючи граматику G зі стартовим символом S, можна використати відношення →^* для визначення L(G), мови, породженою граматикою G. Рядки в L(G) можуть містити тільки термінальні символи з G, тобто рядок терміналів w належить L(G) тоді й тільки тоді, коли S →⁺ w. Рядок w при цьому називається реченням G, а мова, що може бути породжена граматикою, — контекстно-вільною. Якщо дві граматики породжують одну й туж саму мову, то ці граматики називаються еквівалентними.

Якщо S →⁺ α , де α може містити нетермінали, то ми говоримо про те, що α є сентенціальною формою G. Речення являє собою сентенціальну форму без нетерміналів.

Приклад 4.5

Рядок -(id+id) є реченням граматики (4.3) через наявність породження E→ -E → -(E) → -( E + E) → -(id + E) → -(id + id) (4.4)

Рядки E, -Е, -(E),.., -(id+id), що з'являються в процесі породження, являють собою сентенціальні форми даної граматики. Для підкреслення того, що -(id + id) може бути виведене з Е, ми записуємо E →^* -( id + id).

За допомогою індукції по довжині породження можна показати, що кожне речення в мові граматики (4.3) являє собою арифметичний вираз, що включає бінарні оператори * й +, унарний оператор -, дужки й операнд id.

Примітка. Слід розрізняти знаки арифметичних операторів множення ‘*’ й додавання ‘+’ від використання цих же символів як “верхніх індексів’ ‘^*’ ‘⁺’ при символі ‘→’, тлумачення яких було наведено вище.

Аналогічно за допомогою індукції по довжині арифметичного виразу можна показати, що всі такі вирази можуть бути породжені даною граматикою. Отже, граматика (4.3) генерує в точності множину всіх арифметичних ви­разів, які включають бінарні оператори * й +, унарний оператор -, дужки й операнд id.

На кожному кроці породження здійснюється два вибори - ми повинні вибрати замінний нетермінал, а потім його альтернативу. Наприклад, породження (4.4) із приклада 4.5 може продовжитися після -(E + E) у такий спосіб:

-(E + E) → -(E +id) → -(id+id) (4.5)

Кожен нетермінал в (4.5) заміщується тією же правою частиною, що й в (4.4), але в іншому порядку.

Щоб зрозуміти, як працюють деякі синтаксичні аналізатори, необхідно розглянути породження, у кожній сентенціальній формі яких заміщується самий лівий нетермінал (такі породження називаються лівими – leftmost). Якщо α → β представляє собою породження, у якому замішається крайній лівий нетермінал в α; ми записуємо α _lm→ β. Оскільки породження (4.4) є лівим, можемо записати його як

Е _lm→ -Е _lm→ -(Е) _lm→ -( Е + Е) _lm→ -(id + Е) _lm→ -(id + id)

Використовуючи уведені нами позначення, кожен крок лівого породження можна записати як wAγ _lm→ wδγ, де w складається тільки з терміналів, А ::= δ являє собою використану в кроці продукцію, а γ — рядок синтаксичних символів граматики. Для підкреслення того факту, що α породжує β лівим породженням, ми записуємо α _lm→^* β. Якщо S _lm→^* α, то говоримо, що α. є лівосентенціальною формою розглянутої граматики.

Аналогічні визначення існують для правих (rightmost) породжень, у яких на кожному кроці заміщається крайній справа нетермінал. Іноді праві приведення називаються канонічними.