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


 

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

84888. CAN YOU TRACK YOUR OWN TRACKS 27 KB
  Knowing where your track is going and being able to find the articles is important. So important that it is time for you to go to the tracking field, without your dog, and lay a typical track. Age it for whatever time you usually age your tracks.
84889. Force Tracking training using articles 84 KB
  Dogs learn that articles are safe spots, rest spots, reward spots. Initially you will lay a straight line track with 20-30 articles. There will be an article at the scent pad. When the dog downs at ANY article you will reward (leaving the article) pet keeping the dog calm, then pick up the article...
84890. Force Track Training (the beginning) 40 KB
  I start with getting the dog to understand the platz for the long down and the article indication. When I train the platz, it is like saying my dog is ready for formal training. Up to this point, it has just been a down and was for fun and a behavioral response.
84891. Handling at Tracking Tests 28.5 KB
  It is not uncommon for a handler to help the dog find the track in a training session, especially when the dog is honestly trying to work out a difficult problem. The last thing you want to do in training is make tracking so difficult that the dog gets frustrated, thereby learning to dislike tracking.
84892. Hard Surface Tracking With the Rotterdam Holland Police 316.5 KB
  In September of this year I went back to the Police Dog Training Center in Rotterdam Holland with my friend Kevin Scheldahl. We went there with the expressed purpose of getting as much information as possible on hard surface tracking.
84893. Litter Tracking Imprinting 48.5 KB
  I leave them to their business and watch which ones seem most intense and which ones wander off. I especially note which ones stay the longest and which ones return hours later to search the same track. When this is the same puppy, I know I have a star.
84894. Расчёт показателей эксплуатационной надёжности эталонных конструкций верхнего строения пути 102.2 KB
  Расчёт показателей эксплуатационной надёжности эталонных конструкций верхнего строения пути Расчёт количества эталонных объектов пути Оценка показателей эксплуатационной надежности технического состояния элементов верхнего строения пути на различных участках зависит от видов и типов конструкций находящихся в различных условиях эксплуатации окружающей среды а также изза влияния других факторов. Расчет...
84895. Исследование характеристик машин переменного и постоянного тока в различных режимах работы: учебно-методическое пособие 1.48 MB
  Приведены методики и примеры расчета асинхронного двигателя с фазным и короткозамкнутым ротором в различных режимах работы, а также двигателя постоянного тока. Содержатся основные технические данные двигателей различных типов.