Классификация грамматик и языков

языков
Лекция 9
Кафедра «Автоматизированные станочные системы»
Dept. of Automated Manufacturing Systems

по Хомскому:
V+ — множество всех цепочек над алфавитом V без

λ;
V* — множество всех цепочек над алфавитом V, включая λ.

КЗ-грамматик один и тот же нетерминальный символ может быть заменен

на ту или иную цепочку символов в зависимости от того контекста, в котором он встречается.

Цепочки α1 и α2 в правилах грамматики обозначают контекст (α1— левый контекст, а α2 — правый контекст), в общем случае любая из них (или даже обе) может быть пустой. Говоря иными словами, значение одного и того же символа может быть различным в зависимости от того, в каком контексте он встречается.

При построении компиляторов такие грамматики не применяются

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

любая цепочка символов может быть заменена на цепочку символов не меньшей длины.

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

при описании простейших конструкций языков программирования: идентификаторов, констант, строк, комментариев

и т. д.

Для классификации грамматик всегда выбирают максимально возможный тип, к которому она может быть отнесена. Сложность грамматики обратно пропорциональна номеру типа, к которому относится грамматика. Грамматики, которые относятся только к типу 0, являются самыми сложными, а грамматики, которые можно отнести к типу 3 — самыми простыми.

языки с фразовой структурой
Это самые сложные языки, которые могут быть

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

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

(КЗ) языки
Тип 1 — второй по сложности тип языков. В

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

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

В компиляторах КЗ-языки не используются

(КС) языки
КС-языки лежат в основе синтаксических конструкций большинства современных языков

программирования,

Тип 3: регулярные языки
Регулярные языки — самый простой тип языков. Поэтому они являются самым широко используемым типом языков в области вычислительных систем. Время на распознавание предложений регулярного языка линейно зависит от длины входной цепочки символов.

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

безобразие распознавать
Для языков с фразовой структурой (тип 0) необходим распознаватель,

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

Для контекстно-зависимых языков (тип 1) распознавателями являются двусторонние недетерминированные автоматы с ограниченной памятью. Количество шагов, необходимых автомату для распознавания входной цепочки, экспоненциально зависит от длины этой цепочки.

разбора от длины цепочки существенно ограничивает применение распознавателей для контекстно-зависимых

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

Для контекстно-свободных языков (тип 2) распознавателями являются односторонние недетерминированные автоматы с магазинной (стековой) внешней памятью — МП-автоматы. При простейшей реализации алгоритма работы такого автомата он имеет экспоненциальную сложность, однако путем некоторых усовершенствований алгоритма можно добиться полиномиальной (кубической) зависимости времени, необходимого на разбор входной цепочки, от длины этой цепочки. Следовательно, можно говорить о полиномиальной сложности распознавателя для КС-языков.

десятичных чисел
G1{0,1,2,3,4,5,6,7,8,9,-,+},{S, Т, F},P1,S):
P1:
S  Т | +Т | -Т
Т

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

По структуре своих правил данная грамматика G1 относится к контекстно-свободным грамматикам (тип 2). Ее можно отнести и к типу 0, и к типу 1, но максимально возможным является именно тип 2, поскольку к типу 3 эту грамматику отнести никак нельзя:
строка Т  F | TF содержит правило Т  TF, которое недопустимо для типа 3, и хотя все остальные правила этому типу соответствуют, одного несоответствия достаточно.

но по-другому:
G1' ({0,1,2,3,4,5,6,7,8,9,-,+},{S, Т},P1',S):
P1':
S  Т | +Т | -Т
Т

 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
0Т | 1T | 2Т | 3Т | 4Т | 5Т | 6Т | 7Т | 8Т | 9Т

По структуре своих правил данная грамматика G1 является праволинейной и относится к типу 3.

G1'' ({0,1,2,3,4,5,6,7,8,9,-,+},{S, Т},P1'',S):
P1':
Т  + | - | λ
S  T0 | T1 | T2 | T3 | T4 | T5 | T6 | T7 | T8 | T9 | S0 | S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8 | S9

Та же грамматика, но леволинейная: