Формальное определение грамматики. Форма Бэкуса-Наура

Понятие о грамматике языка

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

Фактически определение грамматики языка, указывает правила порождения цепочек символов, принадлежащих этому языку. Таким образом, еще одно определение грамматики - это генератор цепочек языка. Она относится ко второму способу определения языков - порождению цепочек символов.

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

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

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

1) первые (определяющие синтаксические конструкции языка) довольно легко поддаются формальному описанию;

2) вторые (определяющие семантические ограничения языка) обычно излагаются в неформальной форме.

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

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

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

Для полного формального определения грамматики кроме правил порождения цепочек языка необходимо задать также алфавит языка.

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

· T – множество терминальных символов.

· N – множество нетерминальных символов. NÇ T= Ø;

· P – множество правил (продукций) грамматики вида a→b, где aÎ V⁺.bÎ V*.

· S – стартовый (начальный) символ грамматики (или аксиома грамматики) S Î N.

Множество V=N È T - полный алфавит грамматики G.

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

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

Эти два множества не пересекаются: каждый символ может быть либо терминальным, либо нетерминальным. Ни один символ в алфавите грамматики не может быть нетерминальным и терминальным одновременно.

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

P - конечное множество правил грамматики, т.е. цепочек вида φ→ψ и называемых также правилами подстановки или продукциями, при этом φ, ψ – цепочки в словаре V = N U Т и φ є (T U N)* N(T U N)*, ψ є (N U T)*. Множество правил подстановки Р называют также схемой грамматики. Цепочка, стоящая в левой части правила грамматики, обязательно содержит хотя бы один нетерминальный символ. В правой же части правила в общем случае может стоять произвольная цепочка из терминальных и нетерминальных символов, включая и пустую цепочку λ.

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

Форма Бэкуса-Наура предусматривает, что нетерминальные символы записываются в угловых скобках:< >. Вместо знака «→» в правилах грамматики можно использовать знак «::=».

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

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

Р:

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

<ч>→<ц>|<ч><ц>

<ц>→0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

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

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

· множество нетерминальных символов N содержит три элемента: символы <число>,<ч>и<ц>;

· множество правил содержит 15 правил;

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

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

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

Та же самая грамматика для целых десятичных чисел со знаком, в которой нетерминальные символы обозначены большими латинскими буквами (это соглашение которое обычно применяется по умолчанию):

G’({0,1,2,3,4,5,6,7,8,9..-+},{S,T,F},P,S)

P:

S→T|+T|-T

T→F | TF

F→0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Здесь изменилось только множество нетерминальных символов. Теперь N={S,T,F}. Язык, заданный грамматикой, не изменился - грамматики G и G’ эквивалентны.

Дата добавления: 2014-12-27