68841

Визначення множин вибору продукцій (продовження)

Лекция

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

Розглядається права частина кожного правила, починаючи з лівого символу. Якщо поточний символ - термінал, то він включається у множину ПЕРШ для поданого правила, і процес зупиняється. В іншому разі у множину, що формується, включається множина ПЕРШ для поточного нетермінала, і якщо цей нетермінал анулює...

Украинкский

2014-09-26

242 KB

0 чел.

Лекція 11

Визначення множин вибору продукцій (продовження)

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

Для граматики  G  маємо

        ПЕРШ(1) = {a, c, d},  ПЕРШ(2) = {a, c},  ПЕРШ(3) = {d},  ПЕРШ(4) = {d},

ПЕРШ(5) = ,    ПЕРШ(6) = {c},  ПЕРШ(7) = {a},   ПЕРШ(8) = ,

ПЕРШ(9) = {с}, ПЕРШ(10) = {d},     ПЕРШ(11) = {e},  ПЕРШ(12) = .

Крок 6.

А  ПРЯМО_ПЕРЕД  В

                                                       Табл.11.1

S

X

Y

R

P

Q

V

T

U

Z

a

c

d

e

S

 

 

X

1

 

 

Y

 

1

R

1

 

P

1

 

Q

 

V

 

T

1

 

U

 

Z

a

1

c

1

d

1

e

1

тоді і тільки тоді, коли у поданій граматиці         існує правило  С  АВ, де - рядок, що анулює,  ,  - довільні рядки символів словника. 

Це відношення будується у результаті  послідовного  перегляду усіх правил.

Для граматики  G  матриця відношення  А ПРЯМО_ПЕРЕД В має вигляд наведений у табл.11.1.

Крок 7.

А  ПРЯМО_НА_КІНЦІ  В

тоді і тільки тоді, коли подана граматика містить правило  В  А, де - рядок, що анулює, а - довільний рядок символів словника.

Це відношення також  будується  послідовним  переглядом  усіх правил.

Матрицю  відношення А   ПРЯМО_НА_КІНЦІ   В   для  граматики G показано у вигляді табл.11.2. 

Крок 8. Відношення

А  НА_КІНЦІ  В

це рефлексивно-транзитивне замикання попереднього відношення.

Матрицю   А   НА-КІНЦІ   В   для  граматики   G     показано   у табл.11.3.

Крок 9. Відношення

А  ПЕРЕД  В

виконується тоді і тільки тоді, коли існує  сентенціальна  форма,  у якій  безпосередньо  після   А   прямує   В.  Відношення   ПЕРЕД   є добутком відношень 

НА_КІНЦІ х ПРЯМО_ПЕРЕД х ПОЧИНАЄТЬСЯ_З,

                                           Табл.11.2

S

X

Y

R

P

Q

V

T

U

Z

a

c

d

e

S

 

 

X

 

 

 

Y

1

 

R

 

P

1

 

Q

1

 

V

1

 

T

 

 

U

1

 

Z

1

a

1

c

1

1

d

1

e

1

                                           Табл.11.5

S

X

Y

R

P

Q

V

T

U

Z

a

c

d

e

S

 

 

 

X

 

1

1

 

 

1

1

Y

 

 

 

1

R

 

1

 

1

P

 

1

1

 

1

1

1

 

1

Q

 

1

1

1

 

1

V

 

 

 

1

 

T

 

1

 

1

U

 

1

 

1

 

Z

 

 

a

 

1

1

 

1

1

1

c

 

1

1

 

1

 

1

1

1

1

1

d

 

1

1

1

e

 

1

 

1

                                           Табл.11.4

S

X

Y

R

P

Q

V

T

U

Z

a

c

d

e

S

 

 

 

X

 

1

 

 

Y

 

 

 

1

R

 

1

 

P

 

1

 

1

 

Q

 

1

 

V

 

 

 

1

 

T

 

1

 

U

 

1

 

 

Z

 

 

a

 

1

 

1

c

 

1

 

1

 

1

1

d

 

1

1

e

 

1

 

1

оскільки з А НА_КІНЦІ В, В ПРЯМО_ПЕРЕД С    та    С  ПОЧИНАЄТЬСЯ_З  В  прямує  А  ПЕРЕД  В.

                                           Табл.11.3

S

X

Y

R

P

Q

V

T

U

Z

a

c

d

e

S

1

 

 

