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

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

Всякая ли фраза может быть переведена с одного языка на другой при заданном наборе правил и заданном объеме машинной памяти;

Как описать множество текстов, доступных для перевода в данных условиях? и.т.д.

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

Появление трансляторов сделало проблему перевода центральной в построении общей теории вычислительных систем.

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

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

Независимо и параллельно развивалась общая теория алгоритмов как ветвь современной математики. Была установлена эквивалентность понятий «нормальный алгоритм Маркова», «общерекурсивная функция» и «машина Тьюринга», а тезис Чёрча связал эти три понятия с интуитивным представлением об алгоритме.

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

Эквивалентность понятий «алгоритм» и «машина Тьюринга» сделало естественным предположение о том, что поиски классификации алгоритмов окажутся связанными с поисками промежуточных моделей между моделями конечного автомата и машиной Тьюринга.

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

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

Эта теория возникла в 50-е годы в работах американского лингвиста

Н. Хомского. По характеру используемого математического аппарата теория формальных грамматик и языков близка к теории алгоритмов и к теории автоматов.

Дадим некоторые определения.

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

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

Словоформа или просто слово – это последовательность (цепочка) морфем.

Морфема – это мельчайшая грамматически значимая часть слова.

Например, слово «ведший» состоит из морфем вед+ ш+ий (корень, суффикс, окончание).

Словосочетание или предложение – это цепочка словоформ.

Грамматика языка – это конечное множество правил, определяющих этот язык.

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

Синтаксис языка – это правила построения предложений в языке.

Семантика языка – толкование этих правил, правила использования синтаксиса.

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

Первым и основным требованием к грамматике является следующее:

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

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

Вторым требованием к грамматике является ее конечность .

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

Классификация грамматик может быть представлена в следующем виде:

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

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

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

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

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

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

Рассмотрим класс, порождающий грамматику. Порождающей грамматикой можно назвать упорядоченную систему

,

где - конечное множество символов, называемых терминальным

или основным словарем G.

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

Конечное непустое множество символов, называемых нетерминальным (вспомогательным) словарем G.

Нетерминальный словарь – набор символов, которые обозначают классы или цепочки исходных элементов, или словарь синтаксических типов.

Элементы и называются соответственно нетерминальными и терминальными символами.

- словарь грамматики G.

Произвольную конечную последовательность элементов будем называть цепочкой в словаре .

Пустая цепочка обозначается , т.о. . Число членов этой цепочки назовём ее длиной и будем обозначать .

Цепочки символов словаря получаются с помощью операции конкатенации
Например, . Символ может опускаться там, где не возникает неоднозначности.

Операция конкатенации ассоциативна, но не коммутативна.
эквивалентно .

S – начальный символ грамматики .

Это выделенный нетерминальный символ, обозначающий класс тех языковых объектов, для описания которых предназначается данная грамматика. Иногда в литературе S называют аксиомой или целью грамматики,

P – правила грамматики или конечное множество цепочек вида j à y, где j и y - слова в словаре V и цепочка j cодержит по крайней мере один символ из словаря Vн.

Конечое двуместное отношение à интерпретируется как “заменить j на y”.

Это отношение несимметрично и нерефлексивно.

Цепочка вида j à y называется правилами грамматики или правилами подстановки, а множество P – схемой грамматики .

Если задана грамматика , то будем говорить:

Цепочка w’ получается непосредственно из цепочки w применением правила j à y, если w=x1jx2 , w"=x1jx2 и {j à y}ÎP.

Последовательность цепочки j=j0, j1, j2 … , jn = y (n³1) ,

где 0 £ i £ n и j - есть вывод цепо чки y, если для каждого i ji+1 следует из ji .

Наличие j - вывода цепочки y будем обозначать: j => y.

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

Цепочка y выводится из цепочки j, если она получается из j примененных некоторых правил грамматики G .

Вывод цепочки y считается законченным , если не следует цепочка, которая следует из j.

Цепочка, состоящая только из терминальных символов, называется терминальной цепочкой .

Множество цепочек, выводимых в грамматике G, называется языком, порожденным этой грамматикой, и обозначается L(G).

Язык L(G) называется терминальным, если L-множество терминальных цепочек грамматики G.

Условимся:

Первыми строчными латинскими буквами a, b, c, … обозначать элементы терминального словаря Vт,

Прописными латинскими буквами A, B, C, … - элементы нетерминального словаря Vн,

Строчными греческими буквами a, b, … - элементы общего словаря V.

