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.  Номери у круглих дужках  відповідають  прямому  порядку  обходу  вершин,  у квадратних - зворотному, а  у  фігурних  -  внутрішньому.  Останній порядок відповідає інфіксній нотації.


 

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

19020. Принципы построения и постулаты квантовой механики. Операторы физических величин 285 KB
  Лекция 2 Принципы построения и постулаты квантовой механики. Операторы физических величин Как следует из опытов по дифракции микрочастиц в квантовой механике отсутствует понятие траектории т.е. состояние квантовой частицы не описывается заданием координаты и имп
19021. Операторы координаты и импульса: уравнения на собственные значения и собственные функции, разложения, координатное и импульсное представления волновой функции 444.5 KB
  Лекция 3 Операторы координаты и импульса: уравнения на собственные значения и собственные функции разложения координатное и импульсное представления волновой функции Найдем оператор координаты в представлении то есть найдем как действует этот оператор на про
19022. Матрицы операторов. Унитарные преобразования базиса. Соотношения коммутации. Одновременная измеримость физических величин 650 KB
  Лекция 4 Матрицы операторов. Унитарные преобразования базиса. Соотношения коммутации. Одновременная измеримость физических величин. Соотношение неопределенностей Гейзенберга Рассмотрим некоторый линейный оператор :. Выберем в рассматриваемом линейном пространст...
19023. Временное уравнение Шредингера. Общее решение уравнения Шредингера в случае ста-ционарного гамильтониана. Стационарные состояния 380 KB
  Лекция 5 Временное уравнение Шредингера. Общее решение уравнения Шредингера в случае стационарного гамильтониана. Стационарные состояния. Плотность потока вероятности Как следует из постулатов квантовой механики волновая функция удовлетворяет уравнению Шрединг
19024. Зависимость средних от времени. Интегралы движения. Законы сохранения и симметрии. Сохранение четности 614 KB
  Лекция 6 Зависимость средних от времени. Интегралы движения. Законы сохранения и симметрии. Сохранение четности Эволюция квантовой системы во времени определяется временным уравнением Шредингера 1 Поскольку это уравнение является уравнением первого пор...
19025. Общие свойства стационарных состояний одномерного движения для дискретного спек-тра. Квантование энергии в потенциале притяжения. Осцилляционная теорема 1.32 MB
  Лекция 7 Общие свойства стационарных состояний одномерного движения для дискретного спектра. Квантование энергии в потенциале притяжения. Осцилляционная теорема Пусть потенциальная энергия частицы зависит только от координаты : Тогда поскольку потенциальн
19026. Бесконечно глубокая прямоугольная потенциальная яма. Спектр, стационарные состоя-ния, разложения по собственным функциям гамильтониана, средние 434.5 KB
  Лекция 8 Бесконечно глубокая прямоугольная потенциальная яма. Спектр стационарные состояния разложения по собственным функциям гамильтониана средние Пусть потенциальная энергия частицы равна бесконечно глубокая потенциальная яма шириной см. рисунок. Най...
19027. Гармонический осциллятор. Уровни энергии и волновые функции (решение в виде ряда) 615.5 KB
  Лекция 9 Гармонический осциллятор. Уровни энергии и волновые функции решение в виде ряда Одномерным гармоническим осциллятором называется частица движущаяся в потенциале где масса частицы число имеющее размерность сек1 в случае классического движения ча
19028. Гармонический осциллятор. Уровни энергии и волновые функции (решение с помощью операторов рождения и уничтожения) 1.04 MB
  Лекция 10 Гармонический осциллятор. Уровни энергии и волновые функции решение с помощью операторов рождения и уничтожения Сегодня мы рассмотрим другой способ решения задачи о гармоническом осцилляторе. Вопервых этот способ и сам по себе поучительный а вовторых ...