17

Глава 2. Способы задания языков

Теория формальных языков (формальных грамматик) занимается описанием, распознаванием и переработкой языков. Описание любого языка должно быть конечным, хотя сам язык мо­жет содержать бесконечное множество цепочек. Полезно иметь возможность описания отдельных типов языков, имеющих те или иные свойства, т. е. иметь различные типы конечных описаний. Синтаксис языка можно задать с использованием синтаксических диаграмм или другим альтернативным способом, воспользовавшись нотацией Бэкуса-Наура (НБН). При ис­пользовании нотации Бэкуса-Наура нетерминальные символы (подлежащие дальнейшему определению) языка заклю­чаются в угловые скобки вида < ... > .

Последовательность символов : : = означает «определя­ется как», а символ | означает "или". Пример описания в нотации Бэкуса-Наура арифметических выражений, содержащих переменные a, b,приведен ниже.

< выражение > : : = < терм > | < терм > + < выражение > | < терм > - < выражение >

< терм > : : = < множитель > | < множитель > * < терм > | < терм > / < множитель >

< множитель > : : = a|b| ( < выражение > )

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

2.1. Грамматики.

2.1.1. Основные понятия и обозначения.

Основными объектами грамматики являются базовые элементы языка или терминальные символы, а также цепочки, построенные из этих элементов.

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

• прописными буквами обозначаются нетерминальные символы языка;

• строчными буквами латинского алфавита обозначаются терминальные символы языка;

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

• символ «→»используется для обозначения отношения "определяется как".

Введем в рассмотрение пустую цепочку ε, не содержащую ни одного символа.

Длинойцепочки будем называть число символов, входящих в эту цепочку, например:

B = abab, |B| = |abab| = 4,

| ε| = 0.

Конкатенациейдвух цепочекXиYназывается такая цепочкаZ, которая получается непосредственным слиянием цепочкиX, стоящей слева, и цепочкиY, стоящей справа. Например, еслиX = ffg,Y = ghh, то конкатенацияXиY– это цепочкаZ=ffgghh.

Будем обозначать через А^*множество всех возможных цепочек конечного множества А базовых элементов (символов), включая пустую цепочкуε; Множество А называют такжеалфавитом. Любое множество цепочек LA^*называетсяформальным языком, определенным на алфавите А.

2.1.2. Классификация грамматик по Хомскому.

Грамматика – это математическая система, определяющая язык. Будем рассматривать класс грамматик, называемых грамматиками Хомского или грамматиками составляющих. В грамматике, определяющей язык L, используется два типа конечных непересекающихся множества символов – множество нетерминальных символов, которое будет обозначаться буквой N, и множество терминальных символов, обозначаемое. Из терминальных символов образуются слова (цепочки) определяемого языка. Нетерминальные символы служат для задания слов языка L.

Основу грамматики составляет конечное непустое множество Pправил образования слов языка. Правило – это пара

(N  )^*N(N  )^* → (N  )^*.

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

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

Формально грамматика задается четверкой

G = (N, , P, S),

где N– конечное множество нетерминальных символов;

– конечное множество терминальных символов, непересекающееся с N;

P– конечное множество правил вида,и– цепочки, причемсодержит хотя бы один нетерминальный символ, а на цепочкуне наложено никаких ограничений;

S– начальный или исходный символ.

Будем использовать следующее обозначение: если V– это множество, тоV^*– это замыкание множестваVили, другими словами, множество всех конечных последовательностей (цепочек), составленных из множестваV.

На множестве (N )^*вводятся отношенияи^*. Если– продукция изP,и– цепочки из множества(N )^*, тоТо есть продукцияприменяется к цепочкедля получения цепочкиили, другими словами, цепочканепосредственно получается (порождается, выводится) из цепочкипосле применения продукцииДве цепочки связаны отношением, если вторая цепочка получается из первой применением продукции изP.Пусть имеется

____…_m-1_m

Здесь __…_m цепочки из(N )*.Последовательность приведенных выше отношений может быть записана так:_^_m .

Язык L, порождаемый грамматикойG, – это множество цепочек, которые состоят только из терминальных символов и которые можно вывести из символаS.Формально это можно записать следующим образом:

L = *, S ^*}.

Грамматики классифицируются по виду их правил. Грамматика называется регулярной, если каждое правило имеет вид

A xB, A → Bx или A → x, где A, B  N, x ^*.

Грамматика называется контекстно-свободной (бесконтекстной),если каждое правило имеет вид

A →, гдеA  N, ^*.

Грамматика называется контекстно-зависимой (не укорачивающей),если каждое правило имеет вид

→, где 

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

Иерархии грамматик соответствует иерархия формальных языков, каждый из которых может быть порожден некоторой формальной грамматикой.