Документ взят из кэша поисковой машины. Адрес оригинального документа : 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
Общее описание

Пакет MapleTFL (версия 0.1.2)

Содержание

Общее описание

Пакет содержит типы данных и алгоритмы для поддержки теории формальных языков в системе 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):

Все классы (в нашем случае их роль выполняют интерфейсы) именуются в стиле CapWords, допустимы аббревиатуры и общепринятые сокращения, например: PushdownAutomaton, RegExp, FiniteAut.

Все процедуры именуются в стиле mixedCase, с дополнительными различиями:

Все закрытые (неэкспортируемые) переменные модулей, отличные от процедур, именуются в стиле 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 для полного прогона всего пакета.