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


 

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

39084. Настройка сети Debian Linux. Серверная структура СДО Moodle 44.99 KB
  Интерфейс СДО Moodle. Серверная структура СДО Moodle. Формы контроля знаний в системе дистанционного обучения Moodle. Система дистанционного обучения Moodle обладает интуитивно понятным интерфейсом.
39085. Понятие инструментальной системы для создания курсов ДОТ, преимущества и классификация. Описание структуры файловой системы Linux 21.75 KB
  Понятие инструментальной системы для создания курсов ДОТ преимущества и классификация. Инструментальные системы для создания курсов ДО ориентированы на пользователей тьюторов разработчиков курсов ДО. Преимущества инструментальных систем: существенно снижается время на разработку курсов; снижаются общие затраты организации на разработку и использование курсов ДО; обеспечивается современный уровень функциональных и коммуникационных возможностей и пользовательского графического интерфейса курсов; исключаются многие ошибки начинающих...
39086. Распределение прав доступа в Linux. Системные требования для развертывания СДО Moodle 27.66 KB
  Системные требования для развертывания СДО Moodle. Количество пользователей которые смогут пользоваться Moodle может быть ограничено производительностью сервера. Большинство предпочитают вебсервер pche но Moodle будет хорошо работать и с любым другим вебсервером который поддерживает PHP например IIS под Windows. Язык сценариев PHP обратите внимание что есть особенности установки Moodle с PHPccelertor.
39087. Дистанционные образовательные технологии: история и развитие в России. Учётные записи в Linux 45.52 KB
  А также необходимостью современной педагогики дать ответ на запрос общества по выработке новых педагогических средств обучения и воспитания в новой культурноинформационной среде. Глобальные изменения в информационнокультурной среде мы относим к макрофакторам способствующим появлению электронного обучения. Мезофакторами определяющими развитие электронного обучения являются современные философские культурологические психологические и педагогические теории отражающие современные реалии культуры.
39088. Алгоритм и программа генерации ключевой информации 1.65 MB
  Настоящая работа посвящена в первую очередь ГПСП, ориентированным на использование в системах защиты информации от случайных и умышленных деструктивных воздействий. Вначале рассматриваются общие принципы проектирования непредсказуемых ГПСП, требования к таким устройствам, описываются основные строительные блоки, используемые при их создании.
39089. Отраслевой резервноинвестиционный фонд развития энергетики ГКД 34. 273.78 KB
  Пересчет характеристик газообразного топлива Приложение В. Пересчет характеристик топлива Приложение Г. Состав и характеристики разных видов органического топлива Приложение Д.
39090. Чернобыль 49.44 KB
  Могло быть такое стечение обстоятельств случайным Исследования показали: не исключенная вероятность того что вибрационнонезащищенная система реактора 4го блока ЧАЭС в период работы в внештатной ситуации за 16 сек. Причина аварии по этой версии связывается не с конструктивными недостатками а с сбоем в работе электротехнического оснащения которое привело к отключению электродвигателей которые обеспечивают подачу воды для охлаждения реактора. Взрывы в 4м реакторе ЧАЭС сдвинули со своего места металлоконструкции верха реактора...
39092. Челябинская ТЭЦ-1 2.88 MB
  Технические характеристики ежегодно корректируют с учетом проведенных модернизаций оборудования а также изменившихся условий работы. На основе технических характеристик составляются режимные карты графики или таблицы экономических режимов работы оборудования цеха устанавливается распределение нагрузок между параллельно работающими турбогенераторами и очередности пуска и остановки агрегатов.Режимные карты и другие материалы по поддержанию экономических режимов работы оборудования доводятся до всего эксплуатационного персонала цеха.Перед...