Тема 4.1. Формальні граматики і мови

[1, гл.2, розд.2; 3, гл.4, § 1; гл.16, § 1, 2, 4; 1. гл.2, розд.4, 6; 4. гл.16. § 3, 27; 4, гл.16, § 3, 5]

Вказівки щодо використання літературних джерел.

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

Відомо, що вид ланцюжків у правилах граматики істотно впли­ває на потужність і структуру ланцюжків мов, що породжуються. Хомський запропонував класифікацію граматик за цією ознакою. Треба вивчити класифікацію Хомського, розглянути достатню кількість мов та відповідних граматик. Дослідження граматик варто розпочинати з уже відомих граматик типу 3 за цією класифікацією або автоматних граматик і їхнього зв’я­зку з регулярними множинами й виразами.

Засоби побудови регулярних множин настільки гнучкі, що, здаєть­ся, не існують множини, які не є регулярними. Щоб переконатися, що це не так, розгляньте множину

{01, 0011, 000111, ... }.

Ця множина не є регулярною, що й обгрунтовано у вказівках до теми 4.1.

Продовжуючи вивчати граматику й мови, слід ускладнювати струк­туру ланцюжка й переходити від автоматних граматик і мов до контекстно-вільних, контекст­но-залежних мов та до мов без обмежень. Треба пересвідчитися, що пе­рехід від граматик типу 3 до граматик типу 0 ускладнює процес розпізнавання, посилюючи його трудомісткість.

Отже, рекомендується застосовувати порівняльний аналіз можливостей граматик різних типів. В першу чергу, розпочинайте вивчати контекстно-вільні граматики шляхом порівняння їх можливостей з можливостями автоматних граматик.

Очевидно, будь-яка автоматна граматика – це контекстно-вільна граматика за означенням. Легко навести приклад контекстно-вільної граматики, що породжує ре­гулярну мову:

G = <{0,1}, {d₀, d₁, d₂}, P, d₀ >, де множина Р включає такі правила:

d₀  d₁0d₂, d₂  0d₂,

d₁  1d₁, d₂  .

d₁  ,

Дійсно, мова, яка породжується наведеною КВ-граматикою G, може бути породжена такою автоматною граматикою:

G = <{0,1}, {d₀, d₁, d₂}, P₁, d₀ >, де множина Р₁ включає такі правила:

d₀  d₁, d₂  0d₂,

d₁  1d₁, d₂  .

d₁  0d₂.

З іншого боку, мова L = {, 01, 0011, 000111, ... } не може бути породжена автоматною граматикою, але для неї легко побудувати відповідну контекстно-вільну граматику. Отже, потужність класу контекстно-вільних мов більша за потужність класу автоматних мов, кожна регулярна мова може бути породжена контекстно-вільною граматикою, але є контекстно-вільні мови, які не можуть бути породжені автоматними граматиками.

Розширення можливос­тей у формуванні ланцюжків складної структури одночасно призво­дить до зменшення потужності мови. Наприклад, для конкретної регулярної мови L₁ = {, 0,1, 01, 00, 10, 11,...} легко знайти контекстно-вільну мову L₂ = {, 01, 0011, 000111, ... } таку, що L₂  L₁. Цей результат легко узагальнити і таким чином підтвердити, що правила контекстно-вільних граматик дозволяють визначати підмножини слів значно складнішої структури, ніж це дозволяють правила регулярних граматик.

Аналогічно вивчайте контекстно-залежні граматики шляхом порівняння їх можливостей з можливостями контекстно-вільних граматик, а останніх – з можливостями граматик без обмежень.

Наприклад, граматика типу 0

G = <{0,1}, {d₀, d₁, d₂}, P₂, d₀ >, де множина Р₂ включає такі правила:

d₀  0d₁1,

d₁  1d₂,

1d₂  01d₁,

1d₂  ,

породжує мову типу 3.

Необхідно пов’язати структуру ланцюжка з труднощами його аналі­зу трансляторами й переконатися у важливості нормальних форм та алгоритмів зведення до них.

Досвід свідчить, що алгоритм перетворення довільної КВ-грама­тики до нормальної форми Хомського особливих утруднень не викликає. У той самий час при використанні алгоритму перетворення довільної КВ-граматики до нормальної форми Грейбах ускладнення викликають проблеми впорядкування нетерміналів і перетворення правил пород­ження виду d_i  .

Роль і визначення інших моделей граматик простежте на прик­ладі індексної та програмної граматик.

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

Алгоритмічні мови програмування також зручно задавати за допомогою формальних граматик. У цьому випадку програми на алго­ритмічній мові виступають як ланцюжки мови, а правила породження граматики дозволяють, починаючи з нетермінального символу <про­грама>, породжувати тільки правильні термінальні ланцюжки, тобто програми на цій алгоритмічній мові.

За наявності граматики алгоритмічної мови можна зручніше й ефективніше розв’язати задачу знаходження синтаксичних помилок у програмі. Для цього підготовлену програму необхідно спробувати породити як ланцюжок у граматиці мови. Якщо програма може бути породжена, то синтаксичних помилок у програмі немає. В іншому випадку помилки у програмі є, причому можна простежити, виконан­ня яких правил породження в перекрученому вигляді привело б до породження ланцюжка. Ці викривлення і вкажуть місця помилок у програмі.

Як приклад розглянемо фрагмент граматики мови програмуван­ня Паскаль:

G_n = <D_n , E_n , P_n , <програма>>.

Множина нетермінальних символів D_n містить назви синтак­сичних конструкцій мови Паскаль. Множина термінальних символів E_n містить літери латинського алфавіту, цифри від 0 до 9, спеціаль­ні символи й зарезервовані олова. Далі нетермінальні символи поміщатимемо в дужки “ < > “. Множини D_n і Е_n задавати не бу­демо, оскільки елементи, що їм належать, легко відновити за пра­вилами множини Р_n .

До множини Р_n правил породження фрагмента граматики мови програмування Паскаль включимо такі правила (для зручності кож­ному правилу припишемо унікальний номер):

