From time to time, posts and translated articles are published on Habré devoted to certain aspects of the theory of formal languages. Among such publications (I do not want to point out specific works so as not to offend their authors), especially among those devoted to the description of various language processing software tools, there are often inaccuracies and confusion. The author is inclined to believe that one of the main reasons that led to this unfortunate state of affairs is the insufficient level of understanding of the ideas underlying the theory of formal languages.

This text is intended as a popular introduction to the theory of formal languages ​​and grammars. This theory is considered (and, I must say, rightly) rather complex and confusing. Students usually get bored at lectures, and exams, moreover, do not arouse enthusiasm. Therefore, in science there are not so many researchers in this subject. Suffice it to say that for all the time, from the birth of the theory of formal grammars in the mid-50s of the last century to the present day, only two doctoral dissertations have been published in this scientific direction. One of them was written in the late 60s by Alexei Vladimirovich Gladkiy, the second is already on the threshold of the new millennium - by Mati Pentus.

Further, in the most accessible form, two basic concepts of the theory of formal languages ​​are described: formal language and formal grammar. If the test is interesting to the audience, then the author makes a solemn promise to give birth to a couple more similar opuses.

Formal languages

In short, a formal language is a mathematical model of a real language. Real language here is understood as a certain way of communication (communication) of subjects with each other. For communication, subjects use a finite set of signs (symbols) that are pronounced (written out) in a strict temporal order, i.e. form linear sequences. Such sequences are usually called words or sentences. Thus, only the so-called. communicative function of the language, which is studied using mathematical methods. Other functions of the language are not studied here and, therefore, are not considered.

To better understand how formal languages ​​are learned, it is first necessary to understand what are the features of mathematical learning methods. According to Kolmogorov et. to whatever it is applied, it always follows two basic principles:

1. Generalization (abstraction). Objects of study in mathematics are special entities that exist only in mathematics and are intended to be studied by mathematicians. Mathematical objects are formed by generalizing real objects. Studying any object, the mathematician notices only some of its properties, and is distracted from the rest. So, the abstract mathematical object "number" can actually mean the number of geese in a pond or the number of molecules in a drop of water; the main thing is that you can talk about geese and water molecules
   talk about aggregates. One important property follows from such an “idealization” of real objects: mathematics often operates with infinite collections, while in reality such collections do not exist.
2. Rigidity of reasoning. In science, it is customary to verify the truth of one or another reasoning by comparing their results with what actually exists, i.e. conduct experiments. In mathematics, this criterion for checking reasoning for truth does not work. Therefore, the conclusions are not verified experimentally, but it is customary to prove their validity by strict reasoning that obeys certain rules. These arguments are called proofs, and proofs serve as the only way to substantiate the correctness of a particular statement.

Thus, in order to study languages ​​using mathematical methods, it is necessary first to extract from the language its properties that seem important for learning, and then these properties are strictly defined. The abstraction obtained in this way will be called a formal language - a mathematical model of a real language. Content specific mathematical model depends on which properties are important to study, i.e. what is planned in this moment highlight and study.

As a well-known example of such a mathematical abstraction, one can cite a model known under the dissonant name for the Russian ear “bag of words”. In this model, natural language texts (ie, one of those languages ​​that people use in the process of everyday communication with each other) are studied. The main object of the bag of words model is a word equipped with a single attribute, the frequency of occurrence of this word in the source text. The model does not take into account how words are placed next to each other, only how many times each word occurs in the text. The bag of words is used in text-based machine learning as one of the main objects of study.

But in the theory of formal languages, it seems important to study the laws of the arrangement of words next to each other, i.e. syntactic properties of texts. For this, the bag of words model looks poor. Therefore, a formal language is defined as a set of sequences composed of elements of a finite alphabet. Let's define this more strictly.

The alphabet is a finite non-empty set of elements. These elements will be called symbols. To denote the alphabet, we will usually use the Latin V, and to denote the symbols of the alphabet, we will use the initial lowercase letters of the Latin alphabet. For example, the expression V = (a,b) denotes an alphabet of two characters a and b.

A string is a finite sequence of characters. For example, abc is a string of three characters. Often when designating chains in symbols, indices are used. The chains themselves are denoted by lowercase characters of the end of the Greek alphabet. For example, omega = a1...an is a string of n characters. The chain can be empty, i.e. not contain any character. Such chains will be denoted by the Greek letter epsilon.

Finally, a formal language L over an alphabet V is an arbitrary set of strings composed of symbols of the alphabet V. Arbitrariness here means the fact that the language can be empty, i.e. not have a single chain, and infinite, i.e. made up of an infinite number of chains. The last fact is often puzzling: are there any real languages ​​that contain an infinite number of strings? Generally speaking, everything in nature is finite. But here we use infinity as the possibility of forming chains of unlimited length. For example, a language that consists of the possible variable names of the C++ programming language is infinite. After all, variable names in C++ are not limited in length, so there can potentially be an infinite number of such names. In reality, of course, long variable names don't matter to us. special meaning because by the end of reading such a name, you already forget its beginning. But as a potential possibility to set variables of unlimited length, this property looks useful.

So, formal languages ​​are simply sets of strings made up of symbols of some finite alphabet. But the question arises: how can one define a formal language? If the language is finite, then one can simply write out all its chains one after another (of course, one might wonder if it makes sense to write down the chains of a language that has at least ten thousand elements and, in general, is there any point in writing it out?). What to do if the language is infinite, how to define it? This is where grammar comes into play.

Formal grammars

The way of specifying a language is called the grammar of that language. Thus, we call grammar any way of specifying a language. For example, the grammar L = (a^nb^n) (here n is a natural number) defines a language L consisting of strings of the form ab, aabb, aaabbb, etc. The language L is an infinite set of strings, but nevertheless, its grammar (description) consists of only 10 characters, i.e. finite.

The purpose of grammar is the task of language. This task must necessarily be final, otherwise the person will not be able to understand this grammar. But how does the final task describe infinite collections? This is possible only if the structure of all chains of the language is based on uniform principles, of which there are a finite number. In the example above, the following principle acts as such a principle: "each string of the language begins with the characters a, followed by the same number of characters b". If a language is an infinite collection of randomly typed chains, the structure of which does not obey uniform principles, then it is obviously impossible to invent a grammar for such a language. And here is another question, whether or not such a collection can be considered a language. For the purposes of mathematical rigor and uniformity of approach, such collections are usually considered a language.

So, the grammar of a language describes the laws of the internal structure of its chains. Such laws are usually called syntactic laws. Thus, one can rephrase the definition of grammar as the final way of describing the syntactic patterns of a language. For practice, not just grammars are interesting, but grammars that can be set within the framework of a single approach (formalism or paradigm). In other words, on the basis of a single language (metalanguage) for describing the grammars of all formal languages. Then you can come up with an algorithm for a computer that will take as input a description of the grammar made in this metalanguage and do something with the chains of the language.

Such paradigms for describing grammars are called syntactic theories. Formal grammar is a mathematical model of grammar, described within the framework of some kind of syntactic theory. There are quite a few such theories. The best-known metalanguage for specifying grammars is, of course, Chomsky's generative grammars. But there are other formalisms as well. One of these, neighborhood grammars, will be described below.

From an algorithmic point of view, grammars can be subdivided according to the way the language is specified. There are three main such ways (types of grammars):

• Recognizing grammars. Such grammars are devices (algorithms) that are given a language chain as input, and at the output the device prints “Yes” if the chain belongs to the language, and “No” otherwise.
• Generating grammars. This kind of device is used to generate chains of languages ​​on demand. Figuratively speaking, when a button is pressed, some language chain will be generated.
• Enumerative grammars. Such grammars print all the chains of the language one after the other. Obviously, if a language consists of an infinite number of strings, then the process of enumeration will never stop. Although, of course, it can be stopped forcibly at the right time, for example, when the desired chain is printed.

An interesting question is about the transformation of grammar types into each other. Is it possible, having a generative grammar, to construct, say, an enumerative one? The answer is yes, you can. To do this, it is enough to generate chains, ordering them, say, by length and order of characters. But in the general case, it is impossible to turn an enumerating grammar into a recognizing one. You can use the following method. Having received a chain as input, start the process of enumerating chains and wait whether the enumerating grammar prints this chain or not. If such a chain is printed, then we finish the enumeration process and print "Yes". If the string belongs to a language, then it will certainly be printed and thus recognized. But, if the chain does not belong to the language, then the recognition process will continue indefinitely. The grammar recognizer will loop. In this sense, the power of recognizing grammars is less than the power of generators and enumerators. This should be kept in mind when comparing Chomsky's generative grammars and Turing's recognition machines.

Neighborhood grammars

In the mid-60s, the Soviet mathematician Yuliy Anatolyevich Shreider proposed a simple way to describe the syntax of languages ​​based on the so-called. neighborhood grammars. For each character of the language, a finite number of its “neighborhoods” are specified - chains containing this character (the center of the neighborhood) somewhere inside. A set of such neighborhoods for each character of the alphabet of a language is called a neighborhood grammar. A chain is considered to belong to the language defined by the neighborhood grammar if each symbol of this chain is included in it along with some of its neighborhood.

