68824

Перетворення вхідної граматики у LL(1)-граматику

Лекция

Информатика, кибернетика и программирование

Аналогічне ствердження має місце відносно ліворекурсивного циклу приклад якого дають правила 1. У наведеному прикладі правила 2 3 4 6 утворюють ліворекурсивний цикл який завжди можна вилучити перетворив одне з правил наприклад 6 у ліву рекурсію. Для С існують два правила 4 та 5.

Украинкский

2014-09-26

93 KB

0 чел.

Лекція 12

Перетворення вхідної граматики у  LL(1)-граматику

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

1. Чи можна будь-яку мову генерувати  LL(1)-граматикою?

2. Якщо ні, чи існує алгоритм, що визначає можливість генерації поданої мови  LL(1)-граматикою?

Відповідь на перше питання негативна. Наприклад, мова L = {R |   (0 + 1)*, що генерується граматикою з правилами

1. S 0S0

2. S 1S1

                                                              3. S  ,                               

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

Відносно другого питання відомо, що  існують  мови,  які  можна генерувати як  LL(1)-граматикою, так і граматикою, що не належить до цього класу. Тому поставлене питання зводиться до такого - чи  існує алгоритм, що  перетворює  будь-яку  подану  граматику  у  еквівалентну  LL(1)-граматику, або встановлює неможливість такого перетворення.  З теорії [1] відомо, що це питання має негативну відповідь, тобто сформульована проблема алгоритмічно нерозв’язна.

На  практиці  виявляється,  що  граматика  для  більшості   мов програмування,  яку  легко  визначити  ("очевидна"  граматика),   не належить до класу  LL(1)-граматик. Оскільки універсального алгоритму для  одержання  еквівалентної  LL(1)-граматики  нема,   у   кожному конкретному випадку застосовують окремі штучні засоби.  Якщо  знайти потрібне  перетворення  не    вдається, то використовують  LL(1)-граматику, що дозволяє перевіряти не усі властивості мови, але якомога  більшу  їх  частину.  Інакше  кажучи, у такому випадку користуються нееквівалентною граматикою.

Розглянемо найбільш поширені окремі штучні засоби переходу  від поданої граматики до еквівалентної  LL(1)-граматики.

Усування лівої рекурсії

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

У випадку, коли одне з альтернативних правил є лівою рекурсією, граматика не належить до класу  LL(1)-граматик,  бо  множини  вибору таких правил, очевидно, перетинаються. Наприклад, для обох правил А А  і  А а  множина вибору містить символ  а.

 Враховуючи,  що  кожна  рекурсія  повинна  мати   альтернативне правило (інакше рядок, одержаний з застосуванням  рекурсії,  завжди буде містити нетермінал), можна стверджувати, що  LL(1)-граматика не містить лівої рекурсії. Аналогічне ствердження  має  місце  відносно ліворекурсивного циклу, приклад якого дають правила  

1. S Aa            4. С  Dd

                                                 2. A Bb            5. С  e

                                                 3. B Сс            6. D Az

Для того, щоб від граматики з ліворекурсивним циклом  перейти до еквівалентної, яка може виявитися LL(1)-граматикою,  спочатку  ліворекурсивний  цикл замінюють лівою рекурсією,  а  потім  останню  замінюють  правою  за допомогою  уведення  додаткових  нетерміналів.   Можливість   такого перетворення  прямує  з  існування  нормальної  форми  Грейбах   для  КВ-граматики.  

У наведеному прикладі правила  2, 3, 4, 6 утворюють ліворекурсивний цикл, який завжди можна вилучити, перетворив одне  з  правил  (наприклад,  6)  у  ліву рекурсію. Оскільки є тільки одне правило, ліва частина якого дорівнює  А, то правило 6 еквівалентне такому  D  Bbz. Аналогічно, користуючись правилом 3, одержуємо   D  Ссbz. Для  С існують два правила - 4 та 5. Тому попереднє правило для  D  еквівалентне двом таким D  Ddcbz  i  D  ecbz.

Отже, перетворена граматика містить такі правила  

1. S Aa            4. С  Dd        7. D Ddcbz

                                 2. A Bb           5. С  e         

                                 3. B Сс           6. D ecbz

 Тепер для того,  щоб  вилучити  ліву  рекурсію,  уведемо  новий  нетермінал  Е  і замінимо останнє правило трьома новими  

D   ecbzE

                                                              E  dcbz

                                                              E  dcbzE

Зрозуміло, що і до перетворення і після   символ  D  породжує регулярну множину  ecbz(dcbz)*.

У загальному випадку, коли нетермінал  А  з’являється  у  лівих частинах  r + s  продукцій,  r  з яких є лівими рекурсіями, а   s  - ні 

А А1    А А2  ... А А r

                                           А  1        А  2  ...    А  s,                    

ці продукції еквівалентні таким

А  1B   А  2B ... А sB

                                              А  1     А  2  ...   А  s 

                                              B  1     B  2  ...   B  r

                                              B  1B  B  2B ...  B   rB.                   

Легко бачити, що і до і після перетворення символ  А породжує регулярну множину   (1|2| … |s)( 1|2| … | r)*. Отже, для вилучення лівих рекурсій можна скласти алгоритм.

Факторізація

Факторізація - це  таке  перетворення  граматики, при якому альтернативні  правила  з  співпадаючими  першими  символами  правих частин  замінюються  на  еквівалентні  правила  з  різними   першими символами у правих частинах.

Розглянемо  факторізацію  на  прикладі граматики з правилами

1. S  

                                                                 2. S  aSb

    3. S  a

Друге  і  третє  правила  у  правій  частині  містять  однакову послідовність  символів   aS.  Кажуть,  що  цю  послідовність  можна винести за дужки (звідси і виникає термін факторізація).

S aSb|aSс  S aS(b|с).

Скориставшись новим нетерміналом  Х, який породжує термінали  b  та  c, можна перейти до еквівалентної граматики  

           1. S  

                                                                       2. S  aSX

                                                                       3. X  b

                                                                       4. X  c

Отримали   LL(1)-граматику, оскільки множини вибору для альтернативних правил тепер не перетинаються.

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

                               1. P  Qx           3. Q  sQm        5. R  sRn

                               2. P  Ry           4. Q  q             6. R  r

Альтернативні правила  для  Р  мають  множини   вибору,   що перетинаються:  

ВИБІР(1) = {s, q},  ВИБІР(2) = {s, r}.                       

Для того, щоб спільний символ  s  винести за дужки,  перетворимо правила для  Р, використовуючи правила для  Q  та  R.

                                      1’.  P sQmx           2’.  P sRny        

                                      1’’. P qx                2’’. P ry             

До цих правил можна застосувати факторізацію

                           1’’’. P sP1           2’’. P ry        2’’’’. P1  Rny

                           1’’.  P qx            2’’’. P1  Qmx             

Але тепер множини вибору правил для  Р1  перетинаються,  і  процес факторізації може продовжуватись до нескінченості.

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

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

struct (int a, b, real x, y).

Так в  Алголі-68 описуються структури, що відповідають  записам у Паскалі. Слова struct, int, real - це ключові слова мови;  a, b, x, y -  ідентифікатори  полів.  У дужках вказується список, що складається з необмеженої  кількості  підсписків.  Кожний  підсписок складається зі слова, що визначає тип полів підсписку, та  наступних ідентифікаторів полів, що розділяються комами. Граматику, що  описує структури, можна подати у вигляді 

                                                S  struct (СПИСОК)                      

                                  СПИСОК ПІДСПИСОК                        

                                  СПИСОК ПІДСПИСОК, СПИСОК                   

                           ПІДСПИСОК ТИП СПИСОК_ІДЕНТ                   

                     СПИСОК_ІДЕНТ ІДЕНТИФІКАТОР

СПИСОК_ІДЕНТ  ІДЕНТИФІКАТОР, СПИСОК_ІДЕНТ

                                           ТИП  real | int.                         

    Якщо до поданої  граматики  застосувати  факторізацію,  то  можна одержати 

                                                 S  struct (СПИСОК)                      

                                   СПИСОК ПІДСПИСОК  X                      

                                                 X  , СПИСОК                   

                                                 X                      

                             ПІДСПИСОК ТИП СПИСОК_ІДЕНТ                   

                     СПИСОК_ІДЕНТ   ІДЕНТИФІКАТОР Y                  

                                                  Y  , СПИСОК_ІДЕНТ

                                                  Y  

                                             ТИП  real | int.                         

Множини вибору правил для нетерміналу  Y  перетинаються - кожна з них містить символ ",". Це означає, що  одержана  граматика  не  є  LL(1)-граматикою. Зробити  потрібне  перетворення  вдається  завдяки іншому варіанту означення нетерміналів 

                                                  S  struct (СПИСОК)                      

                                   СПИСОК ТИП ІДЕНТИФІКАТОР ЗАЛИШОК                      

                                 ЗАЛИШОК , ЕЛЕМЕНТ ЗАЛИШОК                   

                                 ЗАЛИШОК       

                                 ЕЛЕМЕНТ   ТИП  ІДЕНТ ИФІКАТОР                  

                                   ЕЛЕМЕНТ ІДЕНТИФІКАТОР

                                              ТИП  real | int.                         

Від  розглядання   LL(1)-граматик  можна  перейти  до   поняття  LL(k)-граматик (k>1). Така  граматика  для  детермінованого  аналізу потребує переглядання  k  записаних підряд  символів  вхідного  рядка після  поточного  символу.  Існують  алгоритми  аналізу  для   таких граматик,  але  їх   обчислювальна   складність   значно   перевищує складність  LL(1)-методу.

 Оскільки досить широкий клас граматик не  можна  перетворити  у еквівалентну  LL(1)-граматику,  виникає  питання,  чи  існують  інші методи  детермінованого  аналізу  з   перегляданням   тільки   одного чергового вхідного символу. Один з них  -  LR(1)-метод  належить  до класу  висхідних методів або методів аналізу  "знизу вгору".

Висхідний аналіз

Розглянемо граматику  G, утворену такими продукціями

1. S (AS)

                                                          2. S (b)

  3. A (SaA)

                                                          4. A (a)

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

Рис.12.1. Дерево виводу рядка (((b)a(a))(b)).

Розглянемо рядок  (((b)a(a))(b)). Дерево виводу цього рядка показано на рис.12.1.

Правий вивід цього рядка:

 S 1 (AS) 2 (A(b)) 3  ((Sa A)(b)) 4 ((Sa(a))(b)) 2 (((b)a(a))(b)).  

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

(((b)a(a))(b))

                                                                 2  

((Sa(a))(b))

                                                                      4

((SaA)(b))

                                                                    3

(A(b))

                                                                        2

(AS)

1

S

На кожному кроці підрядок, що дорівнює правій  частині  деякого правила замінюється нетерміналом  з  лівої  частини  цього  правила. Кожний такийнаведеному прикладі підкреслений) підрядок називають "основою" рядка, а відповідне правило - "основним правилом" цього рядка. Наприклад,  (а)  -  основа,  а  правило  4  - основне правило рядка ((Sa(a))(b)).