І. <програма>  <заголовок-програми> ; <блок-програми>

2. <заголовок-програми>  PROGRAM <ідентифікатор>

3. <заголовок-програми>  PROGRAM < ідентифікатора > (< параметри - програми >)

4. <параметри – програми>  <список–ідентифікаторів>

5. <список–ідентифікаторів>  <ідентифікатор>

6. <список-ідентифікаторів>  <ідентифікатор> <список-ідентифікаторів>

7. <блок-програми>  <блок>

8. <блок>  <розділ-опису-міток>

<розділ-визначення-констант >

<розділ-визначення-типів>

<розділ-опису-змінних>

<розділ-опису-процедур-та-функцій>

<розділ-операторів>

9. <розділ-опису-міток>  

10. <розділ-опису-змінних>  

11. <розділ-опису-змінних>  VAR <список-опису-змінних>;

12. <список-описів-змінних>  <опис-змінних>

ІЗ. <список-описів-змінних>  <опис-змінних>; <список-описів-змінних>

14. <опис-змінних>  <список-ідентифікаторів> : <позначення-типу>

15. <розділ-визначення-типів>  

16. <розділ-визначення-констант>  

17. <розділ-опису-процедур-та-функцій>  

18. <розділ-операторі в>  < складений оператор> .

19. <складений-оператор>  BEGIN <послідовність-операторів> END

20. <послідовність-операторів>  <оператор>

21. <послідовність-операторів>  <оператор> ; <послідовність-операторів>

22. <оператор>  <простий-оператор>

23. <оператор>  <складний оператор>

24. <простий–оператор>  <пустий-оператор>

25. <простий–оператор>  <оператор-привласнення>

26. <складний-оператор>  < умовний-оператор>

27. <складний-оператор>  <складений-оператор> ;

28. < складний-оператор>  <оператор-циклу>

29. <пустий-оператор> 

30. <оператор-привласнення>  <позначення-змінної>:= <вислів>

3І.. <умовний–оператор>  <оператор–якщо>

32. <оператор–якщо>  IF <логічний-вислів> TNEN <оператор> ;

33. <оператор–якщо>  IF <логічний–вислів> THEN <оператор> <частина-інакше>

34. <частина–інакше>  ELSE <оператор>

35. <оператор-циклу>  <оператор-повтор>

36. <оператор–циклу>  <оператор–поки>

37. <оператор–циклу>  <оператор–для>

38. <оператор–повтор>  REPEET <послідовність-операторів> UNTIL <логічний–вислів>

39. <оператор-поки>  WHILE <логічний-вислів> DO <оператор>

40. <оператор-для>  FOR <управляюча-змінна> = <початкове-значення> ТO <кінцеве-значення> DO <оператор>

41. <управляюча-змінна>  <повна-змінна>

42. <початкове-значення>  <вислів>

43. <кінцеве–значення>  <вислів>

44. <позначення-типу>  <ідентифікатор-типу>

45. <ідентифікатор–типу>  <ідентифікатор>

46. <ідентифікатор>  <літера>

47. <ідентифікатор>  <літера> <послідовність-літера–цифра>

48. <послідовність-літера-цифра>  <літера-цифра>

49. <послідовність-літера-цифра>  <літера-цифра> <послідовність-літера-цифра>

50. <літера–цифра>  <літера>

51. <літера-цифра>  <цифра>

52. <літера>  А

53. <літера >  Z

54. <літера>  а

55. <літера>  z

56. <цифра>  0

57. <цифра>  9

58. <позначення-змінної>  <повна–змінна>

59. <повна-змінна>  <ідентифікатор-змінної>

60. <ідентифікатор-змінної>  <ідентифікатор>

61. <вислів>  <список-простих–висловів>

62. <список-простих-висловів>  < простий-вислів>

63. <список-простих-висловів>  <простий-вислів>

<операція-відношення>  <список-простих–висловів>

64. <простий–вислів>  <знак> <список-термів>

65. <простий-вислів>  < список-термів>

66. <список–термів>  <терм>

67. <список-термів>  <терм> <операція-типу-додавання> <список–термів>

68. <терм>  <список–множників>

69. <список-множників>  <множник>

70. <список–множників>  <множник> <операція-типу-множення> <список–множників>

71. <множник>  <позначення–змінної>

72. <множник>  <константа-без-знака>

73. <множник>  (<вислів>)

74. <константа-без–знака>  <число-без- знака>

75. <число - без - знака > —— <ціле - без – знака >

76. <число - без – знака >  <дійсне - без – знака >

77. <ціле - без - знака > — <послідовність – цифр >

78. <дійсне - без – знака >  <ціле - без – знака > , <дробова – частина >

79. <дійсне - без - знака >  < ціле - без – знака > , <дробова – частина > Е <порядок >

80. < дійсне - без - знака >  <ціле - без – знака > E <порядок >

81. <дробова – частина >  <послідовність – цифр >

82. <порядок>  <ціле - зі – знаком >

83. < операція - типу - множення >  *

84. <операція - типу - множення>  /

85. < операція - типу - множення >  AND

86. <операція - типу – додавання>  +

87. <операція - типу - додавання>  -

88. < операція - типу - додавання >  OR

89. < знак >  +

90. < знак >  -

91. < операція - відношення >  =

92. < операція - відношення >  < >

93. < операція - відношення >  <

94. <операція – відношення >  >

95. < операція - відношення >  < =

96. < операція - відношення >  > =

97. < логічний - вислів >  <вислів >

98. <дійсне - зі – знаком >  <знак > <дійсне - 6ез – знака >

99. <ціле - зі - знаком > < знак > < ціле - без – знака >

100. <ціле - зі – знаком >  < ціле - без - знака >

101. <послідовність – цифр >  <цифра >

102. <послідовність – цифр >  < цифра > < послідовність – цифр >

103. <простий – оператор >  <виклик - процедури >

104. < виклик - процедури >  READ <список – параметрів – процедури - READ>