X

1

 

 

 

Y

1

1

 

R

1

 

 

P

1

1

 

Q

1

1

 

V

1

1

1

 

T

1

 

 

U

1

1

 

Z

1

1

a

1

1

1

c

1

1

1

1

1

1

d

1

1

e

1

1

1

 

Добуток матриць   НА-КІНЦІ  х  ПРЯМО-ПЕРЕД   для  граматики   G  показано у  табл.11.4,  а  матрицю  відношення   А   ПЕРЕД   В  -  у табл.11.5.

                                                Табл.11.6

S

X

Y

R

P

Q

V

T

U

Z

a

c

d

e

S

 

 

 

1

X

 

1

1

 

 

1

1

Y

 

 

 

1

1

R

 

1

 

1

P

 

1

1

 

1

1

1

 

1

Q

 

1

1

1

 

1

V

 

 

 

1

 

1

T

 

1

 

1

 

U

 

1

 

1

 

Z

 

 

1

a

 

1

1

 

1

1

1

c

 

1

1

 

1

 

1

1

1

1

1

1

d

 

1

1

1

 

e

 

1

 

1

 

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

Отже, розширення відношення  ПЕРЕД   полягає  у  додаванні  до матриці цього  відношення  стовпця,  що  відповідає  символу   S   у матриці відношення  НА-КІНЦІ.

    Розширену матрицю відношення  А  ПЕРЕД   В   для  граматики   G показано у табл.11.6.

    Крок  11.  Обчислення  множин   НАСТ для кожного не терміналу, що анулює,  виконується за допомогою розширеної  матриці  відношення ПЕРЕД, оскільки  А  НАСТ(В) тоді і тільки тоді, коли В  ПЕРЕД  А. 

Для нетерміналів, що анулюють,  одержуємо

НАСТ(X) = {d}, НАСТ(P) = {a, d}, НАСТ(Q) = {d}, НАСТ(Z) = {}.   

    Крок  12.  Обчислення  множин  вибору   для   кожного   правила виконується на підставі знайдених множин  ПЕРШ  та  НАСТ.

Якщо знайдені  множини  вибору  для  альтернативних  правил  не перетинаються, граматика належить до класу  LL(1)-граматик  і  можна побудувати еквівалентний  ДМП-автомат.

Множини вибору  для  кожного  правила  граматики   G  приймають відповідно значення 

ВИБІР(1) = {a, c, d},  ВИБІР(2) = {a, c, d},  ВИБІР(3) = {d},  ВИБІР(4) = {d},

ВИБІР(5) = {a, d},   ВИБІР(6) = {c},  ВИБІР(7) = {a},  ВИБІР(8) = {d},

ВИБІР(9) = {c},  ВИБІР(10) = {d},   ВИБІР(11) = {e},   ВИБІР(12) = {}.

Отже,  G  є  LL(1)-граматикою.

LL(1)-таблиці розбору

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

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

Якщо верхній  символ  стеку  -  нетермінал,  то  застосовується правило граматики, ліва частина якого є цей  нетермінал,  а  множина  ВИБІР   містить  вхідний  термінал,  що  знаходиться  під   головкою читання. При цьому верхній символ стеку замінюється на праву частину застосованого правила.

Далі процес аналізу  продовжується  аналогічно,  доки  не  буде прочитаний увесь вхідний рядок.

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

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

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

            type

              ptr = ^list;

             list = record

               symb : char;

               ref : ptr

             end;

             rec = record

                terms : list;

                jump : integer;

                accept, stack, return, error : boolean

              end;

              tab = array [1..n] of rec;

Для того, щоб пояснити призначення полів, розглянемо  граматику з попередньої лекції. Спочатку пронумеруємо усі символи  у  правилах граматики, і  будемо  вважати  номер  символа  номером  відповідного запису або індексом масиву  tab.

1. S1  X2Y3Z4                7. Q18  a20a21

                                       2. X5  P6Q7                   8. Q19   22   

                                       3. Y8  R9V10                  9. V 23 с24с25

                                       4. R11  T12U13              10. T26  d27d28 

                                       5. P14  16                     11. U29  e30e31

                                       6. P15 с17                      12. Z32  33   

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

(1)                                                                      (2)

                                                                          (3)   

                                                                          (4)

(32)                                                                     (33)

(8)                                                                       (9)

                                                                          (10)

(23)                                                                    (24)

                                                                          (25)

