73509

КС-грамматики и синтаксический анализ сверху вниз

Лекция

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

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

Русский

2014-12-17

215.5 KB

0 чел.

Лекция 2

3. КС-грамматики и синтаксический анализ сверху вниз

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

3.1. Определения

Определение. Обозначения в написании LL(1)-грамматики означают:

  •  L  строки разбираются слева направо;
  •  L  используются самые левые выводы;
  •  1  варианты порождающего правила выбираются с помощью одного предварительного просмотра символа.

Т.е. грамматику называют LL(1)-грамматикой, если для каждого нетерминала, появляющегося в левой части более одного порождающего правила, множество направляющих символов, соответствующих правым частям альтернативных порождающих правил, – непересекающиеся.

Пример. Рассмотрим грамматику G = ({E, E´, T, T´, F}, {id, +, *, (, )}, P, E), где P =

(1) E  T E´

(2) E´ + T E´

(3) E´  e

(4) T  F T´

(5) T´ * F T´

(6) T´  e

(7) F  ( E )

(8) F  id

Нетерминал

Входной символ

id

+

*

(

)

$

E

(1)

(1)

E´

(2)

(3)

(3)

T

(4)

(4)

T´

(6)

(5)

(6)

(6)

F

(8)

(7)

Символом $ обозначается конец цепочки.

Пусть G = (N, Σ, P, S) – КС-грамматика. Обозначим вершину магазин как M (M  N  Σ {$}) текущий символ входной цепочки – как IN (IN  Σ {$}), а элемент таблицы разбора – как LT(A, a), где A  N, a  Σ. Тогда правила разбора будут следующими:

1) Положить в магазин S $

2) Если M  N, то

2.1) Если LT(M, IN) = A α, то

2.1.1) убрать из магазина A

2.1.2) положить в M правую часть правила α

2.1.3) Вывести правило A α

2.2) Иначе – ошибка

3) Иначе если M  Σ, то

3.1) Если M = IN = a, то

3.1.1) убрать a из M

3.1.2) убрать a из IN

3.2) Иначе – ошибка

4) Иначе

4.1) Если M = IN = $, то конец разбора

4.2) Иначе переход на шаг 2

Разбор:

Входная цепочка: id + id*id$

Магазин

Вход

Выход

E $

id + id*id$

E  T E´

T E´ $

id + id*id$

T  F Tґ

F Tґ Eґ $

id + id*id$

F  id

id Tґ Eґ $

id + id*id$

Tґ Eґ $

+ id*id$

Tґ  e

Eґ $

+ id*id$

Eґ + T Eґ

+ T Eґ $

+ id*id$

T Eґ $

id*id$

T  F Tґ

F Tґ Eґ $

id*id$

F  id

id Tґ Eґ $

id*id$

Tґ Eґ $

*id$

Tґ * F Tґ

* F Tґ Eґ $

*id$

F Tґ Eґ $

id$

F  id

id Tґ Eґ $

id$

Tґ Eґ $

$

Tґ  e

Eґ $

$

Eґ  e

$

$

Определение. Множество терминальных символов-предшественников определяется следующим образом:

a  S(α) α + aβ,

где

  •  α, β  – строки терминалов и/или нетерминалов, α, β (N  Σ)*;
  •  S(α) – множество символов-предшественников α, S(α) Σ {e}.

Это множество символов, с которых могут начинаться строки, выводимые из α.

Пример:

 P  Ac

 P  Bd

 A  a

 A  Aa

 B  b

 B  bB

Здесь символы a и b – символы-предшественники для P.

Определение. Множество терминальных символов-последователей определяется следующим образом:

a  F(A) αAβ + αaγ,

где

  •  Aнетерминал, A  N;
  •  α, β, γ  – строки терминалов и/или нетерминалов, α, β, γ (N  Σ)*;
  •  F(A) – множество символов-последователей A, F(A) Σ {$}.

Это множество символов, которые могут следовать за A.

В предыдущем примере a и c – символы-последователи для A (т.е. появляются непосредственно справа от A при выводе)

Определение. Если Aнетерминал, то его направляющими символами (T) будут символы-предшественники A и все символы, следующие за A, если A может генерировать пустую строку.

В общем случае, для заданной цепочки α и нетерминала A (Aα) имеем

