Формальные грамматики и их свойства. Формальные грамматики
- Tutorial
Небольшое предисловие
Этот текст является продолжением поста, в котором автор попытался как можно более просто и без сложных математических выкладок описать понятия формального языка и грамматики. На этот текст пришло достаточно много откликов и автор счел себя обязанным написать продолжение.Ниже описывается формализм порождающих грамматик Хомского. Методы задания языка с помощью порождающих грамматик сейчас довольно популярны, особенно для машинной обработки компьютерных языков. Но обычно изучение порождающих грамматик в теории трансляторов заканчивается на контекстно-свободных грамматиках. Последние являются довольно узким специальным классом порождающих грамматик Хомского и обычно используются как вид категориальных грамматик (как конкретно это делается, будет показано ниже) для задания синтаксических анализаторов. Последнее обстоятельство только затуманивает понимание подхода Хомского. Дальнейшее изложение предназначено тем, кому интересно понять, в чем состоит этот подход.
Определение порождающей грамматики
Грамматика представляет собой конечное описание формального языка. Формальный язык, в свою очередь, является произвольным множеством цепочек, составленных из символов некоторого конечного алфавита. Произвольность множества здесь понимается в том смысле, что оно может быть бесконечным, конечным или пустым.Формализм порождающих грамматик Хомского был введен Ноамом Хомским в конце 50-х годов прошлого века. За короткое время этот формализм обрел необычайную популярность. Некоторое время порождающие грамматики рассматривались как панацея - универсальный подход для задания всевозможных языков, в том числе и естественных (т.е. языков, которые люди используют для повседневного общения между собой). Но время показало, что порождающие грамматики для описания естественных языков не очень удобны. Сейчас порождающие грамматики применяются, в основном, для описания синтаксиса формальных языков, подобных языкам программирования и другим компьютерным языкам.
Порождающая грамматика Хомского задается как множество «правил порождения» (продукций). Каждое правило является просто парой цепочек (w", w"") и задает возможность замены левой цепочки на правую при генерации цепочек языка, задаваемого грамматикой. По этой причине, правила обычно записывают в виде w" --> w"" , указывая конкретно, что на что можно заменять. Множество правил в грамматике должно быть непустым и конечным, и обычно обозначается латинской P.
Цепочки в правилах грамматики могут быть составлены из символов двух алфавитов: алфавита терминальных символов (терминалов) и алфавита нетерминальных символов (нетерминалов). Алфавит терминалов обозначают через T. Этот алфавит на самом деле совпадает с алфавитом того формального языка, который задает данная грамматика. Смысл термина «терминальный» состоит в том, что в правилах грамматики в левой части не может быть цепочек, которые составлены только из терминальных символов. Поэтому, если такая цепочка получилась в результате подстановки, то следующая процесс порождения цепочки остановится (terminate). Нетерминальные символы используются в промежуточных порождениях цепочек. Смысл нетерминала в задании алгоритма порождения цепочки может быть самый разный и обычно зависит от типа грамматики, в которой этот символ используется. Различные примеры использования нетерминальных символов будут рассмотрены ниже.
Но один нетерминальный символ всегда имеет один и тот же смысл - он обозначает все цепочки языка. Называется этот нетерминал «начальным нетерминальным символов порождающей грамматики» и обычно обозначается посредством латинского S (start или sentence). В каждой порождающей грамматике обязательно должно быть правило, к которого левая часть состоит из единственного начального нетерминала, иначе в данной грамматике нельзя будет породить даже одной цепочки.
Итак, порождающая грамматика Хомского - это четверка G = {N, T, P, S} , где
- N - конечный алфавит нетерминальных символов.
- T - конечный алфавит терминальных символов (совпадает с алфавитом языка, задаваемого грамматикой).
- P - конечное множество правил порождения.
- S - начальный нетерминал грамматики G .
Язык порождающей грамматики
Порождающая грамматика Хомского задает язык посредством конечного числа подстановок цепочек из начального нетерминала грамматики на основе правил порождения. Опишем это чуть более конкретно.Шаг порождения w" alpha w"" => w" beta w"" состоит в замене подцепочки alpha на подцепочку beta в соответствии с правилом порождения alpha --> beta . При этом, очевидно, из цепочки w" alpha w"" получается цепочка w" beta w"" . Иначе говоря, если имеется некоторая цепочка и некоторая ее подцепочка является левой частью какого-то правила грамматики, то мы имеем полное право заменить эту левую часть правила на правую. Конечная последовательность шагов порождений называется порождением. Нуль или более порождений будет обозначать знаком =>* . Обозначение alpha =>* beta говорит о том, что цепочка beta получена из цепочки alpha конечным числом подстановок на основе правил порождения. В этом обозначении может быть так, что подстановка (порождение) не была применена ни разу, в этом случае цепочка alpha совпадает с beta .
Итак, язык порождающей грамматики G = {N, T, P, S} - это множество цепочек, составленных из терминальных символов и порожденных из начального символа грамматики. Математическая формула такова: L = {w | S =>* w} .
Для иллюстрации приведем два простых примера.
Пример очень простого языка
Пусть язык L состоит из одной цепочки, которая состоит из единственного символа a . Иначе говоря, L = {a} . Для порождения цепочки a достаточно одного правила S --> a . Единственное порождение, которое может быть в данной грамматике - это S => a .Следует заметить, что для этого языка можно было бы ввести еще один нетерминальный символ, скажем, символ A , а также правила S --> A и A --> a . Тогда единственным порождением было бы следующее: S => A => a . Так как алфавит нетерминалов грамматики мы выбираем произвольно, становится понятно, что даже для такого простого языка имеется бесконечное множество порождающих грамматик, задающих данный язык.
Язык простых арифметических выражений
Рассмотрим язык A = {a+a, a+a+a, a+a+a+a, ...} . Цепочки этого языка представляют собой последовательности символов a , разделенных символами + . Как задать правила порождения этого языка? Заметим, что каждая цепочка языка начинается с символа a за которым идет одна или более цепочек +a . Соответственно, возникает мысль сначала породить символ a , а затем каждая цепочка языка будет получаться присоединением к этому символу справа одной или более цепочек +a . Чтобы отделить эти две стадии порождения друг от друга, введем нетерминальный символ A . Тогда, получим грамматику со следующими правилами: S --> aA, A --> +aA, A --> +a .Рассмотрим, например, как можно породить цепочку a+a+a . S => aA => a+aA => a+a+a . В этом порождении последовательно были применены все три правила: S --> aA, A --> +aA, A --> +a .
Язык A содержит бесконечное число цепочек, значит, ограничения на длину цепочки в этом языке нет. Единственный способ порождать цепочки неограниченной длины, это использовать рекурсивные правила порождения, т.е. правила, в которых в правой части правила содержится его левая часть. В примере выше это правило A --> +aA . Левая часть - это цепочка из единственного символа A , который также содержится и в правой части. Такая рекурсия позволяет последовательно применять в подстановке одно и то же правила, увеличивая, сколько необходимо, длину порождаемой цепочки. Рекурсия может быть и опосредованной, через промежуточные правила. Например, правила A --> aBc, B --> deA задают опосредованную рекурсию цепочки A .
Классы грамматик
Ноам Хомский ввел классы грамматик (и соответствующие классы языков) задавая ограничения на вид правил порождающей грамматики. Каждый класс грамматик имеет свою описательную мощность. Описательную мощность класса грамматик можно охарактеризовать, как возможность выражений в правилах грамматики определенных синтаксических отношений. Рассмотрим, как классы грамматик задают синтаксические отношения.Грамматики типа 3
Этот класс грамматик задает алгоритм порождения цепочек присоединением некоторого количества терминальных символов с правого или левого края порождаемой цепочки. Очевидно, что правила для такого метода порождения должны иметь вид A --> alpha B или A --> B alpha , где alpha - цепочка, состоящая из терминальных символов. В этом случае, если имеется промежуточная (в процессе порождения) цепочка X1..Xn A , то замена в соответствии с правилом A --> alpha B даст цепочку X1..Xn alpha B . Например, для правил S --> aaaA , A --> abcA и A --> bbb можно задать порождение S => aaaA => aaaabcA => aaaabcbbb .Синтаксическое отношение, которое задается грамматиками типа 3, можно обозначить термином «быть рядом». Под «рядом» здесь подразумевается как непосредственно рядом, если это задано в правой части какого-то правила порождения, так и опосредованно рядом, через нетерминальные символы в связанных между собой правилах порождения.
Для математической строгости строку терминальных символов в правилах грамматик типа 3 разбивают на несколько правил с одним терминальным символом в правой части. Например, если имеется правило A --> abcB , то его можно заменить на следующие правила, применение которых в результате порождает ту же цепочку: A --> a A1 , A1 --> b A2 , A2 --> cB . Иначе говоря, подстановка A => abcB эквивалентна последовательности подстановок A => a A1 => a b A2 => abcB . Такие грамматики, где нетерминальный символ стоит справа в правой части правила, называют праволинейными грамматиками, если в правой части нетерминальный символ стоит слева от терминала, то грамматику называют леволинейной.
Зададим, например леволинейную грамматику для языка A = {a+a, a+a+a, a+a+a+a, ...} . Правила грамматики типа 3, как было рассмотрено выше, это: S --> aA, A --> +aA, A --> +a . Здесь цепочки порождаются присоединением пары символов справа. Изменим грамматику так, чтобы символы присоединялись слева, а также добавим нетерминальные символы, чтобы каждый раз добавлять только по одному символу. Получим грамматику:
S --> Aa
A --> B+
B --> Aa
B --> a
Вот как выглядит порождение цепочки a+a+a: S => Aa => B+a => Aa+a => B+a+a => a+a+a .
Внимательный читатель вероятно заметил, что грамматика типа 3 похожа на попрождающий автомат, в котором роль состояний играют нетерминальный символы грамматики. Одна из возможных интерпретаций этой грамматики - это, действительно, конечный автомат.
Контекстно-свободные грамматики
Контекстно-свободные грамматики имеют правила вида: A --> alpha . В левой части правила должен стоять один символ (конечно, нетерминальный), а справа может быть любая цепочка из терминальных и нетерминальных символов (в том числе и пустая).КС-грамматики задают два вида синтаксических отношений: отношение «быть рядом» и отношение «быть частью» или отношение иерархии. Отношение иерархии наиболее естественно для человеческого ума. Человеку свойственно типизировать вещи, т.е. рассматривать конкретные объекты своего мышления как части какого-то общего типа (класса). Каждая вещь, о которой думает человек, является экземпляром некоторого класса. Например, конкретный стул является экземпляром класса «стул» с соответствующими признаками. Человеческому уму также свойственно разделять типы на подтипы, двигаясь от более конкретных типов к более абстрактным. Скажем, стул есть подтип типа мебель, мебель есть подтип типа предмет, предмет есть подтип типа объект и т.п. Отношение «тип-подтип» и есть отношение иерархии.
КС-грамматика может быть проинтерпретирована как категориальная грамматика, т.е. грамматика типов. Символы грамматики в этом случае могут мыслиться как типы, а правила тогда задают отношение иерархии между типами. Нетерминальные символы выступают как сложные типы, а терминальный символы - как атомарные типы, у которых не может быть подтипов. Такая интерпретация КС-грамматики очень популярна и часто используется при создании трансляторов языков. Но, задавая класс КС-грамматик, Хомский имел ввиду нечто другое.
Ввиду того, что КС-грамматика является порождающей, она задает алгоритм (строго говоря, не алгоритм, но исчисление - многовариантный алгоритм) порождения цепочек языка. Порождение здесь задается не только присоединением цепочек справа или слева имеющейся цепочки, но и вставкой цепочки куда-нибудь внутрь имеющейся. Вставка производится заменой нетерминального символа в цепочке на цепочку, которая стоит в правой части некоторого правила, в левой части которого находится этот нетерминал. Скажем, цепочку aabBBACbbb можно преобразовать в цепочку aabBBaaaCbbb , если есть правило A --> aaa . В этом смысле, порождаемая цепочка растет не равномерно с какого-то края, но как-бы «пухнет» изнутри.
Проиллюстрируем сказанное на примере. Рассмотрим язык L = {a^n b^n | n = 1, 2, 3,...} . Выражение a^n здесь означает повторение n раз символа a . Таким образом, язык L состоит из цепочке вида ab, aabb, aaabbb и т.д. Зададим КС-грамматику для этого языка. Для этого заметим, что из цепочки языка можно получить другую цепочку языка, присоединяя к первой слева символ a , а справа символ b . Скажем, если имеется цепочка aabb , то из нее можно получить цепочку aaabbb . Это замечание дает правило порождения S --> aSb (напомним, что цепочки языка порождаются из начального нетерминала грамматики и, значит, могут быть обозначены этим символом). Есть еще специальный случай цепочки, которая не дробится на более мелкие - это цепочка ab . Введем для ее порождения правило S --> ab . Итак, грамматика языка имеет правила: S --> aSb и S --> ab . Зададим порождение цепочки aaabbb: S => aSb => aaSbb => aaabbb .
Контекстно-зависимые грамматики и грамматики без ограничений
В правилах КС-грамматики нетерминальный символ в левой части правила порождения можно менять на правую часть в любом месте порождаемой цепочки, где бы этот символ не встретился. Но иногда хотелось бы различать контексты, в которых находится символ в цепочке, и в одних случаях производить замену символа, в других - нет. Правила КС-грамматики этого делать не позволяют, поэтому для таких случаев необходимы правила специального вида.Контекстно-зависимая грамматика имеет правила вида w" A w"" --> w" alpha w"" . Здесь w" и w"" - цепочки (может быть пустые), составленные из терминальных и нетерминальных символов грамматики, alpha - непустая цепочка из тех же символов. Иначе говоря, нетерминальный символ A заменяется на цепочку alpha в контексте цепочек w" и w"" .
С КЗ-грамматикой связан другой класс грамматик - неукорачивающие грамматики. Правила в таких грамматиках должны удовлетворять одному условию: длина правой части должна быть не меньше длины левой части. Так как в правилах КЗ-грамматик имеется условие, чтобы цепочка alpha была непустая, то эти грамматики также являются неукорачивающими. Но, самое интересное состоит в том, что для каждого языка, заданного неукорачивающей грамматикой, может быть придумана КЗ-грамматика, задающая тот же язык. Иначе говоря, классы языков, задаваемых КЗ-грамматиками и неукорачивающими грамматиками, совпадают.
Зачем так необходимо выделять класс языков, задаваемых неукорачивающими грамматиками? Дело в том, что для таких языков можно задать распознающий автомат. Распознающая грамматика конструируется следующим образом: получая на вход цепочку, последовательно делаем порождения, упорядочивая их по длине порождаемой цепочки. Т.к. грамматика неукорачивающая, то таких порождений будет конечное множество и, если среди них не нашлось совпадения с данной на вход цепочкой, то напечатать «нет».
Для грамматики без ограничений на вид правил такой алгоритм распознавания в общем случае построить нельзя. Порождаемая цепочка может вести себя как «гармошка», раздуваясь и сдуваясь в процессе порождения. Поэтому достижение порождаемой цепочкой определенной длины не гарантирует, что далее в процессе порождения не будет получена поданная на вход цепочка.
Действительно ли КЗ-языки образуют собственный класс, не совпадает ли этот класс с классом КС-языков. Иначе говоря, есть ли язык, для которого гарантировано нельзя задать КС-грамматику, но можно задать КЗ-грамматику? Ответ: да, такие языки есть. В качестве примера такого языка можно привести следующий язык L = {ww} . Цепочки этого языка составлены из двух повторяющихся цепочек над каким-то алфавитом. Доказывать, что для этого языка нельзя построить КС-грамматики мы здесь не будем. КЗ-грамматику можно задать на основе следующего соображения. Сначала сгенерировать цепочку w и нетерминальный символ, скажем A , т.е. получить цепочку Aw . Затем продвинуть символ A сквозь цепочку w , генерируя по ходу копии символов этой цепочки, после чего продвинуть эти символы направо. Примерно то же, как это будет реализовано в примере ниже.
Рассмотрим пример задания грамматики для языка L = {a^n^2 | n = 1, 2, 3, ...} . Цепочки этого языка состоят из символов a , причем число этих символов есть квадрат натурального числа: 1, 4, 9, 25 и т.д. Мы зададим для этого языка грамматику без ограничений. Генерация цепочек будет состоять из следующих этапов:
- Генерация n символов для некоторого натурального числа n .
- Порождение из этого числа символов n^2 символов.
- Преобразование этих символов в символы a .
S --> LS"R
S" --> AS"B
S" --> AB
Первым правилом оборачиваем порождаемую цепочку в ограничители L и R . Они нам понадобятся в дальнейшем для реализации третьей фазы генерации. Оставшиеся два правила просто генерируют цепочку вида AA...ABB...B , где число символов A и B совпадает.
Теперь необходимо породить n^2 символов на основе цепочке AA...ABB...B . Это делает простым приемом. Двигаем символы B налево и, при каждом переходе через символ A , порождать еще один символ C . Через символы C символ A может свободно проходить направо, а символ B - налево. Правила для этого этапа следующие:
AB --> BAC
AC --> CA
CB --> BC
Когда все символы B дойдут до левого края, перейдя символы A , символов C будет ровно n^2 .
Теперь надо освободиться от символов L , A , B и R , а также преобразовать символы C в символы a . Для этого аннигилируем символ B при его проходе до левого края, т.е. до символа L . Соответственно поступаем и с символом A на правом крае. При реализации такой стратегии останется цепочка вида LCC....CR . Чтобы избавится от символов L и R , начинаем двигать левый ограничитель к правому и, при их соприкосновении, уничтожаем эти символы. Заодно, при прохождении через символы L , преобразуем их в символы a . Приведем правила для этой фазы генерации.
LB --> L
AR --> R
LC --> aL
LR --> epsilon
Здесь epsilon обозначает пустую цепочку.
Приведем в качестве примера порождение цепочки aaaa: S => LS"R => LAS"BR => LAABBR => LABACBR => LBACACBR => LACACBR => LACABCR => LACBACCR => LABCACCR => LBACCACCR => LACCACCR => LCACACCR => LCCAACCR => LCCACACR => LCCACCAR => LCCACCR => LCCCACR => LCCCCAR => LCCCCR => aLCCCR => aaLCCR => aaaLCR => aaaaLR => aaaa
Заключение
Автор надеется, что последний пример ясно продемонстрировал читателю, что порождающая грамматика Хомского представляет собой своего рода программу, предназначенную для генерации цепочек формального языка, задаваемого этой грамматикой. Язык задания программы довольно специфический, соответственно и реализация «программ генерации» (грамматик) требует опыта и определенной привычки в их написании.Порождающие грамматики Хомского основаны на глубоких идеях и нет ничего удивительного в том, что какие-то подклассы этого вида грамматик генерируют не только определенный вида языков, но и пересекаются с идеями из других разделов математической лингвистики. К таких разделам относятся категориальные грамматики и распознающие автоматы. Конечно, в этом тексте описаны только основные идеи, теория порождающих грамматик шире и глубже, чтобы ее можно было описать в рамках одной статьи.
Формальная грамматика или просто грамматика в теории формальных языков - способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита . Различают порождающие и распознающие (или аналитические ) грамматики - первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит ли оно в язык или нет.
Энциклопедичный YouTube
-
1 / 5
Словами языка, заданного грамматикой, являются все последовательности терминалов, выводимые (порождаемые) из начального нетерминала по правилам вывода.
Чтобы задать грамматику, требуется задать алфавиты терминалов и нетерминалов, набор правил вывода, а также выделить в множестве нетерминалов начальный.
Итак, грамматика определяется следующими характеристиками:
Вывод
Выводом называется последовательность строк, состоящих из терминалов и нетерминалов, где первой идет строка, состоящая из одного стартового нетерминала, а каждая последующая строка получена из предыдущей путём замены некоторой подстроки по одному (любому) из правил. Конечной строкой является строка, полностью состоящая из терминалов, и следовательно являющаяся словом языка.
Существование вывода для некоторого слова является критерием его принадлежности к языку, определяемому данной грамматикой.
Типы грамматик
Терминальный алфавит:
Σ {\displaystyle \Sigma } = {"0","1","2","3","4","5","6","7","8","9","+","-","*","/","(",")"}Нетерминальный алфавит:
{ ФОРМУЛА, ЗНАК, ЧИСЛО, ЦИФРА }
1. ФОРМУЛА → {\displaystyle \to } ФОРМУЛА ЗНАК ФОРМУЛА (формула есть две формулы, соединенные знаком) 2. ФОРМУЛА → {\displaystyle \to } ЧИСЛО (формула есть число) 3. ФОРМУЛА → {\displaystyle \to } (ФОРМУЛА) (формула есть формула в скобках) 4. ЗНАК → {\displaystyle \to } + | - | * | / (знак есть плюс или минус, или умножить, или разделить) 5. ЧИСЛО → {\displaystyle \to } ЦИФРА (число есть цифра) 6. ЧИСЛО → {\displaystyle \to } ЧИСЛО ЦИФРА (число есть число и цифра) 7. ЦИФРА → {\displaystyle \to } 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (цифра есть 0 или 1, или... 9)
Начальный нетерминал:
ФОРМУЛА
Вывод :
Выведем формулу (12+5) с помощью перечисленных правил вывода. Для наглядности, стороны каждой замены показаны попарно, в каждой паре заменяемая часть подчеркнута.
ФОРМУЛА → 3 {\displaystyle {\stackrel {3}{\to }}} (ФОРМУЛА) (ФОРМУЛА ) → 1 {\displaystyle {\stackrel {1}{\to }}} (ФОРМУЛА ЗНАК ФОРМУЛА ) (ФОРМУЛА ЗНАК ФОРМУЛА) → 4 {\displaystyle {\stackrel {4}{\to }}} (ФОРМУЛА + ФОРМУЛА) (ФОРМУЛА + ФОРМУЛА ) (ФОРМУЛА + ЧИСЛО ) (ФОРМУЛА + ЧИСЛО ) (ФОРМУЛА + ЦИФРА ) (ФОРМУЛА + ЦИФРА ) (ФОРМУЛА + 5 ) (ФОРМУЛА + 5) → 2 {\displaystyle {\stackrel {2}{\to }}} (ЧИСЛО + 5) (ЧИСЛО + 5) → 6 {\displaystyle {\stackrel {6}{\to }}} (ЧИСЛО ЦИФРА + 5) (ЧИСЛО ЦИФРА + 5) → 5 {\displaystyle {\stackrel {5}{\to }}} (ЦИФРА ЦИФРА + 5) (ЦИФРА ЦИФРА + 5) → 7 {\displaystyle {\stackrel {7}{\to }}} (1 ЦИФРА + 5) (1 ЦИФРА + 5) → 7 {\displaystyle {\stackrel {7}{\to }}} (1 2 + 5)Формальная грамматика или просто грамматика в теории формальных языков - способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита . Различают порождающие и распознающие (или аналитические ) грамматики - первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит ли оно в язык или нет.
Термины
- Терминал (терминальный символ) - объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»). В формальных языках, используемых на компьютере, в качестве терминалов обычно берут все или часть стандартных символов ASCII - латинские буквы, цифры и спец. символы.
- Нетерминал (нетерминальный символ) - объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.
Порождающие грамматики
Словами языка, заданного грамматикой, являются все последовательности терминалов, выводимые (порождаемые) из начального нетерминала по правилам вывода.
Чтобы задать грамматику, требуется задать алфавиты терминалов и нетерминалов, набор правил вывода, а также выделить в множестве нетерминалов начальный.
Итак, грамматика определяется следующими характеристиками:
Вывод
Выводом называется последовательность строк, состоящих из терминалов и нетерминалов, где первой идет строка, состоящая из одного стартового нетерминала, а каждая последующая строка получена из предыдущей путём замены некоторой подстроки по одному (любому) из правил. Конечной строкой является строка, полностью состоящая из терминалов, и следовательно являющаяся словом языка.
Существование вывода для некоторого слова является критерием его принадлежности к языку, определяемому данной грамматикой.
Типы грамматик
Терминальный алфавит:
Σ {\displaystyle \Sigma } = {"0","1","2","3","4","5","6","7","8","9","+","-","*","/","(",")"}Нетерминальный алфавит:
{ ФОРМУЛА, ЗНАК, ЧИСЛО, ЦИФРА }
1. ФОРМУЛА → {\displaystyle \to } ФОРМУЛА ЗНАК ФОРМУЛА (формула есть две формулы, соединенные знаком) 2. ФОРМУЛА → {\displaystyle \to } ЧИСЛО (формула есть число) 3. ФОРМУЛА → {\displaystyle \to } (ФОРМУЛА) (формула есть формула в скобках) 4. ЗНАК → {\displaystyle \to } + | - | * | / (знак есть плюс или минус, или умножить, или разделить) 5. ЧИСЛО → {\displaystyle \to } ЦИФРА (число есть цифра) 6. ЧИСЛО → {\displaystyle \to } ЧИСЛО ЦИФРА (число есть число и цифра) 7. ЦИФРА → {\displaystyle \to } 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (цифра есть 0 или 1, или... 9)
Начальный нетерминал:
ФОРМУЛА
Вывод :
Выведем формулу (12+5) с помощью перечисленных правил вывода. Для наглядности, стороны каждой замены показаны попарно, в каждой паре заменяемая часть подчеркнута.
ФОРМУЛА → 3 {\displaystyle {\stackrel {3}{\to }}} (ФОРМУЛА) (ФОРМУЛА ) → 1 {\displaystyle {\stackrel {1}{\to }}} (ФОРМУЛА ЗНАК ФОРМУЛА ) (ФОРМУЛА ЗНАК ФОРМУЛА) → 4 {\displaystyle {\stackrel {4}{\to }}} (ФОРМУЛА + ФОРМУЛА) (ФОРМУЛА + ФОРМУЛА ) (ФОРМУЛА + ЧИСЛО ) (ФОРМУЛА + ЧИСЛО ) (ФОРМУЛА + ЦИФРА ) (ФОРМУЛА + ЦИФРА ) (ФОРМУЛА + 5 ) (ФОРМУЛА + 5) → 2 {\displaystyle {\stackrel {2}{\to }}} (ЧИСЛО + 5) (ЧИСЛО + 5) → 6 {\displaystyle {\stackrel {6}{\to }}} (ЧИСЛО ЦИФРА + 5) (ЧИСЛО ЦИФРА + 5) → 5 {\displaystyle {\stackrel {5}{\to }}} (ЦИФРА ЦИФРА + 5) (ЦИФРА ЦИФРА + 5) → 7 {\displaystyle {\stackrel {7}{\to }}} (1 ЦИФРА + 5) (1 ЦИФРА + 5) → 7 {\displaystyle {\stackrel {7}{\to }}} (1 2 + 5)Алгоритм был ранее определен как алфавитный оператор с конечной системой правил преобразования. Для записи входных, промежуточных и выходных слов используется некоторый алфавит. Каким-то образом должны быть описаны и правила преобразования. Очевидно, для этого требуется некоторый язык. Пригоден ли для описания алгоритма обычный разговорный язык?
Любой естественный язык возникал как средство общения людей. Именно по этой причине ему присущи такие особенности как:
· изменчивость, которая состоит в непостоянстве словарного состава языка;
· неоднозначность трактовки фраз различными людьми;
· избыточность, о чем шла речь в главе «Кодирование символьной информации».
Перечисленные особенности не позволяют применить естественный язык для записи алгоритма, поскольку одним из свойств алгоритма является его детерминированность, т.е. однозначность выполнения шагов любым исполнителем. Наиболее простой путь преодоления нежелательных свойств естественных языков - построение языков искусственных со строгим синтаксисом и полной смысловой определенностью - такие языки получили название формальных.
В любом языке - естественном или искусственном - можно выделить две составляющие: синтаксис и семантику. Синтаксис (грамматика языка) - это совокупность правил, согласно которым строятся допустимые в данном языке конструкции. Семантика - смысловая сторона языка - она соотносит единицы и конструкции языка с некоторым внешним миром, для описания которого язык используется.
Для описания формального языка необходим другой язык, с помощью которого будут создаваться языковые конструкции. Описываемый формальный язык называется языком-объектом, а язык, средствами которого производится описание - метаязыком. Метаязык должен обеспечивать как описание структурных единиц языка и правил объединения их в допустимые предложения, так и содержательную (смысловую) сторону языковых конструкций.
Любая грамматика начинается с указания алфавита, т.е. набора символов, посредством которого строятся конструкции языка.
Синтаксис формального языка задается некоторой системой правил (порождающей системой), которая из небольшого набора исходных конструкций порождает все допустимые их комбинации, т.е. язык образуется как множество разрешенных правилами сочетаний исходных конструкций. Кроме этого, синтаксис содержит формулировку условия, которое выполняется для законченных конструкций языка и не выполняется в противном случае.
Помимо синтаксиса устанавливается система правил, позволяющих конструкциям языка придать смысл - эти правила образуют семантику языка.
Формальная грамматика - система правил, описывающая множество конечных последовательностей символов формального алфавита.
Конечные цепочки символов называются предложениями формального языка, а само множество цепочек - языком, описываемым данной грамматикой.
Набор синтаксических правил формального языка аналогичен системе подстановок, используемых в нормальных алгоритмах Маркова. Вывод в данной порождающей грамматике есть последовательность цепочек, в которой любая, начиная со второй, получается из предыдущей применением какого-либо правила вывода.
Формальная грамматика задается упорядоченной четверкой {T , N, S, Р }, где Т и N - непересекающиеся конечные множества, образующие алфавит или словарь порождаемого формального языка; Т называется множеством (словарем) терминальных символов; N - множеством (словарем) нетерминальных (вспомогательных) символов. S - начальный (выделенный) вспомогательный символ из множества N. Р - набор правил вывода конструкций языка (подстановок) из выделенного вспомогательного символа, имеющие вид g → h, где g и h - цепочки, состоящие как из терминальных, так и нетерминальных символов.
Подстановки работают следующим образом: если в преобразуемой цепочке есть слово g , то оно заменяется словом h. Единственное ограничение на вид подстановок состоит в том, что слово g не может состоять только из терминальных символов. Это означает, что получение на некотором шаге цепочки, состоящей только из терминальных символов, свидетельствует о прекращении процесса порождения - эта цепочка является правильной, завершенной конструкцией порождаемого языка. Подстановки Р могут применяться к трансформируемой цепочке в произвольном порядке.
ВВЕДЕНИЕ………… ………………………………….…………….4
Глава 1. ЯЗЫКИ И ГРАММАТИКИ. ОБОЗНАЧЕНИЯ, ОПРЕДЕЛЕНИЯ И КЛАССИФИКАЦИЯ ………………………………………………………………………………6
1.1. Понятие грамматики языка. Обозначения……………………………………………7
1.2. Классификация грамматик по Хомскому………………………..…………………13
1.3. Техника построения КС- и А- грамматик…………………………………………..16
1.4. Синтаксические деревья вывода в КС-грамматиках. Представление
А-грамматик в виде графа состояний. Неоднозначность грамматик……………..19
1.5. Синтаксический анализ А-языков…………………………………………………..23
Упражнения……………………………………………………………………………….29
Глава 2. РАСПОЗНАВАТЕЛИ И АВТОМАТЫ .……………………………….….…………32
Глава 3. АВТОМАТНЫЕ ГРАММАТИКИ И КОНЕЧНЫЕ АВТОМАТЫ …………….35
3.1. Автоматные грамматики и конечные автоматы…………………………………….35
3.2.Эквивалентность недетерминированных и детерминированных А-грамматик…… 36
Упражнения………………………………………………………………………………… 41
Глава 4. ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ КОНТЕКСТНО-СВОБОДНЫХ
И АВТОМАТНЫХ ГРАММАТИК ………………………………………………..….42
4.2. Исключение тупиковых правил из грамматик………………………………………46
4.3. Обобщенные КС-грамматики и приведение грамматик к удлиняющей форме…….48
4.4. Устранение левой рекурсии и левая факторизация………………………………..…52
Упражнения………………………………………………………………………………….53
Глава 5. СВОЙСТВА АВТОМАТНЫХ И КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ …55
5.1. Общий вид цепочек А-языков и КС-языков………………………………………..55
5.2. Операции над языками………………………………………………………………….59
5.2.1. Операции над КС-языками………………………………………………………59
5.2.2. Операции над А-языками………………………………………………………62
5.2.3. Операции над К-языками………………………………………………………66
5.3. Выводы для практики…………….………………………………………………….67
5.4. Неоднозначность КС-грамматик и языков…………………………………………71
Упражнения…………………………………………………………………………....…74
Глава 6. СИНТАКСИЧЕСКИЙ АНАЛИЗ КС-языков ……………………………...……...75
6.1. Методы анализа КС-языков. Грамматики предшествования………………….…75
6.2. Грамматики предшествования Вирта……………………………………………...77
Грамматики предшествования Флойда…….……………………………………...79
Функции предшествования…………………………………………………………81
Упражнения………………………………………………………………………………84
Глава 7. ВВЕДЕНИЕ В СЕМАНТИКУ ……………………………………………………….85
7.1. Польская инверсная запись….……………………………………………………...85
7.2. Интерпретация ПОЛИЗа……………………………….………………………..….87
7.3. Генерирование команд по ПОЛИЗу………………………………….…………....89
7.4. Алгоритм Замельсона и Бауэра перевода выражений в ПОЛИЗ………..……….91
7.5. Атрибутные грамматики……………………………………………………………97
Упражнения……………………………………………………………………………..100
Глава 8. ОСНОВНЫЕ ФАЗЫ КОМПИЛЯЦИИ ……………………………………...……100
ЗАКЛЮЧЕНИЕ
ПРИЛОЖЕНИЕ …………………………………………………………………………………105
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ ……………………………………………………….…….…115
Введение
Лингвистика - наука о языке. Математическая лингвистика - наука, занимающаяся формальными методами построения и изучения языков.
Теория формальных грамматик - раздел математической лингвистики, включающий способы описания формальных грамматик языков, построение методов и алгоритмов анализа принадлежности цепочек языку, а также алгоритмов перевода (трансляции) алгоритмических языков на язык машины.
Импульсом к созданию и совершенствованию этой теории послужило развитие вычислительной техники и, как следствие, необходимость в средствах общения человека с ЭВМ. Во всех применениях ЭВМ должна понимать какой-либо язык, на котором пользователь может сообщить ей алгоритмы решения задач и исходные данные. Каждая ЭВМ имеет собственный язык машинных команд, представляемых в двоичном коде и отражающих отдельные операции процессора. На первых этапах развития вычислительной техники программисты общались с ЭВМ именно на этом примитивном языке, но человек не способен хорошо мыслить в категориях цифрового языка машины. Автоматизация программирования привела к созданию вначале языков ассемблера, а затем и алгоритмических языков высокого уровня, перевод с которых на родной машинный язык был поручен самой ЭВМ. Программы такого перевода называются трансляторами .
С проблемами объяснения языка машине сталкиваются многие разработчики программного обеспечения. Человеку свойственно изобретать новые языки. Здесь речь может идти не только о сложных компиляторах для новых алгоритмических языков программирования. Любая автоматизированная система должна понимать некоторый входной язык запросов. Новые информационные технологии предполагают привлечение конечного пользователя (ученого, конструктора, технолога, оператора) - специалиста в конкретной области, а не в области вычислительной техники и технологии программирования, к решению своих задач на ЭВМ. Для качественного решения этой проблемы между пользователем и ЭВМ должен существовать интеллектуальный интерфейс: пользователь должен ставить задачи и получать результаты их решения в терминах известной ему предметной области. То есть, необходима разработка широкого спектра предметно-ориентированных языков. Специалист в области программного обеспечения должен знать, как создаются языки и их программная поддержка.
Чтобы объяснить язык машине, необходимо четко представлять, как он устроен и как мы его понимаем. Задумавшись над этим, мы увидим, что не знаем, как мы понимаем наш родной язык. Процесс этого понимания подсознателен, интуитивен. Но чтобы создать транслятор, необходимо иметь алгоритм перевода текста в те действия, которые этот текст требует выполнить, а это, в свою очередь, требует формализации языка . Задачи формализации языка и решает математическая лингвистика. Естественные языки слишком сложны, и формализовать их полностью пока не удается. Алгоритмические языки, напротив, уже создаются в расчете на формализацию. Теория формальных языков - это наиболее развитая ветвь математической лингвистики, представляющая по сути методику объяснения языка машине. Прежде чем рассматривать определения, модели и методы этой теории, рассмотрим некоторые понятия на примерах из естественных языков.
Язык – это множество предложений (фраз), построенных по определенным правилам.
Грамматика - свод правил, определяющих принадлежность фразы языку.
Любой язык должен удовлетворять свойствам разрешимости и однозначности.
Язык разрешим , если за конечное время можно определить, что фраза или предложение принадлежит языку. Язык однозначен , если любая фраза понимается единственным образом.
Основными разделами грамматики являются синтаксис и семантика.
Синтаксис - свод правил, определяющих правильность построения предложений языка.
Семантика - свод правил, определяющих семантическую или смысловую правильность предложений языка.
Предложение может быть синтаксически верным и семантически неверным.
Синтаксис обычно упрощается тем, что не все фразы языка обязаны иметь смысл. Зачастую трудно понять смысл футуристов или речь некоторых политиков. В этой связи интересен пример академика Л.В.Щербы: «Глокая куздра штеко будланула бокра и кудрячит бокренка». Это фраза на русском языке, так как её можно разобрать по членам предложения, но смысл её неясен.
Синтаксический анализ фразы можно записать в виде дерева грамматического разбора. Узлы дерева, такие как подлежащее, сказуемое, группа подлежащего, предложение соответствует синтаксическим понятиям, а листья – это слова, из которых строится предложение. Обрубив в дереве часть листьев и ветвей, мы получим сентенциальную форму (выводимую цепочку).
<предложение>
Природу неоднозначности фразы можно объяснить на примере все того же дерева разбора для фразы «Мать любит дочь».
Эта фраза двусмысленна, так как имеет два варианта синтаксического разбора. Синтаксическая неоднозначность напрямую влечет неоднозначность семантическую. Но можно предложить и примеры синтаксически однозначных фраз, которые могут быть не поняты из-за неоднозначного смысла слов. Напомним, что алгоритмический язык должен быть однозначным.
Формальный язык – это математическая абстракция, возникшая как обобщение обычных лингвистических понятий естественных языков. Теория формальных языков изучает в основном синтаксис языков и является фундаментом синтаксически управляемых процессов перевода, к которому можно отнести трансляцию, ассемблирование и компиляцию. Основы этой теории были заложены американским математиком Н. Хомским в конце 50-х начале 60-х годов и до настоящего времени продолжают развиваться вместе с развитием вычислительной техники. Остановимся на основных элементах этой теории.
