Название: Информатика (формальные языки и грамматики) - Методическая разработка(С.Е. Рояк)

Жанр: Информатика

Просмотров: 1363


Занятие  10.  построение распознавателей для кс-языков

 

Цель занятия: овладеть навыками построения алгоритмов распознавания для КС – языков. Эти алгоритмы являются основой синтаксического анализа в процессе трансляции для языков этого класса.

 

Методические указания

 

Что необходимо знать:

1) алгоритм построения распознавателя Глушкова;

2) алгоритм распознавателя, моделирующего стратегию сверху - вниз;

3) алгоритм распознавателя, моделирующего стратегию снизу-вверх.

 

Основные определения

 

Автоматом с магазинной  памятью называется семерка (A, Q, Z, d, s, q0, F), где

A - конечное множество входных символов,

Q - конечное множество внутренних состояний,

Z - конечное множество символов магазина,

 d: Q´A´ Z ®Q´Z* - функция перехода для детерминированного автомата  и

 d: Q´A´ Z ® Ã(Q´Z*) - для недетерминированного автомата.

sÎ Z - маркер конца магазинной памяти,

q0 Î Q - начальное состояние,

F Ì Q - множество конечных состояний.

Пример  «магазинного» автомата, распознающего язык L = = {cnbn| n = 1,2,...}:

A ={c,b}; Q = {q0,q1,q2,q3}{ error} ; Z =  {c,b,s}; F = {q3}.

d: {(c,q0, s) ® (q1,c) – если автомат, находясь в начальном состоянии и имея пустой магазин, читает с входной ленты символ с, то символ с записывается в «магазин» и автомат переходит в состояние q1.

(b,q0,s) ®  error - состояние ошибки: цепочка ее может начинаться с  символов b.

(c,q1,c) ® (q1,c) – в данном состоянии символ читается с входной ленты и записывается в «магазин».

(b,q1,c) ® (q2,e) – если на входной ленте читается символ b в данном состоянии, то автомат переходит в состояние q2 и из «магазина» читается верхний символ.

(е, q1,c) ® error - цепочка не может состоять из одних символов c.

(b, q2,c) ® (q2,e) - в состоянии q2 автомат считывает с входной ленты символ b  и одновременно читает символ из «магазина».

(e,q2, s) ® (q3) – если в «магазине» остался символ s и входная лента пустая, и автомат перешел в конечное состояние, то данная цепочка допускается автоматом.

(e,q2, с) ® error - автомат переходит в состояние error, так как символов b на ленте меньше, чем символ с.

(b,q2, s) ® error - автомат переходит в состояние error, так как символов c на ленте меньше чем символ b}.

 

3. Алгоритмы построения магазинных автоматов по данной КС-грамматике.

 

Вход:     дана грамматика  G = <T, N, S, P >

Выход:  магазинный автомат МP = <A,Q,Z,s,d,q0,F>

L(MP) Ì L(G) и L(G) Ì L(MP).

 

Построение автомата:

а) автомат, моделирующий левосторонний вывод цепочки (стратегия развертки сверху - вниз )

