Предлагается тема проекта для студентов 3–5 курсов университетов, специализирующихся в области информационных технологий, связанная с исследованием схемы реализации алгоритмических языков на базе объектно-ориентированного описания семантики языка и метода синтаксически управляемого перевода входной программы в промежуточный объектно-ориентированный код. Семантика программы реализуется за счёт использования одной полиморфной функции, вызываемой рекурсивно для исполнения конструкций программы в динамической последовательности, зависящей от значений данных. Этот полиморфизм учитывает как бесконтекстную синтаксическую структуру программы, так и её контекст, связанный видами или типами конструкций, её составляющих. Такая объектно-ориентированная спецификация семантики языка программирования приводит к функционально-ориентированной структуре выходной программы, которая может реализовываться на базе функциональных систем программирования. Цель работы: изучить метод описания алгоритмических языков по А. ван Вейнгаардену и исследовать предлагаемую схему их реализации с использованием современных средств синтаксического анализа и систем объектно-ориентированного программирования.

The scheme for implementation of algorithmic languages is proposed, based on object-oriented specification of semantics and syntax-directed translation technique. The resulting code is generated in object-oriented style. The project is suggested as a research topic for 3rd, 4th, or 5th year IT students. Program semantics are implemented by means of a polymorphic function being recursively called for the purpose of executing the program constructs in a dynamic sequence, depending on actual data values. The polymorphism takes into account context-free structure of the program, as well as context dependence on the modes or types of constructions. The object-oriented specification of the programming language semantics results in functional program structure that may be implemented by a functional programming system. The main goals are to study the algorithmic language description method by A. van Wijngaarden and to investigate the scheme for language implementation by means of the present-day parsing technique and object-oriented programming systems.

Рассматривается реализация приведений в объектно-ориентированной модели семантики на примере языка программирования Алгол 68.

Рассматривается реализация условных и вариантных предложений как конструкций в объектно-ориентированной модели семантики на примере языка программирования Алгол 68.

The implementation of the conditional clause and the case clause based on the object-oriented model of semantics of the programming language Algol 68, as example, is discussed.

Рассматриваются некоторые нерешённые вопросы реализации семантики алгоритмических языков в контексте обсуждаемого проекта.

Some unresolved questions of implementation of semantics of algorithmic languages in a context of the discussed project are considered.

Существует множество технологических средств построения анализаторов формальных языков, используемых при создании разного вида трансляторов языков программирования. Все они, в конечном счёте, основываются на КС-грамматиках с теми или иными ограничениями, частным случаем которых являются регулярные (автоматные) грамматики. Как правило, эти технологические средства обеспечивают лишь проверку соответствующих требований, предъявляемых к грамматике, и выдачу диагностических сообщений об их нарушениях, тогда как существует множество способов эквивалентных преобразований КС-грамматик, которые могут быть выполнены автоматически и дать грамматики, удовлетворяющие требованиям метода анализа. Цель этой статьи – описать способ исключения несамовставленных нетерминалов из КС-грамматик за счёт введения регулярных выражений в правые части правил грамматики. В предельном случае такая преобразованная грамматика включает единственное правило для начального нетерминала.

There is a variety of parser generators for formal languages being used during designing compilers for programming languages of different types. All of them are based on the use of context-free grammars with various restrictions, regular grammars being a special case. As a rule, they only check the requirements imposed on grammar, and issue diagnostic messages in case of their violation. The purpose of this article is to describe the way of eliminating all nonterminals from the non-self-embedding grammar that gives the equivalent regular expression as result.

Описывается метод построения контекстно зависимых сплайновых челночных процессоров, используемых в SYNTAX-технологии для реализации синтаксически управляемых трансляций. Метод базируется на RBNF-грамматиках, представляемых в виде модифицированных диаграмм Н. Вирта, граф-схем. Процессоры обладают линейной оценкой сложности по времени относительно длины входного предложения. С. 3-15.

The method of creation contextually dependent spline shuttle processors used in SYNTAX-technology for implementation of syntactically controlled translations is described. The method is based on RBNF-grammars, represented in a form of modified N. Wirth’s charts, graph-schemes. The processors possess the linear estimation of complexity on time concerning length of an input sentence.

Метод минимизации приведённых детерминированных конечных автоматов, описанный в частности в [1], не всегда даёт минимальный по числу состояний автомат. В данной статье предлагается процесс минимизации этим методом считать лишь первым этапом и дополнить его вторым этапом, гарантирующим искомый результат. С. 23-27.