105. < виклик - процедури >  READLN <список - параметрів - процедури – READLN >

106. < виклик - процедури >  WRITE <список - параметрів - процедури - WRITE >

107. < виклик - процедури >  WRITELN <список - параметрів – процедури – WRITELN>

108. < список - параметрів - процедури – READ >  (<список - позначень – змінної>)

109. <список - позначень – змінної > <позначення – змінної >

110. < список - позначень – змінної > < позначення - змінної > , <список - позначення - змінної >

111. < список - параметрів - процедури – READLN > < список - позначень – змінної >

112. <список - параметрів - процедури – READLN>  

113. < список - параметрів - процедури - WRITE >  (<змінна - файл >)

115. < список - параметрів - процедури – WRITE -I > <параметр - процедури – WRITE >

116. <список - параметрів - процедури - WRITE -I >  <параметр - процедури – WRITE >,

< список - параметрів - процедури - WRITE -I >

117. < параметр - процедури - WRITE > <вислів >

118. < параметр - процедури - WRITE > <вислів > : < вислів >

119. < параметр - процедури - WRITE > <вислів > : < вислів >: < вислів >

120. < список - параметрів - процедури - WRITELN > 

121. < писок - параметрів - процедури - WRITELN > (<змінна – файл >)

122. <список - параметрів - процедури - WRITELN > (<змінна – файл > ,

< список - параметрів - процедури - WRITE -I > )

123. < змінна - файл >  < позначення - змінної >

124. < оператор - привласнення > <ідентифікатор - функції > := <вислів >

125. (ідентифікатор – функції > < ідентифікатор >

Варто зазначити, що у фрагменті не відбиті можливості мови Паскаль щодо обробки записів, масивів, визначення різних типів даних, констант, процедур, функцій, міток та ін. Фактично фраг­мент граматики дозволяє досліджувати тільки програми на мові Паскаль, що містять розділи операторів і опису змінних, при­чому з урахуванням наведених вище обмежень.

Також відзначимо, що у фрагменті опушені правила породжен­ня виду 52 і 53 для великих літер латинського алфавіту, крім літер А і Z . Аналогічно для практичного використання необ­хідно додати правила породження виду 54, 55 для решти маленьких літер латинського алфавіту і правила виду 56, 57 - для решти арабських цифр.

Повну граматику мови програмування Паскаль можна знайти у [27] . Проте у цьому підручнику, так само як і в інших, гра­матика наведена з урахуванням спеціальних узгоджень, то дозволя­ють задавати правила породження більш наочним і зручним способом. Найчастіше використовуються два типи таких узгоджень, відомих під назвами форма Бекуса - Наура /ФБН/ і розширена форма Бенуса -Наура /РФБН/.

Для описання мови /мова програмування, що описується, висту­пає як мова - об’єкт / у системі ФБН використовуються металінгвістичні формули Бекуса - Наура. Кінцеве число цих формул представляє мета - мову. Кожна формула мета -мови включав символи мови - об’єкта і спеціальні мета - символи ":=" та “|”.

Символ ":=" можна читати "за означенням є", а символ "|" -"або". Перший з них замінює символ "", що використовується при завданні правил породження формальних граматик Ханського, a другий - для спрощення запису правил, породження, що включають однакову ліву частину. Наприклад, правила породження 35, 36, 37 граматики мови Паскаль у ФБН можна записати за допомогою однієї формули такого вигляду;

< оператор - циклу >:= <оператор – повтор> | <оператор – пока> | <оператор - для >

У ФБН у лівій частині завжди міститься символ з множини D_n граматики G_n кожна формула записується з нового рядка, й при перенесенні формули на наступний рядок ніякі нові символи не використовуються.

Система РФБН робить описання мови - об’єкта ще зручнішим за допомогою таких мета - символів:

“=” - використовується так само, як символ ":=" ФБН;

"|" - використовується так само, як символ "|" ФБН;

“( )” - використовується для запису двох і більше формул ФБН, що незначно відрізняються правими частинами;

"[ ]" - використовується для запису двох формул, одна а яких містить праву частину, що включав праву частину іншої формули;

"{ }" - використовується для вказання довільного числа повторів вмісту цих дужок.

Приклади використання мета - символів РФБН. Правила породження 30 і 123 граматики мови Паскаль можна задати формулою ФБН

<оператор - привласнення > := < ідентифікатор – змінної > := <вислів> | <ідентифікатор - функції >: = < вислів >

У РФБН для цього можна використовувати ще більш зручну форму­лу:

оператор - привласнення = ( Ідентифікатор - змінної | ідентифікатор - функції ) : = вислів

Використовуючи мета - символи "[ ]", правила породження 2, 3 граматики мови Паскаль можна задати однією формулою РФБН:

заголовок - програми = PROGRAM ідентифікатор [ ( параметри - програми )]

Правила породження 46-51 граматики мови Паскаль, використо­вуючи мета - символи “{ }” та "|", можна задати однією формулою:

ідентифікатор = літера { літера | цифра }

Крім того, як можна помітити на прикладах, нетермінальні сим­воли множини D_n граматики G_n у формулах РФБН у дужки "< >" не беруться, але слова природної мови, що входять до нетермінального символу, з’єднується з допомогою дефіса. У системі РФБН послідовність формул завершується символом "."

Вочевидь, фрагмент граматики мови Паскаль належить до класу контекстно - вільних граматик Хомського.

Приклад породження програми мовою програмування Паскаль у фрагменті формальної граматики G_n наведено для вправи 25 теми 4.1.

Рекомендується самостійно задати граматикою мову програмування Паскаль, причому використати для цієї мети зображення формула­ми ФБН і РФБН. Якщо ліміт часу не дозволяє зробити це, спробуйте самостійно задати граматикою який-небудь фрагмент мови. Було б дуже корисно перенести цей підхід на вивчення інших алгоритмічних мов дисципліни "Основи програмування й алгоритмічні мови".

Вправи до теми 4.1.

Вправа І. Класифікувати за Хомським такі граматики:

G = <D, E, P, d₀ >, де D = {d₀, d₁, d₂}, E = {0,1}.

Варіанти множини правил виведення:

1) d₀  010 d₁, 2) d₀  010 d₀, 3) d₀  01 d₁ 01,

