Главная | Обратная связь
МегаЛекции

Пункт 2. Понятие о формальной грамматике.





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

Пример. Даны два нумерованных правила:

1)

2)

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

Рассмотрим применение данных правил в последовательности 1, 1, 2:

. Это есть вывод строки 0011 из символа .

Руководствуясь правилами 1 и 2, можно вывести все строки соответствующего языка и никакие другие. Таким образом, формальная грамматика есть своеобразный алгоритм порождения всех строк языка, который эта грамматика описывает.

 

Пункт 3. Определение формальной грамматики.

Формальная грамматика определяется как четверка , в которой приняты следующие обозначения:

· - алфавит языка, строки которого порождает грамматика. Элементы множества называют терминалами;

· - вспомогательный алфавит, символы которого обозначают допустимые комбинации элементов множеств и . Элементы множества называют нетерминалами. . Объединение этих множеств называют словарем грамматики;

· - множество порождающих правил. Каждое правило состоит из пары , где - левая часть правила, а - правая часть. Правила записываются в виде , где строка должна содержать хотя бы один нетерминал. Очевидно, справедлива запись (это прямое произведение множеств, результат – пара, один элемент которой из одного множества, а другой – из другого);

· - начальный символ (аксиома) грамматики. С него начинается вывод, генерирующий любую строку языка.

 

Грамматику обычно именуют. Имя грамматики можно использовать вместо определяющей ее четверки. Обозначим грамматику, генерирующую язык , как . Тогда грамматику можно определить так:



.

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

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

 

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

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

Запись вида применяют для обозначения вывода строки из строки за один или более шагов применения правил грамматики . Запись означает вывод из за нуль или более шагов применения правил грамматики .

Таким образом, если

и ,

то обычно пишут

или короче: .

При используется общая запись . Число шагов вывода называют степенью отношения и иногда обозначают .

Строка , для которой существует вывод , где - аксиома грамматики , есть сентенциальная форма, а строка , для которой имеется вывод , есть строка языка , порождаемого грамматикой . Формально .

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

 





Рекомендуемые страницы:

Воспользуйтесь поиском по сайту:
©2015- 2020 megalektsii.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.