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


 

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

58120. Создание Интернет-страниц 32 KB
  Он требует терпения и знания основ «программирования» на языке html, который, по сути, языком программирования не является. Итак. Для работы нам будет достаточно программы Блокнот. И даже более того, достаточно будет использовать только меню FILE.
58121. СУСПІЛЬНО-ІСТОРИЧНІ УМОВИ РОЗВИТКУ УКРАЇНСЬКОЇ ЛІТЕРАТУРИ ХХ ст., ОСНОВНІ СТИЛЬОВІ НАПРЯМИ 120.5 KB
  Цi хронологiчнi межi визначаються не тiльки перебiгом революцiї 1905–1917 рр., а й вiдходом iз життя I. Франка (1916 р.) та М. Коцюбинського й Лесi Українки (обоє померли в 1913 р.). Формування пiсля 1905 р. Києва як лiтературної столицi України, поширення загальноукраїнської лiтературної перiодики
58122. ВВЕДЕНИЕ. МИР В XVI – XVIII ВВ 46 KB
  В более узком смысле история — это наука, изучающая всевозможные источники о прошлом для того, чтобы установить последовательность событий, исторический процесс, объективность описанных фактов и сделать выводы о причинах событий.
58123. Задачи бухгалтерского учета в общественном питании 34 KB
  Контроль за финансовыми показателями (размер прибыли, источники поступления средств и порядок их расходования, оборотные средства, отчисления от прибыли и.т.д.) за правильностью расчетов с поставщиками и покупателями, за своевременным поступлением платежей в бюджет, за правильностью использования банковских кредитов...
58124. Сущность и виды государственной финансовой политики 17.12 KB
  В любом цивилизованном обществе правительство использует финансовые отношения для достижения определенных целей, для осуществления своих функций и задач. В этой связи финансовая политика выступает инструментом воздействия на экономические интересы отдельных слоев населения и общества в целом.
58125. Конструкция и область применения кабелей 72 KB
  Преимущественно применяются кабели с алюминиевыми жилами. Кабели с медными жилами применяются редко: для перемещающихся механизмов во взрывоопасных помещениях.
58126. Моделі фінансових відносин у суспільстві 28.69 KB
  Розподіл і перерозподіл ВВП може здійснюватись за різними схемами, згідно з якими будуються моделі фінансових відносин у суспільстві. В основі побудови фінансової моделі суспільства лежать роль і місце в ній держави.
58127. Familie und Freunde 1.15 MB
  Ich liebe meine Mutter und meinen Vater. Er kommt heute oder morgen. Er hat keinen Bruder aber zwei Vetter. Die Konjunktionen und, aber, oder, denn verbinden Sätze. Das Verb steht auf Position...
58128. Неличные формы глагола, инфинитив. Функции инфинитива, инфинитивные обороты. Lasers Shed Light on a «Black Art» 177.5 KB
  The mechanical engineers want further research to be carried out into new kinds of motive power. After the test runs the locomotive was found to have some drawbacks in its design. The data to be obtained in the course in the experimental runs are to be used later for improving the passenger rolling stock.