d₁  0 d₁, d₀  Є, d₁  0 d₁ 0,

d₁  Є, d₁  Є.

4) d₀  0 d₁ 0, 5) d₀  0 d₁ d₂ , 6) d₀  1 d₁ 1,

d₁  1 d₁, d₁  1 d₁, d₁  1 d₁ 1,

d₁  11 d₂, d₂  1 d₂ 0, 1 d₁ 1  1 0 1.

11 d₂  1 d₃ 1, d₁  Є,

d₃  d₂ 0, d₂  0,

01 d₂  Є,

Вправа 2. Класифікувати за Хомським граматики із вправи 6 теми 1.2.

Вправа 3. Які з граматик, наведених у вправі 1, породжують регулярну мову.

Вправа 4. Задати граматику Хомського, що породжує мову, яка містить тільки слова вигляду 0…0 1…1, де кількість n символів 0 рівна кількості

k символів 1, збільшеній на k, k = 1, 2, 3, ...

Вправа 5. Задати граматикою регулярні множини вправи 6 теми 1.2.

Вправа 6. Навести приклади ланцюжків, які породжуються граматиками вправи 1.

Вправа 7. Навести фрагмент (з правилами виведення) формальної граматики української мови для породження речень вигляду: "Фор­мальна граматика однозначно визначає мову".

Вправа 8. Навести приклади слів регулярних мов, заданих регулярними виразами, які відповідають множинам із вправи 17 теми 1.2.

Вправа 9. Задати граматику G, що породжує мову

L(G) = {A, AAБ, AAAББ,...}.

Вправа 10. Задати граматику G, що породжує мову

L(G) = {АББ, ААБББ, АААББББ ,...}.

Вправа 11. Задати граматику G, що породжує мову

L(G) = {AБ, AAББ, АААБББ,...}.^

Вправа 12. Які з граматик, наведених у вправі 6 теми 1.2, породжують контекстно-вільну мову?

Вправа 13. Навести приклади слів, що породжуються такими граматиками:

І) G = <{d₀ , d₁, d₂}, {A, Б}, P, d₀ > дe множина Р містить правила

d₀  Ad₁A , d₁  Ad₂A ,

d₁  Бd₁Б , d₂  A ;

2) G = <{d₀ , d₁, d₂}, {Б, A }, P, d₀ > де множина Р містить правила

d₀  Бd₁A, d₂  Б A ;

d₁  Бd₂A,

3) G = <{d₀ , d₁, d₂}, { A, Б }, P, d₀ >, де множина містить правила

d₀  Бd₁A, d₂  Бd₂A,

d₁  Бd₂A, d₂  Є;

4) G = <{d₀ , d₁, d₂, d₃, d₄}, { A, В, Е, К, Л, И, С, У,- }, P, d₀ >, де множина Р містить правила

d₀  Сd₁У, d₂  Аd₃Б,

d₁  Лd₂В, d₃  Вd₄И,

d₄  А-К .

Вправа 14. Які з граматик вправи 1 породжують контекстно-вільні мови?

Вправа 15. Задати граматику, що породжує такі мови:

1) L = {010, 00100, 0001000,…}

2) L = {1001, 110011, 11100111, …}

3) L = {01010, 0110110, 011101110,…}

4) L = {АБВ, ААБВВ, АААБВВВ, …}

5) L = {АБВ, АББВВ, АБББВВВ, ...}

6) L = {АБВ, ААББВ, АААБББВ, ...}

7) L = {АБВ, АБАБВ, АБАБАБВ,....};

8) L = {АБВАБ, АБАБВАБАБ, АБАБАБВАБАБАБ,…}

9) L = {АБВА, АББВВА,АБББВВВА,...}

10) L = {АБВВ, АБАБВВВ, АБАБАБВВВВ, ...}

11) L = {АБВ, ААБВБВ, АААБВБВБВ, ...}

I2) L = {АБВВ, АББВВВ, АБББВВВВ, ....}

I3) L = {АА, ААБВ, ААББВВ, ААБББВВВ, ...}

I4) L = {А, БАВ, ББАВВ, БББАВВВ, ...}

I5) L = {АБВА, АБВАБВА, АБВАБВАБВА, ...}

I6) L ={Б, ББА, БББААВ, ...}

Вправа 16. Нехай задані контекотно-вільні граматики:

I) G₁ = <{d₀ , d₁, d₂}, {e₁, e₂}, P₁, d₀ >, де множина Р містить правила

d₀  d₁d₂d₂, d₂  e₁e₂d₂,

d₁ e₁d₂e₂, d₂  Є;

2) G₂ = <{d₀ , d₁, d₂, d₃}, {e₁, e₂, e₃}, P, d₀ >, де множина Р містить правила

d₀  e₁d₁d₂, d₃  e₂d₃e₂,

d₁ e₂d₂d₃, d₃  Є;

d₂ e₁d₂d₃,

З) G₃ = <{d₀ , d₁, d₂, d₃}, {e₁, e₂, e₃}, P, d₀ >, де множина Р містить правила

d₀  e₁d₁e₁, d₂  e₃d₃e₃,

d₁ e₂d₂e₂, d₃  e₁d₃e₁,

d₃  Є.

Необхідно:

І) представити кожну граматику в нормальній формі Хомського;

2) представити кожну граматику у нормальній формі Грейбах.

Приклад: Нехай G₄ = <{d₀ , d₁, d₂}, {e₁, e₂}, P, d₀ >, де множина Р містить такі правила:

І/ d₀  e₁d₁e₁, 3/ d₂  d₂d₂,

2/ d₁  d₂d₂e₂, 4/ d₂  e₂;