(11)                                                                    (12)

                                                                          (13)

(29)                                                                    (30)

                                                                          (31)

(26)                                                                    (27)

                                                                          (28)

(5)                                                                       (6)

                                                                           (7)

(18)                                                                     (20)

(19)                                                                     (21)    

                                                                           (22)

(14)                                                                     (16)

(15)                                                                     (17)

Рис.11.1. Схема граматики G.

Кожному прямокутнику відповідає запис у таблиці. У  полі  terms для нетерміналу  зберігається множина вибору, а для терміналу -  сам цей символ. Множина вибору записується у вигляді списку  list, а  не як  змінна типу  set  для того, щоб структура  таблиці  не  залежала від алфавіту граматики.

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

На наступному  кроці відбувається перехід  до п’ятого запису, але перед тим у стек заноситься адреса запису (це - число 3), до якого треба повернутись після закінчення аналізу нетермінала  Х. Так само при  переході  від шостого  запису  до  чотирнадцятого  у  стек  заноситься  число  7.

Якщо  перший  вхідний  символ  належить  до  множини вибору чотирнадцятого запису, то відбувається  перехід  до  запису 16. В іншому разі - перехід до запису 17. Припустимо, що відбувся перехід до запису 17. Це означає, що перший символ вхідного рядка - с. Тоді драйвер робить зсув  по  вхідному  рядку, і під головкою читання опиняється наступний вхідний символ. Крім того,  оскільки  запис 17 містить нульове посилання, то адреса наступного запису  береться  зі стеку, і  верхній елемент стеку виштовхується. Далі  починається аналіз нетерміналу Q. Якщо процес дійде до запису 33, то це буде означати, що вхідний рядок належить до поданої граматики,  тобто  не містить помилок.

При обробці запису виконуються такі дії:

                                                           Табл.11.7

Ном.зап.

terms

jump

accept

stack

return

error

1

a,c,d

2

0

0

0

1

2

a,c,d

5

0

1

0

0

3

d

8

0

1

0

1

4

32

0

0

0

1

5

a,c,d

6

0

0

0

0

6

a,c,d

14

0

1

0

0

7

a,d

18

0

0

0

1

8

d

9

0

0

0

0

9

d

11

0

1

0

0

10

c

23

0

0

0

1

11

d

12

0

0

0

0

12

d

26

0

1

0

0

13

e

29

0

0

0

1

14

a,d

16

0

0

0

0

15

c

17

0

0

0

0

16

a,d

0

0

1

0

17

c

1

0

1

0

18

a

20

0

0

0

0

19

d

22

0

0

0

0

20

a

21

1

0

0

0

21

a

1

0

1

1

22

d

0

0

1

0

23

c

24

0

0

0

0

24

c

25

1

0

0

0

25

c

1

0

1

1

26

d

27

0

0

0

0

27

d

28

1

0

0

0

28

d

1

0

1

1

29

e

30

0

0

0

0

30

e

31

1

0

0

0

31

e

1

0

1

1

32

33

0

0

0

0

33

stop

0

0

0

0

1) просування по вхідному рядку;

2) занесення у стек адреси повернення;

3) виштовхування елемента зі стеку і повернення до запису, на який вказує цей елемент;

4) перевірка збігу чергового вхідного символу з  одним  з елементів, що знаходяться у полі  terms.

Саме для того, щоб вказати, які з  цих  дій  треба  виконувати, застосовуються відповідно поля  accept, stack, return, error  (1  - дія виконується,  0  -  ні). Поле jump показує  адресу прямого переходу.

Для граматики  G,  схему якої  наведено  вище,   LL(1)-таблицю показано у вигляді табл.11.7. У  випадках, коли черговий вхідний символ не співпадає з жодним елементом поля   terms,  а  у  полі error записане нульове значення,  відбувається перехід до запису, номер якого більше поточного на одиницю. Така  дія  виконується  при обробці записів 14  та  18.


 

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

13436. СТВОРЕННЯ ЗВЕДЕННИХ ТАБЛИЦЬ В MICROSOFT EXCEL 354.5 KB
  МЕТОДИЧНІ ВКАЗІВКИ ДО ЛАБОРАТОРНОЇ РОБОТИ №6 СТВОРЕННЯ ЗВЕДЕННИХ ТАБЛИЦЬ В MICROSOFT EXCEL 1. Мета роботи Придбати практичні навички по створенню і використанню зведених таблиць в Microsoft Excel. 2. Задачі роботи Опанувати прийоми формування редагування зміни та