As an example, consider the language A = (a+a, a+a+a, a+a+a+a,...) . This language is the simplest model of the language of arithmetic expressions, where the symbol "a" plays the role of numbers, and the symbol "+" plays the role of operations. Let us compose a neighborhood grammar for this language. Let's set the neighborhood for the symbol "a". The character "a" can occur in A language strings in three syntactic contexts: at the beginning, between two "+" characters, and at the end. To indicate the beginning and end of the chain, we introduce the pseudo-symbol "#". Then the neighborhoods of the symbol "a" will be the following: #a+, +a+, +a# . Usually, to highlight the center of the neighborhood, this symbol in the chain is underlined (after all, there may be other such symbols in the chain that are not the center!), We will not do this here for lack of a simple technical possibility. The "+" character only occurs between two "a" characters, so it is given one neighborhood, the string a+a .

Consider the chain a+a+a and check if it belongs to the language. The first character "a" of the chain enters it along with the neighborhood #a+ . The second character "+" enters the chain along with the neighborhood a+a . A similar occurrence can be checked for the rest of the characters in the string, i.e. this chain belongs to the language, as one would expect. But, for example, the string a+aa does not belong to the language A, since the last and penultimate characters "a" do not have neighborhoods with which they are included in this string.

Not every language can be described by a neighborhood grammar. Consider, for example, language B, whose strings begin either with the character "0" or with the character "1". In the latter case, the characters "a" and "b" can go further in the chain. If the chain starts from zero, then only the characters "a" can go further. It is not difficult to prove that no neighborhood grammar can be invented for this language. The legitimacy of the occurrence of the character "b" in the chain is due to its first character. For any neighborhood grammar that specifies a link between the characters "b" and "1", it will be possible to choose a chain long enough so that any neighborhood of the character "b" does not reach the beginning of the chain. Then it will be possible to substitute the character "0" at the beginning and the chain will belong to the language A, which does not correspond to our intuitive ideas about the syntactic structure of the chains of this language.

On the other hand, it is easy to build state machine, which recognizes this language. This means that the class of languages ​​that are described by neighborhood grammars is narrower than the class of automata languages. The languages ​​defined by neighborhood grammars will be called Schrader's. Thus, in the hierarchy of languages, one can single out the class of Schrader languages, which is a subclass of automata languages.

We can say that Schrader's languages ​​define one simple syntactic relation - "to be near" or the relation of immediate precedence. The far-precedence relation (which obviously exists in language B) cannot be specified by a neighborhood grammar. But, if we visualize the syntactic relations in the chains of the language, then for the diagrams of relations into which such chains turn, we can come up with a neighborhood grammar.

Programming language- an artificial (formal) language designed to write programs for an executor (for example, a computer or a numerically controlled machine). A programming language is defined by its description. A programming language description is a document that specifies the capabilities of an algorithmic language. The description usually contains:

· the alphabet of admissible symbols and service (key) words;

syntactic rules for constructing admissible language constructions from the alphabet;

semantics explaining the meaning and purpose of language constructs.

Programming languages ​​are used to represent the solution of problems in such a form that they can be executed on a computer.

Machine language, which consists of computer processor instructions, is also a programming language. But algorithms written in machine language are difficult to read even for a programmer-developer, in addition, working with such a language requires knowledge of the architecture of a particular computer, therefore, in programming, as a rule, languages ​​of a higher level are used than machine languages. High level language is a programming language, the concepts and structure of which are convenient for human perception and do not depend on the specific computer on which the program will be executed.

In order for a program written in a high-level programming language to be executed on a computer, it must be translated into machine language. The software tool that performs this function is called a translator.

Translator is a program that reads the text of a program written in one language and translates (translates) it into the equivalent text in another language (usually machine language). There are two main types of translators: compilers and interpreters.

Compiler converts the source program text into a set of instructions for a given type of processor (machine code) and then writes it into an executable file (exe file), which can be run as a separate program. In other words, the compiler translates the program from a high-level language into a low-level language.

Interpreter as a result of translation, performs the operations specified in the source program. In this case, the program remains in the source language and cannot be launched for execution without an interpreter.

The division into compiled and interpreted languages ​​is somewhat arbitrary. So, for any traditionally compiled language, such as Pascal, you can write an interpreter, and for any interpreted language, you can create a compiler - for example, BASIC, originally interpreted, can be compiled without any restrictions.

Some languages, such as Java and C#, fall between compiled and interpreted. Namely, the program is not compiled into machine language, but into low-level machine-independent code, bytecode. The bytecode is then executed by the virtual machine. To execute bytecode, interpretation is usually used. This approach, in a sense, allows you to use the advantages of both interpreters and compilers.

Since the creation of the first programmable machines, mankind has come up with more than two and a half thousand programming languages. The number of programming languages ​​is constantly growing, although this process has clearly slowed down. Some languages ​​are used only by big number programmers, others become known to millions of people. Some of them are highly specialized (designed to solve a certain class of problems), and some are universal. Professional programmers sometimes use more than a dozen different languages programming.

Programming languages ​​can be classified according to several criteria: machine-oriented (assemblers) and machine-independent, specialized and universal.

Specialized languages ​​include the ART language ( A automatically P programmed T ools) is the first specialized programming language for machine tools with numerical control. The language was developed by a group of American specialists in 1956–1959. under the guidance of mathematician Douglas T. Ross. COBOL language ( co mmon B usiness– O directed L angle), created in the USA under the leadership of Grace Murray Hopper in 1959, is focused on the processing of economic information. Mathematician Grace Murray Hopper led the COBOL project with the rank of captain second rank, she later became a rear admiral. G.M. Hopper is called COBOL's "mother and grandmother".

(Grace Murray Hopper)

Specialized languages ​​include modern languages web programming Perl and PHP. The languages ​​Rapira, E-language (Russia), SMR (Great Britain), LOGO (USA) can be classified as languages ​​intended for teaching programming.

The most common universal programming languages ​​today are C++, Delphi, Java, Pascal, Visual Basic, Python.

But, considering programming languages ​​as an independent object of study, it is possible to classify them according to the concept of building a language.

Classification of programming languages

Programming languages ​​can be divided into two classes: procedural and non-procedural. procedural (imperative) languages ​​are operator-type languages. The description of the algorithm in this language has the form of a sequence of operators. Characteristic of a procedural language is the presence of an assignment operator (Basic, Pascal, C). A program written in an imperative language is very similar to orders expressed in the imperative mood in natural languages, that is, it is a sequence of commands that the computer must execute. When programming in an imperative style, the programmer must explain to the computer as problem needs to be solved.

Non-procedural (declarative) languages ​​are languages, when using which the program explicitly states what properties the result should have, but does not say how it should be obtained. Non-procedural languages ​​are divided into two groups: functional and logical.

Declarative programming languages ​​are high-level programming languages ​​in which statements are declarations or statements in symbolic logic. A typical example of such languages ​​are logic programming languages ​​(languages ​​based on a system of rules and facts). A characteristic feature of declarative languages ​​is their declarative semantics. The basic concept of declarative semantics is that the meaning of each statement is independent of how that statement is used in the program. Declarative semantics are much simpler than those of imperative languages, which can be seen as an advantage of declarative languages ​​over imperative ones.

Logic languages

In programs in logic programming languages, the corresponding actions are performed only if there is a necessary permissive condition for the derivation of new facts from these facts according to the given logical rules. Logic programming is based on mathematical logic (see “ logical operations. quantifiers”, “Boolean expressions”).

The first logic programming language was Planner, developed by Carl Hewitt at the Laboratory artificial intelligence Massachusetts Institute of Technology in 1969. This language was based on the possibility of automatically deriving (obtaining) a result from data and given rules by enumerating options (the totality of which was called a plan). But most known language logic programming is PROLOG (Prolog), which was created in France at the University of Marseille in 1971 by Alain Colmerauer.

Alain Colmero
(Alain Colmerauer)

A PROLOGUE program contains two components: facts and rules. Facts are the data that the program operates on, and the collection of facts makes up the PROLOG database, which is essentially a relational database. The main operation performed on data is the matching operation, also called the unification or reconciliation operation. Rules consist of a heading and subgoals. The execution of a program written in PROLOG begins with a query and consists in proving the truth of some logical statement within a given set of facts and rules. The algorithm for this proof (the algorithm inference) and defines the principles for executing a program written in PROLOGUE.

Unlike programs written in procedural languages, which prescribe a sequence of steps that a computer must perform to solve a problem, in PROLOG the programmer describes facts, rules, relationships between them, and queries on a problem. For example, let's say we have the following facts about who is whose mother:

mother ("Dasha", "Masha").

mother ("Natasha", "Dasha").

In addition, there is a rule introducing the grandmother relation:

grandma(X,Y):-

Now we can make queries about who is the grandmother of this or that person, or who is the granddaughter (grandson) of a certain woman:

grandmother("Natasha",X).

The answer to this request will be given by the PROLOG system as follows:

The possibilities of using the PROLOG language are very extensive. Among the most famous are applications in symbolic mathematics, planning, computer-aided design, building compilers, databases, processing texts in natural languages. But perhaps the most characteristic application of PROLOG is expert systems.

Today there is a whole class of logical languages; thus, the logical programming languages ​​QA-4, Popler, Conniver and QLISP also originated from the Planner language. The programming languages ​​Mercury, Visual Prolog, Oz, and Fril are descended from Prolog.

Functional Languages

The first functional type language is the LISP language created at the Massachusetts Institute of Technology in 1956–1959. John McCarthy, who in 1956 at the Dartmouth Conference (USA) first proposed the term “artificial intelligence”.

