Способы получения одних цепочек символов из других

Вступление

Предлагается курс дистанционного обучения системному программированию объёмом 50 часов лекционных и 62 часа лабораторных занятий.

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

Курс составили: Авраменко Виктор Васильевич, кандидат технических наук, доцент, доцент кафедры информатики Сумского государственного университета.

Преподаёт дисциплины: «Алгоритмические языки», «Системное программирование», «Основы математического моделирования и вычислительной техники».

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

Контактный телефон: 21-40-84

Электронная почта: avr@sumdu.edu.ua

Скаковская Алла Николаевна, ст. преподаватель кафедры информатики Сумского государственного университета.

Преподаёт дисциплины: «Алгоритмические языки», «Системное программирование», «Системы и методы принятия решений», «Программное обеспечение».

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

Контактный телефон: 39-23-01.

Электронная почта: sk_alla@id.sumdu.edu.ua

Список литературы

Берн Страуструп. Язык программирования С++ (спец. издание). М.: Диасофт, 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 раз. Например, abba² это abbaabba.

2) х^R. Цепочка символов х записывается в обратной последовательности. Например, port^R это 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 – стартовый (главный) нетерминальный символ. Для алгоритмических языков это обычно нетерминальный символ “программа”.

Способы получения одних цепочек символов из других

1 Это можно сделать непосредственно, т.е. за одну операцию. Условное обозначение Þ.

Например, dÞh означает, что цепочку символов h можно получить из цепочки d за одну операцию.

Пример. Есть цепочка d=aAb и h=anb. Здесь, a,n,b - терминальные символы (обозначены строчными буквами), а А – нетерминальный символ. Пусть среди множества правил Р есть такое: A®nЄР. То есть нетерминальный символ АЄN можно заменить на терминальный n. Таким образом, за одну операцию из d можно получить цепочку h.

2 Одну цепочку из другой можно получить не за одну операцию. Условие обозначения Þ*

Например, a₀ Þ*a_n

Это имеет место, если a₀ = a_n , или существует последовательность непосредственно получаемых цепочек таких, что a₀ Þ a₁ Þ a₂ Þ… a_n-1 Þ a_n

Не нашли, что искали? Воспользуйтесь поиском по сайту: