68826

Порівняння LL- та LR-методів розбору

Лекция

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

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

Украинкский

2014-09-26

180 KB

1 чел.

Лекція 14

Порівняння  LL-  та  LR-методів розбору

Як  LL-, так і  LR-методи мають багато позитивних рис.  Головна з них полягає у тому, що обидва методи детерміновані.  LR-метод  має ту перевагу, що він застосовується до більш широкого класу мов і, як правило, не  потребує  перетворення  граматики.  Оцінюючи  в  цілому  LR-метод, слід зауважити, що його можна застосовувати до будь-якої мови, яка допускає детермінований розбір. Зокрема,  усі   LL(1)-мови мають  властивість   LR(1).  Це  пояснюється  тим,  що  рішення  про застосування конкретного правила під час  LL(1)-розбору базується на заміні нетермінала в сентенціальній формі  з  врахуванням  чергового символа під головкою читання. Цей символ, як і у  LR(1)-методі можна вважати завчасно проглянутим. В той же час правило для  застосування у  LR(1)-методі визначається, коли у магазині знаходиться уся  права частина правила, а під головкою читання відповідний вхідний  символ. Таким чином можна вважати, що у   LR(1)-методі  використовується  не менш   інформації,  ніж  у   LL(1)-методі.  Разом з тим існують  LR(1)-мови, що не належать до  LL(1)-класу.

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

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

Генерація коду, проміжний код, транслююча граматика

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

Надалі будемо вважати, що генерація машинного коду  складається з двох етапів: 1) генерація не залежного від машини проміжного  коду (об’єктного коду); 2) генерація машинного  коду  (коду  збирання)  для конкретної машини.

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

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

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

Будемо позначати символами у фігурних дужках дії, що треба  виконати для створення проміжного коду.  Наприклад,  {a} буде означати, що треба записати символ  “а”  у файл, де формується проміжний код.  Якщо символи у  дужках записати на певних місцях  у  правих  частинах продукцій і домовитись, що   ДМП-автомат  буде  видавати  на  виході (записувати у файл) ці  символи  кожного разу, коли такий символ з’являється у вершині магазину, то тоді  паралельно  з  синтаксичним аналізом буде створюватись проміжний код.

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

Розглянемо приклад. Нехай надана  s-граматика, у  яку  включено символи дій. Припустимо, що застосовується  низхідний метод розбору, у вершині магазину знаходиться нетермінал  А, і правило  з  символом  А  у лівій частині має вигляд   А  {v}a{w}B{x}c{y}. Тоді у наступному такті права  частина  цього  правила  потрапить  у магазин. Далі автомат повинен видати символ  v  і виштовхнути його з магазину. Наступний такт полягає у виштовхуванні з магазину  символу  а  у разі співпадання його з символом під головкою  читання. Одночасно виконується зсув входу. Потім виштовхується  і  видається символ  w, застосовується правило з символом  В  у лівій  частині  і так далі.

Отже, включення символів дій у граматику дає змогу сумістити генерацію  проміжного коду і синтаксичний аналіз. Можна також застосовувати інші символи дій для того, щоб під  час  синтаксичного аналізу будувати таблиці символів та звертатися до них. Перш за  все такий підхід реалізується у однопроходних  компіляторах,  але  часто застосовується і у інших. Розглянемо застосування  включення символів дій у вхідну граматику.

Обробка арифметичних виразів з використанням тетрад та тріад

    Нехай граматика Ga, що визначає арифметичні вирази має вигляд

1. E T          3. T F         5. F - F    7  F x|y|z

                         2. E E + T   4. T T * F   6. F (E)

 Приклади виразів: 

( x + y ) * z,

x * y + z,

- x * y + x * y * z.

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

x + y = 1

1 * z = 2,

а третьому

                                                                    - x = 1

1 * y = 2

x * y = 3

3 * z = 4

                                                                2 + 4 = 5.

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

Граматика тетрад містить такі правила

                                  ТЕТР ОП1 ОПЕРАНД = ЦІЛЕ

ТЕТР ОПЕРАНД ОП2 ОПЕРАНД = ЦІЛЕ

                        ОПЕРАНД ЦІЛЕ 

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

                                  ЦІЛЕ ЦИФРА

                                  ЦІЛЕ ЦИФРА ЦІЛЕ

                             ЦИФРА 0|1|2|3|4|5|6|7|8|9

           ІДЕНТИФІКАТОР  x|y|z

                                   ОП1 -

                                   ОП2 +|*.

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

1. E  T          3. A +T         

                                               2. E TA        4. A +TA

Після факторізації маємо

1. E   TB          3. B            

                                                  2. B   A            4. A  +TB

Зробивши підстановку отриманого четвертого правила у друге і замінивши символ  B  на  A, отримуємо три правила, що еквівалентні першим двом вихідної граматики

1. E  TA         2. A  +TA          3. A   

Після аналогічного перетворення третього та четвертого правил граматики  Ga отримуємо еквівалентну  LL(1)-граматику

1. E   TA       3. A          5. B *FB     7.  F -F       9. F x|y|z

             2. A +TA      4. T FB      6. B           8. F (E)

з такими множинами вибору для альтернативних правил

ВИБІР(2)={+}, ВИБІР(3)={, )}, ВИБІР(5)={*}, ВИБІР(6)={+, , )}

ВИБІР(7)={-}, ВИБІР(8)={ ( }, ВИБІР(9)={x, y, z}.

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

         1. E  TA                       4. T  FB                        7. F  -{-}F{n1}

         2. A  +{+}T{n2}A      5. B  *{*}F{n2}B        8. F  (E)

         3. A                           6. B                             9. F  x{x}|y{y}|z{z}

Символом   n1   позначено  дію,   що    відповідає   закінченню утворення чергової тетради у разі унарної операції, а  n2 -  у  разі бінарної. Послідовність тактів  ДМП-автомату, при аналізі рядка   - x * y + x * z   показано у табл.14.3.

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

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

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

Наприклад, виразу   x + y + x * z   відповідає послідовність тетрад
x
+ y = 1
x
* z = 2
1 + 2 = 3.

Табл.14.3

Вхід

Магазин

Адр.

Правило

Стек

Вихід

-x*y+x*z

E

0

1

-x*y+x*z

TA

0

4

-x*y+x*z

FBA

0

7

-x*y+x*z

-{-}F{n1}BA

0

ЗСУВ

x*y+x*z

{-}F{n1}BA

0

ВШТ.

-

x*y+x*z

F{n1}BA

0

9

-

x*y+x*z

x{x}{n1}BA

0

ЗСУВ

-

*y+x*z

{x}{n1}BA

0

ВШТ.

a-

*y+x*z

{n1}BA

1

ВИШТ.

1

-a=1

*y+x*z

BA

1

5

1

*y+x*z

*{*}F{n2}BA

1

ЗСУВ

1

y+x*z

{*}F{n2}BA

1

ВШТ.

*1

y+x*z

F{n2}BA

1

9

*1

y+x*z

y{y}{n2}BA

1

ЗСУВ

*1

+x*z

{y}{n2}BA

1

ВШТ.

y*1

+x*z

{n2}BA

2

ВИШТ.

2

1*y=2

+x*z

BA

2

6

2

+x*z

A

2

2

2

+x*z

+{+}T{n2}A

2

ЗСУВ

2

x*z

{+}T{n2}A

2

ВШТ.

+2

x*z

T{n2}A

2

4

+2

x*z

FB{n2}A

2

9

+2

x*z

x{x}B{n2}A

2

ЗСУВ

+2

*z

{x}B{n2}A

2

ВШТ.

x+2

*z

B{n2}A

2

5

x+2

*z

*{*}F{n2}B{n2}A

2

ЗСУВ

x+2

z

{*}F{n2}B{n2}A

2

ВШТ.

* x+2

z

F{n2}B{n2}A

2

9

* x+2

z

z{z}{n2}B{n2}A

2

ЗСУВ

* x+2

{z}{n2}B{n2}A

2

ВШТ.

z*x+2

{n2}B{n2}A

3

ВИШТ.

3+2

x*z=3

B{n2}A

3

6

3+2

{n2}A

4

ВИШТ.

4

2+3=4

A

4

2

4

4

STOP

4

Відповідна послідовність тріад має вигляд

x + y

x * z

1 + 2

Остання тріада показує, що обчислюється сума результатів  першої  та другої тріад.

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

Як тріади, так і тетради застосовують не тільки для уявлення арифметичних  виразів, але  і  для  інших  конструкцій.  Наприклад, присвоєння x := y   у вигляді тетради записується як  x := y = 1, а у вигляді тріади -  x := y.                              

Аналогічно, умовний оператор  if a then b else c  можна записати як тетраду або тріаду з трьома операндами.

Префіксні, постфіксні та інфіксні нотації

Розповсюдженими формами проміжного коду є також префіксна та постфіксна  нотації. У префіксній нотації  кожний  знак  операції безпосередньо передує своїм операндам, а у постфіксній записується безпосередньо після них. Звичайна форма арифметичних  виразів,  коли знак операції записується  між  операндами,  називається  інфіксною. Інфіксний вираз   x + y  у префіксній нотації приймає вигляд  + x y, а у постфіксній - x y +.                               

Префіксна нотація відома також як польський запис (за назвою батьківщини її автора - математика  Лукашевича), а постфіксна  -  як зворотний польський запис. За допомогою цих нотацій можна записувати складні вирази. Наприклад, вираз  ( x + y ) * ( z + u )  у префіксній формі записується як  * + x y + z u,  а у постфіксній -  x y + z u + *.                           

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

                           (1)

                        [7]          {4}

           (2)                                      (5)

        [3]          {2}             [6]         {6}

(3)                        (4)   (6)                       (7)

         {1}     [2]                               [5]    

                

[1]                     {3}     {5}                   {7}    

Рис.14.1.Дерево арифметичного виразу

               (x+y)*(z+u).

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

Прямий порядок (корень - лівий син - правий син) обходу цього дерева дає префіксну нотацію, а зворотний (лівий син  - правий син  -  корень)  -  постфіксну.  Наприклад,  для  останнього розглянутого інфіксного виразу дерево зображено на рис.14.1.  Номери у круглих дужках  відповідають  прямому  порядку  обходу  вершин,  у квадратних - зворотному, а  у  фігурних  -  внутрішньому.  Останній порядок відповідає інфіксній нотації.


 

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

44123. Формирование и развитие рынка речных круизов в Перми и Пермском крае на примере туристической фирмы ООО «Кубань» 838 KB
  Основные понятия рынка и государственное регулирование сферы туризма в России Переход страны к рыночной экономике сопровождается постепенным созданием конкурентной среды во всех отраслях современного туризма в том числе и в сфере речного круизного туризма. В российской экономической литературе вопросам туризма посвящено немало научных исследований. Таким образом планируется рассмотреть проблемы и сформировать программы развития туризма регионального муниципального уровней в которых предстоит разработать и реализовать комплекс мер...
44124. Проектирование районной понизительной подстанции 356.24 KB
  На данной подстанции по ПУЭ устанавливается 2 трансформатора, это делается из-за того что на ней присутствуют потребители I и II категории. Перерыв в электроснабжение которых для I категории допускается лишь на время автоматического восстановления питания, а для II категории – на время
44125. Оценка стоимости недвижимости. Анализ ипотеки в Барнауле и Алтайском крае 1.09 MB
  Мне было дано провести анализ по оценки объекта недвижимости в городе Барнаулея взял как примержилой дом находящегося по адресу: г. Оценка стоимости недвижимости процесс определения рыночной стоимости объекта или отдельных прав в отношении оцениваемого объекта недвижимости. Оценка стоимости недвижимости включает: определение стоимости права собственности или иных прав например права аренды права пользования и т. в отношении различных объектов недвижимости.
44126. Создание электронного библиотечного каталога 1.79 MB
  На практике это означает выполнение автоматизированной обработки новых поступлений в библиотеку; освобождение сотрудников от ряда рутинных работ по подготовке картотек изданий списков заказов писем отчетной документации; создание базы данных о поступлениях; осуществление операций по созданию и копированию тематических архивов литературы. Благодаря автоматизации с минимальными временными затратами можно выполнять следующие функции: предметный поиск информации по запросам читателей; обслуживание баз данных информационных и периодических...
44127. Проект управління якістю продукції в ВАТ “Поліграфкнига” 961 KB
  В ринковій економіці велике значення приділяється проблемам якості. За методами забезпечення конкуренція поділяється на цінову (конкуренція за рахунок зниження ціни) та нецінову, при якій за ту ж саму ціну виробник пропонує товар з більш високими якісними параметрами та комплексом послуг. Тільки якість може привернути увагу споживача
44128. Адольф Гитлер: политико-психологический портрет 353.5 KB
  Личность Адольфа Гитлера поэтому представляет и будет представлять собой особой интерес. Так как за всю историю XX века, пожалуй, не найти личность, о которой было бы сложено столько различных предрассудков и стереотипов.
44129. Построение и проверка локальной логической модели данных 524.5 KB
  Например объект работник безусловно является сущностью потому что любой работник существует независимо от того знаем мы его имя адрес и номер телефона или нет. Сведения об атрибутах Тип сущности Атрибут Описание Тип данных длина Ограничения Допустность NULL Производный Отдел Отдел_№ Уникальный идентификатор отдела компании Целое Первичный ключ нет нет Отдел_Имя Наименование отдела Символьный до 50 символов нет нет Тел_№ Номер телефона отдела Символьный фиксированный 13 символов Альтернативный ключ нет нет Факс_№ Номер факса...
44130. Государственное регулирование бюджетного процесса на федеральном и региональном уровнях 419 KB
  Центральное место в финансовой системе любого государства занимает государственный бюджет - имеющий силу закона финансовый план государства (роспись доходов и расходов) на текущий (финансовый) год. Новый Бюджетный кодекс Российской Федерации (БК РФ) определяет бюджет как «форму образования и расходования фонда денежных средств, предназначенных для финансового обеспечения задач и функций государства и местного самоуправления»
44131. Системний аналіз предметної області – процесу зборки регулятора напруги 143 KB
  Огляд методів моделювання й опису процесів. Методи імітаційного моделювання. Постановка задачі моделювання виробничого процесу зборки регулятора напруги. Розробка математичної моделі виробничого процесу зборки регулятора напруги.