13437. Опрацювання результатів прямих багаторазових вимірювань 238 KB
  ЛАБОРАТОРНА РОБОТА 1 ОПРАЦЮВАННЯ РЕЗУЛЬТАТІВ ПРЯМИХ БАГАТОРАЗОВИХ ВИМІРЮВАНЬ Мета роботи: вивчити методику опрацювання результатів прямих багаторазових вимірювань; навчитись визначати характеристики похибки результату вимірювання в залежності від кількості в...
13438. Повірка чи калібрування приладів прямої дії 102.5 KB
  Лабораторна робота 2 Повірка чи калібрування приладів прямої дії Мета роботи: вивчити теоретичні та практичні основи повірки чи калібрування приладів прямої дії на прикладі калібрування амперметра та вольтметра зіставленням їх показів із показами робочих еталонів.
13439. ВИМІРЮВАННЯ ПОСТІЙНИХ СТРУМІВ ТА НАПРУГ 160 KB
  ЛАБОРАТОРНА РОБОТА 3 ВИМІРЮВАННЯ ПОСТІЙНИХ СТРУМІВ ТА НАПРУГ Мета роботи: Навчитись: вимірювати постійні струми та напруги електромеханічними приладами; раціонально обирати межу вимірювання та клас точності стрілкового приладу для вимірювання заданої з допустим
13440. ВИМІРЮВАННЯ СТРУМІВ, НАПРУГ ТА ПАРАМЕТРІВ ЕЛЕКТРИЧНИХ ЛАНЦЮГІВ КОМБІНОВАНИМИ ПРИЛАДАМИ (ТЕСТЕРАМИ) 2.84 MB
  ЛАБОРАТОРНА РОБОТА 4 ВИМІРЮВАННЯ СТРУМІВ НАПРУГ ТА ПАРАМЕТРІВ ЕЛЕКТРИЧНИХ ЛАНЦЮГІВ КОМБІНОВАНИМИ ПРИЛАДАМИ ТЕСТЕРАМИ Мета роботи: вивчити принцип дії будову та властивості комбінованих приладів КП здобути навички вимірювань і перевірки справності елементів ...
13441. Деякі особливості використання вольтметрів змінного струму 237.5 KB
  ЛАБОРАТОРНА РАБОТА № 5 Деякі особливості використання вольтметрів змінного струму Мета роботи : Опрацювати опис даної роботи та відповідні розділи рекомендованої літератури [1] [2] [3] [5]. 2. Уміти відповідати на наступні запитання: 1. Поясніть будову та принцип д
13442. ДОСЛІДЖЕННЯ ВИМІРЮВАЛЬНИХ МОСТІВ ПОСТІЙНОГО СТРУМУ 131.5 KB
  Лабораторна робота № 6 ДОСЛІДЖЕННЯ ВИМІРЮВАЛЬНИХ МОСТІВ ПОСТІЙНОГО СТРУМУ Мета роботи: вивчити основи теорії схеми та будову врівноважених мостів постійного струму дослідити властивості врівноважених мостів здобути навички вимірювань за допомогою мостів. При пі...
13443. НЕВРІВНОВАЖЕНИЙ ВИМІРЮВАЛЬНИЙ МІСТ ПОСТІЙНОГО СТРУМУ 118.5 KB
  ЛАБОРАТОРНА РОБОТА 7 НЕВРІВНОВАЖЕНИЙ ВИМІРЮВАЛЬНИЙ МІСТ ПОСТІЙНОГО СТРУМУ Мета роботи: вивчити принцип дії елементи теорії схеми властивості та особливості застосування неврівноважених вимірювальних мостів НМ постійного струму. При підготовці до виконання р...
13444. ДОСЛІДЖЕННЯ ВИМІРЮВАЛЬНИХ МОСТІВ ЗМІННОГО СТРУМУ 193.5 KB
  ЛАБОРАТОРНА РОБОТА N 8 ДОСЛІДЖЕННЯ ВИМІРЮВАЛЬНИХ МОСТІВ ЗМІННОГО СТРУМУ Мета роботи: вивчити основи теорії принцип дії схеми властивості і особливості експлуатації мостів змінного струму МЗС. Провести дослідження властивостей мостів змінного струму. При п...