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

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


 

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

65117. Из истории изучения формирования тюркоязычного населения Пермского края 63.5 KB
  Тюркоязычное население Пермского края татары и башкиры длительное время поддерживали интенсивные этнические контакты. Именно поэтому история изучения формирования пермских татар и башкир рассматривается вместе.
65118. К вопросу о клановой принадлежности Тайбугидов (по русским и тюркским источникам) 45 KB
  Носители титула Сибирский князь Тайбугиды возводимые в сохранившихся в составе так называемых Сибирских летописей родословных к некоему князю Тайбуге см. Родословная их согласно Сибирским летописям выглядит так: I II III IV Царь Он князь Тайбуга князь Ходжа князь Мар Адер Одер...
65119. К вопросу об этносоциальной структуре татарских ханств (на примере Казанского и Касимовского ханств ХV-сер. ХVI вв.) 49.5 KB
  Более чем двухвековой спор сторонников булгарского и золотоордынского ("татарского") происхождения волго-уральских татар сегодня приобретает новый импульс. Объясняется это тем, что появился целый ряд новых исследований, раскрывающих роль золотоордынско-тюркского компонента в формировании татар Поволжья.
65120. Чингисхан. Формирование личности Темучжина 117.5 KB
  В давнем споре эпоха ли создает личности или личности формируют эпоху нет пока ни победителей ни побежденных. Эпоха несомненно сыграла огромную роль в формировании личности Темучжина будущего Чингисхана. В любом случае это было время когда первое еще дочингисовское государство монголов именовавшееся...
65121. ИСТОРИЯ ТИБЕТА С ДРЕВНЕЙШИХ ВРЕМЕН ДО НАШИХ ДНЕЙ 2.26 MB
  Далайлама XIV покинул Тибет что тоже осложнило и осложняет продвижение Тибета по пути преобразований. Б Дхармасале Индия размещается эмигрантское правительство Тибета возглавляемое Далайламой. В хронике Далайламы V говорится...
65122. Медные джучидские монеты XV века 70 KB
  Особенностью этих пулов является форма начертания слова чекан. Тем же резчиком очевидно делались и штемпеля для чеканки аверса пулов с изображением утки в картуше. Опираясь на фактурные признаки не характерные для пулов предыдущего периода.
65123. ПО ПОВОДУ ОДНОГО «ОТКРЫТИЯ» В ДЖУЧИДСКОЙ НУМИЗМАТИКЕ 38 KB
  На основании этих данных усугубленных грамматически ошибочным чтением строки 2 в первом издании во втором; перевод не соответствует ни тому ни другому: Да будет счастлив этот год Лебедев выстраивает следующую логическую цепочку...
65124. СТАРЫЙ И НОВЫЙ САРАЙ - СТОЛИЦА ЗОЛОТОЙ ОРДЫ 61 KB
  В археологической и исторической литературе последнего столетия посвященной проблемам истории Золотой Орды и государств соприкасавшихся с ней указываются обычно две столицы Сарай и Новый Сарай. Арабский писатель Эломари ал Омари рассказывая о делах в Улусе Джучиевом приводит два описания города Сарая...
65125. ДЖУЧИДСКИЕ МОНЕТЫ В КОНТЕКСТЕ ТЮРКСКОЙ И МУСУЛЬМАНСКОЙ КУЛЬТУР 69.5 KB
  Воины Чингизхана конем и мечём перекраивали карту континента. Кроме этого полновесные из хорошего серебра монеты должны были помочь ханам Золотой Орды в политике протекции торговле и привлечении иностранных купцов на рынки восстановленных и новопостроенных городов.