John McCarthy

And although the disputes around this term and the developed scientific direction within its framework still do not subside, researchers are unanimous in the use of functional and logical languages ​​for this area. A significant number of works on artificial intelligence have been implemented on LISP.

After its appearance, LISP was assigned many epithets reflecting its features: function language, symbolic language, list processing language, recursive language. From the point of view of today's classification, LISP is defined as a programming language of a functional type, which is based on the -calculus method (the -calculus method was developed in the 30s of the last century by A. Church as a rigorous mathematical model for computable functions, see. “Theory of Algorithms”).

A program written in a functional language consists of an unordered set of equations that define functions and values ​​that are given as functions of other values. LISP programs and data exist in the form of symbolic expressions, which are stored as list structures. LISP deals with two kinds of objects: atoms and lists. Atoms are symbols used to identify objects, which can be numeric or symbolic (concepts, materials, people, etc.). A list is a sequence of zero or more elements enclosed in parentheses, each of which is either an atom or a list. Three primitive operations are performed on lists: extracting the first element of the list; getting the rest of the list after removing the first element; the union of the first element of the list L and the rest of the list Q.

Program texts in functional programming languages ​​only describe way of solving the problem, but do not prescribe a sequence of actions for solving.

The following are usually considered as the main properties of functional programming languages: brevity and simplicity; strong typing; modularity; functions - calculation objects; purity (no side effects); delayed (lazy) evaluation.

In addition to LISP, functional languages ​​include REFAL (developed in the mid-60s by V.F. Turchin at Lomonosov Moscow State University), Haskell, Clean, ML, OCaml, F#.

Let us give an example of the description of the well-known algorithm quick sort list in Haskell:

qsort (x:xs) = qsort elts_lt_x ++ [x]

Qsort elts_greq_x where

elts_lt_x =

elts_greq_x =

It says here that the empty list is already sorted. And sorting a non-empty list is to split the list into three: a list of elements less than the head of the original list, the head of the original list ([x]), and a list of elements of the tail of the original list greater than or equal to x.

Object Oriented Languages

Object Oriented Languages are languages ​​in which the concepts of procedure and data used in conventional programming systems are replaced by the concept of “object” (see the article “ Object Oriented Programming”). SmallTalk is considered to be the language of object-oriented programming in its pure form, the possibilities of object-oriented programming are also laid down in Java, C ++, Delphi.

The further development of modern programming is connected with the so-called “parallel programming”. To implement this technology, specialized object-oriented languages ​​are being developed. This type of language includes, for example, MC# ( mcsharp) is a high-level object-oriented programming language for the .NET platform that supports the creation of programs that work in a distributed environment with asynchronous calls.

Programming language structure

There are fundamental differences between the existing programming languages ​​in the concept of building languages, this is especially true for earlier languages, but all these languages ​​are called programming languages ​​because they have the same formal structure from the point of view of the internal building system.

Any programming language consists of sentences (operators). Sentences (like words) are defined over some alphabet C. The syntax of the language describes a set of sentences over the alphabet C that externally represent well-formed programs.

Syntax of a language are the rules for obtaining words and sentences of that language. Syntax is schematically described using certain grammatical rules.

Knowledge of the formal language (alphabet + syntax), although sufficient to establish syntactic correctness program, but not enough to understand its purpose and mode of action. The meaning and mode of action of a program in a programming language are specified by specifying semantics.

The semantics of a language are the rules for interpreting the words of a formal language, i.e. establishing the meaning of individual language elements.

To define formal languages, including programming languages, BNF (Backus-Naur forms) and syntax diagrams are used. These are two interchangeable ways of describing.

When describing a programming language in terms of BNF, the following notation is used:

1) <..>- defined word;

2) R - a rule from the syntax for word formation;

3) ::= - BNF rule.

Each R consists of terminal words or tokens language and possibly the following characters:

· [..] - this element is present in the BNF;

· (..) - this occurrence can be used in BNF;

· (..)* - this occurrence can be used in BNF a finite number of times.

Example 1 Let us give an example of a BNF rule that defines an integer.

This rule is read like this: “An integer is the character 0 or a sequence of characters that may begin with the character “–”, followed by a non-zero digit, followed by any finite sequence of digits.”

A special, similar to BNF, form of description of formal languages ​​is syntactic diagrams. Three types of elements are used in syntax diagrams: oval/circle, rectangle, arrows. Terminal words or lexemes are placed in ovals, defined words are placed in rectangles. Graphical representation of the language through syntax diagrams makes the description of the language visual.

Example 2. Describing an integer using a syntax diagram.

According to the Exemplary Program, it is necessary that students present a modern classification of programming languages, as well as orient themselves in the areas of application of each of them. The easiest way to present this topic is after a detailed acquaintance with one of the programming languages ​​has already taken place.

It should be explained why new languages ​​arise and old ones are improved: first of all, this happens when looking for a means for quickly writing complex programs that also did not contain errors. An example is known when the creation of the ADA language (named after the first female programmer Ada Lovelace, daughter of Byron) was initiated in 1974 in the US Department of Defense. The US military has realized that they are wasting a lot of time, effort, and money developing and maintaining embedded computer systems (such as missile guidance systems), and subtle errors in programming languages ​​lead to real disasters.

Declarative languages ​​were very popular in the late 80s and early 90s of the last century, they were called artificial intelligence programming languages ​​for fifth generation computers. However, hopes for their wide distribution have not yet materialized. Perhaps because the existing systems of functional and logic programming do not allow you to create fast programs for meaningful tasks. It is possible that their time has simply not yet come.

When choosing a strategy for teaching the topic “Algorithmization and programming”, it must be taken into account that the task of a general education course is to a large extent the development of a certain style of thinking, the formation of the most general skills, abilities and ideas, rather than the development of certain specific languages ​​and technical programming tools. At the same time, such a course should serve as a basis for subsequent professional study programming in high school or high school high school(as part of vocational training).

Currently, there are two most common approaches to teaching programming:

1) teaching on the basis of a specially developed language of an educational language focused on teaching basic programming skills;

2) the study of one or more programming languages ​​widely used in practice in solving scientific and economic problems (such languages ​​can be called standard).

The first approach is often used when teaching the basics of programming in lower grades high school using special languages, such as Rapier, E-language, LOGO. These languages ​​take into account the possibilities of elementary school students. This approach is good for in-depth study of computer science in grades 5-6.

Regarding the second approach, we can say that most modern implementations of standard languages ​​are loaded with a lot of technical details and are difficult to learn. However, the most suitable secondary school, where the informatics course is taught in grades 8–11, is teaching the theoretical foundations of programming based on a standard language. In this case, it is not necessary to go into the depths of the language. Students who are interested in it can do it themselves. The greatest attention should be paid to the transition from algorithmic structures to their software implementation in a programming language.

It is worth noting here that Pascal was originally created as an educational language, but over time it became widespread as a standard language and developed as an object-oriented language with Delphi's visual programming technology. Pascal or Basic can be taken as the basis of the course in grades 8–9, and as an extended (optional) course in grades 10–11, introduce students to their object-oriented extensions (Delphi and Visual Basic). Each language has its supporters and opponents, and the final choice is up to the teacher.

There are two main approaches to learning a programming language: formal and “Pattern Programming”. The first one is based on a formal (strict) description of programming language constructs ( syntax language and his semantics) in one way or another (with the help of syntactic diagrams, meta-language or formal verbal description, in particular, semantics) and using only studied, and therefore understandable, elements of the language when solving problems. In the second approach, students are first given ready-made programs, they are told what exactly they are doing, and they are asked to write a similar program or change the existing one, without fully explaining a number of “technical” or insignificant, from the point of view of the teacher, details for solving the problem. At the same time, it is said that you will learn the exact meaning of the corresponding constructions later, but for now, do the same. The second approach allows the so-called “quick start”, but creates the danger of getting semi-literate users of the programming environment, i.e. people who use rather complex structures in their practice, but cannot clearly explain why in this or that case it is necessary to use them, and how they work. As a result, sooner or later such “programmers” encounter errors, which they are simply not able to fix - they lack knowledge.

One of the tasks of school informatics is to teach exactly the formal approach, in particular, when applying various definitions. And the formal study of a programming language contributes a lot to this. But even without good examples (samples) when teaching programming to schoolchildren, one cannot do. And the younger the students, the more examples should be given when describing the language (sometimes even replacing a strict definition with them). Another thing is that it is necessary to ensure that, as a result of the discussion of the example, all its details are clear to schoolchildren (it is necessary to explain how and why it works, including relying on the already studied formal material). In this case, strong students will have the opportunity to understand everything thoroughly and will be able to use the knowledge gained in the future, while the rest will acquire specific skills and leave the opportunity to return to formal definitions later if necessary.

Natural programming languages(ESL) define the next step in the development of programming languages, differing from query languages the fact that a user of any level is freed from the need to master any special dictionaries, grammar and syntax - suggestions ELP are very similar to the sentences of ordinary human speech. ELP further alienate the user from the CS and its open source software, significantly increasing the intellectual level of the interface first with computing resources. Currently, PCs successfully use ELP with limited capabilities, such as Clout, Q&A, Savvy Retriever, HAL and others. The main developments of the ELP are associated with the tasks of AI and the intellectualization of the interface in the SUBS. In this direction, direct applied significance (especially in connection with the massive use of PCs) received various kinds of SNP-interfaces with computers. From the ELP of this type, one can note regulated languages (menus, questionnaires, instructions, etc.), which play a large role in the intellectualization of the interface with a computer when using various kinds of software; they play an important role in various systems interviewing,training, expert etc., however, their use is strictly regulated by certain limits, and in the case of transferring systems from regulated ELP for other types of computers often require significant modifications. Therefore, for more flexible and natural communication between the user and the computer, it is more adequate to natural language.

