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

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


 

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

3404. Штамповка поковки типа цилиндр с отростками в условиях мелкосерийного производства на базе ОАО ЭНЕРГОМАШ 8.15 MB
  Технологический раздел. Основной задачей проекта является разработка технологического процесса штамповки поковок деталей жидкостной ракеты. Чертеж детали представлен на рис.1. Материалом изготавливаемой детали является жаропрочный титановый сп...
3405. Теплотехнический расчет теплопередач 58.57 KB
  Задача №1. Расчет теплопередачи через плоскую многослойную стенку Плоская стальная стенка толщиной. Определить коэффициент теплопередачи k от газов к воде, плотность теплового потока q и температуры обеих поверхностей стенки, если известны коэффициенты теплоотдачи от газа к стенке α1 и от стенки к воде α2, коэффициент теплопроводности стали λ....
3406. Расчёт точностных параметров изделий 1.15 MB
  В курсовой работе для заданного механизма назначены посадки для всех сопрягаемых размеров, рассчитана посадка с натягом для соединения 4-7, переходная для соединения 4-6, назначены и рассчитаны посадки для подшипников качения 1, рассчитана размерная...
3407. Расчет крыльевого профиля 122 KB
  Расчет крыльевого профиля. Варианты заданий Все профили симметричные с хордой в = 150 мм и максимальной толщиной с = 14 мм. Параметры потока обтекающего крыловой профиль № варианта № профиля M P(МПА) T(K) k угол атаки угол атаки угол атаки 1 1 3.6 0...
3408. Геометрический расчет и конструирование зубчатых колес 2 MB
  Геометрический расчет и конструирование зубчатых колес Геометрический расчет выполняется в минимальном объеме. Определению подлежат: делительные d1 и d2 и начальные dw1 и dw2 диаметры колес; коэффициенты смещения X1 и X2; диаметры окружностей вершин...
3409. Hазработка технологического процесса штамповки шестерни 165.22 KB
  В данной курсовой работе представлена разработка технологического процесса штамповки шестерни. Курсовая работа состоит из расчетно-пояснительной записки и графической части. В пояснительной записке выбирается метод штамповки, и метод нагрева заготов...
3410. Краны башенные. Строение и назначение 113.09 KB
  Назначение башенных кранов. Башенные краны широко применяются в гражданском, промышленном, энергетическом и гидротехническом строительстве для монтажных работ и работ по вертикальному и горизонтальному перемещению различных грузов. Если на строитель...
3411. Быстрорежущие стали 65.05 KB
  Классификация быстрорежущих сталей Быстрорежущие стали широко применяют для изготовления режущего инструмента, работающего в условиях значительного силового нагружения и нагрева (до 600–640 °С) режущих кромок. К этой группе сталей относятся...
3412. Исследование электромеханических свойств двигателя постоянного тока независимого возбуждения 306 KB
  Исследование электромеханических свойств двигателя постоянного тока независимого возбуждения. Исследовать влияние сопротивления цепи якоря, напряжения питания и магнитного потока на электромеханические и механические свойства двигателя постоянного тока независимого возбуждения, а также изучить способы изменения направления вращения якоря двигателя, построить естественные и искусственные характеристики двигателя.