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

Фоpмальная гpамматика - фоpмальная система пpавил, описываю-

щих в опpеделенном аспекте некотоpый язык G=(Vt,Vn,P,S), где:

Vt - множество терминальных символов;

Vn - множество нетерминальных символов;

P - конечный набор правил подстановки;

S С Vn - начальный символ.

Символы в левой и правой частях правил в совокупности обра-

зуют словарь V, V = Vt U Vn.

Символы грамматики G, встречающиеся в левой части правил,

называются нетерминальными. Множество нетерминалов Vn С V являет-

ся подмножеством словаря, остальная часть множества V образует

множество терминальных симолов Vt С V.

В зависимости от ограничений, накладываемых на грамматичес-

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

(по Хомскому). Их определение содержится ниже.

Правила автоматной гpамматики имеют вид:

U ::= N или U ::= NW, где N C Vt, а U, W C Vn.

Правила контекстно-свободной гpамматики имеют вид:

U ::= u, где U C Vn, u C V.

Правила контекстно-зависимой грамматики имеют вид:

xUy ::= xuy, где U C Vn, x, u, y C V.

Грамматика без ограничений на грамматичекие правила:

u ::= v, где u C V+ и v C V*.

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

вается цепочкой.

Непосредственный вывод. Пусть G - грамматика. Говорят, что

цепочка v непосредственно порождает цепочку w, т.е. v -> w, если

для некоторых цепочек x и y можно написать v = xUy, w = xuy, где

U ::= u - правило грамматики G. Также говорят, что w непосред-