Usage problem natural language to organize the interface with intellectual VS at the content level with interesting illustrative examples is well described in the specialized literature. However, one important remark should be made on this issue. It is often taken for granted that natural language is the best way to organize a user interface with a computer. This assumption is even taken as the basis for the 5th generation computer project. However, it does not seem to us so obvious.

In a number of cases natural language is less expressive graphic, carefully crafted formal domain language is more expressive natural language (also having quite a few shortcomings). Moreover, many subject areas (mathematics, physics, chemistry, biology, etc.) have their own linguisticslang, in some cases significantly different from ordinary natural language. Therefore, developed language interface may be symbiosis natural and formal languages ​​or be hierarchy languages: natural language - formal (structured) computer language. In any case, this problem is still very far from its complete solution.

Lecture No. 34 application software

Lecture plan.

1. Applied computer software.

2. Classes of application packages.

3. Basic application tools.

4. Qualitative characteristics of the software.

34.1. Applied computer software

In the previous section, at the most general level, the structure of PES was discussed, which is based on PSPs of various types, purposes and organizations. In connection with the intensive intrusion into human activity of the PC and the mass nature of the use, the share of PPP in computer software is rapidly growing. Given the importance of this component, which provides a high-level interface for a non-professional user with computer computing resources, we will consider it in more detail, based on three levels:

(1) the principle of organization of the PPP;

(2) user training requirements;

(3) the main modern PPP groups.

One of characteristic features modern RFP is to use the principle synthesis work programs from subroutines based on meaningful descriptions tasks in a problem-oriented language close to the concepts and terms of the user's problem area. With this approach, the user through a special package formation language(JFP) informative describes individual task or class of tasks (requiring a decision), forming generation program a specific RFP from the toolbox fixed or expandable program environments(rice. ZZA). Based on this program, an RFP is generated for a specific application with its own input language(VY) communication with the user. After creating a PPP, the user works with it in the process of solving their problems. As a rule, the described principle of organization is used for problem-oriented PPP, when the range of tasks they solve is clearly defined and the tasks are related by some common characteristics, for example, numerical methods, statistical analysis, modeling in a specific subject area, etc. The range of PPP of such an organization is very wide - from library organization of subprograms of a certain direction (for example, statistical analysis) to complex software environment (Fig. 33a), requiring a special JFP for a formal description of the subject area, which should be oriented (generated) PPP. When creating a specific package, they are used as a means of its own software environment and reprogrammable.

Creating a PPP is a rather long and laborious process that requires the use of special tools. However, in the general case, such systems turn out to be very complex, and the packages they create are quite far from the required efficiency. Therefore, one of the ways to eliminate these shortcomings is to create specialized instrumental systems focused on families problem-oriented IFR with homogeneous input languages ​​and the same functioning principles. Of the domestic funds of this type, it can be noted meta system SATURN and PACKAGE. Yes, in PACKAGE like other similar systems, the above two phases are distinguished: description desired PPP on a special NFP (subsystem Constructor) and generation PPP with its input language (subsystem Preprocessor); at the same time, the manufacturability of programming is ensured at the main stages generation package: (1) description of the class of tasks solved by the package and methods for their solution; (2) creation of the PPP input language; (3) programming and debugging the required software modules.

With this technology, the development of a specific PPP begins with a description of the problems to be solved in terms of subject areas, i.e. the programming of the functional properties of the desired object is carried out - PPP by means of a special metalanguage, including input the language in which the user will subsequently have to communicate with the package in question. The result of the execution of the translated JFP program is the desired PPP with the given input language. Thus, this technology generally assumes the presence of two levels of users - systemic, generating PPP with a given subject area, and problematic, using the created PPP through its input language close to the concepts of the subject area or to natural language. Naturally, in the case of a fairly simple software environment, a narrowly oriented class of problems to be solved, and a simple JFP function systemic and problematic user can combine the same person.

Currently computer experimentation(CE) is becoming one of the main research tools for major scientific, engineering, technical and public problems: in astronautics, nuclear physics and energy, forecasting, etc., complexity which does not allow, on the one hand, to study them strictly enough analytically, and on the other hand, to investigate by very expensive experimental methods. The FE method involves the use by problematic users of sets of various application software, which, due to the experimental nature of the work, are largely subject to various kinds of changes. The considered principle of PPP organization has quite flexible adaptive capacity to automate this type of work, well responding both to the tasks of modifying and expanding the original software environment of the package. To increase the intellectual level of the interface with the package, especially those operated on a PC by a mass user, an important role is played by its graphic component, which is also determined in the developed metasystems design and generation PPP. In addition, in order to increase logical interface layer of already existing popular APIs are created graphic Metasystems, significantly expanding GUI packages, making it friendlier.

In contrast to the considered organization of PPP, which ensures their flexibility and adaptability to the subject area and puts forward a number of requirements for the professional level of the user, for the mass user, as a rule, tough an organization preventing him from modifying the package. Such an organization has two main performances: (1) high logical level package input language(VYP), focused on the user and the subject area, and internal package language, which allows creating modules in its environment that provide package extension functions, as well as creating documents for specific applications of the package; (2) the interface with the package is provided only at the level of the domain-specific VLP. AT both cases the practice of creating a WLL for a package uses two main approaches: (1) creating a language based on an already existing HLL (which, as a rule, is and implementation language package) and (2) development original input language. At first approach greatly simplifies the implementation input language, while for a non-professional user there are additional difficulties in mastering the package. Second approach requires in some cases significantly higher development costs. input language, however, allows you to make it easy to learn and use (menu language, elements of natural professional language, query language, dialog graphics language, etc.).

Wherein range The user orientation of VLP lies in a very wide range - from a novice user to a professional in a certain subject area. For example, gaming packages have high concept graphic interface and do not require special development; packages text editors also have a developed language menu systems, a sufficiently high conceptual level (for example, a package MS Word); domain-specific packages (for example, MathCAD, Reduce. Mathematica secured input a language oriented to a user familiar with the mathematical language. Finally, interior the language of the package is focused mainly on programming functions not directly supported by the package, or programming documents for specific applications. Often as internal language used language implementation package or its modifications (for example, packages reduce. Mathematica and etc.); however, in some cases interior language is oriented towards subject area package has input language based on a simple and friendly menu system and interior C-like SALT language , allowing you to easily and quickly create and execute SLT-documents (programs, modules for specific applications of the package) in the environment of the package). Complexity internal languages ​​of the PPP is different, it requires a certain programming skill to master them; however, they allow the creation of rich document libraries that, when executed in a package environment, allow significantly expand its functions and scope of applications.

Finally, a rigid organization in combination with a subject-oriented VLP is focused on relatively small packages or packages of a special orientation, but of mass application. As a rule, languages ​​such as menu, dialog graphics, query and others, aimed at the non-professional user. An example of such organizations simple text editor packages, special packages, etc. can serve. At the same time, the more developed of them have macro tools that allow you to draw up at the level macros most used sequences package operations (eg. ChiWriter, Ms Word, Word Perfect versus. etc.).

According to their organization, packages allow different levels and types extensions co user side: from the possibility complete generating a package for specific conditions of use (taking into account the possibility of expanding its software environment) to the absence of any possibility of expanding the package. However, in most cases, modern PPPs allow extensions, of which for the problem user the most natural way is to create libraries(documents, programs, modules, macros) on domestic package language, decisive tasks in some subject area and executing in the environment of the package itself. A range of packages allow extension its capabilities by creating both external(relative to the main modules of the package), and embedded functions. However, for the purposes compatibility packages, the most appropriate is to expand the package due to its external functions and tools, which does not allow the user to modify (with certain reservations) basic part of a package supplied and maintained by the developer.

Most modern TPNs require surgery before use installations, consisting in customizing the package for specific conditions exploitation (hardware configuration, problem solving mode, etc.). As a rule, the installation is carried out once and is performed either internal package means (Ms Word, Quattro etc.), or through special utilities (Sprint, Mathematica and etc.). For simple packages initialization, as a rule, it is performed automatically every time they are loaded by means of the operating system (Framework, AutoSketch and etc.).

Documentation, supplied with the package, should include recommendations for its installation for specific conditions of use. Having considered three the basic principles of organizing PPP, we will briefly discuss functional filling packages, which file level in in the general case can be represented as: (1) modules providing the basic functions of the package; (2) configuration files; (3) general purpose utilities and extension functions of the package; (4) specialized database; (5) a document library for executing them in the package environment; (6) files containing help, license information on the package, as well as documentation. As a rule, in all modern PPP, the marked structuring them file systems.

A number of notable packages (Expert Choice, Mathematica, MathCAD, Ms excel etc.) are also supplied at the level of illustrative and / or training versions, which are functionally limited relative to the main package, but allow you to illustrate the package in action, as well as teach the basics of working in its environment, which in a number of cases allows you to make a more informed choice of this funds for subsequent commercial use.

Basic concepts