а) представимо G₄ у нормальній формі Хомського. Правило d₀  e₁d₁e₁ представимо у вигляді таких правил:

5) d₀  e'₁ <d₁ e₁>, 6) <d₁ e₁>  d₁ e'₁ ,

де e'₁ , <d₁ e₁> -нові нетермінали.

Правило d₁  d₂ d₂ e₂ представимо у вигляді таких правил:

7) d₁  d₂ <d₂ e₂>, 8) <d₂ e₂>  d₁ e'₂ ,

де <d₂ e₂>, e'₂ - нові нетермінали.

Правила 3 та 4 мають вигляд, потрібний для нормальної форми Хомського .

Тоді G₅ = <{d₀ , d₁, d₂, e'₁ , <d₁ e₁>, e'₂ , <d₂ e₂>},{e₁, e₂}, P, d₀ >,

де Р₁ містить правила 3-8, - граматика у нормальній формі Хомського;

б) представимо G₄ у нормальній формі Грейбах. Упорядкуємо не термінали таким чином:

d₀ < d₁< d₂.

Тепер випишемо правила:

9) d₂  e₂ , І2) d₀  e₁ d₁ e₁,

10) d₂  e₂ d₂, І3) e'₂  e₂ ,

11) d₁  e₂ d₂ e'₂, І4) e'₁  e_{1 .}

Таким чином, G₅ = <{d₀ , d₁, d₂, e'₂ , e'₁ },{e₁, e₂}, P₂, d₀ >,

де P₂ містить правила виведення 9 - І4, - граматика у нормальній формі Грейбах.

Вправа 17. Чи може дерево виводу для якої-небудь контекстно - вільної граматики мати такий вигляд:

Вправа 18. Установити порожнечу або непорожнечу мов, що породжуються такими граматиками:

І) G₁ = <{d₀ , d₁, d₂, d₃ , d₄, d₅}, {0, 1, 2, 3}, P, d₀ > ,

де Р містить правила

d₀  d₁d₂ , d₂  1d₀ , d₄  2d₅ 2,

d₁ 0d₁ , d₃  2d₃ d₄ , d₅  3d₃ 3,

d₁  1, d₃  2d₅ , d₅  2;

2) G₂ = <{d₀ , d₁, d₂}, {0, 1, 2, 3}, P, d₀ > ,

де P містить правила

d₀  0d₁d₂ , d₂  2d₂2 ,

d₁  1d₀ , d₂  Є ;

3) G₃ = <{d₀ , d₁, d₂}, {0, 1, 2, 3}, P, d₀ > ,

де P містить правила

d₀  0d₁0 , d₁  3 ,

d₁  1d₁2 , d₂  Є ;

4) G₄ = <{d₀ , d₁, d₂, d₃}, {0, 1, 2, 3}, P, d₀ > ,

де P містить правила

d₀  1 , d₁  0d₁2 , d₃  1 d₃,

d₀  0d₁2 , d ₁ 1 , d₃  Є ;

d₂  3d₃ ,

5) G₅ = <{d₀ , d₁, d₂}, {0, 1, 2, 3}, P, d₀ > ,

де P містить правила

d₀  0 d₀ 1 d₁, d₁  2 ,

d₀  Є , d₂  3 .

Вправа 19. Вирішити проблему порожнечі мов, що породжуються граматиками вправи 13.

Вправа 20. Установити некорисні та недосяжні символи граматик із вправи 18.

Вправа 21. Перетворити граматики вправи 18 до вигляду, вільного від некорисних та недосяжних символів.

Вправа 22. Перетворити граматики вправи 18 у невкорочуванні граматики без символу d₀ у правій частині правил виводу.

Вправа 23. Навести приклади граматик, що містять у собі некорисні символи.

Вправа 24. Чи можуть бути у граматиці побудовані різні дерева виводу для якого-небудь ланцюжка? Якщо відповідь позитивна, тоді навести приклад такої граматики і не менш ніж двох різних дерев виводу для цього ланцюжка.

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

Приклад: Нехай програма на мові Паскаль має такий вигляд:

PROGRAM bsv (input, output);

VAR y, a, b:real;

BEGIN

READ (a, b);

IF a < b THEN y:=a*b

ELSE y::=a/b;

WRITE ( y)

END.

Д

(n)

ля позначення того факту, що ланцюжок  породжує ланцюжок  будемо використовувати традиційне позначення  ==>  . Але, щоб приклад був більш iнформативним, будемо використовувати позначення  ==>  , де n - номер правила породження, використованного під час породження ланцюжком  ланцюжка  . Звичайно, початковий символ граматики G_n виписуємо першим, а використовуючи правило 1 отримуємо:

(1)

(1)

< програма > ==> < заголовок - програми > ; < блок - програми > . Потім, використовуючи правила породження 3-6, формуємо структуру

(3)