Предложения, составные из этих предложений будем обозначать последними буквами этих алфавитов, т. е. x1 , y1 , … - предложения составляемые из элементов Vт, X, Y, … - предложения, составляемые из элементов Vн, w, j, y , … - предложения составляемые из элементов общего словаря V.

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

Рассмотрим пример:

G=(Vт, Vн,P,S), где Vт={a, b}; Vн={A,B,C}; S=C; P={Càab, CàaCb}.

Пусть w=aCb, w"=aaCbb. Цепочка w" непосредственно выводится из w применением одного правила.

j-вывод: aCb, aaCbb, aaaCbbb, aaaabbbb (терминальная).

Длина вывода = 3.

Из примера видно, что порождающая грамматика не является алгоритмом.

Правила подстановки грамматики – это не последовательность предписаний, а совокупность разрешений.

Это означает следующее:

Правило j à y понимается как “ j может быть заменено на y”, а не “должно быть заменено”;

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

Две грамматики G1 и G2 называются слабо эквивалентными , если они порождают один и то же язык L(G1)= L(G2), то есть совпадает множество порождаемых ими фраз.

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

Основным объектом применения таких формальных грамматик являются не произвольные грамматики, а грамматики некоторых специальных типов.

Выделение этих типов производится по виду правил.

В теории Хомского выделяются четыре типа языков , порожденных четырьмя основными типами грамматик .

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

Грамматика называется грамматикой типа 1 , если в системе Р правила j à y удовлетворяют условию j = j1Аj2 y = j1wj2,

j, y, w - цепочки из словаря V.

Таким образом, нетерминальный символ А переходит в непустую цепочку w в контексте j1 и j2 (j1 и j2 могут быть пустыми цепочками).

Грамматики типа 1 называют контекстными .

Грамматика называется грамматикой типа 2 – бесконтекстной , если в системе правил Р допустимы лишь правила вида:

где А – нетерминальный символ,

w - непустая цепочка из V.

Грамматика называется грамматикой типа 3 , когда допустимы лишь правила вида:

где w = аВ либо w = а.

Веденные классы могут быть разбиты на подклассы, но об этом немного позже

Л А Б О Р А Т О Р Н А Я Р А Б О Т А №1

Cоздание формальной грамматики и построение

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

ОСНОВНЫЕ СВЕДЕНИЯ

Создание грамматики языка

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

Каковы же основные принципы проектирования и разработки новых языков программирования? Каким требованиям должен удовлетворять язык, рассчитанный на широкое использование при решении задач на ЭВМ? В первую очередь, язык должен быть удобен для программиста. В частности, он должен быть легок в изучении, а также иметь средства, позволяющие с минимальными затратами времени подготовить задачи к решению на ЭВМ. С другой стороны, должны учитываться характеристики работы ЭВМ с программой: память, необходимая для обработки программы, количество машинного времени для решения задачи и пр. К сожалению, эти требования являются в известной степени трудно совместимыми. То, что «удобно» для ЭВМ, оказывается не совсем удобным для программиста и наоборот. Но, т.к. любая задача содержит, как правило и те, и другие требования к используемому языку, то при его создании необходимо учитывать обе стороны работы с ним.

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

Основным определением такого аппарата является определение формального языка. Всякий язык программирования можно определить как множество предложений – некоторое множество цепочек или конечных последовательностей элементарных единиц из некоторого непустого конечного множества символов, называемого словарем или алфавитом. При таком рассмотрении языка программирования задается только множество символов, которые можно использовать для записи программы, а также класс допустимых или синтаксически правильных программ и при этом не затрагивается вопрос зада­ния смысла каждой правильной программы. Чтобы отличать употребление слова «язык» в значении точно определенного множества цепочек от употребления этого слова в повседневной речи, множество цепочек иногда называют формальным языком .

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

Синтаксис – внешнее представление предложений языка.

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

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

Формальная грамматика – абстрактное обобщение грамматики естественных языков – рассматривает строки (цепочки) символов.

Формальная грамматика есть четверка

G = { V , V , P , S },

где V- алфавит терминальных символов, т.е. символов, которые могут входить в левые части правил (соответствует набору слов и знаков языка);

V-алфавит нетерминальных символов (соответствует набору обобщающих понятий языка);

Р - набор порождающих правил вида

где  и  - цепочки терминальных и нетерминальных символов;

S - начальный символ грамматики (соответствует начальному понятию).

Грамматика G для любой цепочки    задает множество выводимых из нее цепочек, определяя их рекурсивно следующим образом: если  содержится в Р, то цепочка r =  непосредственно выводима из  (обозначается r), если  выводима из  и r , то r нетривиально выводима из  (  + r) ; если   + r или =r, то r выводима из  (=*r). Последо­вательность применения правил  1   2 ... r называется выводом цепочки , если  1 = S,  r =  .

