Реферат: Проектирование трансляторов

Всякая конечная последовательность символов языка называет-

ся цепочкой.

Пустая цепочка - цепочка, не содержащая ни одного символа.

Ее длина равна 0.

Множества цепочек в алфавите обычно обозначаются заглавными

буквами.

Х = mABCn

│ │

голова хвост

xy - конкатенация цепочек x, y. х - голова, у - хвост цепоч-

ки z=xy.

Произведение АВ двух множеств цепочек А и В:

AB = { xy │ x C A, y C B }

Степень цепочки: x^0 - "", x^N = x^(N-1)*x

V* - рефлексивно-транзитивное замыкание (итерация).

V+ - транзитивное замыкание (усеченная итерация).

Бесконечные множества:

V* = V^0 U V^1 U ... U V^N U ...

Формальное описание строки:

V*={z │ z = "",z = xU}, z,x C V*, U C V - любой символ из V.

Строка x непосредственно порождает y относительно P (x->y),

когда существуют строки u, w, (возможно пустые) такие, что x=uVw,

y=uzw, V ::= z C P.

Строка x порождает y относительно P (x=>y), когда сущес-

твует последовательность строк x0, x1, x2, ... xN, такая, что

x=x0, y=xN, xI-1 -> xI (I=1,2,...,N).

Язык - некоторое множество предложений:

Lg = { x │ x C Vt*, S => x }.

Порождение (либо свертывание) строк Lg можно представить в