заголовку програми: <заголовок - програми > ; < блок –програми > ==> PROGRAM <{iдентифiкатор > /параметри - програми/ ; < блок - програми >==>PROGRAM <iдентифікатор ( < список – iдентифікаторів> ); <блок –

(4)

програми > ==>PROGRAM < iдентифікатор (<ідентифікатор >, <список –

(5)

iдентифікаторів >); <блок - програми > ==> PROGRAM < iдентифікатор > (<iдентифікатор> , < iдентифікатор >) ; < блок -програми > .

У прикладі програма містить тільки розділи опису змінних та операторів. Тому, породження програми можливо використанням правил 7-9, 11, 15, 16-19. Такім чином, породження програми прикладу може бути продовжено так: PROGRAM< ідентифікатор > (<ідентифікатор >, <

(7)

iдентифікатор >); <блок програми > ==> PROGRAM <ідентифікатор > (<

(8)

ідентифікатор>, < ідентифікатор >);<блок >==> PROGRAM <ідентифікатор >(< ідентифікаторі>, < ідентифікатор >);< розділ -опису -міток > < розділ –визначення -констант > < розділ –визначення -типів > < розділ –опису -змінних > <розділ –опису –процедур -та -функцій > < розділ -операторів>

(9)

==>

PROGRAM< ідентифікатор > (<: ідентифікатора, < ідентифікатор >);

<

(9)

розділ -визначення-констант> < розділ -визначення-типів > <роздiл-опису-змінних > <розділ –опису –процедур –та -функцій > <Розділ –

(16)

операторів >==> program <ідентифікатор > (< iдентифікатор>, < iдентифікатор >); <розділ -визначення-типів > <розділ –опису –змінних > <

(15)

розділ –опису –процедур –та - функцій > < розділ -операторів >==> PROGRAM< iдентифікатор >(< ідентифікатор >, < ідентифікатор >);

<розділ –опису -змінних > < розділ –опису –процедур –та -функцій >

(17)

< розділ -операторів > ==> PROGRAM< ідентифікатор > (< ідентифікатор >, < ідентифікатор >);

(11)

<розділ –опису –змінних > < розділ -операторів > ==> PROGRAM < ідентифікатор > (<iдентифікатор >, < ідентифікатор >); VAR <список –

(18)

описів -змінних >; < розділ -операторів >==> PROGRAM < ідентифікатор >(< ідентифікатор >, < ідентифікатор >); VAR < список –описів - змінних >;

(19)

<складений -оператор > ==> PROGRAM <ідентифікатор> (< ідентифікатор>, < ідентифікатор >);

VAR < список – описів - змінних ; BEGIN < послідовність -операторів > END.

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

У фрагменті граматики мови Паскаль породження такого опису змінних забезпечують правила породження 12, 14, а вказаної послідовності - правила породження 20-23, 26, 103.

Породжуючи процес породження за допомогою наведених вище правил породження, отримуємо:

(12)

==> PROGRAM < ідентифікатор> (< ідентифікатор >, < ідентифікатор>); VAR < опис -змінних >: BEGIN < послідовність –

(14)

операторів> END. ==>PROGRAM < ідентифікатор> (< ідентифікатор> < ідентифікатор >);

VAR < список-ідентифікатор >: < позначення типу >; BEGIN <

(21)

послідовність-операторів > END. ==> PROGRAM < ідентифікатор > (< ідентифікатор > , < ідентифікатор >); VAR. <список –ідентифікаторів>:

< позначення – типу> ; BEGIN < оператор > ; < послідовність –

(20)

операторів > END ==>.

PROGRAM < ідентифікатор > (< ідентифікатор >, < ідентифікатор >);

VAR < список - ідентифікаторів >: < позначення - типу >; BEGIN < оператор

(22)

>; < оператор> ; <послідовність - операторiв > END ==>.

PROGRAM < ідентифікатор > ( < ідентифікатор >, < ідентифікатор > ); VAR < список - ідентифікаторів >: < позначення - типу >; BEGIN < оператор >; < оператор >, <оператор > END ==>. PROGRAM < ідентифікатор > (< ідентифікатор >, < ідентифікатор >), VAR. <список - ідентифікаторів >: < позначення - типу> ; BEGIN < простий - оператор >; <оператор >; <

(23)

оператор > END ==>

PROGRAM < ідентифікатор >(<: ідентифікатор >, <ідентифікатор >);

VAR < список - ідентифікаторів > : <позначення - типу >; BEGIN <

(22)

простий – оператор>; <складний – оператор >; < оператор > END. ==> PROGRAM <ідентифікатор > (< ідентифікатор > , < ідентифікатор >); VAR<список - ідентифікаторі в >: < позначення - типу >; BEGIN < простий - оператор> ; < складний оператор >; < простий оператор > END.

(103)

==> PROGRAM < ідентифікатор > (< ідентифікатор >, < ідентифікатор >);

VAR < список –ідентифікаторів >: < позначення - типу >; BEGIN < виклик - процедури >; < складний - оператор >, < простий - оператор > END

(26)

==> PROGRAM < ідентифікатор > (< ідентифікатор >, < ідентифікатор >);

VAR < список - ідентифікаторів >: < позначення - типу >; BEGIN < виклик - процедури>; < умовний – оператор>; < простий - оператор > END.

(25)

==>PROGRAM < ідентифікатор > (< ідентифікатор >, < ідентифікатор >);

VAR.<список – ідентифікаторів >: < позначення - типу >, BEGIN < виклик - процедури >; < умовний - оператор>; < виклик - процедури > END.

Подальші кроки процесу породження, мабуть, зв’язані із формуванням операторів виклику процедур вводу/ виводу, умовного оператора, cписка ідентифікаторів змінних та позначення типу змінних.

П

(n₁, n₂, …, n_r)

ереконавшись у важливості точного слідування правилам породження, формальності, послідовності та методичності процесу породження, можна звернути увагу на скорочення обсягу записів. Далі, скрізь, де породження ланцюжків очевидно, ми не будемо записувати безпосередні породження, а фіксуватимемо тільки найбільш важливі породження ланцюжка, тобто програми прикладу. Щоб зберегти інформативність запису, факт породження ланцюжком  ланцюжка  шляхом використання послідовності правил породження n₁, n₂,…, n_r будемо позначати  ========> .

Продовжуючи процес породження у наміченому вище напрямку та використовуючи прийняті спрощення, отримуємо:

(104, 108, 110, 109)

==========> PROGRAM< ідентифікатор > (< ідентифікатор >, < ідентифікатор >);

VAR < список - ідентифікаторів >: < позначення - типу >; ВEGIN

R

(106, 114)

EAD <позначення - змінної > , < позначення - змінної > );

< умовний - оператор >; < виклик - процедури > END. =======> PROGRAM <ідентифікатор (< ідентифікатор >, < ідентифікатор>);

VAR < список - ідентифікаторів >: < позначення - типу >; BEGIN

READ (< позначенкя - змінної >, < позначення – змінної>); <умовний -

(6,6,5,44,45)

оператор > ; WRITE <змінна - файл > END.=======>