Algorithm - this is a prescription (an order or a system of orders) that determines the process of converting the initial data into the desired result k, which has the following properties:

• certainty, i.e., accuracy and comprehensibility for executives; due to this property, the process of executing the algorithm is mechanical;
• effectiveness, i.e., the ability to lead to the desired result after a finite number of fairly simple steps;
• mass character, i.e., suitability for solving any problem from a certain class of problems.

From the definition of the algorithm, it can be seen that the process of its implementation must be discrete, consisting of separate steps, algorithmic acts. The requirement for the simplicity of these steps is due to the fact that, assuming an unlimited complexity of the steps, we will deprive the concept of an algorithm of any certainty. The property of an algorithm to lead to a solution in a finite number of steps is called potential feasibility.

Natural languages ​​are of little use for formulating definite and precise prescriptions in them. The algorithm, therefore, must be a prescription in a formal language.

Each computer is designed to solve mainly problems of a certain class. In this regard, it is required that the computer provides the ability to perform in the required combinations of a certain set of operations, taken as elementary.

Elementary machine operations are the input of information into a cell of random access memory from some other storage device, the issuance of information from the cell, as well as any operation that: is implemented in hardware; has initial data that are the results of elementary machine operations and are fixed in one or more cells; gives a result that is fixed in one separate cell and is available, but not obligatory for use as the initial data of any elementary operation of the machine; cannot be considered as a complex of simpler machine operations that satisfy the three previous conditions.

Operations system is the totality of all machine operations provided in the computer.

Team is an elementary prescription that provides for the performance of a certain group of operations.

Main Operations Computers are arithmetic, logical, transfers, transitions, when the machine makes a transition from executing one command to executing another, fetching commands from RAM and stopping the machine (“stop”). The main operations on literal information are: determining the length of a word; transfer of a word from one place of RAM to another; highlighting a certain part of a given word; inclusion of spaces between words; dividing a string of words into smaller strings; comparison of two words. Usually these operations are called editing.

Programming

Computers are usually used either to solve individual problems (belonging to a certain class), or to solve a complex of interrelated problems of various classes.

When solving a certain task (class of tasks) on a computer, the work is divided into the following stages:

mathematical formulation of the problem;

development of a methodology for its solution;

development of an algorithm for solving it and writing it in some programming language;

programming;

debugging the program on the machine;

preparation of initial data, solution of the problem on a computer.

The described complex of works is called problem programming.

When developing a system of programs for solving a complex of interrelated tasks, during the development of each program, the described sequence of work is preserved. In addition, there are a number of additional stages of work associated with the need to ensure the unity of the system. A set of works to create a system of programs for solving interrelated tasks is called system programming.

Mathematical formulation of the problem. This work consists in determining the composition and nature of the initial data for solving the problem, in determining the initial results, writing the conditions of the problem using mathematical notation. The mathematical apparatus used in the mathematical formulation of the problem depends on which class the problem belongs to.

Development of a problem solving technique. The solution technique is considered developed when the dependences of all the desired results on the initial ones are established and such methods for obtaining the desired results that can be implemented on a computer are indicated. If the unsuitability of the chosen methods is found in the process of solving the problem on a computer, it is necessary to return to the method development stage.

Development of an algorithm for solving the problem. An algorithm for solving the problem is developed on the basis of the methodology for solving it. The algorithm is developed in the language of mathematical descriptions, and then written in an algorithmic language from among the so-called programming languages. The development of an algorithm for solving the problem should be carried out taking into account the features of the computer.

When using a computer to solve a problem, it is necessary to take into account the following features:

• a large but limited number of digits in number images;
• greater speed of performing operations on numbers stored in RAM;
• relatively low speed of input of initial data and output of results;
• relatively low speed of exchange of numbers between RAM and external storage devices;
• a relatively small capacity of RAM with a very large capacity of external storage devices;
• the possibility of random failures of the machine and the consequent need to monitor its operation.

Programming. Programming is in recording the developed algorithm in a programming language (for example, in the so-called ASSEMBLY language or in ALGOL, FORTRAN, COBOL, PL / I), performed manually, and subsequent translation into a machine algorithmic language.

broadcast is the process of equivalent transformation of an algorithm given in a programming language into an algorithm in a machine language. This process is carried out using a special program called a translator.

Debugging the program on the machine. Debugging a program on a machine aims to eliminate errors in the program and includes: program control; search and determination of the content (diagnostics) of errors; correction of found errors.

Preparation of initial data. Solving a problem on a computer. The initial data of the task to be entered into the computer must be previously transferred from forms or documents to punched tapes or punched cards. This process is carried out on special perforating devices equipped with a keyboard. AT In the perforation process, errors are possible both as a result of random failures of perforating devices, and as a result of errors in the work of perforating operators. All errors introduced into the information during perforation and entry must be corrected.

As a rule, either 80-column PCs or a paper PL are used to enter information into a computer. Larger machines have both. A punched card contains 12 lines, and therefore 12 punches are possible in each column; in the transverse direction of the punched tape, 5, 6, 7 and 8 punching positions are allowed. Thus, it is theoretically possible to use an alphabet from 2 5 =32 to 2 12 =4096 characters, but in practice more than 3 punches are rarely found in a punched card column, so that, as a rule, the alphabet used contains from 40 to 80 characters. Among the computer equipment there is an independent device for reproducing on paper information contained on punched cards and punched tape in a form convenient for human reading. As a result, we get what is usually called listing or printout.

After entering the programs and initial data into the computer, the problem is solved automatically.

Computer software

Mathematical software (MO) of the computer can be defined as a collection of programs, each of which can be practically used by the user alone or in conjunction with some other programs to solve problems, or to perform some work related to programming, or to create a certain mode of computer operation.

AT MO computer system may include the following groups of programs:

operating system programs;

software system;

applications to programs;

software support software system;

a system of test programs designed to monitor the health of the computer.

Operating system contains programs that determine the mode of operation of the computer and expand its operational capabilities. The operating system includes a number of programs, of which the main ones are the following:

dispatcher- a program that provides a certain mode of operation of the computer;

supervisor, or monitor,- a program that provides work given to the machine by a human operator within the framework of the mode established for it;

a number of utility programs, such as programs for entering initial data, programs for editing and issuing results, a loader - a program for entering so-called working programs into RAM, i.e. programs for solving problems, a librarian - a program for entering subroutines for performing macro operations and themselves subroutines of macro operations, a program for communication between the operating system and the human operator.

For the operation of the operating system, the capabilities that modern machines have (and that the machines of the first generation did not have) are of great importance: the presence of an interrupt system, memory protection, instruction protection, and interrupt masking.

The essence of the dispatcher lies in the fact that he refers any interruption in the operation of the machine either to the number of tactical ones and in this case immediately transfers control and information about the interruption to the supervisor, or to the number of strategic ones. In the latter case, it enables the interrupt itself. The text corresponding to this reaction will be called a conclusion.

The supervisor plans, at the request of the human operator, the order of execution of programs and distributes the available computer equipment between them, organizes their queue and maintains order in this queue. The main tasks facing the supervisor are: managing the progress of the computer; maintaining contact with the human operator.

There are various modes of operation of the computer, the provision of which is one of the main purposes of the dispatcher.

A number of modes are associated with solving problems presented in the form of the so-called work package. At the same time, the entire package is supplied with information about the tasks included in it and their advantages over each other (priority system).

The execution of the work package is carried out under the control of the supervisor. In this case, single-program, two-program or multi-program operation of the machine can be carried out. The effectiveness of its use largely depends on how the work is combined into a package. A packet is considered good if the CPU (arithmetic unit and control unit) is not idle. The described modes are called batch modes. Modern computers allow the simultaneous execution of up to 16 jobs.

Time-sharing mode characterized by the fact that a large number of remote input-output devices, called terminals, are simultaneously connected to the computer. While in batch operation, users are not allowed to the control panel, in time-sharing mode, each of them communicates with the machine without the participation of the operator. The dispatcher ensures that small chunks of time are consistently granted to all queued users. Over a period of time measured in a few seconds, the machine serves each user little by little. The time sharing mode is convenient in cases where the execution of machine work should proceed in the form of a dialogue between the computer and the user. Ego takes place when debugging computer programs, when solving information problems such as question-answer.

Software system contains a number of translator programs for translating algorithms specified in various input programming languages ​​into machine language. Typically, a programming tool system contains translators from three levels of algorithmic languages.

The process of translating an algorithm and the process of its execution by a machine can be combined in one of two ways.

The first method, called compilation, is that the process of executing the algorithm by the machine is carried out after the process of its translation is completely completed. The name "compilation" arose due to the fact that originally meant the process of translation, based on the combination of pre-prepared parts (subroutines) corresponding to certain parts of the translated algorithm into a single whole. Subsequently, this name was extended to the case of "dynamic" translation, not associated with the use of pre-prepared texts.

The second way of combining the translation process and the algorithm execution process is called interpretation. This method consists in the fact that individual parts of the algorithm are performed immediately after the translation, after which the same procedure is carried out on other parts of the algorithm, etc.

Compilation is characterized by the fact that the compiler program that implements it during the execution of the algorithm is no longer needed and therefore is not located in the main memory of the computer. The application of the interpretation method requires the presence of an interpreter program in the main memory of the computer during the solution of the problem.

