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),  але він не має правого виводу, а це  означає,  що  у  нього  нема  і основи.  

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


 

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

20317. Европейская культура средневековья: философия, архитектура, литература, театр, музыка 107.5 KB
  Содержание: Введение Особенности культуры западноевропейского Средневековья Аспекты интеллектуальной и художественной культуры западноевропейского Средневековья: Философия Литература Театр и драматургия Музыка Архитектура и строительство Изобразительное искусство Заключение Литература Введение Средние века это время которое находится посередине между Античностью и Новым Временем и по какойто невероятной причине не имеет своего собственного названия.222 14] Историческая ситуация средних веков не может быть както однозначно...
20318. Русское актерское искусство второй половины XX века 98.5 KB
  Восстановление зданий театров развитие киносети расширение издательской деятельности все это создавало необходимые условия для оживления культурной жизни общества. вышли постановления ЦК ВКПб: €œО журналах €œЗвезда€ и €œЛенинград€ €œО репертуаре драматических театров и мерах по его улучшению€ €œО кинофильме €œБольшая жизнь€ €œОб опере €œВеликая дружба€ В. В этих постановлениях писатели журналисты композиторы деятели кино и театра обвинялись в аполитичности и безыдейности в пропаганде буржуазной идеологии. Лишение поддержки со...
20319. Творческое сотрудничество режиссера и художника 123.5 KB
  ОСНОВНЫЕ ПРИНЦИПЫ СОВРЕМЕННОЙ РЕЖИССУРЫ Режиссерское искусство заключается в творческой организации всех элементов спектакля с целью создания единого гармонически целостного художественного произведения. Но такая случайная неофициальная режиссура редко доводила задачу создания идейнохудожественного единства спектакля до конца: разнобой между отдельными его элементами в той или иной степени оказывался неизбежным. Это же происходило и в тех случаях когда коллектив не имея единоличного руководителя сам пытался добиться творческой...
20320. Русский театр второй половины ХVIII- начале XIX века 1.08 MB
  Театральная жизнь в XIX веке не просто развивалась она по настоящему зацвела. Именно в это время стали появляться первые театры сохранившиеся по сей день писаться пьесы тематика которых актуальна и сегодня и наконец именно в этом столетии появились первые актеры и театральные критики чьи имена вошли в историю искусства. Театральное искусство этого времени прощалось с екатерининской эпохой с ранним русским классицизмом. Вторым по значимости историческим событием оказавшим влияние на становление театра в XIX веке стало восстание...
20321. Основные этапы развития сцены 40.5 KB
  Читай Базанова Основные этапы развития сцены и ее техники Базанов В.Между тем в мире происходят интересные процессы поиска современной сценической архитектуры техники и технологии сцены. А поскольку театр является заказчиком проекта то его специалистам необходимо знать не только основы построения сцены и ее оборудования но и современные тенденции развития и обогащения театрального пространства.
20322. Русский театр второй половины XIX века 314.5 KB
  в истории русского театра наступает новая эпоха на сцене появляются пьесы великого русского драматурга А. Драматургия Островского это целый театр и в этом театре выросла плеяда талантливейших актеров прославивших русское театральное искусство. на сцене Малого театра когда была сыграна комедия Не в свои сани не садись. После первой постановки комедии Не в свои сани не садись Островский все свои пьесы отдает на сцену Малого театра.
20323. Театрально-декорационное искусство на современном этапе 97 KB
  Сценография как синоним декорационного искусства. Поэтому как считают некоторые исследователи он не отвечая сути современного искусства лишь характеризует определенный период развития сценического оформления базирующийся на чисто живописных приемах станковой живописи. Вот почему в настоящее время синонимом декорационного искусства стал термин сценография. К тому же если история декорационного искусства создается в основном на изучении эскизного материала художников то история сценической графики должна ориентироваться на всю...
20324. Культура эпохи Просвещения в Западной Европе и России 469.5 KB
  Западноевропейская культура эпохи Просвещения 3 2. Главные ценности эпохи Просвещения 4 3. Особенности Просвещения в странах Европы 8 3.
20325. Русский театр конца XX века 203 KB
  Началом того театра который нам привычен и знаком следует считать времена оттепели. Знаменитый двадцатый съезд КПСС перевернувший всю страну своим осуждением культа личности перевернул и театр. Появление театра ориентированного на современную драматургию и пытающего осмыслить происходящее сегодня было только делом времени.