Означення 12.1. Основне правило рядка - це  останнє  правило,  застосоване у правому виводі цього рядка.

Означення 12.2. Основа рядка - це підрядок, що утворюється  при застосуванні основного правила.

Якщо граматика однозначна, кожна  сентенціальна  форма  має  не більш однієї основи і не більш  одного  основного  правила.  Але довільний рядок може і не мати основи. Наприклад, рядок (а)  взагалі не можна вивести з початкового символу  S. Рядок  ((a)S) має вивід  S (AS) ((a)S),  але він не має правого виводу, а це  означає,  що  у  нього  нема  і основи.  

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


 

А также другие работы, которые могут Вас заинтересовать

73659. Латинская патристика IV - V века 150 KB
  Прилагательное латинская приложенное к слову патристика указывая на то внешнее обстоятельство что церковные писатели о которых пойдет речь пользовались преимущественно или только латинским языком вместе с тем нацеливает на выявление некоторых особенностей более существенным образом характеризующих описываемое явление коль скоро перевод с одного языка на другой это всегда в какойто степени переход из одной культурной реальности в другую. Движение это происходит не только в пространстве но и...
73660. Антинаполеоновские коалиции и их противник 37.73 KB
  Троицкий считает что гуманная фразеология дипломатических документов освобождение от ига и цепей Наполеона обеспечение прав и свобод народов это не более чем фиговый листок . Данное обстоятельство в немалой степени обеспечило поражение Наполеона в информационной и идеологической войне а это в свою очередь безусловно повлияло и на достижение конечного победного результата в военных действиях. Поэтому не стоит столь категорично сбрасывать со счетов либеральную...
