Сведения о регулярных выражениях
Вступление
Предлагается курс дистанционного обучения системному программированию объёмом 50 часов лекционных и 62 часа лабораторных занятий.
Естественно, предлагаемый объём материала недостаточен для всеобъемлющего изложения системного программирования. Поэтому предполагается, что более полные сведения об этом предмете студенты смогут найти в специальной литературе, а также в сети Internet.
Курс составили: Авраменко Виктор Васильевич, кандидат технических наук, доцент, доцент кафедры информатики Сумского государственного университета.
Преподаёт дисциплины: «Алгоритмические языки», «Системное программирование», «Основы математического моделирования и вычислительной техники».
Научные интересы: статистические методы контроля сложных объектов управления, разработка интегральных оценок спектральных плотностей и законов распределения случайных величин, разработка и исследование характеристик непропорциональностей числовых функций и их использование для решения задач распознавания образов.
Контактный телефон: 21-40-84
Электронная почта: [email protected]
Скаковская Алла Николаевна, ст. преподаватель кафедры информатики Сумского государственного университета.
Преподаёт дисциплины: «Алгоритмические языки», «Системное программирование», «Системы и методы принятия решений», «Программное обеспечение».
Научные интересы: информационный анализ и синтез интеллектуальных систем контроля и управления, адаптивные системы.
Контактный телефон: 39-23-01.
Электронная почта: [email protected]
Список литературы
Берн Страуструп. Язык программирования С++ (спец. издание). М.: Диасофт, 2000г.
Бруно Бабэ. Просто и ясно о Borland C++. М.: Бином, 1995.
Проценко В.С., Чаленко П.И., Ставровський А.Б. Техніка програмування мовою Сі:. Навчальний посібник. – Київ, 1993
Теренс Чан Системное программирование на С++ для UNIX. BHV.- Киев, 1999.
И.М.Двоеглазов. Язык программирования С++(Справочное руководство).- Киев: Евроиндекс ,1993.
Стефан Дьюхарст, Кэти Старк. Программирование на С++. Киев: НИПФ «Диасофт»,1993.
Пол Лукас. С++ под рукой. Киев: НИПФ,”ДиаСофт”,1993.
Деревянко Ф.С. Системное программное обеспечение персональных ЭВМ. Учебное пособие.- Харьков: ХГПУ,1994.
А.И. Касаткин, А.Н. Вальвачев. От TURBO C к BORLAND C++.,- Минск: - ВШ, 1992.
Сложные системные приложения пишутся на алгоритмических языках Си и С++. Язык Си обычно изучается в дисциплине «Алгоритмические языки». Как правило, количество учебных часов, выделяемых под курс ”Алгоритмические языки”, достаточно только для изучения языка Си. В то же время при написании системных приложений для ОС широко используется язык С++. В отличие от других процедурных языков программирования, он обеспечивает более строгий контроль типов и содержит объектно-ориентированные конструкции. Указанные особенности очень полезны для разработки и сопровождения крупномасштабных и достаточно сложных приложений для ОС UNIX. Поэтому в предлагаемом дистанционном курсе часть учебных занятий выделено под С++.
Предполагается, что программы на Си и С++ будут вводиться, отлаживаться и запускаться в интегрированной среде Borland C++.
Дистанционный курс «Системное программирование» состоит из двух частей. Первая из них включает сведения, необходимые для написания однопроходного интерпретатора . Этот интерпретатор переводит программу, написанную на учебном алгоритмическом языке SPL, в последовательность промежуточных команд и затем выполняет их. При написании этой части использовано учебное пособие [2]. В процессе написания программы- интерпретатора студенты получают представления о том , каким образом обрабатываются программы, написанные на алгоритмических языках. Вторая часть посвящена изучению языка С++.
Лекция 1
Анализ формальных языков
Сведения о регулярных выражениях
Любой язык имеет алфавит.
Алфавит – это конечное множество I элементов, называемых символами.
Цепочка или слово в алфавите I – это конечная последовательность элементов (символов) из алфавита I.
Например, если алфавит языка состоит только из заглавных и строчных букв латинского алфавита, то любые последовательности этих букв являются цепочками (словами), в том числе цепочка может состоять из одного символа.
С цепочками (словами) могут быть проделаны действия, которые имеют следующие обозначения:
1) хn. Цепочка символов х повторяется (пишется без пробелов одна за другой) n раз. Например, abba2 это abbaabba.
2) хR. Цепочка символов х записывается в обратной последовательности. Например, portR это trop.
3) xy. За цепочкой символов x без пробела помещается цепочка символов y.
4) х*. Цепочка символов х в цикле может повторяться нуль и более раз.
Обычно в алгоритмических языках это действие реализуется циклом с предварительной проверкой условия.
Например: intl iden (‘,’ iden)* ‘;’
Это означает, что за символом intl должно следовать iden. Затем через запятую может еще повторяться iden нуль и более раз. В конце должна быть точка с запятой.
5) х+. Цепочка символов х должна повторяться один и больше раз. В алгоритмическом языке Pascal это реализуется оператором repeat, а в языке Си – оператором цикла do while.
6) |х|. Определение длины цепочки символов х (количество символов в цепочке).
7) {} или e, или e - обозначение пустой цепочки символов.
8) [х]. Так обозначается необязательная цепочка символов. Например, такая запись нужна для того, чтобы обозначить, что перед числом знак может быть, а может и отсутствовать.
Кроме алфавита и цепочки символов (слов), важным понятием является язык.
Язык в алфавите I – это произвольное множество цепочек (слов).
Регулярные выражения
Это цепочки символов, в которые входят не только символы из некоторого алфавита I, но и другие символы, которые часто носят служебный характер. Например, это может быть запятая для разделения других символов, а также символы для обозначения каких-либо действий над цепочками. Пусть множество {,* |} из перечисленных в фигурных скобках символов не входят в алфавит I. Тогда цепочка символов из объединения IU{,* |} называется регулярным выражением. Эти выражения обычно используются для описания синтаксиса какого-либо алгоритмического языка.
Грамматика
Грамматика-
G=(T,N,P,S),
где T - алфавит т.н. терминальных символов. Это символы, которые заведомо определены. Например, это символы, используемые в каком-либо алгоритмическом языке. Какие это символы и какое их количество – все это заведомо определено. Только эти символы в дальнейшем используются при написании программ на этом алгоритмическом языке.
N – алфавит т.н. нетерминальных символов. Это символы, которые обычно используются для определения каких-либо понятий. Такими понятиями в алгоритмическом языке, например, являются идентификатор, переменная, константа, выражение, оператор и, в конце концов, программа. Обычно эти понятия перечисляются и обозначаются символами. Эти символы определяются через терминальные символы или, кроме того, через другие нетерминальные символы более низкого уровня. Например, при определении нетерминального символа “программа” используются терминальные символы алгоритмического языка, а также нетерминальные символы “оператор”, “выражение”, “слагаемое” и др.
Множества T и N не пересекаются. Обычно терминальные символы обозначаются строчными буквами, а нетерминальные – заглавными. Р – множество правил вывода для нетерминальных символов. Например, это правила описания переменных, констант, написания выражений, операторов и т.д. S – стартовый (главный) нетерминальный символ. Для алгоритмических языков это обычно нетерминальный символ “программа”.