Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://al.cs.msu.su/static/seminars/catfl/maple_tfl/doc/index.html
Дата изменения: Wed Feb 22 02:43:48 2006 Дата индексирования: Mon Oct 1 20:07:52 2012 Кодировка: koi8-r |
Пакет содержит типы данных и алгоритмы для поддержки теории формальных языков в системе Maple.
Для введения новых типов, соответствующих объектам теории,
используется механизм модулей и интерфейсов.
Для представления символов используется тип type/character
,
Для представления цепочек — тип type/string
.
Среди цепочек языка принимается порядок —
лексикографический.
Основной новый тип: Language
. В нем заключены все возможности
по заданию, преобразованию и анализу формальных языков.
Задать язык возможно любой из структур следующего типа:
допускателем (Acceptor), генератором (Generator), выражением (Expression).
Ниже приведена краткая диаграмма классов:
Использована нотация UML: Пустые ромбики означают агрегацию (отношения «целое-часть», но часть может существовать без целого), пустые стрелки — наследование (в нашем случае расширение интерфейса). (Спецификация пока неполная, будут добавлены многие операции над языками).
тип: 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
для полного прогона всего пакета.