Each of the methods has its own advantages, but the interpretation method is more flexible. In addition, it simplifies the task of allocating memory, although it requires a lot of extra memory to store the interpreting program itself.

The software systems of the latest computers are often based on the so-called principle of modularity. modules are called "pieces" of algorithms specified in the language of the executive system or in the input programming language, for which the following conditions are met:

"Pieces" of algorithms specified in the language of the executive system must be provided with additional information sufficient to ensure that, with their appropriate processing, it is possible to assemble a program specified in the language of the executive system from them;

"Pieces" of algorithms specified in the input programming languages ​​must be provided with additional information sufficient to enable them to be converted into modules specified in the algorithmic language of the executive system with appropriate processing.

Modularity principle is that programs in the language of the executive system are assembled from modules. Modules in the language of the executive system can be accumulated in the library. The modular principle allows the use of modules compiled in various algorithmic languages ​​when assembling a program. The ability to accumulate modules and then reuse them saves programmers' work.

All software programs must be members of some library. Library of standard programs is a collection of pre-compiled programs in which each program is provided with additional information that identifies it. Data on all programs should be summarized in a common table called directory. The directory should allow you to find a subroutine by its name and by its purpose.

The library collects usually specially compiled and specially designed programs.

The listed programming tools should be used to solve various tasks (problems). At the same time, it is believed that the programs of individual tasks (problems) may not be very “good”, but the total expenditure of funds for programming and solving a problem on a computer is usually less than when compiling more “good” programs.

Mathematical support of ACS

Mathematical support (MO) ACS- this is a system of methods, techniques and tools that allow you to effectively develop programs for solving specific problems of automated control systems on a computer, control the operation of a computer in the process of solving these problems, and control the correct operation of a computer.

The main provisions that must be followed when creating a MO ACS are the following:

• compatibility and basing of the developed MO ACS on the existing MO computer;
• the focus of the chosen means of the MD on the tasks of the automated control system;
• a sufficient variety of programming automation tools;
• the ability to effectively make changes to work programs;
• the possibility of an unambiguous and exhaustive description of algorithms;
• the possibility of optimizing the work of programs of private use;
• modularity of building programs.

MO ACS serves to provide the user with a wide range of services on programming technology. It can be divided into two parts: drawing up control programs and drawing up processing programs.

Control programs carry out the initial loading of the RAM of the machines and the control of the work of the automated control system, including the processing of interrupts, the distribution of the work of channels, the loading of programs from the library into the RAM. Control programs provide multi-program work, communicate with the operator.

Processing programs include a programming automation system and service programs.

Functions of the programming automation system the following: writing programs in input programming languages; translation of programs into the internal language of the computer; association (assembly) of the necessary configurations (segments) from standard routines; debugging programs at the level of input languages; correction of programs at the level of input languages.

The main tasks of service programs are as follows: writing programs to the library; exclusion of programs from the library; rewriting programs from one magnetic media to another, printing and outputting programs to punched media; calling the necessary programs in the process of working into RAM and setting it up at its location.

The main components of MO ACS are a system dispatcher program and a library of standard subroutines and standard programs designed to process production and economic information.

System dispatcher ensures the functioning of the automated control system in the mode determined by the production and economic or administrative activities.

Library of standard routines, available in MO computers is a transitional step towards the development of a system library focused on information processing processes in automated control systems. System Library must contain:

programs for input and conversion into machine form of documents and other written sources of initial data;

programs for organizing computer arrays, characterized by both large volumes and the complexity of their structure, for efficient search and extraction of the required data from arrays;

programs for converting data into the most human-friendly form (in the form of graphs, charts, images) and outputting them to external devices.

Programming languages

programming language called sign systems used to describe the processes of solving problems on a computer. By their nature, programming languages ​​are divided into three groups:

1. formal algorithmic languages;
2. formal non-algorithmic programming languages;
3. not quite formalized sign systems used in programming.

Formal programming languages. This group of languages ​​includes: algorithmic languages ​​of machines and operating systems; machine-oriented algorithmic languages; problem-oriented algorithmic languages; universal machine-independent algorithmic languages.

Operating system languages Algorithmic languages ​​are called algorithmic languages ​​perceived by complexes formed from a computer and a dispatcher program developed for them (sometimes also called a supervisor).

Compiling programs directly by hand in the language of the machine or operating system is not currently used, since it requires the programmer to remember a large number of details, without which it is impossible to build a program from commands.

Machine-Oriented Algorithmic Languages contain expressive means that allow you to indicate in the record of the algorithm by what technical means certain parts of it should be performed and how memory devices should be used in this case. Machine-oriented programming languages ​​include autocodes and some languages ​​that are close in their capabilities to universal algorithmic languages, such as ALMO.

Domain-Driven Algorithmic Languages these are languages ​​that are specially designed to describe the processes of solving problems of a certain narrow class, for example, problems of linear algebra, statistics, data processing problems, etc. In particular, COBOL belongs to problem-oriented languages.

Universal Machine-Independent Algorithmic Languages suitable for creating algorithms for solving problems of very wide classes. These languages ​​include the already mentioned ALGOL, FORTRAN, PL/1.

Among the universal machine-independent algorithmic languages, the exception is YLS. The purpose of this language is not limited to being a programming language. YALS is used as the first stage of describing algorithms when programming in machine language or in ASSEMBLY language (operator programming method; the algorithm written on YALS is manually translated into machine language or ASSEMBLY language).

The table below provides a comparison of formal programming languages.

Not quite formalized sign systems. These languages ​​are typically used in manual programming or in the preliminary manual step of automated programming. An example of this is a program flowchart. The block diagram of the program is an enlarged description of the program, in which its individual parts are depicted in the form of "blocks" (rectangles, rhombuses, circles, etc.), within which the content of these parts is stated in a natural language (for example, in Russian). Communication between blocks (parts of the program) is depicted with the help of lines denoting the transfer of control. The lines may be labeled to indicate the conditions under which control transfer occurs. Block diagrams are similar to algorithms written in the LLS using generalized operators, but differ from them in that the meaning of the blocks is stated in a natural, informal language, while in the LLS the generalized operators are decoded in an exact formal language.

Currently, more than 2000 different algorithmic languages ​​and more than 700 areas of their application are known for solving the corresponding problems on a computer.

There are programming languages ​​of the following levels:

zero or lower level language - machine code;

the language of the first level is the mnemocode, or the language of symbolic coding;

second level language - autocode (macrocode);

languages ​​of the third level (higher) - problem-oriented languages.

As input languages, depending on the type of tasks of the automated control system, it is advisable to use domain-specific languages various types

Comparative data of formal algorithmic programming languages

Class of algorithmic programming languages	Accounting for computer features	Characteristics of the task class	Programming way	Conditional assessment of program quality
Machine languages
Machine-oriented languages	Partial	Determined by the features of the computer	automated	Satisfactory
Domain-specific languages	Minor		automated	Satisfactory
Universal Machine Independent Languages	None or very little	Very extensive	automated	low

(for example, for analysis - ALGOL, FORTRAN, etc., for economic problems - ALGEK, etc., for information problems - COBOL, SYNTOL, etc.).

Consider some of the algorithmic programming languages.

ALGOL-60. The name of the language comes from English words Algorithmic Language. It was developed by a group of scientists from various countries in 1960 and has become widespread. The reasons for success are its proximity to the usual mathematical language, the convenience of describing a wide class of problems, universality and complete independence from a particular computer, strict formalization of the language from the alphabet to the most complex structures.

ALGOL-60 is not only a universal programming language, but also an international language for describing algorithms.

The basis for writing algorithms in the ALGOL-60 language is a sequence of operators separated by the symbol ";". This sequence of statements, which are single actions in the language, is joined by a sequence of descriptions that give the translator information about the necessary properties used in the statements. Descriptions, for example, give information about the classes of numbers used as variable values, about the dimensions of arrays of numbers, etc. Such a combination of descriptions and operators in this language is called a block.

A program in the ALGOL-60 language is a block, or a compound statement that does not contain another statement inside and does not use another statement that is not contained in it.

Computing centers in which ALGOL programming is carried out should accumulate experience not in the form of complete ALGOL programs, but in the form of procedure descriptions. This is due to the fact that it is practically impossible to include ready-made ALGOL programs in new programs, while the descriptions of procedures are specially designed for this.

In the USSR, ALGOL-60 became widespread in the form of some of its variants.

FORTRAN. The word FORTRAN is formed from two English words (Formula Translator). One of the most important features of the FORTRAN language is that it is relatively free from the specifics of a particular computer. FORTRAN is a machine independent programming language.

The most extensive mathematical software libraries in this language have been accumulated, including both standard (frequently used) programs and many special programs used to solve specific problems.

The widespread introduction of FORTRAN into programming practice is due to its qualities, of which it should be noted, firstly, its simplicity in comparison with other algorithmic languages ​​(for example, ALGOL); secondly, due to the absence of overly complex structures, translated programs are more efficient than programs written in other languages; at the same time, FORTRAN is suitable for programming most computational algorithms;

thirdly, FORTRAN has very powerful means for connecting a person with a machine: the information issued by a computer is presented in a form familiar to scientists and engineers. And finally, fourthly, FORTRAN is well suited for effective use external computer devices.

The algorithm for solving the problem, written using FORTRAN, consists of a sequence of operators. These operators can be of several different types. Taken together, the operators that determine the algorithm for solving the problem make up the original program. After the source program is written and punched on punched cards, it is converted into a working program using a FORTRAN translator.

