22

Глава 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, ^*.

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

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

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

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