Кто не делится найденным, подобен свету в дупле секвойи (древняя индейская пословица)
Версия для печати
Библиографическая запись: Формальные грамматики. — Текст : электронный // Myfilology.ru – информационный филологический ресурс : [сайт]. – URL: https://myfilology.ru//165/yazyki-programmirovaniya-i-ix-ispolzovanie-v-informaczionnyx-sistemax/formalnye-grammatiki/ (дата обращения: 22.02.2024)
Формальные грамматики
Содержание
Формальная грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита. Различают порождающие и распознающие (или аналитические) грамматики — первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит ли оно в язык или нет.
По иерархии Хомского, грамматики делятся на 4 типа, каждый последующий является более ограниченным подмножеством предыдущего (но и легче поддающимся анализу):
- тип 0. неограниченные грамматики — возможны любые правила
- тип 1. контекстно-зависимые грамматики — левая часть может содержать один нетерминал, окруженный «контекстом» (последовательности символов, в том же виде присутствующие в правой части); сам нетерминал заменяется непустой последовательностью символов в правой части.
- тип 2. контекстно-свободные грамматики — левая часть состоит из одного нетерминала.
- Тип 3. регулярные грамматики — более простые, эквивалентны конечным автоматам.
Контекстно-свободные грамматики широко применяются для определения грамматической структуры в грамматическом анализе. Регулярные грамматики (в виде регулярных выражений) широко применяются как шаблоны для текстового поиска, разбивки и подстановки, в том числе в лексическом анализе.
Грамматики с фразовой структурой (тип 0). Этот тип грамматик характеризуется ничем не ограниченным набором правил вида α → с, где α — это любая строка нетерминальных символов, а β — любая строка, составленная из терминальных или нетерминальных символов (их так и называют «unrestricted grammars» — «неограниченные грамматики»).
Свойства этого типа грамматик следующие:
- Они могут использоваться для распознавания любой вычислимой функции. Например, можно создать грамматику (хотя это и не очень просто) для цепочки anbf(n), представляющей функцию f (n). По заданному n — числу элементов a, эта грамматика генерирует цепочку, содержащую f (n) элементов b.
- Большая часть свойств этих грамматик относится к неразрешимым. Это означает, что не существует процесса, с помощью которого можно было бы определить, выполняется ли данное свойство для всех грамматик данного типа (например, является ли множество цепочек данного языка пустым?). Отличие от контекстно-зависимых грамматик заключается в том, что у последних о многих свойствах просто ничего не известно — они могут быть истинными, ложными или быть неразрешимыми.
Контекстно-зависимые грамматики (тип 1). Такой тип грамматики характеризуется правилами вида:
α → β
где α — это любая цепочка, состоящая из нетерминальных символов, β — любая цепочка, состоящая из терминальных и нетерминальных символов, и количество символов в α меньше или равно количеству символов в β.
Ниже перечислены некоторые свойства контекстно-зависимых грамматик:
- Все цепочки, последовательно выводимые из начального символа, имеют длину не меньшую, чем предыдущая, поскольку каждое правило должно оставлять длину цепочки неизменной или увеличивать ее (их еще называют неукорачивающими грамматиками).
- Контекстно-зависимые грамматики генерируют цепочки, для хранения которых требуется фиксированный объем памяти. Например, такие грамматики способны распознавать цепочки вида anbncn, что не может сделать контекстно-свободная грамматика.
- Контекстно-зависимые грамматики обычно слишком сложны, чтобы быть практически полезными для моделирования языков программирования.
- Некоторые свойства контекстно-зависимых грамматик до сих пор не исследованы.
Контекстно-свободные грамматики (тип 2). Правила таких грамматик являются правилами НФБ-грамматик (контекстно-свободных грамматик, от «нормальная форма Бэкуса»). Они записываются в форме X —> а, где под а понимается любая последовательность терминальных или нетерминальных символов.
Эти грамматики характеризуются следующими свойствами.
- Многие свойства такой грамматики являются разрешимыми. (Это означает, что можно получить ответы, например, на такие вопросы: генерирует ли
данная грамматика какие-либо цепочки? Сгенерирована ли этой грамматикой данная цепочка языка? Является ли язык, порождаемый грамматикой,
пустым?) - Такие грамматики можно использовать для подсчета вхождения в цепочку двух символов и последующего сравнения. То есть они характеризуются
цепочками вида ancbn для любого n. - Контекстно-свободная грамматика может быть «реализована» при помощи стеков. Для распознавания цепочки ancbn из предыдущего пункта можно занести в стек цепочку аn, затем проигнорировать с и сравнить содержимое стека с цепочкой bn, чтобы удостовериться в одинаковой длине этих двух
цепочек. - Эти грамматики можно использовать для автоматического построения дерева грамматического разбора.
- Грамматики типа 2 и типа 3 по большей части более не представляют интереса и не являются объектом исследований. Судя по всему, все важные свойства этих грамматик уже изучены.
Тип 3. Регулярные грамматики обеспечивают модель для конструирования лексического анализатора в трансляторе некоторого языка программирования. Свойства регулярных грамматик таковы:
- Большинство свойств такой грамматики разрешимы. (Это означает, что можно получить ответы, например, на такие вопросы: генерирует ли данная грамматика любые цепочки? Сгенерирована ли этой грамматикой заданная цепочка символов языка? Ограничено ли количество цепочек в языке?)
- Для любой конечной последовательности а и целого п регулярная грамматика может генерировать строки вида а". Это означает, что регулярная грамматика может распознавать любое количество образцов конечной длины.
- С помощью регулярной грамматики можно реализовать счет до любого конечного целого числа. Например, вы можете распознать цепочку {an
| n = 147}, если построите КА, в котором будет как минимум 148 состояний. Ввод первых 146 символов не приведет КА в конечное состояние, тогда как
очередной ввод символа под номером 147 будет принят. Ни один К А с числом состояний ровно 148 не сможет надежно принять цепочку символов
длиной больше 147. - Грамматики такого типа часто используются в сканерах (лексических анализаторах) компиляторов для распознавания отдельных лексем (идентификаторов, литералов и строк) или ключевых слов данного языка (например, if, begin, while).
Нормальная форма Хомского
КС-грамматика G = (Т, N, S, R) представлена в нормальной форме Хомского, если она неукорачивающая и каждое ее правило имеет одну из следующих
форм:
А → ВС или А → а, где А, В, C ∈ N, a ∈ Т.
Простыми эквивалентными преобразованиями любую неукорачивающую грамматику можно привести к нормальной форме Хомского.
Общие методы разбора. Эффективные методы разбора: LL и LR грамматики - как-нибудь потом.
23.04.2022, 613 просмотров.