Содержание

     Введение

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

     Центральным разделом математической логики является теория формальных грамматик, возникшая главным образом благодаря работам Н. Хомского. Она изучает способы описания закономерностей, которые характеризуют уже не отдельный текст, а всю совокупность правильных текстов того или иного языка. Эти закономерности описываются путём построения «формальной грамматики» — абстрактного «механизма», позволяющего с помощью единообразной процедуры получать правильные тексты данного языка вместе с описаниями их структуры.

     1. Описание синтаксиса  языка

     1.1 Бэкуса-Наура формы (БНФ)

     Впервые для описания синтаксиса реального  языка программирования – Алгол 60. Описание языка – наглядно, что позволяет широко использовать данную нотацию для описания реальных языков программирования. Для описания использованы следующие обозначения:

• символ "::=" отделяет левую часть правила от правой;
• нетерминалы обозначаются произвольной символьной строкой, заключенной в угловые скобки "<" и ">";
• терминалы - это символы, используемые в описываемом языке;
• каждое правило определяет порождение нескольких альтернативных цепочек, отделяемых друг от друга символом вертикальной черты "|".

     Пример  описания идентификатора с использованием БНФ:

• <буква>::=А|В|С|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
• <цифра> :: = 0|1|2|3|4|5|6|7|8|9
• <имя>::=<буква>|<имя><буква>|<имя><цифра>

     Правила можно задавать и раздельно:

• <имя> :: = <буква>
• <имя> :: = <имя> <буква>
• <имя> :: = <имя> <цифра>

     1.2 Расширенные Бэкуса-Наура  формы (РБНФ)

     Для повышения удобства и компактности описания, в язык вводятся дополнительные конструкции. В частности, специальные метасимволы были разработаны для описания необязательных цепочек, повторяющихся цепочек, обязательных альтернативных цепочек. Существуют различные расширенные формы метаязыков, незначительно отличающиеся друг от друга. Их разнообразие зачастую объясняется желанием разработчиков языков программирования по-своему описать создаваемый язык. Зачастую такие языки называются расширенными формами Бэкуса-Наура (РБНФ).

     В частности, РБНФ, используемые Виртом (Никлаус Вирт  — швейцарский учёный, специалист в области информатики, один из известнейших теоретиков в области разработки языков программирования), имеют следующие особенности:

• Квадратные скобки "[" и "]" означают, что заключенная в них синтаксическая конструкция может отсутствовать;
• фигурные скобки "{" и "}" означают ее повторение (возможно, 0 раз);
• круглые скобки "(" и ")" используются для ограничения альтернативных конструкций;
• сочетание фигурных скобок и косой черты "{/" и "/}" используется для обозначения повторения один и более раз. Нетерминальные символы изображаются словами, выражающими их интуитивный смысл и написанными на русском языке.

     Если  нетерминал состоит из нескольких смысловых  слов, то они должны быть написаны слитно. В этом случае для повышения удобства в восприятии фразы целесообразно  каждое ее слово начинать с заглавной  буквы или разделять слова во фразах символом подчеркивания. Терминальные символы изображаются словами, написанными буквами латинского алфавита или цепочками знаков, заключенными в кавычки. Синтаксическим правилам предшествует знак "$" в начале строки. Каждое правило оканчивается знаком ".". Левая часть правила отделяется от правой знаком "=", а альтернативы - вертикальной чертой "|". В соответствии с данными правилами синтаксис идентификатора будет выглядеть следующим образом:

     $буква  = "A"|"B"|"C"|"D"|"E"|"F"|"G"|"H"|"I"|"J"|"K"|"L"|"M"|"N"|"O"|"P"| "Q"|"R"|"S"|"T"|"U"|"V"|"W"|"X"|"Y"|"Z"|"a"|"b"|"c"|"d"|"e"|"f"|"g"|"h"|"i"|"j"|"k"|"l"|"m"|"n"|"o"|"p"|"q"|"r"|"s"|"t"|"u"|"v"|"w"|"x"|"y"|"z".

     $цифра  = "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9".

     $ имя = буква {буква | цифра}.

      1.3 Диаграммы Вирта

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

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

      Пример  описания имени с использованием диаграмм Вирта представлен на рис 1.1.

                 Рис.1.1. Описание имени с использованием диаграмм Вирта 

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

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

     2. Формальная грамматика

     Грамматика — наиболее распространённый класс описаний языков. Описание грамматики языка начинается с определения алфавита, набора терминальных символов из которых состоит язык. После создания алфавита, необходимо определить набор ограничивающих правил, те правила, по которым будут строиться слова и предложения в языке, вида α→β. В левой и правой частях этих выражений могут содержаться специальные нетерминальные символы. В процессе вывода нетерминальные символы заменяются соответствующими терминальными, до полной их замены, с помощью соответствующих правил. Каждая грамматика должна содержать начальный символ или аксиому, с которой и начинается любое слово или предложение языка.

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

     Объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение называется терминальным символом (терминалом). В формальных языках, используемых на компьютере, в качестве терминалов обычно берут все или часть стандартных символов ASCII (американский стандартный код для обмена информацией) — латинские буквы, цифры и специальные символы.

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

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

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

     Итак, грамматика определяется следующими характеристиками:

• T — конечное множество терминальных символов;
• N — конечное множество нетерминальных символов;
• P — конечное множество продукций вида: «левая часть»   «правая часть», где:
• «левая часть» — непустая последовательность терминалов и нетерминалов, содержащая хотя бы один нетерминал;
• «правая часть» — любая последовательность терминалов и нетерминалов;
• S — начальный символ грамматики из набора нетерминалов.

     Последовательность строк, состоящих из терминалов T и нетерминалов N, где первой идет строка, состоящая из одного стартового нетерминала S, а каждая последующая строка получена из предыдущей путем замены некоторой подстроки по одному (любому) из правил P называется выводом. Конечной строкой является строка, полностью состоящая из терминалов, и, следовательно, являющаяся словом языка.

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

      3. Типы грамматик

     3.1 Классификация  формальных грамматик

      Согласно классификации Хомского (лингвист Ноам Хомский),  формальные грамматики делятся на четыре типа. Для отнесения грамматики к тому или иному типу необходимо соответствие всех её правил (продукций) некоторым схемам.

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

     На  рис 3.1 представлена классификация  грамматик, предложенная Хомским, где:

     Грамматика типа 0 - генеративная, самая сложная, никаких ограничений на вид ее правил не накладывается. Грамматика типа 0, порождающая (generative grammar), - в классической записи это четверка G=(N,T, P, S), где N, T – конечное множество (N - нетерминальные символы, T - терминальные символы метаязыка); S - начальный символ нетерминального множества, Р - правила репродукции (rewriting rules).

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

     Грамматика типа 1 - называют контекстно-зависимыми грамматиками, и в них возможность замены цепочки символов может определяться контекстом. Используются для генерации элементов естественных языков и подъязыков.

     Грамматика типа 2 - контекстно-свободные, при чем в левой части нетерминал может быть всем, чем угодно. Они распознаются в информатике так называемыми автоматами с магазинной памятью (стековые автоматы). Используются для генерации элементов языков программирования (выражений, команд).

     Грамматика типа 3 - называют регулярными, самые простые и ограниченные грамматики, распознаются конечными автоматами. Используется для простых элементов языков (числа, константы, переменные).

      3.2 Неограниченные грамматики

       К типу 0 по классификации Хомского относятся неограниченные грамматики (также известные как грамматики с фразовой структурой). Это — все без исключения формальные грамматики. Для грамматики G = (T,N,P,S), α=T∪N все правила имеют вид:

• α→β, где α — любая цепочка, содержащая хотя бы один нетерминальный символ, а β — любая цепочка символов из алфавита.

     Практического применения в силу своей сложности  такие грамматики не имеют.

      3.3 Контекстно-зависимые грамматики

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

     Формальная  грамматика G = (N, T, S, P) является контекстно-зависимой, если все правила P имеют вид: αSβ → αωβ, где:

• S ∈ N - одиночный нетерминальный символ;
• ω ∈ (N ∪ T)⁺ - непустая цепочка, состоящая из терминальных и/или нетерминальных символов (А⁺ - множество всевозможных конечных последовательностей символов и слов в алфавите А, не включая пустое слово λ);
• α, β ∈ (N ∪ T)* - любая цепочка, состоящая из терминальных и/или нетерминальных символов (А* - множество конечных слов в алфавите А, включая пустое слово λ).

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

      3.4 Контекстно-свободные грамматики

       Контекстно-свободная грамматика — частный случай формальной грамматики, у которой левые части всех продукций являются одиночными нетерминалами. Смысл термина «контекстно-свободная» заключается в том, что возможность применить продукцию к нетерминалу, в отличие от общего случая грамматики Хомского, не зависит от контекста этого нетерминала.

     Формальная  грамматика G = (N, T, S, P) является контекстно-свободной, если все правила P имеют вид: α→β, где:

• S ∈ N - одиночный нетерминальный символ;
• α ∈ (N ∪ T)⁺ - непустая цепочка, состоящая из терминальных и/или нетерминальных символов (А⁺ - множество всевозможных конечных последовательностей символов и слов в алфавите А, не включая пустое слово λ);
• β ∈ (N ∪ T)* - любая цепочка, состоящая из терминальных и/или нетерминальных символов (А* - множество конечных слов в алфавите А, включая пустое слово λ).

     Язык, который может быть задан Контекстно-свободной грамматикой, называется контекстно-свободным языком. Контекстно-свободная грамматика описывается БНФ (Формой Бэкуса-Наура).

     3.5 Регулярные грамматики

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

       Они являются контекстно-свободными, но с ограниченными возможностями.

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

