Расчетно-графическая работа №4 Тема: «Разработка формальной грамматики Хомского».

1. Теоретическая часть

1.1 Формальная грамматика

Грамматика языка – это набор средств для его описания. Различают порождающие и распознающие грамматики, в зависимости от того, какая задача ставится: строить новые цепочки языка или определять принадлежит или нет некоторая цепочка языку.

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

где V_T - терминальный алфавит (словарь); буквы этого алфавита называются терминальными символами; из них строятся цепочки порождаемые грамматикой;  V_H - нетерминальный, вспомогательный алфавит (словарь); буквы этого алфавита используются при построении цепочек; они могут входить в промежуточные цепочки, но не должны входить в результат порождения;  f - начальный символ грамматики f  V_H; P - множество правил вывода или порождающих правил вида a→b , где a и b - цепочки, построенные из букв алфавита V_T и V_H , который называют полным алфавитом (словарем) грамматики G.

Множество конечных цепочек терминального алфавита V_T грамматики G, выводимых из начального символа f, называется языком, порождаемым грамматикой G и обозначается L( G):

1.2 Пример построения грамматики

Примером языка может являться множество различных корректных формул, включающих в себя натуральные числа, скобки и знаки арифметических действий. Алфавитом в этом случае будет множество Σ = { 0, 1, 2, 3 , 4, 5, 6, 7, 8 , 9 , + , - , *, / , ( , ) }. Например, строка (2+3)*(5+7) будет словом такого языка, а строка +2(3-1( не будет (хотя она и состоит из допустимых символов, но записана с очевидными ошибками). Как можно описать этот язык? Мы знаем, что числа состоят из цифр и могут объединяться с помощью знаков арифметических действий в формулы (например, формулой будет цепочка 2+3). Формулы можно заключать в скобки, а также складывать, вычитать, умножать и делить — то есть объединять друг с другом (и с числами) в более сложные формулы. Например, (2+3)*(5+7) — это сложная формула, состоящая из двух более простых, ее можно символически записать следующим образом: ФОРМУЛА ЗНАК ФОРМУЛА. Заметим, что вместо слов ФОРМУЛА можно подставить любую корректную формулу, а вместо слова ЗНАК — знак любого арифметического действия, и эта строка останется правильной формулой.

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

1. ФОРМУЛА → ФОРМУЛА ЗНАК ФОРМУЛА

Правило нужно читать так: «вместо слова ФОРМУЛА можно подставить цепочку ФОРМУЛА ЗНАК ФОРМУЛА». При этом вместо «кирпичика» ЗНАК можно подставлять один из четырех символов алфавита Σ : ( +, - , * , / ). Это можно записать с помощью следующих четырех правил.

2. ЗНАК→  +

3. ЗНАК→  -

4. ЗНАК→  *

5. ЗНАК→  /

Такая запись обычно сокращается до следующей (символ "|" не принадлежит Σ).

6. ЗНАК→ + | - | * | /

«Кирпичики», обозначаемые нами большими буквами (например, ЗНАК), не являются символами рабочего алфавита Σ (хотя и могут быть на них заменены в процессе подстановок). Они называются «нетерминалами» (или «нетерминальными символами»), в отличие от букв алфавита Σ, называющихся терминалами. Смысл этих названий состоит в том, что нетерминал может быть заменен на цепочку других символов (как в случае с нетерминалом ФОРМУЛА), в то время как терминал уже ни на что заменен быть не может и является своеобразным «пунктном назначения» наших замен (от англ. terminal — конечный пункт). Чтобы получить слово языка, мы должны все нетерминалы в конечном итоге заменить на терминалы, а для этого в описание языка должны входить соответствующие правила.

В рассмотренном примере для определения нетерминала ЧИСЛО можно ввести такие правила

7. ЧИСЛО→  ЦИФРА | ЧИСЛО ЦИФРА

8. ЦИФРА → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Иными словами, если к числу приписать справа еще одну цифру, то получится снова число. Одно число — это также корректная формула, что записывается следующим образом:

9. ФОРМУЛА→ ЧИСЛО

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

10. ФОРМУЛА→ ( ФОРМУЛА )

Надо отметить, что нетерминал ФОРМУЛА в нашем случае является выделенным — он задает правильные формулы, то есть слова нашего языка, в то время как, например, нетерминал ЗНАК не задает слово языка. В таком случае говорят, что нетерминал ФОРМУЛА является начальным.

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

Выведем формулу (12+5) с помощью перечисленных правил вывода:

ФОРМУЛА (ФОРМУЛА) (ФОРМУЛА ЗНАК ФОРМУЛА) (ФОРМУЛА + ФОРМУЛА) (ФОРМУЛА + ЧИСЛО) (ФОРМУЛА + ЦИФРА) (ФОРМУЛА + 5) (ЧИСЛО + 5) (ЧИСЛО ЦИФРА + 5)  (ЦИФРА ЦИФРА + 5) (1 ЦИФРА+5) (12+5)