DonNTU   Masters' portal

Abstract

Content

Introduction

Software development technology require the involvement a huge number of engineers of different directions, which are manually make a product. Using this approach, the development of software systems is faced with the obvious problems: lack of coordination of structural parts, ambiguity, redundancy (incomplete) of the project documentation, etc. This is due to the fact that the aim of developing is a large, complex analysis and design of the system.

One of the most expensive phases of software development is, in fact, writing program code (functional parts). That is why research area is the automatic generation of source code. In an analysis of possible approaches to solving problems associated with the automatic synthesis of programs SADT methodology was selected and reviewed.

1. SADT metodology actuality

Structural analysis relates graphical notation with a human language (Russian, English, etc.) and allows us to construct a description of almost any object (domain) hierarchically with any degree of detail. Linking together the parts of the whole thing is the essence of structural analysis.

1.1 The formal specification language SADT review

SADT (Structured Analysis and Design Technique) has gained popularity because of its characteristic features, namely:

Thus, the formal specification language SADT improves the accuracy of the transmitted concepts of understanding, helps to overcome the limitations imposed by the formal language that was used for the description of the selected object.

Various commercial organizations make extensive use of SADT methodology to define requirements for the projected system. SADT methodology is applied in many cases in the early stages process of creating of the system, often even before the development of technical specifications, and specially for this purpose. This is due to the fact that the detection of errors and inaccuracies, it was early in the design of complex systems, will help to avoid huge costs later, for example in the testing phase of the product.

1.2 SADT methodology application

SADT has been successfully used in military, industrial and commercial organizations to solve a wide range of tasks: the software of telephone networks, system support and diagnostics, long term and strategic planning, computer–aided manufacturing and design, configuration of computer systems, staff training, embedded software for defense systems, management finance and logistics, etc. One relatively new application of the methodology SADT, is the application of SADT as a tool for quality management [1].

2. A review of research on the topic of master's work

At present, research is underway to address the problems of inconsistency of the structural parts, ambiguity, redundancy (incomplete), followed by the project documentation. Formed even a whole scientific field — CASE–technology (Computer Aided Software Engineering), implementing the execution of certain stages of development in automatic mode. According to some studies, this approach allows to increase productivity of system design, reduce material costs, reduce complexity and improve the quality of projects [2]. 

2.1 Methods of generating source code

Currently, the software development industry uses a visual method of dealing with the user, not a text, as it were, for example, while working in DoS. That is why, the question of the generation source code for graphical models (primitives) is important. Models can be divided into two classes: static and dynamic [3].

The basis for the static models of object–oriented programs is a class diagram. Many of the tools (Rational Rose) uses this approach — the basis of the source code generated by the class diagram [3].

The dynamic properties of this class of programs are best described using state diagrams (transition graphs). This is because every program has a state, even if not clearly marked. There are tools that generate code for a transition graph. These tools are highly specialized — they make the code on one (sometimes two) of a particular programming language.

In practice, hardware solutions are used to generate source code to get the code in different programming languages. This approach was considered in Kanzheleva S., Automatic code generation programs with a clear separation of states. The aim is to describe an approach to code generation programs with explicit conditions on any a priori given programming language [3].

This work result is a tool that allows you to convert images to transition graphs presented with an editor MS Visio, in the source code in different programming languages for which the first had been set up templates [3]. The code generation process has been divided into three stages: the transformation of the transition graph representation of software, conversion software submission to a common format, and directly further the transformation of a common format in the code.

Another approach has been considered in Kruchinin's A. Automatic generation of software components on high–level specifications. The author pays attention to the problem of quality of generated code that indicates the emergence of complex code, which eventually becomes non–obvious and very difficult to understand and subsequent modifications. The main purpose of this paper is to review methods to achieve acceptable localization of of source code. Offer a solution to the problem of implementing crosscutting concerns. This will reduce the cost of making changes to the code. The work is a continuation and development of Fuksman's A. works focusing on the dispersion of software code, as well as the ideas of the vertical foliation of the program.

In this paper authors have developed methods for structuring of source code. To achieve this goal they are developing methods for aspect–oriented paradigm is not limited solely object–oriented languages, by solving the following problems: extension of the applicability of the points are not binding on the object–oriented languages, expanding the range of applicability of the aspects on non–object–oriented languages [4].

2.2 Toolkit for implementation