The method for minimizing reduced deterministic finite automata, described in particular in [1], not always gives minimum on number of it states. It is offered to add the second stage to the method in question in order to guarantee required outcome.

Описывается метод генерации тестов минимальной длины для синтаксически управляемых конечных процессоров, реализующих регулярные языки. Критерий выбора тестовых вариантов выражает заданную степень покрытия дуг графа, представляющего регулярное выражение, по которому строится процессор. Поскольку дуги графа помечены семантическими метками, то критерий выражает соответствующую степень взаимодействия между семантиками, и тест гарантирует выполнение этого критерия. Метод основан на алгоритме решения задачи Китайского почтальона на ориентированном графе, выводимом из регулярного выражения, определяющем конечно-автоматный язык, реализуемом процессором. С. 17-45

A method of generation of tests of minimum length for the purpose of testing of syntax directed finite processors recognizing regular languages is described. A criterion of the test cases selection is introduced that represents the requested level of coverage for the acres of the graph that corresponds to the regular expression for which the processor has been constructed. Since the graph acres are labeled with semantic labels, the criterion defines the degree of interaction between these semantics, so such a test must be built that the criterion conditions are met. The method is based on the algorithm of the solution of the Chinese Postman Problem on a directed graph, that is built for the input regular expression that defines the language recognized by the finite processor.

Описывается алгоритм минимизации приведённых детерминированных конечных автоматов, основанный на использовании классов эквивалентности по признаку неразличимости множеств цепочек, принимаемых в соответствующих состояниях. Проводится сравнение с алгоритмом Дж. Хопкрофта, в котором классы эквивалентных состояний строятся, исходя из отношения различимости состояний по допустимым входным цепочкам. C. 5-14.

An algorithm for minimizing the number of states of the well-formed deterministic finite automaton is described. It is based on the use of equivalence classes on the relation of the indistinguishability of string sets accepted by the automaton. A comparison is made with the well-known algorithm of J.E. Hopcroft, which constructs the classes of equivalent states on the property of the distinguishability of input strings accepted in the corresponding states.

Рассматривается моделирование генераторов Алгола 68 в форме объектов-конструкций, а также результатов их исполнения, то есть значений имён соответствующих видов. В частности, обсуждается представление косвенных имён. Демонстрируется их использование на примерах.

The modelling of the Algol 68 generators in the form of object-constructions, as well as results of their elaboration, i.e. values of names of appropriating types, is considered. In particular, the representing of indirect names is discussed. Their use based on examples is demonstrated.

Цель данной статьи – методологическая. Описывается опыт применения модифицированных синтаксических диаграмм Н. Вирта в SYNTAX-технологии, разработанной в связи с реализацией языка программирования Алгол 68 в начале 1970-х. С. 3-19.

The purpose of the article is a methodological one. An application of modified the Wirth's syntactic charts is described in connection with the implementation of the programming language Algol 68 in the early 1970s.

Рассматривается представление значений простых видов в форме объектов-контейнеров и реализация элементарных конструктов, источников таких значений, в форме объектов-конструкций, то есть изображений соответствующих видов, а также формул над простыми значениями со стандартными операциями. Описывается реализация последовательных предложений, входящих в состав всех других предложений, таких как замкнутые, выбирающие (по логическому условию, вариантные целому или по виду) и циклические предложения.

The representation of the plain mode values in the forms of the object-containers and the elementary constructs resulting in values of such a kind, i.e. the plain denotations and the standard mode formulas, are considered. The implementation of the serial clauses constituting closed, choice using boolean, integral or united clauses, as well as the loop clauses, is described also.

Описывается метод регуляризации приведённых КС-грамматик без самовставлений, основанный на топологической сортировке нетерминалов грамматики по отношению зависимости, определяемой правилами грамматики.

The method for the regularization of reduced non-self-embedding context-free grammars, based on the topological sorting of nonterminals of the grammar according the relation of the dependence defined by the grammar rules, is described.

Рассматривается представление описаний простых видов в форме объектов-конструкций, а также окружений, реализуемых в виде иерархии участков в стеке, заполненных индикаторами, посредством которых программа получает доступ к значениям. Описывается сам этот метод доступа.

The article describes representation of plain mode declarations as object-oriented constructs, and implementation of environments in the form of hierarchy of stack frames. The indicators stored in a stack frame are used for the program to have access to valid values. The access method to the values in question is described.