Понятие грамматики языка. Обозначения

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

Всякая конечная последовательность символов алфавита называется цепочкой. Так a, b, c, ab, aaca - цепочки в алфавите A = {a,b,c}.

Допустим существование пустой цепочкиe, не содержащей ни одного символа.

Важен порядок символов в цепочке. Цепочка ab отличается от ba.

Длина цепочки ½a½ равна количеству символов в цепочке. Так ½a½=1, ½abc½=3, ½ e ½=0.

Если a иb цепочки, то их конкатенациейab является цепочка, полученная путем дописывания символов цепочки b вслед за символами цепочки a . Например, если a=ab, b=bc, то ab= abbc и ba= bcab. Поскольку e - цепочка, не содержащая символов, то в соответствии с правилами конкатенации для любой цепочки a можно записать ea=ae=a.

Обращением цепочки a (обозначается a ^R ) называется цепочка a, записанная в обратном порядке, т.е. если a = a₁...a_n, где все a_i- символы, то a^R= a_n... a₁. Кроме того, e ^R=e .

Языком Lв алфавите A называется множество цепочек в A.

Это определение подходит почти для любого языка. Языки Паскаль, С, Модула-2, английский и русский охватываются этим понятием.

Рассмотрим простые примеры языков в алфавите A.

Пустое множество Æ - это язык. Множество {e },содержащее только пустую цепочку, также является языком.

Заметим, что Æ и { e } - это два разных языка.

Обозначим через A^* множество, содержащее все цепочки в алфавите A, включая e.

Например, если A бинарный алфавит {0,1}, то

A^* = { e , 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, ...}.

Цепочку, состоящую из i символов a будем обозначать a ⁱ, то есть a⁰=e, a¹= a, a²= aa, a³= aaa и т.д.

Итак, язык L – это некоторое множество цепочек в некотором алфавите A. Как описать этот язык. Если L состоит из конечного числа цепочек, то самый очевидный способ состоит в составлении списка всех цепочек этого языка. Однако для большинства языков нельзя или нежелательно устанавливать верхнюю границу длины самой длинной цепочки. Следовательно, приходится рассматривать язык, содержащий сколь угодно много цепочек. Очевидно, их нельзя описать перечислением цепочек. Мы хотим, чтобы описание языка было конечным (имел конечный объем), хотя сам язык может быть и бесконечным. Известно несколько методов такого описания. Один из основных методов состоит в использовании порождающей системы, называемой грамматикой.

Грамматика языка – множество объектов: G = <S, V_T, V_N, R>

S – начальный, выделенный символ грамматики ( аксиома грамматики);

V_Т – множество терминальных символов (терминал – конечный, неделимый символ);

V_N– множество нетерминальных символов (понятий ) ;

R – множество правил грамматики.

Грамматику языка обозначим через G, возможно с индексом, илиG(S). Язык L, определяемый грамматикой G, обозначимL(G).

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

Нетерминальные символы обозначаются заглавными латинскими буквами, либо текстом, заключенными в угловые скобки: <нетерминал>.

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

V*- множество цепочек, построенных на алфавите языка V.

Правила обычно записывают в виде a ® b или a ::=b, что означает a порождает (состоит из)b.

Язык, порождаемый грамматикой,- это множество цепочек, которые состоят только из терминалов и выводятся, начиная с одного, особо выделенного, нетерминала S, называемого начальным символомили аксиомой грамматики. Среди множества правил грамматики должно присутствовать хотя бы одно правило S® b .

Обозначение правил в форме записи x ::= h относится к нотации Бэкуса – Наура (бэкусовой нормальной форме - БНФ). В этой нотации используются обозначения:

::= - это есть, ô- или,

[ ]- факультативный элемент (необязательная часть), то есть конструкция в скобках может присутствовать или отсутствовать во фразе языка,

{ }- множественный элемент (одно из, элемент выбора), то есть во фразе языка используется один из элементов внутри скобки.

Правило вида a ::=b ½bg можно представить a ::=b [g ].

Бэкусовая нормальная форма (БНФ) или форма Бэкуса-Наура была предложена Д.Бэкусом в 1959 году и впервые применена П.Науром для описания языка Алгол-60. Метаязыком называется язык, который используется для описания других языков.

Правила вида x ® h являются порождающими, правила вида x h - распознающими.

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