Лабораторные работы 1-7(старые) / Отчет по ТЯП6

Санкт-Петербургский государственный электротехнический университет

КАФЕДРА МО ЭВМ

ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ N6

по дисциплине "Теория языков программирования"

“Алгоритм разбора для LR(0) – грамматик.”

Преподаватель: Самойленко В.П.

студенты гр. 0341 Юбрин А.Н.

Шин Е.Д.

Санкт-Петербург

2002

1 Построить LR(0) – распознаватель грамматики G = (T,N,S,R).

T= {a,b,c}

N= {S,A,B}

R= {S  aSb (1), S  aSc (2), S  ab (3)}

V={S,a,b,c}

V_P={S₀, a_11, S_12, b₁₃, a_21, S₂₂, c₂₃, a₃₁, b₃₂, }

1. Построим управляющую таблицу, для функции f

Она должна содержать 10 строк помеченных символами из множества V_P и 4 столбца помеченных символами из T{}

Управляющая таблица f

	a	b	c	
S0				ДОП
a11	П	П	П
S12	П	П	П
b13	C,1	C,1	C,1	C,1
a21	П	П	П
S22	П	П	П
c23	C,2	C,2	C,2	C,2
a31	П	П	П
b32	C,3	C,3	C,3	C,3
	П	П	П

Построим таблицу ВПОД

Для этого определим отношения

S₁₂ ВПОД b₁₃

S₂₂ ВПОД c₂₃

a₃₁ ВПОД b₃₂

 ВПОД Y, где YВПЕРВ(S₀), ВПЕРВ(S₀)={a₁₁, a₂₁, a₃₁, S₀}

a₁₁ ВПОД Y, где Y ВПЕРВ(S₁₂)={a₁₁, a₂₁, a₃₁, S₁₂}

a₂₁ ВПОД Y, где Y ВПЕРВ(S₂₂)={a₁₁, a₂₁, a₃₁, S₂₂}

	S0	a11	S12	b13	a21	S22	c23	a31	b32
S0
a11		1	1		1			1
S12				1
b13
a21		1			1	1		1
S22							1
c23
a31									1
b32
	1	1			1			1

Построим по таблице недетерминированную управляющую таблицу для g

Управляющая таблица f

	a	b	c	S
S0
a11	a11, a21, a31			S12
S12		b13
b13
a21	a11, a21, a31			S22
S22			c23
c23
a31		b32
b32
	a11, a21, a31			S0

Преобразуем в детерминированный автомат

{a_11, a₂₁, a₃₁} - a_x

{S₁₂, S₂₂} - S_x

Запишем окончательный вариант управляющей таблицы

	a	b	c		a	b	c	S
S0				ДОП
ax	П	П	П		ax	b32		Sx
Sx	П	П	П			b13	c23
b13	C,1	C,1	C,1	C,1
c23	C,2	C,2	C,2	C,2
b32	C,3	C,3	C,3	C,3
	П	П	П		ax			S0

ПРИМЕР работы анализатора

SaScaabc

^{(2) (3)}

Для цепочки: aabc

Начальная конфигурация (, aabc, ) |(a_x, abc, ) |(a_xa_x, bc, ) |(a_xa_xb, c, ) |

(a_xS_x, c, 3)|(a_xS_xc₃₂, , 3) |(S₀, , 32) |(, , 32)

Выходная цепочка: 3 2