Цепочка, выводимая из S, называется сентенциальной формой . Сентенциальная форма не содержащая нетерминальных символов, называется предложением . Множество предложений образует язык , порожденный грамматикой G (L(G)).

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

Широко используемой формой записи правил грамматик являются формы Бэкуса-Науэра (БНФ).

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

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

Характерной особенностью языков программирования, так же как и естественных языков, является то, что в сложные синтаксические конструкции в качестве составных частей входят другие конструкции. Так, программа на языке TurboPascal является обычно блоком, который в свою очередь может включать в себя один или несколько внутренних блоков. Блок также является сложной конструкцией, включающей в себя описания, операторы; последние тоже имеют составные части и т.д. Таким образом, для того, чтобы написать программу, необходимо знать правила написания блоков и других конструкций, входящих в программу в качестве составных частей. Вторым классом объектов, используемых в формах Бэкуса, как раз и являются имена конструкций описываемого языка, или так называемые металингвистические переменные. Значение металингвистических переменных – это цепочки основных символов описываемого языка.

Каждая металингвистическая формула описывает правила построения некоторой конструкции языка и состоит из двух частей. В левой части находится металингвистическая переменная, обозначающая соответствующую конструкцию (нетерминальный (НТ) символ). Далее следует так называемая металингвистическая связка:: =, проставляемая вместо символа  и имеющая смысл глагола «быть». Она соединяет левую и правую части формулы. В правой части формулы указывается один или несколько вариантов построения конструкции, определенной в левой части. Каждый вариант представляет собой цепочку, состоящующую из металингвистических переменных и основных символов (терминальных(Т)). Для того, чтобы построить конструкцию, определяемую формулой, нужно выбрать некоторый вариант построения из правой части формулы и, используя соответствующие формулы вместо каждой металингвистической переменной некоторые цепочки основных символов. Варианты правой части формулы разделяются металингвистической связкой |, имеющей значение «или».

Наконец, необходимо отметить, что металингвистические переменная может обозначаться словами или некоторыми именами, заключенными в угловые скобки. Имя металингвистической переменной присваивается программистом и поясняет смысл описываемой конструкции, например: арифметическое выражение.

Пример формальной грамматики, записанной в формах Бэкуса-Науэра.

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

Грамматика G1 записи числа содержит следующие 13 правил:

(1) число::= чс

(2) чс::= чс цифра

(3) чс::= цифра

(4) цифра::= 0

(5) цифра::= 1

(6) цифра::= 2

(7) цифра::= 3

(8) цифра::= 4

(9) цифра::= 5

(10) цифра::= 6

(11) цифра::= 7

(12) цифра::= 8

(13) цифра::= 9

G1 = {{0,1,2,3,4,5,6,7,8,9}, {цифра, число, чс}, Р, число },

Где первое указанное множество – алфавит терминальных символов;

второе указанное множество – алфавит нетерминальных символов;

Р - 13 правил, указанных выше;

 число  - начальный символ грамматики.

Поскольку в формах Бэкуса-Науэра вариант “или” записывается знаком «|», то грамматику необходимо записать так:

число::= чс

чс::= чс цифра | цифра

цифра::= 0|1|2|3|4|5|6|7|8|9

Классификация Хомского

Грамматики можно классифицировать по виду их правил.

Существует четыре вида грамматик:

грамматика с фразовой структурой (на ней построены естественные языки);

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

контекстно-свободные (КС) грамматики, где каждое правило имеет вид:

   где  V, а  - цепочка в алфавите V V;

автоматные грамматики, где каждое правило имеет вид:

  х В или

  х, где

х  V, {,B}  V.

Язык L называется автоматным, контекстно-свободным, контекстно-зависимым или с фразовой структурой, если существует определяющая его грамматика G соответствующего типа, для которой L = L(G).

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

Термины

• Терминал (терминальный символ) - объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»). В формальных языках, используемых на компьютере, в качестве терминалов обычно берут все или часть стандартных символов ASCII - латинские буквы, цифры и спец. символы.
• Нетерминал (нетерминальный символ) - объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.

Порождающие грамматики

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

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

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

Вывод

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

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

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

Терминальный алфавит:

Нетерминальный алфавит:

{ ФОРМУЛА, ЗНАК, ЧИСЛО, ЦИФРА }

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

