Специальная математика (стр. 22 )

1.  M = N

N = M.

2.  M = N, N = P

M = P.

3.  M = N

PM = PN.

4.  M = N

MP = NP.

5. M = N

lx. M = lx. N.

Рассмотрим примеры b-редукции (в прикладной варианте записи)

(lх. х + 2у)(а) = а + 2у

(lу. х + 2у)(а) = х + 2а

(lх.(lу. х + 2у))(а)(b) = (lу. а + 2у)(b) = a + 2b

(lx.((ly. xy)u))( lv. v) = (ly.(lv. v)y)u = (lv. v)u

(lx.((ly. xy)u))( lv. v) = (lx. xu)(lv. v) = (lv. v)u

(lx. xx) (lx. xx) = (lx. xx) (lx. xx) = (lx. xx) (lx. xx) =…

((lx. x*3) (ly. if y > 4 then e = 2 else x/2) (ly. y>2)) (5) = 2*5 = 10

(ln.(lx. x-n))(2) = lx. x-2

(lf.2*f(8) – f(f(8)))(half) = 2*8/2 – (8/2)/2 = 6 (half – половина).

7. Формальные грамматики

7.1. Понятие формальной грамматики

Формальная грамматика - это четверка G = <VN, VT, P, S >, в которой

VN - нетерминальный словарь (множество нетерминальных символов);

VT - терминальный словарь (множество терминальных символов ) ;

P - множество грамматических правил;

S Î VN - начальный нетерминальный символ.

Метаязык - язык, с помощью которого описывается язык:

::= - есть по определению;

| - “ исключающее или”;

< ... > - внутри – один нетерминальный символ ;

[ ] - необязательная часть;

, - запятая – разделитель при перечислении.

Пример: Построим грамматику G1:

<прог>::=<оп> | <оп>; <прог>

<оп>::=<пер> := <выр>

<пер>::=a | b | c

<выр>::=<пер> | <пер> <зн> <выр>

<зн>::= + | - | * | /

V = VN È VT - обобщенный словарь.

V* - цепочка символов (строка, слово) из обобщенного словаря;

V*N - цепочка символов (строка, слово) из нетерминального словаря;

V*T - цепочка символов (строка, слово) из терминального словаря.

e Î V - пустой символ, входит в обобщенный словарь.

Строка a непосредственно порождает строку b и обозначается: a Þ b,

если a = vxw b = vyw и существует некоторое правило p: x::= y,

где v, w, Î V* , х Î VN, у = V* \ {e}

Строка a порождает строку b и обозначается a Þ* b, когда от строки a можно перейти к строке b с помощью последовательности непосредственных порождений.

Продолжая пример:

<прог> Þ <оп> ; <прог> Þ <оп> ; <оп> Þ <пер> := <выр> ; <оп> Þ*

a := b + c; c := a + b - c;

Грамматика, использующая процедуры (непосредственного) порождения – порождающая грамматика.

Строка b непосредственно свертывается в строку a и обозначается: a Ü b,

если a = vxw b = vyw и существует некоторое правило p: x::= y,

где v, w, Î V* , х Î VN, у = V* \ {e}

Строка b свертывается в строку a и обозначается a *Ü b, когда от строки b можно перейти к строке a с помощью последовательности непосредственных свертываний.

Грамматика, использующая процедуры (непосредственного) свертывания –распознающая грамматика.

Строки символов из обобщенного словаря, получающиеся в процессе порождения или свертывания, называются сентенциальными формами.

Язык L, порождаемый данной грамматикой G - множество нетерминальных цепочек, порождаемых из начального нетерминального символа. Такие терминальные цепочки называются предложениями данного языка.

L(G) = { x Î V*N | S Þ* x }

Аналогично можно определить язык L через свертывание.

L(G) = { x Î V*N | S *Ü x }

Замечание. Другой вариант метаязыка

вместо ::= используется стрелка ® , терминальные символы записываются маленькими (строчными) буквами, а нетерминальные – большими (прописными) буквами.

Такой вариант мета языка чаще используется в математической литературе. Первый предпочитают использовать в литературе для программистов. Так что мы будем пользоваться и тем и другим вариантами…

7.2. Деревья вывода

Порождение и свертывание можно также представлять с помощью деревьев вывода.

Пусть дана грамматика.

I ® T

I ® I + T

I ®I - T

T ® M

T ® T*M

T ® T/M

M ® (I)

M ® K

K ® a

K ® b

K ® c

Построим дерево вывода.

Для предложения a * b + c дерево вывода будет:

I

I T

T M

 

T * M K

 

M K c

 

a b

Этот же результат можно получить и другим способом:

I ® I + I

I ® I - I I

I ® I*I

I ® I/I I + I

I ® (I)

I ® a I * I c
I ® b

I ® c a b

7.3. Классификация языков по Хомскому

Н. Хомский предложил подразделять формальные грамматики, как и порождаемые ими языки на четыре типа.

Тип 0 - формальная грамматика, на правила которой не накладывается никаких ограничений. Для исследования они интереса не представляют – поскольку режим «делай, что хочешь» для математики и для практики редко представляют интерес.

Тип 1 . К этому типу относятся грамматики, правила которых имеют вид:

vaw ::= vbw, где

v, w Î V* - произвольные цепочки символов, возможно пустые;

a Î VN - нетерминальный символ;

b Î V*\{e} [ иногда b Î V* ].

[ b Î V* ].

Эти грамматики еще называют контекстно-зависимыми или КЗ-грамматиками.

Здесь строка a заменяется на строку b в рамках какого-то контекста. Часто используется на практике подмножество таких грамматик, называемое грамматиками непосредственных составляющих:

vAw ::= vaw, где v, w, aÎV* , AÎVN

При этом часто рассматриваются неукорачивающиеся грамматики (что обеспечивается непустой цепочкой b).

Тип 2 . К этому типу относятся грамматики, правила которых имеют вид:

a ::= b

a Î VN - нетерминальный символ;

b Î V*\{e}:

Здесь также представляют наибольший интерес грамматики непосредственных составляющих.

Такие грамматики называются контекстно-свободными грамматиками или КС-грамматиками.

Языки программирования большей частью описываются грамматиками этого типа.

Тип 3 . К этому типу относятся грамматики, правила которых имеют один из двух видов:

æ A := Bcö

è A := b ø

где A, B, C ÎVN ; b, c Î VT ;

Это так называемый леворекурсивный вариант. В качестве альтернативы возможен и праворекурсивный вариант:

æ A := сBö

è A := b ø

Такие грамматики называют регулярными или автоматными грамматиками. Лексический анализ в компиляторе обычно наиболее целесообразно описывать с помощью этих грамматик.

7.4. Распознающие автоматы

Распознающим называется автомат Мура с множеством выделенных состояний, называемых конечными. Говорят, что автомат распознает входное слово, если, начав свою работу в одном из начальных состояний, он заканчивает ее в одном из конечных.

Пример: Автомат, распознающий слова содержащие попарное вхождение букв а

и b, вроде aabbbbaa. f1, f2 - конечные состояния

2 a

a

b f1

a, b a a