spoPresentation2

	Удаление левой рекурсии
4.2. i z 4
	5.2. i = 3; j = 1; // Ai = B; Aj = S;
	6.2.1. правил в P вида BoSJ нет
	7.2.1. j = 2; j < i; переход к п.6. // Ai = B; Aj = A;

6.2.2. правил в P вида BoAJ нет

7.2.2. j = 3; переход к п.2

2.3. BoCc | d P’ = P’ { BoCc | d }; N’ = N’

{B}; // P’ = { SoAa; AoBb; BoCc | d }4.3. i z 4

5.3. i = 4; j =1; Ai = C; Aj = S;

6.3.1. правил в P вида CoSJ нет

231

Удаление левой рекурсии

7.3.1. j = 2; j < i; переход к п.6. // Ai = C; Aj = A;

6.3.2. { CoAz } P, {AoBb} P’ P = P { CoBbz } \ { CoAz }

//P = { SoAa; AoBb; BoCc | d; CoBbz | a}

7.3.2. j = 3; j < i; переход к п.6. // Ai = C; Aj = B;

6.3.3. { СoBbz } P, { BoCc | d } P’ P = P { Co {Cc | d} bz = Ccbz | dbz } \ { СoBbz }

//P = { SoAa; AoBb; BoCc | d; Co Ccbz | dbz | a }

7.3.3. j = 4; переход к п.2

232

Удаление левой рекурсии

3. P’ = P’ { { AioE1 | E2 |…| Ep | E1Ai’ | E2Ai’ |…| EpAi’; Ai’oD1 | D2 |…|

Dm | D1Ai’ | D2Ai’ |…| DmAi’ }

AioAiE P, E V* и Ai=AiD1 | AiD2 |…| AiDm | E1 | E2 | Ep, где j, 1djdp, не Ej = AkJ, k d i }

N’ = N’ { Ai, Ai’ }

3.4. Co Ccbz | dbz | a P’ = P’ { Codbz | a | dbzD | aD; Docbz | cbzD }; N’ = N’ { C, D }

4.4. i = 4

P’ = { SoAa; AoBb; BoCc | d; Codbz | a | dbzD

| aD; Docbz | cbzD };

N’ = { S,A,B,C,D }

233

МП - автоматы

Язык называется контестно-свободным, если он определяется грамматикой G(N,T,P,S), в которой правила имеют вид AoE, где A N, EV*

Распознавателями КС языков являются автоматы с магазинной (стековой) памятью

МП-автомат: R(Q,A,Z,G, q0, z0, F), где

Q – множество состояний автомата

A – алфавит входных символов

Z – специальный конечный алфавит магазинных символов автомата, A Z

234

МП - автоматы

G - функция переходов, отображает множество Q x ( A {O} ) x Z на конечное

множество подмножеств P ( Q x Z* )

q0 Q – начальное состояние автомата

z0 Z – начальный символ магазина

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

В отличие от КА МП-автомат имеет стек, обычно в него помещаются терминальные и нетерминальные символы

235

Конфигурация МП - автомата

Переходы между состояниями зависят не только от входного символа, но и от символа на вершине стека

Конфигурация автомата определяется: состоянием автомата, цепочкой еще не прочитанных символов, содержимым стека

(q,D,Z)

Один такт работы автомата ( q, aD, zZ ) ( q’, D, JZ ), где (q’,J) G ( q, a, z ), q, q’ Q, a A {O}, D A*, z Z {O}, J,Z Z*

236

Конфигурация МП - автомата

При выполнении такта в стеке заменяется символ, соответствующий условию перехода, на цепочку, соответствующую правилу перехода. Первый символ этой цепочки становится новой вершиной стека

Автомат может и не извлекать символ из стека (J = z)

Допускаются переходы, при которых входной символ игнорируется, оставаясь на следующий такт. Такие переходы (такты) называются O-переходами

237

Конфигурация МП - автомата

Начальная конфигурация определяется как (q0, D, z0), D A*, а множество конечных конфигураций как (q, O, Z) q F, Z Z*

МПА допускает (принимает) цепочку символов, если получив ее на вход и находясь в начальной конфигурации, он может перейти в одну из конечных конфигураций

Язык, определяемый МПА – множество всех цепочек, которые допускает автомат

Два МПА R1 и R2 эквивалентны, если они определяют один и тот же язык L(R1)=L(R2)

238

МП - автоматы

МПА допускает цепочку с опустошением магазина, если по окончании разбора автомат находится в одном из конечных состояний, а магазин пуст (конфигурация

(q,O,O) )

Для любого МПА всегда можно построить эквивалентный ему МПА, допускающий цепочки с опустошением стека

Расширенный МПА может заменять не один символ, а цепочку на вершине стека. Функция переходов для него отображает множество

Q x ( A {O} ) x Z*

239

МП - автоматы

Для любого расширенного МПА всегда можно построить эквивалентный ему обычный

Для произвольной КС-грамматики всегда можно построить МПА, задающий тот же язык

Для произвольного МПА всегда можно построить КС-грамматику, задающую тот же язык

240