T(A, α) = {a | (a  S(α)  ae) * e и a  F(A))}.

Пример:

 T  AB

 A  PQ

 A  BC

 P  pP

 P  e

 Q  qQ

 Q  e

 B  bB

 B  d

 C  cC

 C  f

Эта грамматика дает S(PQ) = {p, q}, S(BC) = {b, d}, поэтому T(A, PQ) = {p, q, b, d} и T(A, BC) = {b, d}.

Из определения LL(1)-грамматики следует, что эти грамматики можно разбирать детерминированно сверху вниз.

3.2. Построение множества символов-предшественников

Пусть G = (N, Σ, P, S) – КС-грамматика. Для произвольной цепочки α определим S(α) как множество терминалов, с которых начинаются строки, выводимые из α. Если α * e, то e также принадлежит S(α).

Алгоритм:

Пусть α = X1 X2Xn.

1) Положить S(α) =

2) i = 1

3) Вычисляем S(Xi)

3.1) Если Xi  Σ {e}, то S(Xi) = {Xi}

3.2) Иначе {Xj  βj}  P, j = 1, 2, …, m,

3.3) S(α) = S(α) (S(Xi) – {e})

3.4) Если e  S(Xi)

3.4.1) Если i < n, то i = i + 1, переход на шаг 3

3.4.2) Иначе S(α) = S(α) {e}, переход на шаг 4

3.5) Иначе переход на шаг 4

4) Конец алгоритма

Чтобы вычислить S(α) для всех нетерминалов грамматики, необходимо, пока удается добавлять новые элементы в какое-либо множество S(A), A  N, повторять алгоритм для каждого A  N. Это позводит в будущем более просто находить множество символов-предшественников для любой цепочки, т.к. упростится выполнение шага 3.

Пример:

S(E) = S(T) = {(, id}

S(E1´) = {+}

S(E2´) = {e}

S(T1´) = {*}

S(T2´) = {e}

S(F1) = {(}

S(F2) = {id}

3.3. Построение множества символов-последователей

Пусть G = (N, Σ, P, S) – КС-грамматика. Для нетерминала A  N определим F(A) как множество терминалов, с которых начинаются строки, выводимые в грамматике после A.

Алгоритм:

Пусть X  N.

1) Положить F(X) =

2) Положить F(S) = {$}

3) Пока удается добавлять новые элементы в какое-либо множество F(X), повторять

3.1) Пусть {A  αBβ}  P, B  N, α, β (N  Σ)* и β ≠ e, тогда F(B) = F(B) (S(β) – {e})

3.2) Если β = e или e  S(β) (т.е. β * e), то F(B) = F(B)  F(A)

Пример:

F(E) = F(E´) = {), $}

F(T) = F(T´) = {+, ), $}

F(F) = {+, *, ), $}

3.4. Построение таблицы разбора

Имея множества символов-предшественников и множества символов-последователей, легко построить множества направляющих символов T(X):

T(X) = (S(X) – {e}) {F(X) | e  S(X)}.

Пример:

T(E) = T(T) = {(, id}

T(E1´) = {+}

T(E2´) = {), $}

T(T1´) = {*}

T(T2´) = {+, ), $}

T(F1) = {(}

T(F2) = {id}

Также легко проверить, является ли грамматика грамматикой типа LL(1): если имеются альтернативы Ai  αi, i = 1, 2, …, n, то грамматика будет относиться к типу LL(1), если

T(Ai)  T(Aj) = , ij.

Пример:

T(E1´)  T(E2´) =

T(T1´)  T(T2´) =

Построение таблицы разбора:

1) Помечаем грамматику

Пусть Pi – правило с номером i из множества P, i = 1, 2, …, n. Тогда:

1) Полагаем i = 1, count = 0

2) Пусть Pi+k–1 = Ak  αk, k = 1, 2, …, p, тогда

2.1) I(Ak) = count + k, count = count + p

2.2) Для каждой цепочки αk = X1, X2, …, Xm, где m = |αk|, полагаем

2.2.1) I(Xj) = count + j, j = 1, 2, …, m

2.2.2) count = count + m

3) i = i + 1

4) Если i < n, переход на шаг 2, иначе – конец алгоритма

Для рассмотренного выше примера

