Тип 0: грамматики с фразовой структурой

Языки и грамматики

 

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

Для задания языка программирования требуется:

1) определить множество допустимых символов языка;

2) определить множество правильных программ языка;

3) задать смысл для каждой правильной программы.

Первые два вопроса полностью или частично удается решить с помощью теории формальных языков.

Грамматика – описание способа построения предложений некоторого языка. Грамматика – математическая система, определяющая язык, т.е. – генератор цепочек языка.

Грамматику языка можно описать различными способами. Для синтаксических конструкций языков программирования можно использовать формальное описание грамматики, построенное на основе системы правил (или продукций).

Цепочкой символов называют произвольную упорядоченную конечную последовательность символов, записанных друг за другом. Количество символов в ней называют длиной цепочки.

Правило (или продукция) – упорядоченная пара цепочек символов (). В правилах важен порядок цепочек, поэтому их чаще записывают в виде → . Такая запись читается как « порождает » или « по определению есть ».

Формально грамматика G определяется как четверка G(VT, VN, P, S), где

VT – множество терминальных символов или алфавит терминальных символов;

VN – множество нетерминальных символов или алфавит нетерминальных символов;

P – множество правил грамматики, вида → , где (VN VT)⁺, (VN VT)^*;

S – целевой (начальный) символ грамматики S VN.

Обозначение вида V⁺ означает множество без пустой цепочки, а обозначение V^* – множество, включающее пустую цепочку.

Алфавиты терминальных и нетерминальных символов грамматики не пересека­ются: VN VT = пустое множество. Это значит, что каждый символ в грамматике может быть либо терминальным, либо нетерминальным, но не может быть терминальным и нетерминальным одновременно. Множество V = VN VT называют полным алфавитом грамматики G.

Целевой символ грамматики – это всегда нетерминальный символ.

Множество терминальных символов VT содержит символы, которые входят в алфавит языка, порождаемого грамматикой. Как пра­вило, символы из множества VT встречаются только в цепочках правых частей правил. Множество нетерминальных символов VN содержит символы, которые определяют слова, понятия, конструкции языка. Каждый символ этого множест­ва может встречаться в цепочках как левой, так и правой частей правил грамма­тики, но он обязан хотя бы один раз быть в левой части хотя бы одного правила. Правила грамматики обычно строятся так, чтобы в левой части каждого правила был хотя бы один нетерминальный символ.

Во множестве правил грамматики может быть несколько правил, имеющих оди­наковые левые части, вида: → ₁, → ₂,... → _n. Тогда эти правила объеди­няют вместе и записывают в виде: → ₁ | ₂| … | _n. Одной строке в такой записи соответствует сразу n правил.

Такую форму записи правил грамматики называют формой Бэкуса-Наура. Форма Бэкуса-Наура предусматривает, как правило, также, что нетерминальные симво­лы берутся в угловые скобки: < >.

Пример грамматики, которая определяет язык целых десятичных чисел со знаком:

G ({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, –, +}, {<число>, <чсл>, <цифра>}, Р, <число>),

где Р:

<число> → <чсл> | +<чсл> | –<чсл>

<чсл> → <цифра> | <чсл><цифра>

<цифра> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Cоставляющие элементы данной грамматики G:

множество терминальных символов VT содержит двенадцать элементов: де­сять десятичных цифр и два знака;

множество нетерминальных символов VN содержит три элемента: символы

<число>, <чс> и <цифра>;

множество правил содержит 15 правил, которые записаны в три строки (то есть имеется только три различных правых части правил);

целевым символом грамматики является символ <число>.

Особенность рассмотренных формальных грамматик в том, что они позволяют определить бесконечное множество цепочек языка с помощью конечного набора правил (конечно, множество цепочек языка тоже может быть конечным, но даже для простых реальных языков это условие обычно не выполняется). Приведенная выше в примере грамматика для целых десятичных чисел со знаком определяет бесконечное множество целых чисел с помощью 15 правил.

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

Чтобы рекурсия не была бесконечной, для участвующего в ней нетерминального символа грамматики должны существовать также и другие правила, которые определяют его, минуя его самого, и позволяют избежать бесконечного рекурсивного определения (в противном случае этот символ в грамматике был бы просто не нужен). Такими правилами являются <чсл> → <цифра>.

Язык, заданный грамматикой G, обозначается как L(G).

Две грамматики G и G' называются эквивалентными, если они определяют один и тот же язык: L(G) = L(G'). Две грамматики G и G' называются почти эквивалентными, если заданные ими языки различаются не более чем на пустую цепочку символов: L(G) { } = L(G') { }, где – пустая цепочка.

Грамматика языка программирования содержит правила двух типов: первые (определяющие синтаксические конструкции языка) довольно легко поддаются формальномуописанию; вторые (определяющие семантические ограничения языка) обычно излагаются в неформальной форме.

Любое описание (или стандарт) языка программирования обычно состоит из двух частей:

1) формальное изложение правил построения синтаксических конструкций,

2) описание семантических правил на естественном языке.

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

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

Тип 0: грамматики с фразовой структурой

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

12Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: