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

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


 

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

32818. Философское значение творчества российских ученых-естествоиспытателей 13.47 KB
  Это позволяет ученому сделать заключение о том что под влиянием научной мысли и человеческого труда биосфера неизбежно должна перейти в новое состояние – в ноосферу высший завершающий и закономерный этап в эволюции биосферы. Вернадский рассматривал переход биосферы в ноосферу как явление планетарного масштаба подчеркивая что на новом этапе эволюции человечество своей жизнью стало единым целым. В статье Несколько слов о ноосфере опубликованной в 1944 году во время разрушительной мировой войны ученый тем не менее утверждает:...
32819. Особенности формирования и характерные черты западноевропейской фил. 20 в 14.25 KB
  ХХ век в мировой истории характеризуется рядом особенностей: небывалый научнотехнический прогресс результаты которого значительно изменили облик мира и человека. В то же время развитие науки и техники породило множество проблем; стремительность масштабность и радикальность изменений происходящих в мире и в жизни общества; глобализация происходящих процессов: научнотехнические достижения становятся достоянием всего мира возникающие проблемы также носят глобальный характер; демократизация политической сферы; глубокий кризис в...
32820. Философия экзистенциализма 14.78 KB
  Философия экзистенциализма. Идеи экзистенциализма оказали большое влияние на литературу театр кино многие его представители – люди искусства. Философия экзистенциализма носит индивидуалистический характер. Важнейшая категория экзистенциализма – смерть.
32821. «Философия жизни», как одно из основных направлений западноевропейской философии 20 в 14.13 KB
  Одним из вариантов стала философия жизни. Все существующее представители этого направления рассматривали как проявление некой первоначальной реальности – жизни недоступной ни чувственному ни рациональному познанию и постигаемой только интуитивно в результате непосредственных переживаний. Противопоставляя науке и разуму интуицию и инстинкт философия жизни представляет собой антисциентистское иррационалистическое направление.
32822. Философия неопозитивизма 16.04 KB
  Бурное развитие науки и техники формирование сциентизма как особого умонастроения стали причиной формирования ряда философских направлений в центре внимания которых проблема науки как феномена культуры а также вопросы методологии научного познания. Он выступил с идеей о неспособности философии ответить на вопросы поставленные развитием науки. Неопозитивизм уходя от решения коренных философских проблем сосредотачивается на частных логикометодологических исследованиях на анализе языка науки. Логический позитивизм спекулирует на реальных...
32823. Философия психоанализа 14.61 KB
  В центре внимания Фрейда – проблема бессознательного. Содержание бессознательного Фрейд сводит к двум видам влечений – сексуальные инстинкты либидо и влечение к жизни направленное на самосохранение оба влечения он выводит из комплекса Эдипа и комплекса электры. Юнг разработал концепцию коллективного бессознательного. Содержанием коллективного бессознательного являются врожденные образы символы – архетипы.
32824. Религиозная философия ХХ в 14.56 KB
  Ее основной чертой является стремление осмыслить проблемы современного человека с позиций христианской религии. Основные идеи Ф Аквинского: о структуре мироздания о соотношения веры и разума о месте человека в мире – являются основой неотомизма. Характерные черты этого направления отличающие его от томизма – внимание к проблемам современного мира и к внутреннему миру человека.Аквинским но расходится с ним в понимании отношения Бога и человека.
32825. Философская герменевтика. Проблема понимания в философии и медицине (медицинская герменевтика) 12.91 KB
  Философская герменевтика. Проблема понимания в философии и медицине медицинская герменевтика. В Древней Греции герменевтика представляла собой искусство толкования иносказаний а позднее – поэтических произведений особенно поэм Гомера. В самостоятельную область знания герменевтика выделилась в XIX в.
32826. Бытие и материя. Категория материя. Ее признаки 17.66 KB
  Бытие – основополагающая философская категория отражающая единство мира и целостность его существования. Бытие – предельно широкое по объему понятие охватывающее все существующее. Понятие бытие введено Парменидом IV в. Для объяснения этого понятия было введено противоположное ему понятие – небытие.