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.


 

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

50114. Рух по діагоналі. Рух по колу. Команди та дії 83.5 KB
  Стройові вправи. Загальнорозвивальні вправи. Прикладні вправи. Стройові вправи.
50115. ОПРЕДЕЛЕНИЕ РАДИУСА КРИВИЗНЫ ЛИНЗЫ И ДЛИНЫ СВЕТОВОЙ ВОЛНЫ ПО КОЛЬЦАМ НЬЮТОНА 366.5 KB
  Закрепите ртутный фонарь высокого давления с двойным конденсором фокусное расстояние 60 мм держатель для линз с интерференционным фильтром устройство для получения колец Ньютона держатель для линз с линзой с фокусом 50 мм и полупрозрачный экран на расстоянии 40 см от линзы на оптической скамье. Затем в держатель для линзы вставьте желтый светофильтр. В экспериментальной установке значение радиуса кривизны плосковыпуклой линзы R = 121 м.
50117. Программирование задач с использованием операторов цикла (табуляции функции) 57.5 KB
  Цель: Получение практических навыков в использовании операторов цикла. Операторы цикла делятся на 3 вида: оператор с параметром с предусловием и с постусловием. Количество повторений цикла определяется начальным значением переменнойсчетчика и условием завершения цикла.
50118. Исследование влияния температуры на характеристики различных материалов и диодов 794 KB
  Существенное изменение сопротивления при изменении температуры обязательно должно учитываться при проектировании и эксплуатации различных электрических устройств и приборов электродвигатели конвейеры бурильные установки нагревательные устройства радиоэлектронные схемы и т. Единицей электрического сопротивления проводников служит Ом. Рассеяние приводящее к появлению сопротивления возникает в тех случаях когда в решётке имеются нарушения структуры. Поэтому любые микронеоднородности структуры препятствуют распространению электронных волн...
50119. Определение коэффициента термического расширения (линейного) твердого тела 141 KB
  Цель работы: 1 определить температуру металлической проволоки при протекании через нее электрического тока; 2 измерить удлинение проволоки при нагревании; 3 определить показатель коэффициента термического расширения. В данной работе экспериментально определяется коэффициент термического расширения твердого тела металлической проволоки. Из формулы [2] следует что для определения коэффициента необходимо знать начальную длину проволоки Lo изменение температуры dt и соответствующее изменение длины dL. Изменение длины проволоки можно...
50120. ИЗМЕРЕНИЕ ВЫСОКИХ ТЕМПЕРАТУР С ПОМОЩЬЮ ПИРОМЕТРА С ИСЧЕЗАЮЩЕЙ НИТЬЮ 210 KB
  Тепловым излучением тел называется электромагнитное излучение возникающее за счет той части внутренней энергии тела которая связана с тепловым движением его частиц. Спектральная плотность энергетической светимости r λ Т энергия излучаемая единицей поверхности тела в единицу времени в единичном интервале длин волн dλ вблизи рассматриваемой длины волны λ. Эта величина зависит от температуры тела длины волны испускаемого света а также от природы и состояния поверхности излучающего тела.
50122. НАГРУЗКИ ОТ МОСТОВЫХ И ПОДВЕСНЫХ КРАНОВ 153.5 KB
  Нормативные значения и коэффициенты надежности Нагрузки от мостовых и подвесных кранов определяют в зависимости от групп режимов их работы устанавливаемых ГОСТ 25546 82 от вида привода и от способа подвеса груза.0785 Нагрузки и воздействия . Нормативное значение горизонтальной нагрузки направленной вдоль кранового пути и вызываемой торможением моста электрического крана следует принимать равным 01 полного нормативного значения вертикальной нагрузки на тормозные колеса рассматриваемой стороны...