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.


 

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

71191. Создание трехмерной модели в программе SolidWorks 531.5 KB
  Цель: Изучить основные приемы создания трехмерных моделей в пакете программ SolidWorks. После занятия студент должен: Знать: Методику создания трехмерных моделей. Уметь: Создать трехмерные модели различными методами.
71192. Построение твердых тел сложной конфигурации в пакете программ SolidWorks 1.63 MB
  Цель: Изучить основные приемы построения твердых тел сложной конфигурации в пакете программ SolidWorks. После занятия студент должен: Знать: Методику построение твердых тел сложной конфигурации в пакете программ SolidWorks.
71193. Формирование чертежа в пакете программ SolidWorks 319 KB
  Цель: Изучить основные правила создания чертежей в пакете программ SolidWorks. После занятия студент должен: Знать: Правила создания чертежей в пакете программ SolidWorks. Уметь: Создать чертеж в пакете программ SolidWorks.
71194. Создание деталей из листового материала в пакете программ Solid-Works 597 KB
  Цель: Изучить основные процедуры создания деталей из листового материала в пакете программ SolidWorks. После занятия студент должен: Знать: Процедуры создания деталей из листового материала в пакете программ SolidWorks.
71195. Создание сборок в пакете программ SolidWorks 303 KB
  Цель: Изучить основные процедуры создания сборок в пакете программ SolidWorks. После занятия студент должен: Знать: Процедуры создания сборок в пакете программ SolidWorks. Уметь: Создать сборку в пакете программ SolidWorks.
71196. Работа с литейными формами в пакете программ SolidWorks 326 KB
  Цель: Изучить основные приемы работы с литейными формами в пакете программ SolidWorks. После занятия студент должен: Знать: Основные приемы работы с литейными формами в пакете программ SolidWorks. Уметь: Создать литейную форму в пакете программ SolidWorks.
71197. Создание поверхностей и деталей на их основе в пакете программ SolidWorks 746 KB
  Цель: Изучить основные методы создания поверхностей и деталей на их основе в пакете программ SolidWorks. После занятия студент должен: Знать: Основные методы создания поверхностей и деталей на их основе в пакете программ SolidWorks.
71198. Прочностные расчеты деталей в приложениях COSMOSXpress и COSMOSWorks 411.5 KB
  Цель: Изучить основные методы выполнения прочностных расчетов деталей в приложениях COSMOSXpress и COSMOSWorks. После занятия студент должен: Знать: Основные методы выполнения прочностных расчетов деталей в приложениях COSMOSXpress и COSMOSWorks.
71199. Создание различных конфигураций деталей в пакете программ SolidWorks 639 KB
  Уметь: Создавать различные конфигурации деталей в пакете программ SolidWorks. 482491 рассмотреть суть таких вопросов: 1 создание конфигурации вручную; 2 создание конфигурации с помощью таблиц параметров; 3 основные сведения о конфигурациях; б занести в отчет такие данные...