The first operator is the header operator, which looks like || PROGRAMa ||, where a is the name of the program, and the last one is the end operator (operator || END ||) and a set of subroutines. The main program and each subroutine localize the labels of statements, as well as the names of variables, arrays and other values, thereby allowing the use of the same labels and identifiers in different subroutines and in the main program. Communication between the main program and subprograms is carried out using the corresponding call operators.

When compiling programs in FORTRAN, it is recommended to adhere to the following order of operators: 1) operator-heading of the main program (subroutine); 2) file description operator; 3) implicit type assignment operator; 4) an explicit operator for specifying a type, an operator for specifying dimensions, an operator for specifying common areas; 5) equivalence specification operator; 6) operator-function, operator-procedure; 7) format setting operator, executed operators (unconditional, conditional, input, output); 8) end operator.

COBOL. The name of the language comes from the English words Common Business Orientated Language. COBOL is a problem-oriented algorithmic language designed to describe the processes of problem solving and data processing. At present, COBOL is the only widely used high-level programming language for economic problems. Its wide popularity is explained by the fact that COBOL is quite close to the natural language in which economic problems are usually formulated and solved.

The distinctive features of the COBOL language are as follows:

language is, in a certain sense, a subset in English; text written in COBOL can be understood without prior preparation;

the language describes data well with a structure typical of business papers; these data may relate to personal affairs, goods, finances (combined data is also allowed);

an attempt is made in the language to solve the problem of full compatibility, i.e., independence from the specifics of specific computers.

A COBOL program consists of four parts called sections. These sections have the following names: identification section, equipment section, data section, and procedures section. The procedure section contains the actual program, but it is meaningless (or at best incompletely defined) if the structure of the data to be processed, as defined in the third section, is unknown. The hardware section is further divided into a configuration section and an I/O section, while the data section is divided into an array section, a working memory section, and a constants section. At the beginning of a section (section) is the name of the section (section), followed by a dot; the name with a dot takes a separate line. The content of a section or section consists of sentences grouped into named paragraphs.

In COBOL, it is much easier to make small changes to the program that are necessary when processing commercial information.

In COBOL, the basic unit of I/O is the data file. Each file is made up of records. The same file is often used in different programs depending on the nature of the tasks being solved. The description of the files is very strict and cannot be modified.

The developers took into account the possibility of using one machine for broadcasting programs, and another machine for solving the problem according to the compiled program. In addition, the same COBOL program can be translated into the languages ​​of different computers with different sets of equipment.

SOL. Digital modeling as an effective research method is gaining more and more popularity among specialists involved in the analysis and design of complex systems.

Very often, a systems specialist has difficulty in writing a program that simulates the operation of the system he is studying. The reason for this may be the extreme complexity of systems that are almost impossible to describe mathematically. Problems of this type abound, in particular, in the practice of creating instrumentation and control systems. To facilitate the compilation of programs, automatic programming languages ​​(specialized modeling languages) are currently used, which allow, with the least time spent on preparing and implementing tasks on a computer, to build and investigate programs that simulate the operation of the system under study.

At the same time, the elements of a specialized language are, as a rule, quite universal and can be . applied to a wide class of simulated phenomena. In addition, specialized modeling languages, in comparison with universal ones, significantly simplify the programming of computational and logical operations that characterize the system being modeled. At the same time, the connection between the task manager and the programmer is also simplified. This is achieved through the following features of specialized modeling languages:

• the ability to fix the structure of the machine's memory allocation between variables and parameters. This distribution is more fine-grained and refined than that achieved with most universal languages;
• the presence of a set of instructions that simplify the change of states of the simulated system. In most cases, this is done by a standard control or temporary subroutine that controls the sequence in which the subroutines are implemented;
• the presence of a set of instructions that determine the need for the implementation of a particular subroutine at a certain time;
• the presence of commands for performing standard or frequently occurring operations related to random numbers and probability distributions;
• the presence of commands that simplify the receipt and registration of statistical indicators during the run of the modeling program.

Consider some specialized algorithmic modeling languages.

The GPSS universal modeling language is the most widely used, simple and intuitive. It does not require knowledge of programming and machine operations. The simulator is presented in the form of a block diagram, which is especially attractive to non-programmers.

The algorithmic language SIMSCRIPT is considered to be the most powerful modeling language at present. Due to a number of its unique features, it is applicable to the widest class of tasks. However, this language is relatively complex, and diagnostic tools for debugging programs are limited. In addition, a potential user of this language must know FORTRAN and have programming experience.

The attention of specialists involved in solving modeling problems is attracted by specialized languages ​​developed for this purpose on the basis of ALGOL. Among such automatic programming languages, the most advanced are SIMULA and SOL (SOL).

An example of one of the most successful specialized algorithmic languages ​​for modeling discretely changing systems is the Simulation Orientated Language (SOL).

The SOL language is built on the basis of the universal programming language ALGOL, has the same structure and uses its main elements. To describe a wide class of processes with discrete events, SOL represents a universal system of concepts, and therefore it is in many respects very similar to domain-oriented automatic programming languages ​​such as ALGOL or FORTRAN. However, the SOL language has the main features that distinguish it from these languages: SOL provides a mechanism for modeling asynchronous parallel processes, convenient notation for random elements within arithmetic expressions, automatic tools for collecting statistical data on the components of the simulated system. On the other hand, many features of domain-specific universal languages ​​are not used in SOL, not because they are incompatible with it, but rather because they add great complexity to its design without expanding its capabilities. The principles underlying the construction of the language and writing simulation programs on it allow building models of complex systems in an easy-to-read form.

PL/I. The name of the language comes from the English words Programming Language/One.

The PL/I language appeared after the creation of a number of highly advanced languages, and, of course, these predecessor languages ​​had a significant impact on its structure. So, it retains the block structure of the program from ALGOL, the possibility of dynamic memory allocation, there is an apparatus for calling procedures, a method for setting formats used in FORTRAN, etc. But there are also many new features. The language is convenient for modeling, solving logic problems, researching logic circuits, solving problems in real time, developing software systems. It is possible to use different types of data (binary, decimal, symbolic, complex numbers, matrices, etc.), but it is very difficult to organize this data into arrays, tables, texts, questionnaires, file cabinets, etc. There is a large set of standard functions and procedures. In the PL/I language, a successful system of operations has been developed that controls all the processes of input, output and exchange of information between main and storage devices. All these features give the impression of a strong congestion of the language. The disadvantages should also be kept in mind: the description of the language is unsatisfactory, it is not formalized.

PL/I is a multi-purpose programming language designed not only for economic and scientific-technical programming, but also for programming real-time jobs and for creating programming systems.

One of the main goals in the development of the language was to achieve modularity, i.e., the ability to use already translated programs in the main program as separate modules without retranslation. The need to ensure the greatest possible simplicity and convenience of writing programs was taken into account. At the same time, the need to draw up general and detailed logical schemes of programs still remains, but with appropriate experience in programming in the PL / I language, one can avoid a lot and tedious work associated with writing a program in machine language.

In the PL/I language, each variable descriptor, each specification-complement, and each specification is given an "interpretation (principle) of default". This means that wherever the language provides several features, and the programmer has not specified any, the compiler uses the "default interpretation", that is, some of the features provided in the language for this case are implied. As implied for each construct, the possibilities in the language are those that are most likely to be required by the programmer.

PL/I programs are written in free form; the programmer himself can develop the forms of writing programs he needs. At the same time, access to all means of the computer system is provided.

The statements of a program written in the PL/I language are combined into "blocks". Blocks perform important functions: they define the scope of variables and other names, so that the same name in different blocks can be used for different purposes; they allow you to allocate memory cells for variables only during the execution of a given block and release them for use for other purposes after the block terminates.

RPG. The RPG language is designed to automate the programming of tasks and the processing of economic information. The content of these tasks is mainly exhausted following processes: maintaining files (i.e. organizing, storing, adjusting and updating), sorting files, compiling and printing various accounting documents, such as lists, statements, tables, summaries, reports, etc. As a rule, calculations occupy a small part of the total volume of problem solving. When solving such problems, it is convenient to use the RPG, especially at the stage of compiling and issuing reports. In this case, it is assumed that the input files that are used for reporting are created and sorted using other means.

RPG allows you to perform some calculations (usually simple and standard) on the input data, generate a report and print it out. Input data can be entered from card input devices, magnetic tapes, or direct access memory devices. In addition to creating a report, RPG allows you to correct and update input files, as well as create new files. The RPG has tools that allow you to perform operations with tables (for example, searching for the required element of the table and displaying the table), as well as tools for organizing the connection of the RPG program with programs written in other languages ​​and used to solve the same problem.

A feature of the language is that the programmer should not describe the sequence of operations for solving the problem (problem algorithm), but should only describe on special forms the input data used to create the report, the calculations performed on this data, and the format of the report.

Based on this information, the RPG translator generates a working program, and then the created program processes the input files and prints the required report.

Preparing a report using RPG consists of the following main steps: defining task data and how to process them; compiling the original program; perforations of the original program; obtaining a work program; execution of the work program.

Before writing the program of the task, it is required to perform some analysis of it. It is necessary to define the input data, the format and type of input data records, the record fields used and their position, the way the data is processed, the number and type of totals to be calculated, the format of the printed report and other output data.