(1) E (1)  T (2) E´ (3)

(2) E´ (4)  + (6) T (7) E´ (8)

(3) E´ (5)  e (9)

(4) T (10)  F (11) T´ (12)

(5) T´ (13)  * (15) F (16) T´ (17)

(6) T´ (14)  e (18)

(7) F (19)  ( (21) E (22) ) (23)

(8) F (20)  id (24)

2) Строим множества T(X)

3) Заполняем таблицу

Введем множество индексов элементов правил, стоящих по левую сторону от знака вывода (L). В нашем случае L = {1, 4, 5, 10, 13, 14, 19, 20}. Введем также множество индексов элементов правил, являющихся самыми правыми в своем правиле (R). В нашем случае R = {3, 8, 9, 12, 17, 18, 23, 24}.

Тогда

ID

X

Terminals

Jump

Accept

Stack

Return

Error

1

E 

(, id

2

2

T

(, id

10

true

3

E´

+, ), $

4

4

E´

+

6

false

5

E´

), $

9

6

+

+

7

true

7

T

(, id

10

true

8

E´

+, ), $

4

9

e

), $

0

true

10

T 

(, id

11

11

F

(, id

19

true

12

T´

+, *, ), $

13

13

T´

*

15

false

14

T´

+, ), $

18

15

*

*

16

true

16

F

(, id

19

true

17

T´

+, *, ), $

13

18

e

+, ), $

0

true

19

F 

(

21

false

20

F 

id

24

21

(

(

22

true

22

E

(, id

1

true

23

)

)

0

true

true

24

id

id

0

true

true

3.5. Алгоритм разбора

1) Положить в M элемент 0 (M ← 0), i = 1

2) Если IN  Terminalsi, то

2.1) Если Accepti = true, то перейти к следующему символу в IN

2.2) Если Stacki = true, то добавить в M индекс i (Mi)

2.3) Если Returni = true, то

2.3.1) k = M, убрать k из M (Mk)

2.3.2) Если k = 0, переход на шаг 4

2.3.2) i = k + 1

2.3.3) Переход на шаг 2

2.4) Если Jumpi ≠ 0, то

2.4.1) i = Jumpi

2.4.2) Переход на шаг 2

3) Иначе если Errori = false, то

3.1) i = i + 1

3.2) Переход на шаг 2

4) Если M не пуст, то ошибка, иначе разбор успешен

Разбор цепочки id + id*id$

Магазин

Вход

i

Действие

0

id + id*id$

1

jump = 2

0

id + id*id$

2

stack, jump = 10

2 0

id + id*id$

10

jump = 11

2 0

id + id*id$

11

stack, jump = 19

11 2 0

id + id*id$

19

error = false, i = 20

11 2 0

id + id*id$

20

jump = 24

11 2 0

id + id*id$

24

accept, return

2 0

+ id*id$

12

jump = 13

2 0

+ id*id$

13

error = false, i = 14

2 0

+ id*id$

14

jump = 18

2 0

+ id*id$

18

return

0

+ id*id$

3

jump = 4

0

+ id*id$

4

jump = 6

0

+ id*id$

6

accept, jump = 7

0

id*id$

7

stack, jump = 10

8 0

id*id$

10

jump = 11

8 0

id*id$

11

stack, jump = 19

12 8 0

id*id$

19

error = false, i = 20

12 8 0

id*id$

20

jump = 24

12 8 0

id*id$

24

accept, return

8 0

*id$

13

jump = 15

8 0

*id$

15

accept, jump = 16

8 0

id$

16

stack, jump = 19

17 8 0

id$

19

error = false, i = 20

17 8 0

id$

20

jump = 24

17 8 0

id$

24

accept, return

8 0

$

18

return

0

$

9

return

$

success


 

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

64773. ФОРМУВАННЯ ВРОЖАЙНОСТІ ТА ЯКОСТІ ЗЕРНА ПШЕНИЦІ ОЗИМОЇ ЗАЛЕЖНО ВІД ПОПЕРЕДНИКІВ, СТРОКІВ СІВБИ ТА НОРМ ВИСІВУ В УМОВАХ ПРИСИВАШШЯ 301 KB
  Мета досліджень полягає в розробці більш досконалих та економічно ефективних агротехнічних прийомів вирощування пшениці озимої при сівбі після соняшнику ячменю ярого у порівнянні з чорним паром за різних строків сівби та норм висіву насіння.