PROGRAM < ідентифікатор(< ідентифікатор>, < ідентифікатор ;

VAR < ідентифікатор, < ідентифікатор >, < ідентифікатор >: < ідентифікатор > ;

BEGIN READ(< позначення – змінної>, < позначення - змінної >);

IF < логічний - вираз > THEN < оператор> ELSE < оператор > ;

WRITE <змінна - файл > END.

На даному етапі процесу породження ланцюжок вже істотно збігається із програмою прикладу. Зараз необхідно сформувати оператори присвоєння в умовному операторі та в операторах вводу/виводу підготуватися до породження ідентифікаторів змінних. Такий план призводить до такої послідовності ланцюжків:

(22, 25, 30)

=======> PROGRAM < ідентифікатор >(< ідентифікатор>, <ідентифікатор >);

VAR < ідентифікатор >, < ідентифікатор >, < ідентифікатор > :

< ідентифікатор > ; BEGIN

READ (< позначення – змінної>, < позначення - змінної >);

IF < логічний - вираз > THEN < позначення змінної > := < вираз >

(61, 62, 65,66, 68, 70)

ELSE <оператор>; WRITE (<змінна - файл >) END. =============>

PROGRAM < ідентифікатор >(< ідентифікатор >, < ідентифікатор>;

VAR < ідентифікатор >, < ідентифікатор >, < ідентифікатор >: < ідентифікатор > ;

BEGIN READ (< позначення – змінної >, < позначення - змінної >);

IF < логічний - вираз > THEN

< позначення змінної >:= <множник> < операція - типу - множення> < множник > ELSE < оператор >; WRITE (<змінна - файл >) END.

Аналогічно можна зробити з оператором присвоєння у частині ELSE умовного оператора. Послідовність правил породження 22, 25, З0, 61, 62, 65, 66, 68, 70, 69 призводить до породження ланцюжка:

PROGRAM < ідентифікатор >(< ідентифікатор >, < ідентифікатор >);

VAR < ідентифікатор > ,< ідентифікатор > < ідентифікатор >.: < ідентифікатор > ;

BEGIN READ < позначення - змінної >, < позначення - змінної >);

IF < логічний-вираз >THEN < позначення-змінної>:= < множник > < операцїя-типу-множення > < множник > ELSE < позначення-змінної >:=<множник> < операція-типу-множення > < множник >; WRITE(<змінна-файл >) END.

Далі, виконуючи підстановку за допомогою правила породження 71, а потім послідовності правил 58-50, отримуємо ланцюжок:

PROGRAM < ідентифікатор> ( < ідентифікатор >, < ідентифікатор >);

\/AR < ідентифікатор> < ідентифікатор.>,< ідентифікатор>: < ідентифікатор >;

BEGIN READ <означення-змінної >, < позначення-змінної >) ;

IF < логічний- вираз > THEN < ідентифікатор >:=<ідентифікатор >

< операція-типу-множення > < ідентифікатор > ELSE

< ідентифікатор >:=< ідентифікатор > <операція-типу-множення> <ідентифікатор > ;

WRITE (< змінна-файл >) END .

Використовуючи правила породження 97, 61, 63, 62 та двічі послідовність 65, 66, формуємо структуру логічного виразу:

PROGRAM <ідентифікатор>(< ідентифікатор>, < ідентифікатор>);

VAR < ідентифікатор > , < ідентифікатор >, < ідентифікатор >: < ідентифікатор > ;

BEGIN READ (< ідeнтифікaтop>, < ідентифікатор >);

IF < терм > < операція-відношення > < терм > THEN

< ідентифікатор >:= < ідентифікатор> <операція-типу-множення >

< ідентифікатор > ELSE < ідентифікатор>:=< ідентифікатор>

<операція-типу-мнохення> <ідентифікатор>;

WRITE (< змінна-файл >) END .

На наступному етапі породження, використовуючи правила породження 83, 84 і 83, підставимо у ланцюжок спеціальні символи математичних операцій та відношень:

PROGRАМ <ідентифікатор> (< ідентифікатор> ,<. ідентифікатор >);

\/AR < ідентифікатор >, < ідентифікатор>, < ідентифікатор >: < ідентифікатор > ;

BEGIN READ (< ідeнтифікaтop >), < ідентифікатор>; IF <терм> ‹ <терм>

THEN < ідентифікатор>:=< ідентифікатор > * < ідентифікатор >

ELSE < ідентифікатор> := < ідентифікатор>/ < ідентифікатор > ;

WRITE (< змінна-файл >) END .

Двічі використовуючи послідовність правил породження 68, 69, 71, 58, 59, 60, а потім один раз послідовність 123, 58, 59, 60, отримуємо ланцюжок:

PROGRAM < ідентифікатор > (< ідентифікатор >, < ідентифікатор >);

VAR < ідентифікатор>, < ідентифікатор>, < ідентифі катор> : < ідентифікатор > ;

ВЕСІ N READ (< ідентифікатор >, < ідентифікатор >};

IF < ідентифікатор > ‹ < ідентифікатор > THEN <ідентифікатор>:=

< ідентифікатор>* < ідентифікатор > ELSE < ідентифікатор > :==

< ідентифікатор>/<ідентифікатор>; WRITE (< ідентифікатор >) END.

Таким чином, для того щоб показати, що програма прикладу породжена граматикою алгоритмічної мови Паскаль залишається сформувати відповідні ідентифікатори у породженому ланцюжку. Це можна зробити використанням правил породження 46-57.

Покажемо, наприклад, породження ідентифікатора bsv:

47

<

49

48

ідентифікатор > ===> < літера > < послідовність - літера -цифра > ===> < Літера >

< Літера-цифра> < послідовність-літера-цифра > ===>

50

<літера> < літера-цифра > < літера- цифра > ===>

50

<літера> <літера> < літера-цифра > ===><літера > <літера > <Літера>===> b < Літера > <літера>====> bs <літера>==> bsv

Ідентифікатори змінних y, a, b можна сформувати за допомогою лише двох правил /46 та правила вигляду 54/. Ідентифікатори input, output, real вимагають використання правил 47-50 та правил вигляду 54.