After the input and output data of the task and the method of their processing are established, it is necessary to describe these data on the corresponding RPG forms. There are several types of RPG forms, each of which is designed to record certain information. The input data description forms list all input files, describe the structure and distinguishing features of all types of records in each of the files, and the location of the fields used in the records. The calculation form indicates what processing of the input data needs to be performed. The output description sheet describes the format of the required report and other output files. The file description form and the additional information form indicate the characteristics of the files used in the program (input, output, tabular, etc.). The initial program is the information indicated on the RPG forms for solving this problem.

After writing the program on the appropriate forms, the text of the program is punched on the cards.

To get a working program, you must first translate the source program. To do this, some control cards are added to the cards of the original program, such as the control card of the RG1G translator and the cards of control operators - TASK CONTROLS, necessary for the operation of the RPG translator. After translation, the resulting module can be edited using the EDITOR. As a result of editing, a ready-to-execute program (load module) is obtained, which is called a working program. Compiling and editing is required to produce the desired report.

The work program can be executed immediately after translation and editing, or at any other time. The work program reads the preparatory input files, processes them, and as a result obtains a report and other output files.

ALGAMS. Algorithmic language ALGAMS is focused on machines of medium power; its basis was a subset of the ALGOL-60 language.

An important problem that is solved in ALGAMS is the introduction of input-output procedures. In ALGAMS, the set of standard functions has been expanded; there is also the possibility of using library subroutines. ALGAMS includes tools that allow you to indicate the possible segmentation of the program, the so-called part identifiers, as well as tools that make it possible to effectively use the computer's buffer memory by describing some of the arrays with special identifiers.

An input statement consists of an INPUT identifier followed by a list of actual parameters enclosed in parentheses. The first parameter specifies the number of the channel through which data is entered, the rest of the actual parameters are simple variables, array identifiers, or variables with indices.

When entering text, successive elements of the array, starting from the specified input object, are assigned integer values ​​corresponding to successive characters of the input string in the sense of the procedure = TEXT. Procedure = TEXT is defined as follows:<оператор текст>::=TEXT (<строка>, <переменная с индексами>).

The identifier of the input procedure is the word OUTPUT. The operator has four types: the number output operator, the boolean operator, the text output operator, and the placement operator. An output statement consists of an OUTPUT identifier followed by a list of actual parameters enclosed in parentheses. The first actual parameter of the procedure defines the number of the output channel, the second parameter defines the format of the output data, and all the others are output objects. There are editing tools for printing information.

BASEY K. The name of the language comes from the English words Beginners all Purpose Symbolic Instructioncode. It has gained wide popularity due to its simplicity, ease of learning and great opportunities for solving a variety of problems. In many minicomputers, this language is adopted as the main spoken language. The BASIC language is a programming language. It is convenient for solving scientific and technical problems of a small volume, both in terms of the number of operations performed and the amount of initial and resulting data. The most important feature of the language is that it is adapted for stepwise implementation. This means that after each change in the source text of a BASIC program, it is possible to retranslate not the entire program, but only those of its statements that have been changed. The possibility of step-by-step implementation of the BASIC language makes it possible to reduce the cost of computer time for retranslation. This, in turn, speeds up the debugging cycle so much that it becomes expedient to debug BASIC programs in dialog mode.

In addition to the ability to accumulate large programs consisting of renumbered BASIC language operators, so-called direct commands are provided, that is, those that are executed immediately after they are entered from the programmer's console (from a teletypewriter). In the direct command mode, not only administrative directives such as RUN-launch of execution, LIST - text printout, SAVE - save the program text in the library, BYE - end of the session can be used; any BASIC statement entered without a sequence number is executed in direct command mode. This allows, in particular, to print out and change the values ​​of variables at any time during the execution of the program.

Service word Action performed

PRINT Print message text enclosed in quotation marks, or the value of an arithmetic expression (after evaluating it), or the values ​​of variables

INPUT Enter numbers from the programmer's console and send them to the specified variables

LET Assign the value of an expression to a variable

GO TO Go to the execution of the statement with the given number

IF If the specified condition is met, then it is necessary to perform the action specified in this operator, otherwise, go to the execution of the next operator

DATA Data; this statement is not executed. It describes a block of debug data (numbers). The set of debug data blocks forms an array of debug data

END End of program

Thus, the step-by-step compilation scheme, combined with the direct command mode, makes it possible to effectively debug BASIC programs in the dialog mode.

A BASIC program consists of statements, each of which begins with a function word. The service word determines the type of operator and the nature of the actions carried out during its execution.

When solving many problems, it is necessary to present data in the form of tables. Using the capabilities of some operators of the BASIC language, it is possible to form tables of various formats.

The 21st century is a time when the possession of information is the most important competitive advantage in any field. However, it will not bring any benefit if it is not expressed in a language understandable to those to whom it is intended or if there is no translator capable of conveying its meaning to the addressee.

At the moment, about 2000 peoples live on earth. Their distinguishing feature, first of all, is the language.

Along with colloquial (natural) mankind has created many artificial languages. Each of them is designed to solve specific problems.

Such sign systems include formal languages, examples of which are presented below.

Definitions

First of all, let's define what a language is. This word is commonly understood as a sign system that is used to establish communications between people and knowledge.

The basis of most of both artificial and natural languages- alphabet.

It is a set of characters used to form words and phrases.

The language is characterized by:

• the set of characters used;
• rules for composing “words”, “phrases” and “texts” from them;
• a set of rules (syntactic, pragmatic, and semantic) for the use of constructed constructs.

Characteristics of natural languages

As already mentioned, all languages ​​are conditionally divided into artificial and natural. There are many differences between them.

Spoken languages ​​are natural. Their characteristics include, among others:

• ambiguity of most words;
• the existence of synonyms and homonyms;
• the presence of several names for the same subject;
• the existence of exceptions to almost all rules.

All these characteristics are the main differences between natural sign systems and formal languages. Examples of ambiguous words and statements are known to all. So the word "ether", depending on the context, can mean both substance and radio or television broadcasting.

The main functions of spoken languages ​​are:

• communication;
• cognitive activity;
• expression of emotions;
• impact on the interlocutor (correspondent, if we are talking about correspondence).

Characteristics of artificial languages

Artificial languages ​​are created by people for special purposes or for specific groups of people.

One of the main characteristics of artificial languages ​​is the unambiguous definition of their vocabulary, as well as the rules for giving them meanings and forming expressions.

Formal languages ​​and grammars

A language, whether natural or artificial, can only exist if there is a set of specific rules. At the same time, a consistent, compact and accurate display of the relationships and properties of the subject area under study should be provided. If they are strictly formulated, then they say that the language. Programming languages ​​are examples of such sign systems, although, strictly speaking, they rather occupy an intermediate position (see below).

The scheme for constructing formal sign systems is as follows:

• an alphabet is selected (a set of initial symbols);
• the rules for constructing expressions (syntax) of the language are specified.

Scope of application

Formal logic, programming, etc.) are used in the process scientific research. They are better than natural ones for representing knowledge and are a means of a more objective and accurate exchange of information.

Formal languages ​​include all known systems of mathematical and chemical symbols, Morse code, musical notation, etc.

In addition, formal programming languages ​​are widely used. Their rapid development began in the middle of the 20th century, in connection with the advent of computer technology.

Formal logic language

At the heart of any programming language is mathematics. It, in turn, relies on the sign system of formal logic.

As a science, logic was created by Aristotle. He also developed rules for transforming statements that preserve their truth value regardless of the content of the concepts included in these statements.

Formal logic struggles with the "shortcomings" of natural languages ​​associated with the ambiguity of some statements, etc. For this purpose, operations with thoughts are replaced by actions with signs of a formal language. This eliminates any uncertainty and allows you to accurately establish the truth of the statement.

Features of programming languages

As already mentioned, with some reservations they can be classified as formal.

They are united with the latter by many syntactic rules, and with the natural ones by some keywords and constructions.

To create a programming language, it is necessary to determine the set of valid symbols and the correct programs of the language and the meaning of each correct program. If the first task can be dealt with by means of formalization, in the case of the latter, these approaches do not work.

The set of valid characters in programming languages ​​are characters that can be typed from the keyboard. They are the first part of the ASCII encoding table.

grammars

Programming languages, like any other, have a grammar. This term is understood as a description of the method of compiling proposals. Grammars are described in various ways. In the case of programming languages, they are rules that are specified by ordered pairs of strings of characters of two types: defining syntactic constructions and semantic restrictions. When setting grammars, first they formally set out the rules for constructing syntactic constructions, and then they set semantic ones in one of the natural languages.

The rules are written in graphical form by means of special diagrams. Initially, this approach was applied when creating the Pascal language. However, then it began to be widely used in others.

Classification of programming languages

At the moment, there are several thousand of them, together with “dialects”. They are classified as procedural and declarative. In languages ​​of the first type, data transformation is specified by describing the sequence of actions performed on them, the second - by relations. There are other classifications as well. For example, programming languages ​​are divided into functional, procedural, object-oriented and logical. If we approach the issue strictly, then no classification can be objective. After all, a significant part of programming languages ​​has the capabilities of formal systems of several types at once. Over time, the edges are likely to blur even more.

Now you will be able to answer the question: “What formal languages ​​do you know?”. Scientists continue to improve them in order to make it possible to solve various practical and theoretical tasks, which are currently considered unsolvable.