A = T {#}, где символ # - маркер начала строки.

Q = {q0,q1,q2}. q0 = q0. F = { q2}.

Функция d строится по следующей схеме:

(q0, #,s) ® (q1,S)

i Ni Î N (q1, , Ni) = {(q1,a1), ..., (q1,an)},если Ni ® a1| a2| ... |anÎ P /* Смысл этих действий следующий, если на вершине магазина находится нетерминальный символ, то он заменяется цепочкой ai .  С входной ленты символ не считывается.*/

" i ai Î T  (q1,ai, ai) ® (q1,e)  /* автомат читает входной символ с ленты и из «магазина», если символ на входной ленте совпадает с символом, находящимся на вершине магазина.*/

(e,q1,s) ® (q2) - /*переход автомата в конечное состояние.*/;

 

б) автомат, моделирующий стратегию свертки снизу-вверх (редукция цепочки)

A= T; Q = {q1,q2}. q0 = q1. . F = { q2}.

Функция d строится по следующей схеме:

" i ai Î T  (q1,ai, ) ® (q1, ai) /*терминальные символы записываются в магазин в независимости от состояния магазина.*/;

(q1,,a) ® (q1, A) /* Если A ® a Î P и на вершине магазина находится цепочка a, то вместо нее в «магазин» записывается не-терминальный символ А. При этом состояние входной ленты не изменяется.*/;

(e,q1,Ss) ® (q2) - /*переход в конечное состояние при условии, что все символы с входной ленты прочитаны, а в «магазине» записан один символ S, не считая s.

в) автомат Глушкова:

Алгоритм построения этого автомата подробно рассмотрен в лекциях. Ниже приведен пример построения автомата этого типа.

Грамматика: G = <{a,b},{S,A}, S, { S → aSb | aAb, A → ab | aA}>

1. Представим правила вывода в виде системы правил, в правой части которых записываются  регулярные выражения, взятые в круглые скобки.

S ::= (aSb + aAb)

A ::= (ab + aA)

2. Преобразуем регулярные выражения, вынося за скобки общие символы. S ::= (a (S + A) b)

                  A ::= (a(b + A)).

3. Присвоим нетерминальным символам, стоящим справа от знака равенства, индексы. Тем самым мы делаем эти символы уникальными, кроме того, определяем множество символов «магазина» Z = {S1,A1,A2}

S ::= (a (S1 + A1) b)

A ::= (a(b + A2))

4. Определяем число состояний автомата методом нумерации черточек.

S ::= |1(|1a|3 (|3S1 |4 + |3A1|4)|4 b|2)|2

A ::= |5(|5a|7(|7b|6 + |7A2|6)|6)|6  

Таким образом,  множество состояний автомата Q = {1, 2, 3, 4, 5, 6, 7},

q0 = 1, F = {2}.

4. Строим функцию перехода δ:

 

 

 

1

2

3

4

5

6

7

 

a

3

 

 

 

7

 

 

 

b

 

 

 

2

 

 

6

P

A1

 

 

 

 

 

4

 

O

A2

 

 

 

 

 

6

 

P

S1

 

4

 

 

 

 

 

PUSH

 

 

 

S1, 1; A1, 5

 

 

 

A2, 5

 

5. Автомат построен MP = <{a,b}, {1, 2, 3, 4, 5, 6, 7}, {S1,A1, A2}, δ , σ, q0 =1, F = {2}> δ – задана таблицей.

6. Пример работы данного распознавателя на цепочке aaaabb Î L(G):

(1, aaaabbb, σ) → (3, aaabbb, σ) → (1, aaabbb, S1) → (3, aabbb, S1)

→ (5, aabbb, A1S1)→ (7, abbb, A1S1) → (5, abbb, A2A1S1) →

     (7, bbb, A2A1S1)

→ (6, bb, A2A1S1) → (6, bb, A1S1)  → (4, bb, S1) → (2,b ,S1) →

     (4,b , σ) → (2, , σ)

Данная цепочка допускается построенным автоматом, так как автомат перешел в конечное состояние, полностью прочитав цепочку на входной ленте, при пустом «магазине».

S → aSb → aaAbb→ aaaAbb → aaaabbb – вывод этой цепочки в заданной грамматике.

Задачи и упражнения

 

1. Построить МП-автомат, допускающий цепочки, выводимые в грамматике G=<{(,)}, {S}, S, {S®SS½(S)½( )}>

МП-автомат, работающий сверху вниз;

МП-автомат, работающий снизу вверх;

МП-автомат Глушкова.

сделайте разбор цепочки ((())()) всеми построенными выше автоматами.

2. Определите цепочки какого языка распознает следующий автомат?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

a

 

 

 

 

 

 

9

 

 

12

 

 

 

16

 

 

 

 

b

 

 

 

 

6

 

9

 

 

 

 

 

11

 

 

 

 

 

c

 

 

4

 

 

 

9

 

 

 

 

 

 

 

 

 

15

 

A1

 

 

 

 

 

 

 

 

 

 

3

 

 

 

 

 

 

P

A2

 

 

 

 

 

 

 

 

 

 

13

 

 

 

 

 

 

O

B1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5

 

 

P

B2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

17

 

 

 

D1

 

 

 

 

 

 

 

2

 

 

 

 

 

 

 

 

 

 

D2

 

 

 

 

 

 

 

8

 

 

 

 

 

 

 

 

 

PUSH

10,A1

 

 

14,B1

 

7,D1

 

 

7,D2

12