Таким чином, підставляючи праві частини правил породження 46-57 замість нетермінальних символів < ідентифікатор>, отримуємо термінальний ланцюжок:

PROGRAM bsv (input, output);

VAR , a, b: real ;

BEGIN READ ( a, b);

IF a < b THEN y:=a* b ELSE y:=a / b ;

WRITE ( y )

END .

Цей ланцюжок збігається із програмою прикладу. Отже, програма прикладу не містить синтаксичних помилок.

Приклад демонструє ще раз формальний характер процесу породження і, тим самим, можливість його реалізації, а також реалізації процесів синтаксичного контролю програм на EОM.

Вправа 26. Задати граматику G , що породжує мову

L(G) = {АБВ, ААББВВ, АААБББВВВ,...} .

Вправа 27. Задати граматики, що породжують такi мови:

І/ L(G) = {АБВВ, ААББВВВ, АААБББВВВВ,... }

2/ L(G) = {ААБВ, АААББВВ, AAAAБББВВВ, ...}

З/ L(G) = {АББВ, ААБББВВ, АААББББВВВ....}

4/ L(G) = {А, ААБ, АААББВ, ААААБББВВ,...}

5/ L(G) = {В, БВВ, АББВВВ, ААБББВВВВ,...}

6/ L(G) = {Б, АББ, ААБББВ, АААББББВВ,... }

Вправа 28. Навести приклади ланцюжків, що породжуються граматикою

G = <{d₀, d₁, }, {А, Б, В}, P, d₀ >, де множина Р містить такі правила:

d₀  А d₁ Б, Б d₁ А  Б Б d₂ БА ,

d₀  Б d₁ А, В d₂ В  В А В,

А d₁ Б  А В d₂ В Б , Б d₂ Б  Б В Б .

Вправа 29. Задати програмну граматику, що породжує мову з вправи 27.

Вправа 30. Задати індексну граматику, що породжує мову з вправи 27.

Вправа 31. Задати програмні граматики, що породжують мови з вправи 27.

Приклад: Нехай L(G) = {АБАА, ААББААА, АААБББАААА,... }.

Структура слова мови L(G) така, що його зручно породжувати, створюючи ніби цикл, кожний крок якого потребує приєднання символів:

І) А до лівого підслова символів А;

2) Б до підслова символів Б;

З) А до правого підслова символів А.

Причому на останньому кроці циклу до правого підслова приєднується не один, а два символи А. Тоді програмна граматика має вигляд

G = <{d₀ , d₁ ,}, {А, Б}, {1, 2, 3, …, 8}, P, d₀ >,

де множина Р містить такi правила:

(1) d₀  d₁ d₂ d₃ {2, 5 } 

(2) d₁  A d₁ {3 } 

(3) d₂  Б d₂ {4 } 

(4) d₃  A d₃ {2, 5} 

(5) d₁  A {6 } 

(6) d₂  Б {7 } 

(7) d₃  AA {8 } 

(8) d₀  d₀  

Правило з міткою (1) формує основу для слова, складеного з підслів символів А (лівий), символів Б та символів А (правий/. Після цього виконується довільне число циклів /2/, /З/, /4/, Останній цикл зв"язаний з використанням правил із мітками /5/, /б/, /7/.

Структура ланцюжка формується при використанні однакової, крім останнього циклу, кількості приєднань символів до підланцюжків.

Вправа 32. Задати індексні граматики, що породжують мови з вправи 27.

Приклад: У слові мови L(G) виділяються три підслова, кожне з яких містить ліве - символи А; праве - символи А; середнє - символи Б. Довжина правого підланцюжка на одиницю більше, ніж довжина обох інших. Завдяки цьому зручно за допомогою індексної граматики спочатку сформувати одне індексне слово і повторити його 3 рази. Після цього можна звести кожне підслово до потрібного вигляду, використовуючи правила виводу без обмежень. Тоді індексна граматика для породження мови, що розглядалась у попередньому випадку, має вигляд

G = <{d₀ , d₁ , d₂ , d₃ ,d₄ }, {А, Б}, {f, 2g}, P, d₀ >,

де множина Р містить такі правила виводу:

d₀  d₁ g; d₂ g  А; d₂ f  А d₂ ;

d₁  d₁ f; d₃ g  Б; d₃ f  Б d₃ ;

d₁  d₂ d₃ d₄ d₄ g  А А; d₄ f  А d₄ .

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

Вправа 33. Навести приклади слів, що породжуються програмною граматикою:

G = <{d₀ , d₁ , d₂ , d₃ }, {А, Б, В, Г}, {1, 2, 3,…,8}, P, d₀ >,

де Р містить такі правила виводу:

І/ d₀  d₁ d₂ d₃ {2, 5 } 

2/ d₁  A d₁ {3 } 

3/ d₂  Б Б d₂ {4 } 

4/ d₃  В В В d₃ {2, 5 } 

5/ d₁  Г {6 } 

6/ d₂  Г {7 } 

7/ d₃  Г {8 } 

8/ d₀  d₀  

Вправа 34. Навести приклади ланцюжків, що породжуються такою iндексною граматикою:

G = <{d₀ , d₁ , d₂ , d₃ , d₄ }, {А, Б, В, Г}, {i₁, i ₂}, P, d₀ >,

де Р містить такі правила:

d₀  d₁ i₁ , d₄ d₂  B B B d₄,

d₁  d₁ i₂ , d₂ i₁  Г,

d₁  d₂ d₃ d₄, d₃ i₁  Г,

d₂ i₂ A d₂, d₄ i₁  Г.

d₃ i₂ Б Б d₃,

Вправа 35. Навести приклади контекстно-залежної мови, яка породжена програмною контекстно-вільною граматикою.

Вправа 36. Навести граматику, що породжує мову L = {0, 00, 000,…}, перше слово якої містить символ 0, а всі наступні отримуються з попереднього приєднанням до нього чергового натурального числа символів 0.