• A→Ba, A→a или A→ε, где:

• ε∈T^*;
• A, B∈N (для леволинейных грамматик).

• A→aB, A→ε или A→a, где:

• a∈T^*;
• A, B∈N (для праволинейных грамматик).

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

       Регулярные выражения состоят из констант и операторов, которые определяют множества строк и множества операций на них соответственно. На данном конечном алфавите Σ определены следующие константы:

• пустое множество - ∅.
• пустая строка - ε обозначает строку, не содержащую ни одного символа. Эквивалентно «».
• символьный литерал - «a», где a — символ алфавита Σ.

     и следующие операции:

• конкатенация – сцепление строк в одну, RхS обозначает множество {αβ | α ∈ R & β ∈ S}. Например, {"А", "B"}{"x", "y"} = {"Ax", "Bx", "Ay", "By"}.
• дизъюнкция - R|S обозначает объединение R и S. Например, {"ab", "c"}|{"ab", "d", "ef"} = {"ab", "c", "d", "ef"}.
• звезда Клини  R* обозначает минимальное надмножество множества R, которое содержит ε и замкнуто относительно конкатенации. Это есть множество всех строк, полученных конкатенацией нуля или более строк из R. Например, {"0", "1"}* = {ε, "0", "1", "00", "01", "10", "11", "000", "001", "010", …}.

     Любая регулярная грамматика G=(N,T, P, S) может быть представлена направленным графом с помеченными узлами и дугами. Каждый узел такого графа может быть помечен символом, являющимся элементом множества N, кроме одного специального – «конечного» узла, помеченного символом #.

     Недетерминированный конечный автомат (НКА) — это пятерка A = (K, T, t, k, F), где:

     К — конечное множество состояний, или вершин;

     T — входной алфавит (также конечный);

     t — множество команд, или дуг;

     k — множество начальных состояний;

     F — множество заключительных состояний.

     Множество  t  можно также интерпретировать  как  отображение  KxT  в множество подмножеств K.

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

       Алгоритм построения НКА по праволинейной грамматике

     1. Множество вершин НКА состоит  из нетерминалов грамматики и  еще одной новой вершины F, которая  объявляется заключительной.

     2. Каждому  правилу  вида  А → аВ  в  автомате  соответствует  дуга  из  вершины  А  в вершину  В,  помеченная  символом  а: A⎯⎯^a→B.  Каждому  правилу  вида  A → a соответствует дуга  A⎯⎯^a→F . Других дуг в автомате нет.

     3. Начальной  вершиной  автомата  является  вершина,  соответствующая  начальному символу грамматики. Вершина В является заключительной, если в грамматике есть правило В → ε. Кроме того, заключительной является F, построенная на шаге 1.

     Алгоритм построения НКА по леволинейной грамматике

     1. Множество вершин НКА состоит из нетерминалов грамматики и еще одной новой вершины Н, которая объявляется начальной.

     2. Каждому  правилу   вида  А → Ва  в  автомате  соответствует  дуга  из  вершины   В  в вершину  А,  помеченная  символом  а: B⎯⎯^a→A.  Каждому  правилу вида  А → а соответствует дуга H⎯⎯^a→A. Других дуг нет.

     3. Заключительной  вершиной  автомата  является  вершина,  соответствующая начальному  символу грамматики. Вершина B является  начальной, если в грамматике  есть  правило B → ε. Кроме   того,  начальной  является  вершина H,  построенная  на шаге 1.

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

     Алгоритм  построения праволинейной грамматики  по НКА с единственной начальной  вершиной

     1. Нетерминалами грамматики будут  вершины автомата, терминалами —  пометки дуг. 

     2. Для каждой дуги вида A⎯⎯^a→B в  грамматику добавляется правило А → аВ. Для каждой заключительной вершины B в грамматику добавляется правило В → ε.

     3. Начальным символом является  нетерминал, соответствующий начальной  вершине. 

     4. К  построенной  по  пунктам  1—3 грамматике  применить   алгоритм  устранения  ε-правил,  затем —  алгоритм  удаления  бесполезных символов (приведения грамматики).

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

     Алгоритм  построения леволинейной грамматики по НКА с единственным заключительным состоянием

     1. Нетерминалами грамматики будут  вершины автомата, терминалами —  пометки дуг. 

     2. Для каждой дуги A⎯⎯^a→B в грамматику добавляется правило В → Аа. Для каждой начальной вершины В в грамматику добавляется правило В → ε.

     3. Начальным  символом  будет   нетерминал,  соответствующий   заключительной вершине. 

     4. К  построенной  по  пунктам  1—3 грамматике  применить   алгоритм  устранения  ε-правил, затем  — алгоритм приведения грамматики.

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

     Все автоматы в примерах 1—4 не являются детерминированными.