|
Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://al.cs.msu.ru/static/seminars/catfl/maple_tfl/doc/index.html
Дата изменения: Wed Feb 22 02:43:48 2006 Дата индексирования: Mon Oct 1 20:07:40 2012 Кодировка: koi8-r |
Пакет содержит типы данных и алгоритмы для поддержки теории формальных языков в системе Maple.
Для введения новых типов, соответствующих объектам теории,
используется механизм модулей и интерфейсов.
Для представления символов используется тип type/character,
Для представления цепочек — тип type/string.
Среди цепочек языка принимается порядок —
лексикографический.
Основной новый тип: Language. В нем заключены все возможности
по заданию, преобразованию и анализу формальных языков.
Задать язык возможно любой из структур следующего типа:
допускателем (Acceptor), генератором (Generator), выражением (Expression).
Ниже приведена краткая диаграмма классов:
тип: Language
операции:
# проверить принадлежность цепочки языку
accept( str )
# сбросить генерацию цепочек
reset()
# выдать следующую по порядку цепочку языка
getNextString()
# выдать список первых n цепочек языка
# (срез по номеру цепочки)
getFirstStrings( n )
# выдать список всех цепочек языка
# ограниченной длины (срез по длине)
getLengthCut( len )
# группа операций set/get для трех типов
# задающих структур
getAcceptor(), setAcceptor( acptr ),
getGenerator(), setGenerator( genr ),
getExpression(), setExpression( expr )
# проверка свойств
whatChomskyType() # тип по Хомскому
isEmpty() # пустота
isFinite() # конечность
# операции над языками
opUnion(lang)
opIntersect(lang)
opConcat(lang)
opKleeneStar()
opKleenePlus()
opMorphism(func)
Все требуемые операции над языками реализуются наиболее подходящими для этого задающими структурами. Вот базовые интерфейсы для трех их типов:
тип: Acceptor
операции:
# проверить принадлежность цепочки языку
accept( str )
# преобразование к другим структурам
toGenerator()
toExpression()
тип: Generator
операции:
# сбросить генератор цепочек
reset()
# выдать следующую по порядку цепочку языка
getNextString()
# преобразование к другим структурам
toAcceptor()
toExpression()
тип: Expression
операции:
# представить в строковой форме
# в частности, для RegExpr форма должна быть
# совместима с StringTools
toString()
# преобразование к другим структурам
toAcceptor()
toGenerator()
Каталог с исходными текстами пакета имеет следующую структуру.
src\ | Исходные тексты | |
doc\ | Документация | |
extra\ | Дополнительные файлы |
Все исходные тексты располагаются на одном уровне каталога, система их следующая:
| Имя файла | Описание | Включает |
tfl.mpl |
Головной файл | Interface.mpl, Debug.mpl, Language.mpl
|
Language.mpl |
Конструкторы и утилиты к типу Language |
Acceptor.mpl, Generator.mpl, Expression.mpl |
Acceptor.mpl |
Конструкторы и утилиты к типу Acceptor
|
FiniteAut.mpl, DGraph.mpl
|
Generator.mpl |
Конструкторы и утилиты к типу Generator
|
|
Expression.mpl |
Конструкторы и утилиты к типу Expression
|
RegExpr.mpl
|
FiniteAut.mpl |
Реализация конечных автоматов | |
RegExpr.mpl |
Реализация регулярных выражений | |
DGraph.mpl |
Реализация D-графов | |
Interface.mpl |
Вспомогательный модуль для работы с интерфейсами | |
Debug.mpl |
Вспомогательный модуль для отладки | |
test.mpl |
Последовательность тестов для всего пакета |
Комментарии и диагностические сообщения пишутся на английском языке — для избежания проблем с кодировками и переключения раскладок;) По поводу отступов, форматов комментариев и прочего — чуть позже.
Возьмем на вооружение следующие стили именования (номенклатура позаимствована из Style Guide for Python Code):
lower_case_with_underscores:
слова пишутся строчными буквами, разделяются подчеркиваниемCapWords: слова пишутся слитно,
первые буквы слов прописныеmixedCase: аналогично CapWords,
но первая буква строчная
Все классы (в нашем случае их роль выполняют интерфейсы)
именуются в стиле CapWords, допустимы
аббревиатуры и общепринятые сокращения, например: PushdownAutomaton,
RegExp, FiniteAut.
Все процедуры именуются в стиле mixedCase,
с дополнительными различиями:
new,
например: newLanguage()
is
(если булевские) или what, например: isFinite(), whatChomskyType()
to, например: toAcceptor(), toRegExp()
Все закрытые (неэкспортируемые) переменные модулей,
отличные от процедур, именуются в стиле
lower_case_with_underscores и имеют префикс m_,
например: m_states_table.
Все параметры процедур именуются в стиле
lower_case_with_underscores и имеют префикс p_,
например: p_length.
Для тестирования пакета предназначен модуль test.mpl,
который запускается так: cmaple < test.mpl.
В нем содержится последовательность общих тестов для пакета,
и могут включаться последовательности для отдельных частей пакета.
Для построения тестов используется процедура assert,
определяемая в Debug.mpl. Вызов
assert(expr,[par1,par2,...]),
проверяет условие expr = true, в случае невыполнения
выводит сообщение об ошибке и список остальных (необязательных)
своих параметров, затем досрочно завершает Maple-сессию с кодом 5.
Такое завершение возможно только в консольном режиме (cmaple),
в графическом же система продолжит вычисление тестов.
Для тестирования своего модуля каждый автор пишет и предварительно прогоняет
свою последовательность тестов (например, для модуля FiniteAut.mpl
пишется testFiniteAut.mpl). Затем все тесты включаются в
test.mpl для полного прогона всего пакета.