Ирина Эланс

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

Автоматные грамматики

Содержание

Введение……………………………………………………………………. 3

1.Понятие грамматики……..……………………………………………… 4

2 Классификация грамматик……………………………………………… 7

3. Автоматные грамматики ……………………………………………… 9

Заключение………………………………………………………………… 14

Литература…………………………………………………………………. 15

Введение

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

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

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

1.Понятие грамматики и формальное определение.

Форма Бэкуса-Наура

Любой конечный механизм задания языка называется грамматикой.

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

Формальное описание грамматики построено на основе системы правил, или продукций. Правило представляет собой упорядоченную пару цепочек символов (a,b), которую обычно записывают как a ® b и читают как «a порождает b».

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

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

Формально грамматика G определяется как четверка G(VT,VN,P,S), где VT – множество терминальных символов (символы алфавита);

VN – множество нетерминальных символов (слова, понятия, конструкции языка); VTÇVN=Æ; V=VTÈVN – полный алфавит грамматики G;

P – множество правил вида a ® b, где aÎV⁺, bÎV*;

SÎVN – начальный (целевой) символ грамматики G, с которого начинается процесс порождения цепочек языка.

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

Во множестве правил грамматики может быть несколько правил, имеющих одинаковые левые части, например: a®b₁, a®b₂, …, a®b_n. Тогда эти правила записываются в одну строку: a®b₁½b₂½…½b_n.

Рассмотренная форма записи правил грамматики называется формой Бэкуса-Наура. В ней, как правило, нетерминальные символы заключаются в угловые скобки <>.

Пример: грамматика порождения целых десятичных чисел со знаком.

G({0,1,2,3,4,5,6,7,8,9,–,+}, {<число>,<чс>,<цифра>}, P, <число>).

<число> ® <чс>½+<чс>½–<чс>

<чс> ® <цифра>½<чс><цифра>

<цифра> ® 0½1½2½3½4½5½6½7½8½9

В данной грамматике множество нетерминальных символов содержит 3 элемента (символы <число>,<чс>,<цифра>), множество терминальных символов – 12 элементов (10 цифр и два знака), множество P – 15 правил, записанных в три строки. Начальный символ грамматики – <число>.

В грамматике можно изменить названия нетерминальных символов без какого-то изменения языка, заданного ею. Терминальные символы изменять нельзя! Они соответствуют алфавиту задаваемого языка.

Рассмотренную в примере грамматику для целых десятичных чисел со знаком можно переписать в виде:

G¢({0,1,2,3,4,5,6,7,8,9,–,+}, {S,T,F}, P, S).

S ® T½+T½–T

T ® F½TF

F ® 0½1½2½3½4½5½6½7½8½9.

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

В грамматиках G и G¢ явная рекурсия присутствует во второй части второго правила: <чс> ® <чс><цифра>, T ® TF.

Чтобы рекурсия не была бесконечной, участвующий в ней нетерминальный символ должен обязательно присутствовать в левой части другого правила, где он определяется, минуя самого себя. В грамматиках G и G¢ это достигается в первой части второго правила: <чс> ® <цифра>, T ® F.

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

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

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

Классификация грамматик по Хомскому

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

Пусть грамматика обозначена как G(VT,VN,P,S), V=VTÈVN. В соответствии с иерархией Хомского выделяют 4 типа грамматик.

Тип 0 – грамматики с фразовой структурой, или без ограничений

На структуру их правил не накладывается никаких ограничений, т.е. правила имеют вид: a ® b, где aÎV⁺, bÎV*. Это самый общий тип грамматик. Грамматики, которые относятся только к этому и не могут быть отнесены ни к какому другому типу, являются самыми сложными по структуре.

Тип 1 – Контекстно-зависимые (КЗ) и неукорачивающие грамматики

К этому типу относятся два основных класса грамматик.

Контекстно-зависимые грамматики имеют правила вида a₁Aa₂ ® a₁ba₂, где a₁,a₂ÎV^*, AÎVN, bÎV⁺.

Неукорачивающие грамматики имеют правила вида a ® b, где a,bÎV⁺, ½b½³½a½.

В КЗ-грамматиках при построении предложений заданного языка один и тот же нетерминальный символ может быть заменен различными терминальными цепочками в зависимости от контекста, в котором он встречается. Цепочки a₁ и a₂ в правилах обозначают контекст: a₁ – левый контекст, a₂ – правый контекст. В общем случае они могут быть пустыми.

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

Эти два класса грамматик эквивалентны.

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

Тип 2 – Контекстно-свободные (КС) грамматики

Контекстно-свободные (КС) грамматики имеют правила вида A ® b, где AÎVN, bÎV⁺. В правой части у них стоит всегда хотя бы один символ.

Такие грамматики еще называют неукорачивающими контекстно-свободными (НКС) грамматиками. Существует почти эквивалентный им класс укорачивающих контекстно-свободных (УКС) грамматик, отличие которого в том, что он допускает пустую цепочку, т.е. правила имеют вид A ® b, где AÎVN, bÎV^*. В дальнейшем, если возможность наличия в языке пустой цепочки не имеет принципиального значения, будем говорить просто о КС-грамматиках.

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

Тип 3 – Регулярные грамматики

К этому типу относятся два эквивалентных класса грамматик: леволинейные и праволинейные.

Леволинейные грамматики могут иметь правила двух видов: A ® Bg, или A ® g, где A,BÎVN, gÎVT⁺.

Праволинейные грамматики имеют правила тоже двух видов: A ® gB, или A ® g, где A,BÎVN, gÎVT⁺.

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

Из определения типов видно, что любая регулярная грамматика является также КС-грамматикой, или любая грамматика может быть отнесена к типу 0. В то же время существуют УКС-грамматики, которые не относятся к типу 1, поскольку могут содержать правила вида A ® l, недопустимые в этом типе. В общем, сложность грамматики обратно пропорциональна тому максимально возможному номеру типа, к которому может быть отнесена эта грамматика. Самыми простыми являются грамматики типа 3, самыми сложными – типа 0.

3.Автоматные грамматики

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

Леволинейные автоматные грамматики G(VT, VN, P, S) могут иметь правила двух видов: A ® Bt или A ® t, где A, BÎVN, tÎVT.

Праволинейные автоматные грамматики могут тоже иметь правила двух видов: A ® tB или A ® t, где A,BÎVN, tÎVT.

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

Конечно-автоматная грамматика, грамматика с конечным числом состояний - это грамматика бесконтекстная, каждое правило которой имеет вид А→aB или A→a где A,B - вспомогательные символы, а - один из основных символов (иногда допускаются также правила вида А→ Λ, где Λ - пустая цепочка. Класс порождаемых языков при этом расширяется только за счет языков, получаемых из прежних добавлением цепочки Λ). Для каждой автоматной грамматики можно построить эквивалентный ей конечный автомат. Класс языков, порождаемых атоматные грамматики. (автоматных языков), совпадает (при допущении правил с пустой правой частью) с классом регулярных множеств. Автоматные языки образуют собственный подкласс класса линейных языков;так, линейный язык ǀn=1,2…} - не автоматный. Класс автоматных языков замкнут относительно объединения, пересечения, умножения, подстановки и усеченной итерации (а при наличии правил с пустой правой частью также и относительно итерации). Пересечение бесконтекстного языка с автоматным есть бесконтекстный язык.

Для наглядного изображения автоматной грамматики используется диаграмма - ориентированный мультиграф, вершинами которого служат вспомогательные символы, и из вершины А в вершину ведет дуга, помеченная (основным) символом а, если в грамматике есть правило кроме того, в диаграмме имеется еще одна вершина А→aB - заключительная, в которую из вершины - вспомогательного символа А - идет дуга, помеченная символом а, если в автоматной грамматике есть правило А→a. (При наличии правил вида А→ Λ каждый символ А , для которого имеется такое правило, также считается заключительной вершиной.) Цепочка в основном словаре выводима в грамматике из вспомогательного символа А тогда и только тогда, когда она "записана" на некотором пути в диаграмме, идущем из А в заключительную вершину. На рис. изображена диаграмма автоматной грамматики с правилами I→aI, I→aB, B→bB, B→b (I - начальный символ, К- заключительная вершина), порождающей язык ǀn,m=1,2…}

