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


 

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

73479. SWOT – анализ OOO Эллис (Homequeen) 230.5 KB
  Чтобы проанализировать предприятие, нужно выбрать верный способ анализа. Так, чтобы при его помощи можно было бы проанализировать и внутреннею, и внешнею среды. Так же нужно оценить возможности выбранного предприятия, чтобы четко понимать, на что оно способно, и какие у него есть перспективы.
73480. ОСОБЕННОСТИ ХИМИЧЕСКИХ СВОЙСТВ АТОМАРНОГО КИСЛОРОДА И ВОДОРОДА 229.5 KB
  В этой работе представлены некоторые особенности химических свойств атомарного водорода и кислорода. Химия этих элементов довольно интересна и разнообразна. Особенности химических свойств объясняются строением этих атомов.
73481. Система применения удобрений в хозяйстве АО «Дружба» 226.5 KB
  Определить потребность севооборота в элементах питания с учетом его продуктивности и разработать наиболее эффективную рациональную систему удобрения в севообороте с учетом агроклиматических ресурсов, плодородия почвы, биологических особенностей культур...
73482. Инвестиционная деятельность предприятий нефтедобывающей отрасли 220 KB
  Целью данной курсовой работы является анализ организации финансов предприятий нефтедобывающей отрасли. Для достижения данной цели были поставлены следующие задачи: раскрыть теоретические аспекты организации финансов предприятий нефтедобывающей отрасли...
73483. Форма сделок 212.5 KB
  Актуальность темы данной курсовой работы в том, что среди вопросов, связанных с оформлением гражданско-правовых договоров, важное значение имеют проблемы квалификации различных форм сделок, приобретающих все более широкое распространение в современном гражданском обороте.
73484. Организация бухгалтерского учета на предприятии «Елена» 208 KB
  Целью практики являлось углубить и закрепить теоретические и практические умения и навыки, полученные в университете при изучении учебных дисциплин; продолжить работу по формированию базовых и ключевых компетенций экономиста в сфере создания бухгалтерской службы на предприятии...
73485. Пути развития коммуникативной компетенции подростков в процессе внеучебной деятельности 202 KB
  Цель исследования: изучить и выявить пути развития коммуникативной компетенции подростков в процессе внеучебной деятельности. Дать характеристику внеучебной деятельности и ее роли в развитии коммуникативной компетенции подростков.
73486. Управління асортиментом товарів 202 KB
  Представлення маркетологів щодо оптимальних обсягів асортименту багато в чому залежать від роду діяльності тих або інших компаній: виробництво оптова торгівля роздріб та інші особливості вужчої спеціалізації. Наприклад у випадку з роздрібним товаром зусилля направлені...
73487. Пути повышения инвестиционной привлекательности ООО «НефтехимРесурс» 196 KB
  Актуальность оценки управления реальными инвестициями предприятия подтверждается большим значением инвестиций не только для будущего положения предприятия но и для экономики страны в целом. При оценке инвестиционной привлекательности предприятия потенциальные инвесторы в первую...