The use of templates is a common programming technique. In many programming languages have functions for working with templates. But when the variables substituted into the templates, have different structures (arrays, lists, files, etc.), the usual patterns become useless, because the processing of the data structure of each individual.

To solve this problem, you can use multiple containers for a single pattern. An appropriate container is choose according to the type and structure of the source data, and then filling of the container is used as a normal pattern.

The essence of the code generation is substitution in the text of container the data, and the universality lies in the fact that different types and data structures defined by a specific container (the algorithm).

To solve this problem you need to create SADT diagrams and link them into a single structure. You must also create templates and containers for each container, designate an appropriate mask use.

Algorithms, which will contain containers, are based on the common parts, so called. invariants of the algorithms for each data structure. Then created blocks are interconnected by comparing the input data one diagrams with the output of another. Next, we choose the appropriate container to input data. After selecting the container should be replaced by the value of input connections in the pattern of data names corresponding to the input connections.

2.3 The current implementation. invariants of the algorithms

A similar software system was developed by Guban B. [5]. It generates code for for working with arrays of integers and arrays of strings. Have been implemented search function maximum (minimum) values in the array and the swapping of the array elements.

The disadvantage of this software is limited functionality and the ability to use only simple data structures (one-dimensional arrays).

The author distinguished common parts of the algorithms, the so–called invariants of the algorithms.

Consider the example of the work methodology of search functions and further remove the item from the list and the one-dimensional array.

Brute-force search algorithm

Figure 1 — Brute-force search algorithm

Removal algorithm with shift

Figure 2 — Removal algorithm with shift

After analyzing the two algorithms for different data structures, we see that some of these algorithms are identical. The remaining parts are specific to each data structure. The result of comparison of two basic algorithms can be represented using diagrams SADT.

SADT diagram for one-dimensional array

Figure 3 — SADT diagram for one–dimensional array
(x — input array, a — element, Res — index of founded element)

Following consideration of principles, one can also distinguish the invariants of algorithms and build SADT–diagrams for the other data structures (files, direct and sequential access, lines of trees).

Conclusion

After analyzing the existing approaches to automatic code generation, selection focused on the use of formal specification language SADT using invariant algorithms. Thus, the direction of future research will improve the existing implementation of this approach. Building on the work [5] to extend the functionality of the basic search algorithms, modify and delete items. Implement the work of these basic algorithms with a large set of basic data structures, programming languages ​​(matrices, lists, trees).


In writing this essay master's work is not yet complete. Final completion: December 2012. The full text of the work and materials on the topic can be obtained from the author or his manager after that date.

References

  1. Герман М.В., Галактионов Е.А., Применение методологии структурного анализа и проектирования SADT/IDEF0 как инструмента менеджмента качества. Электронный ресурс. Режим доступа: http://www.hsb.tsu.ru/content.php?id=116
  2. Козлинский А.В. CASE–технология: индустриальная разработка систем обработки информации // Компьютерное обозрение. — 1993. — №1.
  3. Канжелев С. Ю. Автоматическая генерация кода программ с явным выделением состояний, Software Engineering Conference (Russia) — 2006 (SEC (R) 2006), с. 60–63.
  4. Кручинин А. Н. Автоматическая генерация программных компонент по высокоуровневым спецификациям, Ростов–на–Дону, — 2006.
  5. Губань Б. И., Анализ эффективности алгоритмов генерации кода по технологии SADT, Реферат по теме выпускной работы. Электронный ресурс. Режим доступа: http://masters.donntu.ru/2010/fknt/guban/diss/index.htm
  6. Жарихина М.А. Подготовка управляющих программ для станков с ЧПУ / Учебно–научно–производственный журнал Автоматизация и управление в машиностроении, Выпуск №21, — Москва, — 2003.
  7. Анисимов Б.П., Котов В.В. Современные методологии структурного анализа и проектирования систем обработки информации / Журнал Программные продукты и системы, Выпуск №2, — Москва, — 1997.
  8. Gabrovska K., Smrikarov A. Structural analysis and methods for development of software tool for design and energy simulation of PV–hybrid power supply systems in poultry farms / International Conference on Computer Systems and Technologies CompSysTech, — 2005.
  9. Богатырёв М.Ю. Инварианты и симметрии в генетических алгоритмах. — Тула: Тульский государственный университет, 2003. — 8 с.
  10. Ross D., Structured Analysis (SA): A Language for Communicating Ideas, IEEE Transactions on Software Engineering, vol. SE–3, N. 1, pp. 16–34. 1, Jan. 1977.