64774. МЕТОДИКА ФОРМУВАННЯ ПРАЦЕОХОРОННИХ УМІНЬ І НАВИЧОК СТУДЕНТІВ АГРАРНИХ ВИЩИХ НАВЧАЛЬНИХ ЗАКЛАДІВ ЗАСОБАМИ ІМІТАЦІЙНОГО МОДЕЛЮВАННЯ 592 KB
  Здійснивши аналіз методики викладання нормативних дисциплін Основи охорони праці й Охорона праці в галузі у вищих аграрних навчальних закладах ми дійшли висновку що здебільшого застосовуються традиційні методи навчання які не повною мірою дозволяють сформувати високий рівень...
64775. ОЦІНЮВАННЯ ІННОВАЦІЙНОСТІ ТЕХНОЛОГІЧНИХ ПРОЦЕСІВ МАШИНОБУДІВНИХ ПІДПРИЄМСТВ 283 KB
  Зокрема потребує подальшого теоретичного та прикладного вирішення уточнення й поглиблення поняття інноваційність технологічних процесів виявлення чинників що визначають інноваційність розвиток класифікації технологічних процесів машинобудівних...
64776. Отримання порожнистих деталей із змінною товщиною стінки на базі використання способів радіально-прямого видавлювання 336.5 KB
  Для виготовлення розповсюджених в промисловості порожнистих вісесиметричних деталей із змінною товщиною стінки використовуються способи поздовжнього зворотного та прямого видавлювання витягування локальної обробки та процеси штампування...
64777. МУЗИКА Й ЖИВОПИС У ТВОРЧОСТІ О. КОБИЛЯНСЬКОЇ ТА Я. ІВАШКЕВИЧА: СИНКРЕТИЗМ ХУДОЖНЬОЇ ОБРАЗНОСТІ 162.5 KB
  Сучасність виводить синкретизм на рівень одного з основних понять філософії та культури, що зумовлено зростаючою роллю інтеграційних процесів та явищ у контексті глобалізації всього культурного життя суспільства, яке перетворює навколишній світ.
64778. ПЕДАГОГІЧНІ УМОВИ ФОРМУВАННЯ ПРОЕКТНО-ОБРАЗНОГО МИСЛЕННЯ МАЙБУТНІХ ДИЗАЙНЕРІВ У ВИЩОМУ НАВЧАЛЬНОМУ ЗАКЛАДІ 223 KB
  Сучасний етап розвитку українського суспільства ознаменувався значними трансформаціями в соціальноекономічній політичній культурній та освітній сферах що привели до переосмислення ролі дизайну як особливої діяльності яка завдяки естетичності екологічності технічності...
64779. Поліпшення паливно-економічних та екологічних показників автомобіля на основі оптимізації параметрів системи запалювання 820.26 KB
  Адаптивна настройка систем управління двигуном під конкретний режим руху автомобіля а також перерозподіл пріоритетів між ефективними показниками автомобіля залежно від умов його експлуатації є важливим експлуатаційним резервом економії палива й підвищення екологічної безпеки.
64780. ОПТИМІЗАЦІЯ ЕЛЕМЕНТІВ ТЕХНОЛОГІЇ ВИРОЩУВАННЯ СОЇ ТА КУКУРУДЗИ У ПІВДЕННО-ЗАХІДНІЙ ЧАСТИНІ СТЕПУ УКРАЇНИ 243.5 KB
  В ринкових умовах основою ефективного господарювання є інтенсивні технології вирощування сільськогосподарських культур, які базуються на використанні високопродуктивних сортів та раціональному використанні факторів життя.
64781. ФОРМУВАННЯ КОНКУРЕНТОСПРОМОЖНОСТІ ПІДПРИЄМСТВ ХЛІБОПЕКАРСЬКОЇ ГАЛУЗІ 632 KB
  З іншої сторони забезпечення конкурентоспроможності галузі та конкретних виробників хлібопекарської продукції в умовах жорсткої конкуренції є складним практичним і науковим завданням яке потребує багатоаспектного підходу із застосуванням системної теорії наукового управління.