 |
Пункт 2. Понятие о формальной грамматике.
|
|
|
|
Формальная грамматика – это математическая система, определяющая язык посредством порождающих правил. В отличие от формулы для определения множества формальная грамматика содержит ряд взаимосвязанных правил для получения (порождения, генерации) строк языка.
Пример. Даны два нумерованных правила:
1) 
2) 
Символы 0 и 1 принадлежат алфавиту языка, а 
- вспомогательный символ. Строки языка получаются путем применения этих правил в любой комбинации, причем вспомогательный символ в строке языка не должен присутствовать. Вспомогательных символов может быть любое необходимое количество.
Рассмотрим применение данных правил в последовательности 1, 1, 2:
. Это есть вывод строки 0011 из символа .
Руководствуясь правилами 1 и 2, можно вывести все строки соответствующего языка 
и никакие другие. Таким образом, формальная грамматика есть своеобразный алгоритм порождения всех строк языка, который эта грамматика описывает.
Пункт 3. Определение формальной грамматики.
Формальная грамматика определяется как четверка 
, в которой приняты следующие обозначения:
· 
- алфавит языка, строки которого порождает грамматика. Элементы множества называют терминалами;
· 
- вспомогательный алфавит, символы которого обозначают допустимые комбинации элементов множеств и . Элементы множества называют нетерминалами. 
. Объединение этих множеств 
называют словарем грамматики;
· 
- множество порождающих правил. Каждое правило состоит из пары 
, где 
- левая часть правила, а 
- правая часть. Правила записываются в виде 
, где строка 
должна содержать хотя бы один нетерминал. Очевидно, справедлива запись 
(это прямое произведение множеств, результат – пара, один элемент которой из одного множества, а другой – из другого);
|
|
|
· 
- начальный символ (аксиома) грамматики. С него начинается вывод, генерирующий любую строку языка.
Грамматику обычно именуют. Имя грамматики можно использовать вместо определяющей ее четверки. Обозначим грамматику, генерирующую язык , как 
. Тогда грамматику можно определить так:
.
Каждая строка, которую можно вывести из начального символа грамматики, называется сентенциальной формой. К сентенциальным формам также относят аксиому грамматики, поскольку вывод за нуль шагов тоже считается выводом. Сентенциальная форма может содержать любые символы словаря грамматики – как терминалы, так и нетерминалы.
Сентенциальная форма, состоящая только из терминалов, представляет собой строку языка (или предложение языка).
Обозначение 
применяют в случае, когда хотят показать, что вывод из происходит при однократном применении одного правила грамматики 
.
В случаях, когда не возникает неопределенности относительно применяемой грамматики, обозначение грамматики можно не указывать.
Запись вида 
применяют для обозначения вывода строки 
из строки за один или более шагов применения правил грамматики . Запись 
означает вывод из за нуль или более шагов применения правил грамматики .
Таким образом, если
и 
,
то обычно пишут
или короче: 
.
При 
используется общая запись 
. Число шагов вывода 
называют степенью отношения 
и иногда обозначают 
.
Строка 
, для которой существует вывод 
, где - аксиома грамматики , есть сентенциальная форма, а строка 
, для которой имеется вывод 
, есть строка языка 
, порождаемого грамматикой . Формально 
.
Это определение языка , порождаемого грамматикой , как множества таких строк, которые образованы только из терминалов и выводятся из начального символа грамматики .
|
|
|