73661. ПРАКТИКА ИСПОЛЬЗОВАНИЯ АВТОМАТИЗИРОВАННЫХ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ УПРАВЛЕНИЯ 350.5 KB
  Первоначально системы MRP фактически просто формировали на основе утвержденной производственной программы план заказов на определенный период. Термин замкнутый цикл отражал основную особенность модифицированной системы заключающуюся r том что созданные в процессе ее работы отчеты анализируются и учитываются на дальнейших этапах планирования т. Системы типа MRP используют то что зависимый спрос можно прогнозировать поскольку в его основе лежат планы производства. Суть системы MRP состоит в следующем: на базе заказов определяется...
73663. Управление финансовой деятельностью предприятия 79.5 KB
  Управление финансовой деятельностью предприятия Тема включает два раздела: Сущность управления финансовой деятельностью предприятия. Сущность управления финансовой деятельностью предприятия Цели задачи и функции финансового менеджмента. Финансовый механизм и основные инструменты управления финансовой деятельностью предприятия. Финансовая политика предприятия.
73664. Информационное обеспечение управления финансовой деятельностью 68.5 KB
  Управленческий учет как механизм финансового менеджмента Информационное обеспечение предназначено для предоставления управленческому персоналу информации оперативного и финансового учета необходимой для анализа результатов финансово-хозяйственной деятельности предприятия.
73666. Экономическая деятельность земств Поволжья в середине XIX - начале XX века 24.57 KB
  Нижний уровень включал в себя все многообразие учреждений мелкого кредита. Положения об учреждении мелкого кредита. В середине 1890х годов вопрос об организации мелкого кредита обсуждался в земствах в печати; правительство ставило его в программу своих мероприятий для подъема благосостояния сельского населения. Проекты организации мелкого кредита в это время представляли собой попытки объединить в пределах губерний всякого рода мелкие кредитные учреждения.