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


 

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

8354. История древней Индии и Китая 37.5 KB
  Особый расцвет в индии наступает с 5-6 веков н.э, начинается процесс урбанизации. Ahimsa - не причинение вреда всему живого. Начинается развитие товарно-денежного обращения. Члены всех 4-ех варн отходили от своих традиционных занятий...
8355. Культура Древнего Востока. Бхавадгита 98 KB
  Культура Древнего Востока. БХАГАВАДГИТА КАК ОНА ЕСТЬ Арджуна спросил: О мой Господь, о Высшая личность, что такое Брахман? Что такое душа? Что такое кармическая деятельность? Что представляет собой это материальное проявление? Кто такие полубоги? По...
8356. История Китая. Краткий обзор 482.32 KB
  История Китая Китайская цивилизация - одна из старейших в мире. По утверждениям китайских учёных, её возраст может составлять пять тысяч лет, при этом имеющиеся письменные источники покрывают период не менее 3500 лет. Наличие систем администрат...
8357. Хрестоматія Китайської Літератури (від найдавніших часів до ІІІ ст. н.е.) 中国古代文学作品选 4.19 MB
  Хрестоматія Китайської Літератури(від найдавніших часів до ІІІ ст. н.е.) У хрестоматії широко представлена перекладна й оригінальна давньокитайська література, зокрема народна та авторська поезія, міфологічна, літописна, філософська ...
8358. Історія Китаю та китайських традицій 86.5 KB
  На сьогодні дві держави використовують назву Китай. Це Китайська Народна Республіка (КНР), яка контролює територію материкового Китаю, Гонконг та Макао, а також Республіка Китай, яка володіє островами Тайвань, Мацу і Кіньмень Китай (традиц...
8359. Влияние иностранных инвестиций на экономику Китая 124 KB
  Влияние иностранных инвестиций на экономику Китая Введение Процессы, происходящие в экономике Китая, на протяжении нескольких последних десятилетий привлекают к себе внимание специалистов и широкой мировой общественности. Достижения, демонстрируемые...
8360. История Китая 168.5 KB
  КИТАЙ По истории Китая вы помните, что в Китае сменялись разные династии. Для истории Китая характерна определенная цикличность. Приходит к власти новая династия, проводит реформы, все идет хорошо, процветание. А потом наступает упадок, и смена дина...
8361. Китайские церемонии или радостно встречая 18-ый съезд КПК 47.5 KB
  Китайские церемонии или радостно встречая 18-ый съезд КПК Связка трех сил внутри китайского руководства Учение Маркса (марксизм-ленинизм - идеи Мао Цзэдуна) было всесильным и верным в период индустриального общества борьбы труда и капитала. Теперь ж...
8362. Китай. Экономическое и политическое развитие КНР 707 KB
  План. Введение Экономико- и политико-географическое положение. Особенности исторического развития. Природно-ресурсные предпосылки для развития экономики. Земельные ресурсы. Минеральные ресурсы. Топливные ПИ...