AAA
Обычный Черный



Кто не делится найденным, подобен свету в дупле секвойи (древняя индейская пословица)

версия для печатиВерсия для печати



Библиографическая запись: Формальные грамматики. — Текст : электронный // Myfilology.ru – информационный филологический ресурс : [сайт]. – URL: https://myfilology.ru//165/yazyki-programmirovaniya-i-ix-ispolzovanie-v-informaczionnyx-sistemax/formalnye-grammatiki/ (дата обращения: 7.07.2022)

Формальные грамматики

Формальные грамматики

Содержание

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

    По иерархии Хомского, грамматики делятся на 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, 121 просмотр.


    Уважаемые посетители! С болью в сердце сообщаем вам, что этот сайт собирает метаданные пользователя (cookie, данные об IP-адресе и местоположении), что жизненно необходимо для функционирования сайта и поддержания его жизнедеятельности.

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

    Dear visitors! It is a pain in our heart to inform you that this site collects user metadata (cookies, IP address and location data), which is vital for the operation of the site and the maintenance of its life.

    If you do not want to provide this data for processing under any pretext, please leave the site immediately and we will not tell anyone that you were here. With the same care, the site administration.