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.


 

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

54861. Створення електронних підручників 46.5 KB
  Стрімкий процес інформатизації шкіл на основі сучасних компютерів що поступають в навчальні заклади країни відкриває в освіті шлях електронним підручникам. Сучасні методи представлення інформації в компютерах містять в собі не тільки текст малюнки графіку креслення але й звукові та відео фрагменти що забезпечує наочність підручника. Окремі аспекти електронного підручника досліджувались у роботах А. Вони мають такі загальні ознаки а саме: навчальний матеріал висловлюється з певної області знань та освітлюється на сучасному рівні...
54862. Мультиказковий феєрверк 321.5 KB
  Протилежні числа. Координатний промінь Тема модуля: Додатні та відємні числа. Протилежні числа.
54863. Слово. Значение слова 1.76 MB
  Значение слова. Фундаментом знаний является материал заложенный в первом классе где дети в доступной форме познакомились со словами предметами признаками предметов действиями словами которые служат для связи слов в предложении заменяя данные понятия на слова-художники слова работяги слова узелки.
54864. Градусна сітка Землі. Географічні координати 129.5 KB
  Мета: поглиблення і систематизація знань про географічні координати; вдосконалення практичних навичок і вмінь працювати з географічною картою; розвиток логічного мислення. Географічні координати це адреса точки Г Пн. Які міста мають координати: 56 пн.
54865. Додавання і віднімання раціональних чисел 145.5 KB
  Сума двох відємних чисел це число. Сума двох протилежних чисел дорівнює. Знак для позначення суми чисел плюс.
54866. Княжа Русь-Україна. Підсумково-узагальнюючий урок 66.5 KB
  Сьогодні у нас підсумковоузагальнюючий урок з теми Княжа РусьУкраїна. В процесі гри Історичне лото закріпемо поняття з теми: князь князівство дружина віче полюддя релігія християнство Київська Русь Руська Правда ярлик хан орда язичнизтво бояри. Я створов перший збірник законів що отримав назву Руська Правда.
54867. Теорема Піфагора 578.5 KB
  Що називається соs гострого кута прямокутного трикутника Косинусом гострого кута прямокутного трикутника називається відношення прилеглого катета до гіпотенузи. 6 Знайдіть чому дорівнює соsА соsА = відношенню прилеглого катета АС до гіпотенузи АВ. Знайдіть чому дорівнює соsВ соsВ= відношенню прилеглого катета до гіпо тенузи. 7 Скажіть чи залежить значення соs кута від розмірів трикутника ні.
54868. Теорема Піфагора. Свято однієї теореми 5.94 MB
  Свято однієї теореми Знову теорема Піфагора Так. Теорема Піфагора Мета. Чому Можливо втрачені знання або їх глибина Можливо треба задуматися: а що ми залишимо майбутнім поколінням Цей урок присвяченій одній єдиній теоремі Піфагора доведенням якої займалися і займаються математики всіх країн.
54869. Теорема Піфагора. Розвязування задач 613.5 KB
  Мета: закріпити знання теореми Піфагора навчити учнів користуватися теоремою Піфагора для розвязування задач; розвивати логічне мислення вміння аналізувати порівнювати робити висновки Тип уроку: урок вдосконалення знань. Обладнання: мультимедійний проектор дошка комп'ютер колонки математичне лото Теорема Піфагора дидактичні матеріали з друкованою основою. Вступне слово вчителя Один із афоризмів Піфагора звучить наступним чином: Просипаючись вранці запитай себе: Що я повинен зробити Увечері перш ніж...