Классы обычных регулярных грамматик и автоматных почти эквивалентны (т.е. с точностью до правила S ® l). В автоматных грамматиках разрешается правило вида S ® l, где S – целевой символ грамматики. При этом символ S не должен встречаться в правых частях других правил грамматики; тогда язык, задаваемый автоматной грамматикой G, будет включать в себя пустую цепочку: lÎL(G).

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

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

Рассмотрим ряд теорем.

Теорема. Для каждой праволинейной грамматики существует эквивалентный конечный автомат.

Доказательство. Каждому нетерминалу произвольной праволинейной грамматики G поставим в соответствие одно состояние конечного автомата A. Добавим еще одно состояние - единственное конечное состояние. Состояние, соответствующее аксиоме, назовем начальным состоянием. Каждому правилу A→aB поставим в соответствие команду Aa → B, а каждому терминальному правилу A → a поставим в соответствие команду Aa → F. Таким образом, выводу цепочки в грамматике S ⇒ a1A1 ⇒ a1a2A2 ⇒ ... ⇒ a1a2...ak-1Ak-1⇒ a1a2...ak взаимно однозначно соответствует последовательность команд построенного автомата A: Aa1 → A1; A1a2 → A2; . . . ; Ak-1ak → F. Таким образом, язык L(G) = L(A).

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

S → aS | bB;

A → aA | bS;

B → bB | с | cA.

Решение. Граф автомата будет иметь четыре вершины, три из них помечены нетерминальными символами грамматики S, A, B, четвертая вершина, помеченная символом F, является единственным заключительным состоянием. Начальным состоянием является вершина, соответствующая аксиоме S.

Каждому правилу грамматики поставим в соответствие команду конечного автомата: Sa → S - в начальном состоянии при поступлении на вход терминального символа а автомат остается в том же состоянии S;

Sb → B - из начального состояния при поступлении на вход терминала b автомат переходит в состояние B; Bb → B - в состоянии В при поступлении на вход терминала b автомат остается в том же состоянии B;

Bc → F - из состояния В при поступлении на вход терминала c автомат переходит в заключительное состояние F;

Bc → A - из состояния В при поступлении на вход терминала c автомат переходит в состояние А;

Aa → A - в состоянии А при поступлении на вход терминала а автомат остается в этом же состоянии А;

Ab → S - из состояния A при поступлении на вход терминала b автомат переходит в состояние S. Полученный недетерминированный конечный автомат распознает цепочки языка,порождаемые праворекурсивной грамматикой G.

Теорема. Для произвольного конечного автомата существует эквивалентная праволинейная грамматика.

Доказательство. Каждому состоянию произвольного автомата поставлен в соответствие нетерминал грамматики, причем начальному состоянию будет соответствовать аксиома. Тогда для каждой команды Ac → B в множество правил грамматики включим правило A→ cB, причем в случае, если B - заключительное состояние, добавим правило A → c. Эквивалентность исходного конечного автомата и построенной грамматики очевидна.

Заключение

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

Литература

Бильгаева Н.Ц. «Теория алгоритмов, формальных языков, грамматик и автоматов». Изд. ВСГТУ Улан-Удэ 2000г.
А.Н. Мелихов, В.И. Кодачигов «Теория алгоритмов и формальных языков» Таганрог 2006 г.
Рейуорд-Смит В.Дж. Теория формальных языков. Вводный курс. – М.: Радио и связь, 1988.
Малявко А.А. Теория формальных языков / Учебное пособие, Ч.1,2,3. – Новосибирск: Изд-во НГТУ, 2001-2005.
Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение / Учебник для вузов. – СПб.: Питер, 2001.
Н. Ю. Демин Дискретная математика «О необходимом количестве правил автоматной грамматики, порождающей конечный язык». 2000г.

Автоматные грамматики 📙 Реферат → 🆔 15978