Аннотация: В данном разделе рассматриваются основы дисциплины: "формальная грамматика". Эта дисциплина рассматривает любые операции с символами, а ее выводы широко используются при анализе формальных и "человеческих" языков, а также в искусственном интеллекте. Эта лекция является самой важной и, одновременно, самой сложной для понимания лекцией курса. В связи с этим автор преподносит читателю только ее выводы, опуская математические доказательства. Для лучшего понимания материала может потребоваться обращение к материалам предыдущих и последующих лекций.

10.1. Алфавит

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

О п р е д е л е н и е . Алфавит - это непустое конечное множество элементов.

В "классическом" языке алфавит - это набор литер. В фонетике - набор издаваемых человеком звуков речи. В музыке - это набор нот, и т.д.

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

Всякая конечная последовательность символов алфавита называется словом, или, более профессионально, цепочкой. Цепочками, состоящими из символов {a, b, c}, будут следующие последовательности: a, b, c, aa, ab, bc, ac , bb, abba и другие. Также допускается существование пустой цепочки Л - полное отсутствие символов. Важен также порядок следования символов в цепочке. Так, цепочки ab и ba - разные цепочки. Далее заглавные латинские буквы будут использованы как переменные и символы, а строчные латинские буквы будут обозначать цепочки. Например:

X = SVT Листинг 10.1.

цепочка, состоящая из символов S , V и T , и именно в этом порядке.

О п р е д е л е н и е . Длиной цепочки называется число символов в этой цепочке. Она обозначается как |x| . Например: |Л| = 0, |A| = 1, |BA| = 2, |ABBA| = 4 .

Если x и y являются цепочками, то их конкатенацией будет цепочка xy . От перестановки цепочек при конкатенации результат меняется (как и в теории групп). Если z = xy - цепочка, то x - голова, а y - хвост цепочки. Если нам безразлична голова цепочки, мы будем обозначать:

Z = … x Листинг 10.2.

а если нам безразличен хвост, мы будем писать:

Z = x … Листинг 10.3.

О п р е де л е н и е . Произведение двух множеств цепочек определяется как конкатенация всех цепочек, входящих в эти множества . Например, если множество A = {a, b}, а B = {c,d} , то:

AB = {ac, ad, bc, bd} Листинг 10.4.

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

И при конкатенации цепочек, и при перемножении множеств цепочек истинным остается ассоциативный закон, записывающийся как:

Z = (ab)c = a(bc) = abc Листинг 10.5.

D = (AB)C = A(BC) = ABC Листинг 10.6.

И, наконец, определим степень цепочки. Если x - непустая цепочка, то x 0 = {Л}, x 1 = x, x 2 = xx, x n = x(x) (n-1) . То же самое обстоит и со степенью множеств.

10.2. Терминальные и нетерминальные символы

Понятие терминальных и нетерминальных символов тесно связано с понятием правила подстановки (или продукции). Дадим его определение .

О п р е д е л е н и е . Продукцией, или правилом подстановки, называется упорядоченная пара (U, x ), записываемая как:

U::= x Листинг 10.7.

где U - символ, а x - непустая конечная цепочка символов .

Символы, встречающиеся только в правой части, называются терминальными символами . Символы, встречающиеся и в левой, и в правой части правил, называются нетерминальными символами, или синтаксическими единицами языка. Множество нетерминальных символов обозначается как VN, а терминальных символов - VT.

Примечание . Данное определение терминальных и нетерминальных символов истинно для КС- грамматик и A- грамматик (см. раздел 10.4.3).

О п р е д е л е н и е . Грамматикой G[Z] называют конечное, непустое множество правил, содержащее нетерминальный символ Z хотя бы один раз на множестве правил. Символ Z называют начальным символом. Далее мы все нетерминальные символы будем обозначать как <символ>.

[Пример 01]

Грамматика : "число"

<число> ::= <чс> <чс> ::= <цифра> <чс> ::= <чс><цифра> <цифра> ::= 0 <цифра> ::= 1 <цифра> ::= 2 <цифра> ::= 3 <цифра> ::= 4 <цифра> ::= 5 <цифра> ::= 6 <цифра> ::= 7 <цифра> ::= 8 <цифра> ::= 9

Дадим еще определение :

О п р е д е л е н и е . Цепочка v непосредственно порождает цепочку w , если:

V = xy, а w = xuy Листинг 10.8.

где ::= u - правило грамматики . Это обозначается как v => w . Мы также говорим, что цепочка w непосредственно выводима из v . При этом цепочки x и y могут быть пустыми.

О п р е д е л е н и е . Говорят, что v порождает w , или w приводится к v , если существует конечная цепочка выводов u0, u1, …, u[n] (n > 0) , такая, что