Содержание

 

     Введение

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

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

 

     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 - называют контекстно-зависимыми грамматиками, и в них возможность замены цепочки символов может определяться контекстом. Используются для генерации элементов естественных языков и подъязыков.