Малюнок 2.7. Програма як діалектичне заперечення проблеми 9 страница
4.7 Методи подання синтаксису мов програмування
Граматики типу 2 (контекстно-вільні граматики) відіграють велику роль у формалізації мов програмування. Справа в тому, що вони задають чітке подання деякого синтаксичного поняття як структури, що склається з певних частин. Ті частини, у свою чергу, мають частини і так далі. Тобто конктекстно-вільні граматики подають ієрархічну організацію синтаксичного поняття. Це відповідає і композиційній структурі програм. Саме тому вивченню цього класу граматик буде приділено більшу увагу. Щоб продемонструвати зв’язок з мовами програмування більш чітко, розглянемо методи подання синтаксису мов програмування. Найбільш відомим методом є нормальні форми Бекуса–Наура (БНФ). Цей формалізм (метамова) широко використовується як при поданні синтаксису мов програмування, так і при вивченні природних мов.
4.7.1 Нормальні форми Бекуса–Наура
Ці форми були запропоновані Дж. Бекусом та П. Науром для опису синтаксису мови програмування АЛГОЛ-60. Основним призначенням форм Бекуса та Наура було подання у компактному вигляді строго формальних правил написання основних конструкцій мов програмування.
Приблизно в той самий час Ноам Хомський (1959) ввів аналогічну форму – контексно-вільну граматику – для визначення синтаксису природної мови.
БНФ складається зі скінченої множини правил, що в сукупності і визначають формальну мову (зокрема, синтаксис мов програмування).
|
|
|
Одним із класів об’єктів, що використовуються в БНФ, є символи описуваної мови. Другим класом об’єктів БНФ виступають конструкції описуваної мови, значеннями яких є ланцюжки основних символів. Такі конструкції задаються метазмінними, що для кращої мнемоніки записуються як певні ланцюжкі у кутових дужках. Викликано це тим, що для опису синтаксису мов програмування використовують велику кількість нетермінальних символів, тому для наочності їх подають як комбінації слів природної мови, що поміщені в кутові дужки. Ліву частину правил відділяють від правої частини знаком ::=, крім того, правила з однаковою лівою частину записуються як одне правило, при цьому праві частини (альтернативи) розділяються вертикальною рискою |.
Приклад 4.16 Синтаксис операторів мови SIPL задається наступною БНФ:
| <оператор> ::= | <змінна>:=<вираз> | <оператор> ; <оператор>| if <умова> then <оператор> else <оператор> | while <умова> do <оператор> | begin <оператор> end | skip |
За кожною БНФ легко побудувати конктекстно-вільну граматику, співставляючи правилу БНФ виду A::=a 1 | a 2 | … a n сукупність правил граматики A→a 1, A→a 2, … A→a n.
|
|
|
4.7.2 Модифіковані нормальні форми Бекуса–Наура
Для отримання більш наочних та компактних описів синтаксису застосовують модифіковані БНФ. Найчастіше передбачається введення спеціальних позначень для ітерації та альтернативи.
Наприклад, список якихось елементів задається БНФ
<список>::=<елемент><список>| e
В модифікованій БНФ можна записати
<список>::={<елемент>}*
Така форма передбачає введення операції, яка називається ітерацією і позначається парою фігурних дужок із зірочкою.
Якщо певна частина синтаксичної конструкції може бути пропущена, то в модифікованих БНФ її видяляють квадратними дужками. Наприклад, замість правила БНФ
<оператор> ::=
if <умова> then <оператор> else <оператор> | if <умова> then <оператор>
можна вжити наступне правило модифікованої БНФ:
<оператор> ::= if <умова> then <оператор> [ else <оператор>].
Зрозуміло, що для модифікованих БНФ вживати дужки “ { “, “ } ”, “ [ “ та “ ] ”, а також “ * ” у якості символів мови не слід, тому що вони виступають як метасимволи формалізму модифікованих БНФ. При необхідності вживання цих дужок і зірочки для них використовують спеціальні позначення.
4.7.3 Синтаксичні діаграми
Для поліпшення зорового сприйняття і полегшення розуміння синтаксичних описів, застосовують подання синтаксичних правил у вигляді синтаксичних діаграм. Такі діаграми мають одну вхідну і одну вихідну стрілки. Схематично їх можна зображувати таким чином (D – внутрішність діаграми):
|
|
|
Синтаксичні діаграми є структурованими. Це означає, що вони визначаються індуктивно: є найпростіші діаграми, а більш складні будуються за допомогою певних правил.
Найпростішими є наступні діаграми:
· Порожня діаграма
· Термінальна діаграма ( a – термінальний символ)
· Нетермінальна діаграма ( A – нетермінальний символ)
Далі вважаємо, що побудовані наступні діаграми:
Є три правила побудови нових діаграм з наведених діаграм:
· Послідовність
· Альтернатива
· Ітерація
Діаграми можуть мати назву, яка є нетермінальним символом.
Сукупність іменованих діаграм задає певну формальну мову, кожне слово якої складається з термінальних символів, які знаходяться на шляху від початкової стрілки до заключної (від вхідної до вихідної стрілки), причому нетермінальні символи замінуються на термінальні слова, які задаються діаграмою, що називається цим нетермінальним символом.
|
|
|
Приклад 4. 17 Наведемо кілька діаграм, які задають числа:
· Цифра:
|
· Ціле без знака:
|
· Дійсне число (без експоненти):
Щоб скоротити кількість діаграм, їх часто об’єднують, заміняючи нетермінальні символи, які входять у діаграму, на побудовані для них діаграми.
За кожною БНФ можна побудувати систему синтаксичних діагарам. Метод побудови наступний (індукція за структорою БНФ):
· порожньому слову відповідає порожня діаграма,
· термінальному символу відповідає термінальна діаграми з цим символом,
· нетермінальному символу відповідає нетермінальна діаграми з цим символом,
· послідовності символів, що утворюють одну з альтернатив правої частини правила БНФ відповідає послідовність діаграм, що задають символи цієї частини,
· альтернативам правила (тобто виразу ::=a 1 | a 2 | … a n) буде відповідати діаграма – альтернатива для діаграм, побудованих за виразами a 1, a 2, … , a n,
· правилу A::=a 1 | a 2 | … a n буде відповідати деяка діаграми з іменем A, яка визначається для виразу a 1 | a 2 | … a n.
Неважко побудувати і зворотній алгоритм, який за системою синтаксичних діаграм вказаного вигляду будує еквіваленту їй БНФ.
Таким чином, справедливее наступне твердження.
Твердження 4.1. Наступніформалізми подання формальних мов: БНФ, модифіковані БНФ, контекстно-вільні грамматики, синтаксичні діаграми, є еквівалентними формалізмами.
Зауважимо, що наведене твердження не сформульовано як теорема лише тому, що не було дано достатньо точного визначення формальних мов, що породжуються такими формалізмами, як БНФ, модифіковані БНФ та синтаксичні діаграми. Разом з тим, надати такі формальні визначення не дуже складно (зробіть це самостійно).
Зважаючи на наведене твердження, будемо в подальшому серед указаних формалізмів розглядати переважно формалізм контекстно-вільних граматик.
4.8 Властивості контекстно-вільних граматик
В цьому підрозділі розглянемо властивості контекстно-вільних граматик (КВ-граматик), зокрема їх еквівалентні перетворення та нормальні форми. Спочатку доведемо лему про еквівалентність граматик щодо бієктивного перейменування нетерміналів.
Лема 4.2 (про перейменування нетерміналів). Нехай задані граматика G=(N, T, P, S), та бієктивне відображення r: N® N¢ множини нетерміналів N на деяку іншу множину нетерміналів N ¢ (N ¢Ç T=Æ). Тоді для граматики G ¢=(N ¢, T, S ¢, P ¢), де P ¢ – множина правил, отриманих з P заміною нетерміналів N на відповідні нетермінали з N ¢, а S ¢=r(S), маємо: L(G)= L(G ¢).
Для доведення леми слід скористатись тією обставиною, що кожний вивід в одній граматиці має відповідний вивід (шляхом перейменування нетерміналів) в іншій граматиці.
Зрозуміло, що умова бієктивності є суттєвою.
4.8.1 Видалення несуттєвих символів
Продовжимо розгляд очевидних, але важливих перетворень. В деяких випадках КВ-граматика може містити символи та правила, що не вживаються для виводу термінальних ланцюжків.
Приклад 4.18 В граматиці G=({S, A, B}, {a, b, c}, P, S), де P={S→a, S→cS, A→b}, нетермінал A і термінал b не можуть з’явитися в жодному ланцюжку виведення (в жодній словоформі). Таким чином, ці символи не приймають участь у породженні ланцюжків мови L(G) і правила, що їх містять, можна видалити, не змінивши мови L(G).
Визначення 4.31 Нетермінал AÎNÈТ назвемо недосяжним в граматиці G=(N, Т, P, S), якщо A не з’являється в жодному вивідному ланцюжку, тобто не існує виводу виду SÞ G* gAd, g, dÎ(NÈT)*.
Для знаходження недосяжних нетерміналів спочатку визначимо множину досяжних нетерміналів. Ця множина для заданої КВ-граматики G=(N, T, P, S) легко визначається за допомогою наступних індуктивних визначень.
1. R0={S}.
2. R i={B çє правило A→aBβÎР, що AÎR i-1, BÎN} È R i-1 (i=1,2, …).
Оскільки множина N є скінченною, а формула для визначення Ri задає монотонне за і відображення, то існує k (k³0), що Rk=Rk+1. Іншими словами, послідовність R0, R1, R2, … стабілізується на k-му кроці. Покладемо R=Rk.
Множина UR недосяжних нетерміналів задається формулою UR= N\R.
За граматикою G=(N, T, P, S) будуємо граматику G¢=(N¢, T¢, P¢, S¢) таким чином:
1. N¢= NÇR
2. T¢= T
3. S¢=S
4. P¢= { A→aÎР | aÎ R*}
Очевидною є наступна лема.
Лема 4.3 Для граматики G'=(N', T', P', S') виконуються наступні властивості:
1. L(G')=L(G) (еквівалентність).
2. Для всіх AÎN' існують такі ланцюжки a та β із (N'ÈT)*, що SÞ *G'aAβ (всі нетермінали є досяжними).
Визначення 4.32 Нетермінал AÎN назвемо непродуктивним в граматиці G=(N, Т, P, S), якщо з A не можна вивести жодного термінального ланцюжка, тобто не існує виводу виду AÞ*Gt, tÎT*.
Спочатку визначимо множину продуктивних нетерміналів. Множина продуктивних нетерміналів для заданої КВ-граматики G=(N, T, P, S) легко визначається за допомогою наступних індуктивних визначень.
1. Pr0={ A çє правило A→tÎР, що tÎT*}.
2. Pri={ A çє правило A→gÎР, що gÎ(R i-1ÈТ)*} È R i-1 (i=1,2, …).
Оскільки множина N є скінченною, а формула для визначення Pri задає монотонне за і відображення, то існує k (k³0), що Prk=Prk+1. Іншими словами, послідовність Pr0, Pr1, Pr2, … стабілізується на k-му кроці. Покладемо Pr=Prk.
Множина UPr непродуктивних нетерміналів задається формулою UPr= N\Pr.
За граматикою G=(N, T, P, S) будуємо граматику G¢=(N¢, T¢, P¢, S¢) таким чином:
1. N¢= (NÇPr)È{S}
2. T¢= T
3. S¢=S
4. P¢= { A→aÎР | aÎ Pr*}
Очевидною є наступна лема.
Лема 4.4 Для граматики G'=(N', T', P', S') виконуються наступні властивості:
1. L(G')=L(G) (еквівалентність).
2. Для всіх AÎN'\{S} існують термінальні ланцюжки, що виводяться з A.
Відзначимо, що аксіома S є спеціальним випадком, тому що вона може бути непродуктивною, і разом з тим вона має належати множині нетермінальних символів (за визначенням породжуючих граматик), але в такому випадку множина правил буде порожньою.
До речі, наведений метод побудови множини продуктивних нетерміналів дозволяє дати відповідь на питання, чи є порожньою мова, що породжується граматикою G=(N, T, P, S)?
Відповідь проста: якщо аксіома є продуктивним нетерміналом, то мова непорожня, якщо ж аксіома – непродуктивний нетермінал, то мова – порожня.
Визначення 4.33 Символ ХÎNÈТ назвемо несуттєвим в КВ-граматиці G=(N, Т, P, S), якщо в ній немає виводу виду SÞ*wXyÞ*wxy, де w, x, y належать Т*.
З наведеного визначення бачимо, що нетермінал Х – несуттєвий, якщо Х є недосяжним або непродуктивним нетерміналом (крім, можливо, аксіоми). Термінальний символ Х є несуттєвим, коли немає жодного породжуваного ланцюжка, що містить Х.
Визначення 4.34 Граматика G=(N, T, P, S) називається зведеною, якщо в ній немає несуттєвих символів (можливо, крім аксіоми S).
Для побудови зведеної граматики спочатку видаляємо недосяжні та непродуктивні нетермінали. Потім з множини термінальних символів видаляємо несуттєві символи. Такі термінальні символи не містяться в правих частинах отриманих правил. Отримана граматика буде зведеною.
Лема 4.5 За кожною КВ-граматикою можна побудувати еквівалентну їй зведену граматики, що не містить несуттєвих символів.
Приклад 4.19 Розглянемо граматику G=({S, A, B, C}, {a, b, c}, P, S), де Р складається з правил
S→a
S→ A
A→AB
B→b
C→c
Спочатку видаляємо недосяжні нетермінали. Отримаємо R={S, A, B}. Недосяжним є C. З граматики треба видалити вказаний символ та останнє правило. Далі визначаємо множину продуктивних нетерміналів. Знаходимо, що Pr={S, B}. Непродуктивним є A. Після видалення відповідних правил нетермінал B стає недосяжним. Видяляємо і його. Залишається одне правило S→a. Тому суттєвим термінальним символом є лише a. Видаляємо несуттєві термінальні символи. Отримуємо наступну зведену граматику: G'=({S}, {a}, { S→a}, S).
4.8.2 Видалення e-правил
Визначення 4.35 Назвемо КВ-граматику G=(N, T, P, S) граматикою без e -правил (або нескорочуваною), якщо Р не містить e-правил, тобто правил виду A →e.
Лема 4.6 За кожною КВ-граматикою можна побудувати еквівалентну їй (з точністю до порожнього ланцюжка – e-еквівалентну) граматику без e-правил.
Доведення. Нехай дана КВ-граматика G=(N, T, P, S), що породжує мову L(G). Проведемо серію перетворень множини P. Якщо множина P містить правила B→aAβ і A→e для деяких A, BÎN, a, βÎ(NÈT)*, то додамо правило B→aβ в P. Повторюємо цю процедуру поки множина правил не стабілізується. Далі виключимо із множини P всі правила вигляду A→e.
Дата добавления: 2019-02-13; просмотров: 290; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!