Пакет MapleTFL

Содержание

Общее описание
Архитектура пакета
- Структура файлов
Соглашения и правила
- Оформление исходного кода
- Имена процедур и переменных

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

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

Все требуемые операции над языками реализуются наиболее подходящими для этого задающими структурами. Вот базовые интерфейсы для трех их типов:

     тип: Acceptor
     операции: 
        # проверить принадлежность цепочки языку
        accept( str ) 

        # преобразование к другим структурам
        toGenerator()
        toExpression()

     тип: Generator
     операции:
        # сбросить генератор цепочек
        reset() 
        # выдать следующую по порядку цепочку языка
        getNextString()

        # преобразование к другим структурам
        toAcceptor()
        toExpression()

     тип: Expression
     операции:

        # представить в строковой форме
        # в частности, для RE форма должна быть совместима с StringTools
        toString()
       
        # преобразование к другим структурам
        toAcceptor()
        toGenerator()

Структура файлов

Каталог с исходными текстами пакета имеет следующую структуру.

`src\`	Исходные тексты
`doc\`	Документация
`extra\`	Дополнительные файлы

Все исходные тексты располагаются на одном уровне каталога, система их следующая:

Имя файла	Описание	Включает
`tfl.mpl`	Головной файл	`Interface.mpl, Language.mpl`
`Language.mpl`	Конструкторы и утилиты к типу `Language`	`Acceptor.mpl, Generator.mpl, Expression.mpl`
`Acceptor.mpl`	Конструкторы и утилиты к типу `Acceptor`	`FA.mpl, DGraph.mpl`
`Generator.mpl`	Конструкторы и утилиты к типу `Generator`
`Expression.mpl`	Конструкторы и утилиты к типу `Expression`	`RE.mpl`
`FA.mpl`	Реализация конечных автоматов
`RE.mpl`	Реализация регулярных выражений
`DGraph.mpl`	Реализация D-графов
`Interface.mpl`	Вспомогательный модуль для работы с интерфейсами

Соглашения и правила

Оформление иходного кода

Комментарии и диагностические сообщения пишутся на английском языке — для избежания проблем с кодировками и переключения раскладок;) По поводу отступов, форматов комментариев и прочего — чуть позже.

Имена процедур и переменных

Возьмем на вооружение следующие стили именования (номенклатура позаимствована из Style Guide for Python Code):

lower_case_with_underscores: слова пишутся строчными буквами, разделяются подчеркиванием
CapWords: слова пишутся слитно, первые буквы слов прописные
mixedCase: аналогично CapWords, но первая буква строчная

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

Все процедуры именуются в стиле 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.